操作系统概念：第七章 进程同步.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,操作系统概念,第七章：进程同步,本章主要内容,背景,临界区域问题,同步硬件,信号量,经典同步问题,管程,2,7.1,背景,共享数据的并发访问可能导致数据的不一致,维护数据的一致性需要能够保证协作进程顺序执行的机制,3,竞争条件（,Race Condition,）,生产者,while(1),while(counter=BUFFER_SIZE),;/do nothing,/produce an item and put in,nextProduced,bufferin,=,nextProduced,;,in=(in+1)%BUFFER_SIZE;,counter+;,4,竞争条件,消费者,while(1),while(counter=0),;/do nothing,nextConsumed,=,bufferout,;,out=(out+1)%BUFFER_SIZE;,counter-;,5,竞争条件,counter+,可按如下方式以机器语言实现,register,1,=counter,register,1,=,register,1,+1,counter=register,1,counter-,可按如下方式实现,register,2,=counter,register,2,=,register,2,1,counter=register,2,考虑以下交叉执行顺序,S0:,生产者执行,register,1,=counter register1=5,S1:,生产者执行,register,1,=,register,1,+1 register,1,=6,S2:,消费者执行,register,2,=counter register,2,=5,S3:,消费者执行,register,2,=,register,2,1 register,2,=4,S4:,生产者执行,counter=register,1,counter=6,S5:,消费者执行,counter=register,2,counter=4,6,多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称为,竞争条件,（,race condition,）,7,7.2,临界区问题的解决,代码块：,进入区（,entry section,）,临界区（,critical section,）,退出区（,exit section,）,剩余区（,remainder section,）,互斥,（,Mutual Exclusion,）：,如果进程,P,i,在其临界区执行，那么其他进程都不能在其临界区内执行。,有空让进,（,Progress,）：,如果没有进程在其临界区内执行且有进程希望进入临界区，那么只有那些不在剩余区内执行的进程能参加决策，以选择谁能下一个进入临界区，且这种选择不能无限推迟。,有限等待,（,Bounded Waiting,）：,在一个进程做出进入其临界区的请求到该请求被允许期间，其他进程被允许进入期临界区的次数存在一个上限。,8,两进程解法,两个进程标为,P,0,和,P,1,，为了方便，当使用,P,i,时，用,P,j,来表示另一个进程；即,j=1 i;,9,算法,1,进程共享一普通整数变量,turn,，其初值为,0,（或,1,）,如果,turn=i,P,i,允许在其临界区内执行。,确保了每个时刻只有一个进程处于临界区域。,但不满足“有空让进”需要。,为什么？,P,0,能否连续两次进入临界区？,do,while(turn!=i);/,进入区,临界区,turn=j;/,退出区,剩余区,while(1);,10,算法,2,1.do,2.,flagi,=true;,3.while(,flagj,);/,进入区,4.,临界区,5.,flagi,=false,;/,退出区,6.,剩余区,7.while(1);,增加了更多的状态信息,布尔标志用来表示线程它准备进入其临界区,“,有空让进”的要求仍然没有得到满足,为什么？,将语句,2,与语句,3,的位置互换，又将如何？,11,算法,3,结合算法,1,与算法,2,的思想,是否满足临界区的要求？,do,flagi,=true;,turn=j;,while(,flagj,/,进入区,临界区,flagi,=false;/,退出区,剩余区,while(1);,12,多进程解法,面包店算法的思想：,在进入商店时，每个客户接收一个号码。具有最小号码的客户先得到服务。然而，面包店算法不能保证两个进程不会收到同样的号码。在出现相同号码时，具有最小名称的进程先得到服务。即如果,P,i,和,P,j,收到同样号码，且,i j,，那么,P,i,先得到服务。,实现,boolean,choosingn,;,int,numbern,;,定义：,若,a c,，若,a=c,且,bd,，,(a,b)(c,d),max(a,0,a,n-1,),是数,k,从而,k,a,i,对,I=0,n-1,成立。,算法见下页,13,do,choosingi,=true;,numberi,=max(number0,number1,numbern-1)+1;,choosingi,=false;,for(j=0;j n;j+),while(,choosingj,);,while(,numberj,!=0)&(,numberj,j),numberi,i);,临界区,numberi,=0;,剩余区,while(1);,14,7.3,同步硬件,许多系统提供了临界区代码的硬件支持,单处理器系统 可以禁用中断,当前正在执行的代码可以顺利执行而不会被抢占,在多处理器环境下，这种解决方案是不可行的。,现代机器提供了特殊的原子硬件指令,原子,=,不可中断的,TestAndSet,指令,Swap,指令（交换内存中两个字的内容）,15,TestAndSet,指令,TestAndSet,指令的定义,boolean,TestAndSet(boolean,&target),boolean,rv,=target;,target=true;,return,rv,;,使用,TestAndSet,的互斥实现,do,while(,TestAndSet(lock,);,临界区,lock=false;,剩余区,while(1);,该算法不满足有限等待要求,16,Swap,指令,定义,void,Swap(boolean,&a,boolean,&b),boolean,temp=a;,a=b;,b=temp;,用,swap,实现互斥,do,key=true;,while(key=true),Swap(lock,key);,临界区,lock =false;,剩余区,while(1);,该算法也不满足有限等待要求。,17,使用,TestAndSet,的有限等待互斥,do,waitingi,=true;,key=true;,while(,waitingi,&key),key=,TestAndSet(lock,);,waitingi,=false;,临界区,j=(i+1)%n;,while(j!=i)&!,waitingj,),j=(j+1)%n;,if(j=i),lock=false;,else,waitingj,=false;,剩余区,while(1);,18,7.4,信号量,信号量,S,是个整数变量,两种标准原子操作用来修改,S,：,wait(),和,signal(),原来也称为,P(),和,V(),某些参考书也称为,acquire,和,release,wait,的伪代码定义,wait(S,),while S=0,;/no-op,S-;,signal,的伪代码定义,signal(S),S+;,19,用法：解决,n,个进程的临界区问题,n,个进程共享一个信号量,mutex,，初始值为,1,do,wait(mutex,);,临界区,signal(mutex,);,剩余区,while(1);,用来同步：,P1,和,P2,共享信号量,synch,，其初始值为,0,P,1,:,S,1,;,signal(synch,);,P,2,:,wait(synch,);,S,2,;,20,实现,忙等待,当一个进程位于其临界区内，任何其他试图进入其临界区的进程都必须在其进入代码中连续地循环。这种类型的信号量也称为,自旋锁,（,spinlock,）,改进办法：将忙等待改成阻塞,如,void wait(semaphore S),S.value,-;,if(,S.value,0),add this process to,s.L,;,block;,21,死锁与饥饿,死锁：两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。,设,S,和,Q,为两个信号量，其初值皆为,1,P,0,P,1,wait(S,);,wait(Q,);,wait(Q,);,wait(S,);,signal(S,);,signal(Q,);,signal(Q,);,signal(S,);,饥饿：无限阻塞。一个被悬挂的进程可能永远无法从信号量队列中移出。,22,二进制信号量,计数信号量,其整数值可跨越于一个不受限制的域内。,二进制信号量,只能为整数值,0,或,1,如何用二进制信号量实现计数信号量,设,S,为计数信号量，可以下列数据结构来实现,binary-semaphore S1,S2;,int,C;,开始时，,S1=0,S2=0,整数,C,的值设置为计数信号量的初值,wait,与,signal,的实现见下一页,23,Wait,wait(S1);,C-;,if(C 0),signal(S1);,wait(S2);,signal(S1);,Signal,wait(S1);,C+;,if(C=0),signal(S2);,else,signal(S1);,24,7.5,经典同步问题,有限缓冲问题,读者作者问题,哲学家进餐问题,25,有限缓冲问题,do,produce an item in,nextp,wait(empty,);,wait(mutex,);,add,nextp,to buffer,signal(mutex,);,signal(full,);,while(1);,do,wait(full,);,wait(mutex,);,remove an item from buffer to,nextc,signal(mutex,);,signal(empty,);,consume the item in,nextc,while(1);,26,读者作者问题,一个数据对象可以为多个并发进程所共享。其中有的进程可能只需要读共享对象的内容，而其他进程可能要更新共享对象（即读和写）。,将只对读感兴趣的进程称为读者,其他则称为作者,第一读者作者问题,仅当无读者等待时，才允许写者执行,第二读者作者问题,在读者与作者同时申请资源的时候，写者优先。,27,第一读者作者问题,wait(wrt,);,writing is performed,signal(wrt,);,wait(mutex,);,readcount,+;,if(,readcount,=1),wait(wrt,);,signal(mutex,);,reading is performed,wait(mutex,);,readcount,-;,if(,readcount,=0),signal(wrt,);,signal(mutex,);,28,哲学家就餐问题,29,共享数据,semaphore chopstick5;,哲学家,i,结构,do,wait(chopsticki,);,wait(chopstick(I,+1)%5);,eat,signal(chopsticki,);,signal(chopstick(I,+1)%5);,think,while(1);,30,7.6,管程,(monitor),为了保证共享变量的数据一致性，管程应互斥使用。管程通常是用于管理资源的，因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列，称为,入口等待队列,。当一个已进入管程的进程等待时，就释放管程的互斥使用权；当已进入管程的一个进程唤醒另一个进程时，两者必须有一个退出或停止使用管程。在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程），称为,紧急等待队列,，它的优先级高于入口等待队列。,因此，一个进程进入管程之前要先申请，一般由管程提供一个,enter,过程；离开时释放使用权，如果紧急等待队列不空，则唤醒第一个等待者，一般也由管程提供外部过程,leave,。,31,条件变量,管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量：,var,c:condition,；实际上是一个指针，指向一个等待该条件的,PCB,队列。对条件型变量可执行,wait,和,signal,操作：,wait(c,):,若紧急等待队列不空，唤醒第一个等待者，否则获得管程使用权。执行本操作的进程进入,C,队列尾部；,signal(c,):,若,C,队列为空，继续原进程，否则唤醒队列第一个等待者，自己进入紧急等待队列尾部。,32,带条件变量的管程,33,生产者,-,消费者问题,见,chapter 7,sourcecode.doc,34,哲学家就餐问题的管程解法,见,chapter 7,sourcecode.doc,35,作业,P140,6.3 6.4 6.6 6.8,P175,7.3 7.4 7.8,P176,7.9,7.14,36,