单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第6章 进程同步 Synchronization,主讲教师,:,庞俊彪,邮件：,办公室,:,信息楼 南,412,内容回忆：多道程序,单处理器，多道程序：,交错,多处理器，多道程序：,交错和重叠,Cobegin,get;,copy;,put;,Coend,get,copy,put,f,s,t,g,复制一个记录,内容回忆：并发的原理,与进程的执行顺序有关的错误,源记录,目标记录,内容回忆：进程间的制约关系,进程的同步直接制约：synchronism,指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态,进程的互斥间接制约:mutual exclusion,由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥,c,m,p,m,c1,g2,p1,c2,g3,p2,g1,并发环境下进程间的制约关系,内容回忆：进程的状态和控制,运行,等待,;,运行,就绪,;,就绪,运行,运行态,阻塞态,就绪态,新建态,终止态,该图称为,进程状态图,它能给出进程,生存期,的清晰描述,它是认识操作系统,进程管理,的一个窗口,本章教学目标,临界区,的概念,信号量,硬件,同步,同步,算法：,哲学家进餐,与,Peterson,算法等,管程,CPU,调度,1,.1,进程,同步问题的提出,1,.2,临界资源和临界区,1.4,如何解决临界区问题,进程同步问题的提出-例如1,甲,5:00,查看冰箱，面包没了,5:05,去超市,5:10,到达超市,5:15,买好面包,5:20,回家,把面包放入冰箱,5:25,5:30,乙,查看冰箱，面包没了,去超市,到达超市,买好面包,回家,把面包放入冰箱,噢,Too Much,进程同步问题的提出-例如2,共享变量的修改冲突,例1：,一飞机订票系统，两个终端，运行,T1、T2,进程,T1:T2:,.,Read(x);Read(x);,if x=1 then if x=1 then,x:=x-1;x:=x-1;,write(x);write(x);,.,设,x,的当前值为：100,1.假设执行顺序为：,先T1;后T2;,那么结果：x=98,2.假设执行顺序为：,T1:Read(x);,T2:Read(x);,T1:if x=1 then x:=x-1;,T2:if x=1 then x:=x-1;,T1:write(x);,T2:write(x);,那么结果 x=99,分析：,产生,错误,的原因是,不加控制地访问共享变量,x,c,m,p,m,c1,g2,p1,c2,g3,p2,g1,并发环境下进程间的制约关系,竞争条件,竞争条件,这种两个以上的进程共享数据，而最终的执行结果那么是根据执行次序而决定的，这种情况称为竞争条件,解决方法,控制对共享资源的访问,CPU,调度,1,.1,进程同步问题的提出,1,.2,临界资源,和,临界区,1.4,如何解决临界区问题,临界资源,和,临界区,为了防止竞争条件，必须找到一种方法来阻止多个进程同时读写共享的数据，这些共享的数据称为临界资源。,程序中使用资源的局部称为临界区。,互斥mutual exclusion：如果有进程在临界区中执行，那么其他进程都不能在临界区中执行。这样就可以防止竞争条件的产生,有空让进,有限等待,不对进程的相对执行速度进行任何假设,临界区,问题,进入区,退出区,临界区,剩余区,临界区(critical section)：一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构进行操作,进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志,退出区(exit section)：用于将正在访问临界区标志去除,剩余区(remainder section)：代码中的其余局部,同步机制应遵循的规那么,空闲让进,(2)忙那么等待,(3)有限等待,(4)让权等待,CPU,调度,1,.1,进程同步问题的提出,1,.2,临界资源和临界区,1.3,如何解决,临界区问题,?,如何,解决,临界区问题？,软件,的解决方案,硬件,的解决方案,信号量,的解决方案,管程,的解决,方案,软件,的解决方案,-Peterson,算法,自行阅读，,并,理解,特点,无需硬件、,OS,和程序设计语言的支持,处理开销大,容易出错,学习的意义,更好地理解并发处理的复杂性,适用范围,单处理器系统,共享主存的多处理系统,前提假设:存储器级的访问是互斥的,硬件,的解决,方案,-,中断禁用,1.中断禁用(,关中断,Interrupt Disabling,),思路：,单处理器系统,如果进程访问临界资源时(执行临界区代码)不被中断,就可以利用它来保证互斥地访问,途径:,使用,关中断原语,、,开中断原语,点评：,实现互斥的最简单方法,中断禁用(关中断,过程:关中断;,临界区,开中断；,其余局部,存在问题,不能用于多处理器结构：关一个CPU的中断不能保证互斥。而且，在多处理器上要将信息传递给所有处理器，因此禁止中断可能很费时。导致进入每个临界区都会延迟。,多处理器将出现问题？,-,通信问题,硬件的解决方案多CPU-专用指令,专门的,机器指令,设计一些机器指令，用于保证,两个动作的原子性，,如在,一个指令周期中,实现,测试和修改,TestandSet(TS),指令,Swap,指令,许多现代计算机系统提供了这类特殊指令，可以,原子地,检查和修改和交换字的内容,原语,内核在执行某些根本操作时,往往利用原语操作实现,原语,是一种广义指令,相当于扩充了机器指令集,原语是由假设干条指令构成、用于完成一定功能的一个过程.,原语是原子操作(atomic operation),原子操作:,一个操作中的所有动作,要么全做,要么全不做.,原子操作是一个不可分割的操作,专门的,机器指令,(,多,CPU)-,Test,和,Set,指令(,TS,指令),TS,指令定义(逻辑),boolean TestandSet(boolean*target),boolean rv=*target;,*target =,TRUE,;/,强制为真,Return rv;,使用,TestAndSet,实现互斥,const int n;,boolean bolt=false;,While(true),While(!TestandSet,(&bolt,);,/,什么都不,做,/,临界区;,bolt=,FALSE,;,/,剩余区,为啥,TS,原语能让,多,CPU,互斥？,1.Lock=false;,2.(cpu1)lock=false;-,进入临界区；,3.(cpu2),进入,while,循环；,-,空等；,Swap指令定义：,void Swap(boolean a,boolean b),boolean temp=a;,a=b;,b=temp;,如果机器支持Swap指令，那么可解决互斥问题,进程间的全局布尔变量lock，初值为false,每一个进程均设置一个局部布尔变量key,专门的机器指令多CPU-Swap,使用,Swap,指令,实现互斥,do,key=TRUE;,while(key,=TRUE),Swap(lock,key);,/*临界区*/,lock=FALSE;,剩余区,while(1);,专门,的机器指令,评价,优点,适用于单处理器或共享主存的多处理器系统,进程数目任意,简单且易于证明,可以使用多个变量支持多个临界区，只需为每个临界区设立一个布尔变量,缺点,忙等待：当一个进程正在等待进入一个临界区时，继续消耗处理器时间。等待要消耗CPU时间，不能实现“让权等待,可能饿死：任意选择等待的进程，有的可能一直选不上,可能死锁：高优先级进程等待处于阻塞状态的低优先级进程的资源如：进程P1执行TS或Swap指令并进入临界区，然后P1被阻塞，并把CPU给具有更高优先级的P2,假设P2试图使用与P1相同的资源，由于互斥机制，它被拒绝访问，因此进入忙等待循环，又因P2优先级高于P1，所以P1总得不到调度执行,P2也无法执行。,信号量及,P,、,V,操作,前面的各种算法都是平等进程间的一种,协商,机制，,需要一个地位高于进程的管理者来解决公有资源的使用问题,;,1965,年，由荷兰学者,Dijkstra,提出,(P,、,V,分别是荷兰语的,test(proberen),和,ncrement(verhogen);,最初提出的是二元信号量,(,互斥,),推广到一般信号量,(,多值,同步,);,信号量,(semaphore),一种特殊的用于,发送信号,的变量,;,等待信号的进程被,放到等待队列,中,;,定义如下：,struct semaphore,int count;,queueType queue;,LINUX,定义在,include/asm/semaphore.h,中：,struct semaphore,atomic_t count;,int sleepers;,wait_queue_head_t wait;,信号量原语的定义,void semWait(semaphore s),s.count-;,if(s.count0),该进程状态置为等待状态,;,将该进程的,PCB,插入,s,.,queue,末尾；,重新调度,;,s.count,的绝对值表示在该信号量等待队列中已阻塞进程的数目。,信号量原语的定义,(,续,),void semSignal(semaphore s),s.count+;,if(s.count=0:可用的资源数),假设为负值：其绝对值表示当前等待临界区的进程数(|s.count|为等待的进程数),每个信号量 s 除一个整数值 s.count计数外，还有一个进程等待队列 s.queue，其中是阻塞在该信号量的各个进程的标识,信号量,对信号量操作的物理意义,操作系统对信号量只能通过初始化和两个标准的原语来访问。,对信号量的操作只有三种原子操作:,初始化:通常将信号量的值初始化为非负整数,P操作(wait操作,使信号量的值减1(申请一个单位的资源(s.count-),如果使信号量的值变成负数,那么执行P操作的进程被阻塞(当s.count 0时,资源已分配完毕,进程自己阻塞在S的队列上-让权等待),V操作(signal操作,使信号量的值加1(释放一个单位资源(s.count+),如果信号量的值不是正数,那么使一个因执行v操作被阻塞的进程解除阻塞(假设s.count=0,那么唤醒一个等待进程),信号量,(,总结,),一种整型的变量,;,可以初始化为一个非负数,;,wait,操作减少信号量的数值；,signal,操作增加信号量的数值；,用,P,、,V,原语,解决,n,个进程互斥共享一个临界资源的编程模型,const int n=进程数；,semaphore mutex=1;,Void Process(int i),while(true),P(mutex);,V(mutex);,void main(),Cobegin(Process(1),Process(2),.,Process(n);,Coend,请仔细分析信号量的变化过程，它是如何保证互斥的？,用信号量实现互斥,在互斥问题中，对信号量,mutex,必须设置一次初值，,初值必须为1,P、V,原语操作应该分别紧靠临界区的头部和尾部，从而提高进程的并发度,Mutex,的取值为：1,0,-1,-2,-(,n-1),P、V,操作必须成对出现，而且它们同处于同一个进程中,例,对,共享变量,的访问,Semaphore,mutex=1;,Count=0,;,Process observer,while(true),观察到一辆车；,P(mutex);,count:=count+1;,V(mutex,);,P