进程的同步与互斥.pptx

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,2020/4/23,1,2025/2/23 周日,第,3,章 进程管理,3.1,进程的引入,3.2,进程的结构,3.3,进程控制,3.4,进程的同步与互斥,3.5,进程间通信,3.6,进程调度,3.7,死锁,3.8,线程,2,2025/2/23 周日,两种制约关系,直接相互制约关系（同步）,间接相互制约关系（互斥）,产生的原因,进程合作,资源共享,3,2025/2/23 周日,进程的同步（,1,）,直接相互制约关系（同步）,指系统中一些进程需要相互合作，共同完成一项任务,这种协作进程之间相互等待对方消息或信号的协调关系称为,进程同步,.,具体说，并发进程在一些关键点上可能需要互相等待与互通消息，进程间的相互联系是,有意识,的安排的。,产生的原因,进程合作,4,2025/2/23 周日,进程的同步（,2,）,一般同步问题有两类,保证一组合作进程按逻辑需要的执行次序执行,【,例,】,司机,P1,售票员,P2,REPEAT REPEAT,启动 关门 正常运行 售票 到站停 开门,UNTIL FALSE UNTIL FALSE,保证共享缓冲区（共享数据）的合作进程的同步,【,例,】,输入,进程,PI,缓冲区,缓冲区,计算,进程,PC,打印,进程,PP,5,2025/2/23 周日,进程的互斥,是解决进程间竞争关系,(,间接制约关系,),的手段。,间接相互制约关系（互斥）,是指若干个进程同时竞争一个,需要互斥使用的资源,时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到该资源被释放。进程间要通过某种中介发生联系，是,无意识,安排的。,产生的原因,资源共享,互斥是一种特殊的同步,逐次使用互斥资源，也是对进程使用资源次序上的一种协调。,6,2025/2/23 周日,临界资源,临界资源,系统中某些资源,一次只允许一个进程使用,，称这样的资源为临界资源或互斥资源或共享变量。,硬件临界资源：打印机、磁带机,软件临界资源：只能排它使用的变量、表格、队列,7,2025/2/23 周日,临界资源实例,二人合作存款,count=100;,P,A,S1:N=count;,S2:N=N+100;,S3:count=N;,P,B,S4:M=count;,S5:M=M+200;,S6:count=M;,执行情况：,（,1,）,P,A,P,B,P,B,P,A,count=400,（,2,）,S1,P,B,S2,S3,count=200,（,3,）,S4,P,A,S5,S6,count=300,因,count,是一个互斥性使用的变量，是一个临界资源,8,2025/2/23 周日,临界区,临界区（临界段）,在进程中访问临界资源的那段代码区。,例子,9,2025/2/23 周日,具有临界资源的进程结构,/*,进入区*,/,critical section;/*,临界区*,/,/*,退出区*,/,remainder section;/*,剩余区*,/,entry section,exit section,10,2025/2/23 周日,访问临界区应遵循的原则,空闲让进,当无进程在临界区时，任何有权使用临界区的进程可进入。,忙则等待,不允许两个以上的进程同时进入临界区。,有限等待,任何进入临界区的要求应在有限的时间内得到满足。,让权等待,不能进入临界区的进程应放弃占用,CPU,。,11,2025/2/23 周日,临界区互斥解决方法,硬件,缺点：成本高,软件,用编程解决,缺点：,(1),忙等待,(2),实现过于复杂，需要高的编程技巧,信号量机制,12,2025/2/23 周日,信号量机制,一类资源,抽象成,S,（信号量）,信号量,只能由,P,、,V,操作对其进行操作的变量。,信号量的使用应注意,必须置一次且只能置一次初值。,初值只能为非负整数，实现互斥时初值为,1,。,只能执行,P,、,V,操作。,13,2025/2/23 周日,P,、,V,操作,P(S),：表示申请一个资源。,V(S),：表示释放一个资源。,P,、,V,操作必须成对出现，有一个,P,操作就一定有一个,V,操作。,14,2025/2/23 周日,整型信号量,整型信号量,信号量,S,：整型量，除初始化外仅能通过,P,、,V,操作访问,P,和,V,操作原语定义：,var S:integer;S=1;,P(S),：,while S 0 do no-op,S=S-1,；,V(S),：,S=S+1,；,一类资源,抽象成,S,（信号量）,整型量,15,2025/2/23 周日,利用整型信号量实现进程互斥,P(S),V(S),P,1,P,2,互斥区,P(S),V(S),16,2025/2/23 周日,记录型信号量,记录型信号量,信号量,S,：记录型数据结构,一个分量为整型量,value,另一个分量为信号量队列,L,；,信号量的物理含义,当,S.value,0,：表示可用资源个数,当,S.value,0,：表示可用资源正好用完,当,S.value0,：表示等待该类资源的进程数,一类资源,抽象成,S,（信号量）,value,0,L=nil,信号量的值,(-2),信号量队列指针,17,2025/2/23 周日,struct semaphore,int value;,int*L;,void P(struct semaphore S);,S.value=S.value 1;/*,把信号量减去,1*/,if S.value 0 then block(S.L);,/*,若信号量小于,0,，则调用,P(S),的进 程被置成等待信号量,S,的状态*,/,物理意义：申请一个资源，如果申请成功，则返回；如果申请不成功，则挂在该资源的等待队列上。,void V(struct semaphore S);,S.value=S.value+1;/*,把信号量加,1*/,if S.value 0:,表示有,S,.value,个资源可用,S,.value,=0:,表示无资源可用,S,.value,0:,则,|S,.value,|,表示等待队列中的进程个数,信号量的初值应该大于等于,0,20,2025/2/23 周日,P,、,V,操作讨论,(2),P(S),：表示申请一个资源,V(S),：表示释放一个资源。,P,、,V,操作必须成对出现，有一个,P,操作就一定有一个,V,操作,P,、,V,操作的优点,简单，而且表达能力强，可解决任何互斥问题,P,、,V,操作的缺点,不够安全，,P,、,V,操作使用不当会出现死锁，遇到复杂互斥问题时，实现复杂。,21,2025/2/23 周日,用,P,、,V,操作实现互斥,信号量初值为,1,对于两个并发进程，互斥信号量的值仅取,1,、,0,和,-1,三个值,：,若,mutex.value,1,表示没有进程进入临界区,若,mutex.value,0,表示有一个进程进入临界区,若,mutex.value,-1,表示一个进程进入临界区，另一个进程等待进入。,22,2025/2/23 周日,利用,P,、,V,操作实现两个进程互斥的模板如下,：,struct semaphore mutex;,mutex.value=1;mutex.L=nil;,cobegin,Process P1,:Begin,M,P(mutex);,临界区,1,V(mutex);,M,End,Process P2,:Begin,M,P(mutex);,临界区,2,V(mutex);,M,End,coend,23,2025/2/23 周日,使用,PV,操作实现互斥应注意,识别临界资源,是否被共享,;,是否有排它性使用要求。,临界区代码应尽量短小，不能有死循环。,P,和,V,原语应分别紧靠临界区的头尾。,P,、,V,操作在同一进程中必须成对出现。,24,2025/2/23 周日,思考题,用记录型信号量解决二人存款问题，用,类,C,语言编写进程互斥算法,。,25,2025/2/23 周日,用,P,、,V,操作实现,进程的同步,只要信号量初值是一个大于等于,0,的整数就能达到同步的目的，就可以直接使用,P,、,V,操作实现同步,互斥是一种特殊的同步,P,、,V,操作既可以实现互斥，也可以实现同步,利用信号量实现进程同步的实例,设有三个并发执行的进程,P1,、,P2,、,P3,，其前趋图如下，试用信号量实现这三个进程同步。,设两个同步信号量,S1,、,S2,分别表示进程,P2,、,P3,能否开始执行,struct semaphore S1,S2=0,0;/*,初值均为,0*/,cobegin,P1:,V(S1),;,V(S2),;,P2:,P(S1),;,;,P3:,P(S2),;,coend,P1,P3,P2,27,2025/2/23 周日,使用,PV,操作实现同步应注意,信号量的设置,信号量的初值,PV,操作要成对出现，并在不同的进程中,28,2025/2/23 周日,信号量及,P,、,V,操作讨论,(3),(1)P,、,V,操作必须成对出现，有一个,P,操作就一定有一,个,V,操作,(2),当为互斥操作时，它们同处于同一进程,当为同步操作时，则不在同一进程中出现,(3),如果,P(S1),和,P(S2),两个操作在一起，那么,P,操作的,顺序至关重要。,一个同步,P,操作与一个互斥,P,操作在一起时，同步,P,操作在互斥,P,操作前，而两个,V,操作无关紧要。,29,2025/2/23 周日,PV,操作实现互斥与同步的模板,进程互斥,S,初值为,1,P1,P2,P(S)P(S),临界区,1,临界区,2,V(S)V(S),在,P1,与,P2,中设置相同的,P,、,V,操作,进程同步,S1,初值为,n,，,S2,初值为,0,P1,P2,P(S1),P(S2),段,1,段,2,V(S2),V(S1),30,2025/2/23 周日,经典的进程同步问题,生产者,/,消费者问题,读者,/,写者问题,哲学家进餐问题,31,2025/2/23 周日,生产者,/,消费者问题,生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。,当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。,32,2025/2/23 周日,生产者,/,消费者问题,(,描述,),通过一个公用缓冲池可以把一群生产者,p1,p2,pm,，和一群消费者,Q1,Q2,Qn,联系起来。如图,:,只要缓冲区未满，生产者就可以把产品送入缓冲区,;,只要缓冲区未空，消费者就可以从缓冲区中取走物品。,33,2025/2/23 周日,生产者,/,消费者问题,(,图示,),34,2025/2/23 周日,生产者,/,消费者问题,(,分析,),为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用,empty,表示，初值为缓冲池的大小,N,，另一个说明已用缓冲区的数目，用,full,表示，初值为。,由于在此问题中有,i,个生产者和,j,个消费者，它们在执行生产活动和消费活动中要对缓冲池进行操作。由于缓冲池是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量,mutex,，其初值为。,struct semaphone empty=n,full=0,mutex=1;,void buffern-1;,int in=,out=0;,35,2025/2/23 周日,生产者,/,消费者问题,(,解决,),Consumerj:,while(1),P(full);,P(mutex);,从,Bufferout,取产品,;,out=(out+1)mod n;,V(mutex);,V(empty),;,消费产品,;,coend;,cobegin,procedurei:,while(1),生产产品,;,P(empty),;,P(mutex);,往,Buffer in,放产品,;,in=(in+1)mod n;,V(mutex);,V(full);,36,2025/2/23 周日,生产者,/,消费者问题,(,思考,),在生产者进程和消费者进程中，两个,P,操作的执行顺序是否能交换？两个,V,操作的执行顺序是否能交换？,37,2025/2/23 周日,思考题,两个进程合作完成数据计算和打印工作，计算进程未计算完就不可打印，反之也然，双方共用一个缓冲区，写出此算法,。,38,2025/2/23 周日,读者,/,写者问题,有两组并发进程,:,读者和写者,共享一个数据文件,要求：,允许多个读者同时执行读操作,不允许读者、写者同时操作,不允许多个写者同时操作,39,2025/2/23 周日,读者,/,写者问题,如果读者来：,1,）无读者、写者，新读者可以读,2,）有写者等，但有其它读者正在读，则新读者也可以读,3,）有写者写，新读者等,如果写者来：,1,）无读者、写者，新写者可以写,2,）有读者，新写者等待,3,）有其它写者，新写者等待,40,2025/2/23 周日,读者写者问题的解法,为实现读者和写者、写者和写者之间的互斥，设置一个互斥信号量,Wmutex=1,由于“读,读”允许，再设置一个整型变量,Readcount,表示正在读的进程数，初值,Readcount=0,由于,Readcount,是一个可被多个读者进程访问的临界资源，所以要为它设置一个互斥信号量,Rmutex=1,读者,写者算法如下：,读者：,P(Rmutex),;,if readcount=0 then,P(Wmutex),;,Readcount=Readcount+1;,V(Rmutex),;,读,P(Rmutex),;,Readcount=Readcount-1;,if Readcount=0 then,V(Wmutex),;,V(Rmutex),;,写者：,P(Wmutex),;,写,V(Wmutex),;,41,2025/2/23 周日,哲学家就餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。,每个哲学家的行为是思考，感到饥饿，取筷子，然后吃通心粉，放筷子，思考。,为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。,筷子是临界资源，要用,5,个互斥信号量来表示这,5,只筷子。,42,2025/2/23 周日,哲学家就餐问题解,设,fork5,为,5,个信号量，初值均为,1,struct,semaphore,fork 4;,forki:=1;,Philosopheri,：,While(1),思考；,P(forki);,P(fork(i+1)mod 5),；,进食；,V(forki);,V(fork(i+1)mod 5),；,以上解法会出现死锁,为防止死锁发生可采,取的措施：,最多允许,4,个哲学家同时坐在桌子周围,给所有哲学家编号，奇数号的哲学家必须首,先拿左边的筷子，偶数号的哲学家则反,仅当一个哲学家左右两边的筷子都可用,时，才允许他拿筷子（,）,43,2025/2/23 周日,思考题,桌子上有一只盘子，每次只能放入一只水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，一个儿子专等吃盘中的桔子，一个女儿专等吃盘中的苹果。请利用,P,、,V,操作写出父亲、母亲、儿子、女儿进程的同步算法。,44,2025/2/23 周日,思考题,分析：在本题中，应设置三个信号量,s,、,so,、,sa,，,信号量,s,表示盘子是否为空，其初值为,1,；,信号量,so,表示盘中是否有桔子，其初值为,0,；,信号量,sa,表示盘中是否有苹果，其初值为,0,。,同步描述如下：,45,2025/2/23 周日,struct semaphone s=1,so=0,sa=0;,cobegin,father();,mother();,son();,daughter();,coend,father(),p(s);,将水果放入盘中；,v(sa);,mother(),p(s);,将水果放入盘中；,v(so);,son(),p(so);,从盘中取出桔子；,v(s);,吃桔子；,daughter(),p(sa);,从盘中取出苹果；,v(s);,吃苹果；,