进程管理B互斥与同步.pptx

1第第2、3章章 进程管理进程管理B互斥与同步互斥与同步 本章知识点：本章知识点：并发原理并发原理 互斥互斥软件解决方法软件解决方法互斥互斥硬件解决方法硬件解决方法 2.3 进程同步进程同步管程管程2.5 进程通讯进程通讯2.4 经典进程的同步问题经典进程的同步问题2顺序程序及其特性顺序程序及其特性程序的顺序性包括如下两层含义:(1)内部顺序性,对于一个进程来说,它的所有指令是按序执行的;(2)外部顺序性,对于多个进程来说,所有进程是依次执行的;例如,假设有P1和P2两个进程,其活动分别为:P1活动:a1a2a3a4P2活动:b1b2b3b4顺序执行时,有如下两种情形:情形1:a1a2a3a4b1b2b3b4情形2:b1b2b3b4a1a2a3a43顺序程序设计三个良好的特性：顺序程序设计三个良好的特性：（1）顺序性：处理机严格按照指令次序依次执行，即仅当一条指令执行完后才开始执行下一条指令；（2）封闭性：程序在执行过程中独占系统中的全部资源，该程序的运行环境只与其自身动作有关，不受其它程序及外界因素影响；（3）可再现性：程序的执行结果与执行速度无关，而只与初始条件有关，给定相同的初始条件，程序的任意多次执行一定得到相同的执行结果.4并发程序及其特性并发程序及其特性程序的并发性包括如下两层含义:(1)内部并发性,对于一个进程来说,它的所有指令可能按序执行，也可能不按次序执行;(2)外部并发性:对于多个进程来说,所有进程是交叉(interleave)执行的.例如,对于上面P1和P2两个进程来说,只考虑外部并发性，具有许多情形,如:情形1:a1b1b2a2a3b3a4b4情形2:b1b2a1a2a3b3b4a4并发进程在其执行过程中,出现哪种交叉情形是不可预知的,这就是并发程序带来的不确定性5并发程序三个特性并发程序三个特性(1)交叉性：程序并发执行对应某一种交叉，不同的交叉可能导致不同的计算结果，操作系统应当保证只产生导致正确结果的交叉，去除那些可能导致不正确结果的交叉.(2)非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响(3)不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果6与时间有关的错误与时间有关的错误若有两个进程P1、P2，共享一个公用变量c，初值为8，P1、P2所做工作如下：P1(退票)P2（售票）L1：a=c；L4：b=c；L2：a=a+1；L5：b=b-1；L3：c=a；L6：c=b；7与时间有关的错误与时间有关的错误试看下述两种执行情况：(1)若语句执行顺序为L1，L2，L3，L4，L5，L6，则c=8；(2)若语句执行顺序为L1，L2，L4，L5，L3，L6，则c=7。显然，上述结果是不能令人满意的。P1、P2是进程，每个进程中语句执行顺序是不变的，而两个进程的语句是可以交叉执行的，它们以哪种方式交叉执行是不可预知的。改进：将c处理成临界资源，让P1、P2互斥访问c，一个进程对于c的一次访问完毕，另一个进程才能访问，就不会出现这种情况。8与时间有关的错误与时间有关的错误上述错误并不是一定发生的,它与进程的推进速度有关.即上述错误发生与否与进程P1和P2的推进速度有关,而速度是时间的函数,因而这种错误称为与时间有关的错误.发生上述错误的原因在于两个进程P1和P2同时对于一个变量C进行操作,一个进程对C的操作仅做了一部分,另一个进程中途插入使得变量C处于一种不确定的状态,用数据库的术语来说,就是失去了变量C的数据完整性.9 临界区临界区critical section进程访问临界资源的程序段称为临界区。在一个系统中，可以用某些方法或某种机制保证进程对临界区的互斥访问，一个好的解决方案应该遵循以下条件：(1)任何两个进程不能同时处于临界区内；(2)进程在临界区外只作有限时间的等待；(3)临界区外的进程不得阻塞其它进程进入临界区；(4)等待临界区时,释放CPU。102.3 并发原理并发原理 在单处理机多道程序的系统中，进程的并发执行方式是插入执行，表面看起来进程如同是同时执行的。在多处理机系统中并发执行方式有插入执行和重叠执行。并发的存在要求操作系统必须能跟踪大量活跃进程,必须为每一活跃进程分配资源，必须保护每一进程的数据和物理资源不被其他进程侵犯，并且进程执行的结果与其他并发进程执行时的相对速度无关。112.3 进程间相互联系与进程间相互联系与相互作用相互作用相互联系：（1）相关进程：在逻辑上具有某种联系的进程称作相关进程.（2）无关进程：在逻辑上没有任何联系的进程称作无关进程.相互作用：（1）直接相互作用：进程之间不需要通过中间媒介而发生的相互作用，这种相互作用通常是有意识的.（2）间接相互作用：进程之间需要通过某种中间媒介而发生的相互作用，这种相互作用通常是无意识的.122.3 进程间的相互竞争进程间的相互竞争 并发进程在竞争使用同一资源时将产生冲突。进程间的竞争面临3个控制问题：互斥 mutual exclusion(临界资源和临界段)死锁 deadlock饥饿 starvation 竞争的控制不可避免地涉及到操作系统，因为是操作系统分配资源，另外，进程自身也必须能以某种方式表达互斥的要求。132.3 进程间的相互合作进程间的相互合作 1.通过共享合作这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题。142.3 进程间的相互合作进程间的相互合作2.通过通信合作 进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。这种方式中采用的是通信机构，在进程通信时往往以消息形式传递信息。因为在消息传递中不存在共享，所以这种形式的合作不需要互斥，但是还存在死锁和饥饿问题。15进程互斥的实现进程互斥的实现实现进程互斥,也就是实现对于临界区域的管理.为了保证其管理的正确性和公平性,应当满足下面三个管理原则:(1)正确性原则(correctness)：任意时刻至多只能有一个进程处于关于同一组共享变量的临界区域之中；(2)公平性原则(fairness)：一个请求进入临界区的进程应当在有限等待时间内获得进入该临界区的机会；(3)进展性原则(progress)：当临界区空闲时，竞争进入临界区的多个进程在有限时间之内确定下一个进入临界区的进程.对此资源的管理应当满足如下调度原则:(1)当关于某一组共享变量的所有临界区域均为空闲时,一个要求进入该组共享变量某一临界区域的进程应当能够立即进入;(2)当关于某一组共享变量的某一临界区域被占用时,一个要求进入该组共享变量某一临界区域的进程应当等待;(3)当一个进程离开关于某一组共享变量的某一临界区域时,应当容许某一个等待进入关于该组共享变量某一临界区域的进程进入.16Dijkstra成就成就程序设计：结构化程序设计，goto有害Os中并发程序设计，CS：what，why，how，P、V原语网络：最短路径算法17Dijkstra成就成就1965年提出解决CS问题4个基本准则：1、不能虚设硬件指令或假设处理机数目，但可以认为基本的机器指令是不会被分割执行的。2、不能假设n个进程的相对执行速度。3、当一个进程未处于cs时，它不应阻止其它进程进入cs4、当若干个进程欲进入cs时，os应在有限的时间内选择出一个进程进入其cs。18使用互斥的原则使用互斥的原则由Dijkstra的四个基本准则可以导出：有空让进无空等待多中择一有限等待让权等待19互斥互斥软件解决方法软件解决方法软件方法对并发进程不提供任何支持，因此，无论是系统程序或应用程序，进程都要同其他进程合作以解决互斥，它们从程序设计语言和操作系统那里得不到任何支持。软件方法易引起较高的进程附和较多的错误，但有利于深刻理解并发的复杂性。20Dekker算法算法Dekker算法的优点在于它描述了并发进程发展过程中遇到的大部分共同问题。任何互斥都必须依赖于一些硬件上的基本约束，其中最基本的约束是任一时刻只能有一个进程访问内存中某一位置。21Dekker算法算法 1.第1种途径这种方法保证了互斥，但它只记住了允许哪个进程进入其临界段，未记住每个进程的状态。varturn:0.1;turn为共享的全局变量PROCESS0PROCESS1whileturn0donothing whileturn1donothing；criticalsection;criticalsection;turn:=1;turn:=0;22Dekker算法算法2.第2种途径这种解决方法依赖于进程执行的相对速度共享的全局变量是：varflag:array0.1ofboolean;它被初始化为falsePROCESS0PROCESS1whileflag1donothing;whileflag0donothing;flag0:=true;flag1:=true;criticalsection;criticalsection;flag0:=false;flag1:=false;23Dekker算法算法3.第3种途径这种方法保证了互斥但会导致死锁问题。PROCESS0PROCESS1flag0:=true;flag1:=true;whileflag1donothing;whileflag0donothing;criticalsection;criticalsection;flag0:=false;flag1:=false;24Dekker算法算法4.第4种途径PROCESS0PROCESS1flag0:=true;flag1:=true;whileflag1whileflag0beginbeginflag0:=false;flag1:=false;delayforashorttime;delayforashorttime;flag0:=true;flag1:=true;end;end;criticalsection;criticalsection;flag0:=false；flag1:=false;25Dekker算法算法5.一个正确的解决方法设计一个“指示”小屋，小屋内的黑板标明“turn”，当P0想进入其临界段时，置自己的flag为“true”，这时它去查看P1的flag，如果是“false”，则P0就立即进入自己的临界段，反之P0去查看“指示”小屋，如果turn=0，那么它知道自己应该坚持并不时去查看P1的小屋，P1将觉察到它应该放弃并在自己的黑板上写上“false”，以允许P0继续执行。P0执行完临界段后，它将flag置为“false”以释放临界段，并且将turn置为1，将进入权交给P1。26Peterson算法算法 Dekker算法可以解决互斥问题，但是，其复杂的程序难于理解，其正确性难于证明。Peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法，进一步可将Peterson算法推广到多个进程的情况。27Peterson算法算法varflag:array0.1 ofboolean;flag1:=true;turn:0.1;turn:=0;procedure P0;whileflag0andturn=0donothing;begincriticalsection;repeatflag1:=false;flag0:=true;remainderturn:=1;foreverwhileflag1andturn=1donothing;end;criticalsection;beginflag0:=false;flag0:=false;remainderflag1:=false;forever turn:=1;end;parbeginprocedure P1;P0;P1beginparend repeat end.28Lamport面包店算法该算法的基本思想源于顾客在面包店中购买面包时的排队原理.顾客在进入面包店前,首先抓一个号,然后按照号码由小到大的次序依次进入面包店购买面包.这里,面包店发放的号码是由小到大的,但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥),如果多个顾客抓到相同的号码,则规定按照顾客名字的字典次序进行排序,这里假定顾客是没有重名的.在计算机系统中,顾客就相当于进程,每个进程有一个唯一的标识,我们用P的下面加一个下标来表示.例如:对于Pi和Pj,如果有ij,则先为Pi服务,即Pi先进入临界区.29Lamport面包店算法面包店算法 该算法的实现需要如下两个数据结构:intchoosingn；intnumbern；前者表示进程是否正在抓号，正在抓号的进程choosingi为1，否则为0,其初值均为0.后者用来记录各个进程所抓到的号码,如numberi为0,则进程Pi没有抓号,如numberi不为0,则其正整数值为进程Pi所抓到的号码,其初值均为0.为了方便起见,我们定义下述表记法:(a,b)(c,d)如果ac or(a=candbd).max(a0,an1)其值为一正整数k,对于所有i,0in1,kai.30Lamport面包店算法dochoosingi=1;numberi=maxnumber0,number1,numbern1+1;choosingi=0;for(j=0;jn;j+)while(choosingj)skip;while(numberj0)&(numberj,j)value;if(svaluequeue);V操作原语定义如下:voidV(semaphore*s)svalue+;if(svaluequeue);其中调用了asleep和wakeup两个标准过程,它们的定义如下:asleep(squeue):执行此操作进程的PCB进入队列squeue的尾部,其状态由运行转为等待,系统转到处理机调度程序.wakeup(squeue):将队列squeue头部的进程的PCB由该队列中取出并将其排入就绪队列,其状态由等待转为就绪.51S.value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次P操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value =S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用V原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。52信号量信号量司机活动：司机活动：售票员活动：售票员活动：do do 启动车辆启动车辆 关车门关车门 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 while(1)while(1)53信号量用信号量和用信号量和 P、V操作解决这一问题，需要定义两个信号量，一操作解决这一问题，需要定义两个信号量，一个信号量个信号量start表示是否允许司机启动车辆，另一个信号量表示是否允许司机启动车辆，另一个信号量open表表示是否允许售票员开车门。初始状态是车停在始发站，车门开着，示是否允许售票员开车门。初始状态是车停在始发站，车门开着，等待乘客上车。因此，两个信号量的初值都是等待乘客上车。因此，两个信号量的初值都是0。54信号量信号量关于信号灯变量的使用有如下两个基本要求:(1)必需置一次初值,只能置一次初值,(2)初值必需为非负整数;(3)只能执行P操作和V操作,所有其它操作均是非法的.55信号量信号量基于上述规定,我们可以得到如下几个有用的结论:(1)当svalue0时,svalue为可用资源个数、不被阻塞的进程数，squeue阻塞队列为空；(2)当svaluevalue为squeue中等待进程的个数;(3)当svalue的初值为1时,可以用来实现进程互斥,这只需在进入临界区时执行一次P操作,在离开临界区时执行一次V操作.(4)当svalue的初值为正整数时，可以用来管理同种组合资源(具有多个实例的同种类资源，如5台打印机)，申请时执行一次P操作，归还时执行一次V操作.56用信号量解决互斥问题用信号量解决互斥问题 信号量的互斥算法可以用小屋模型来描述。除了黑板外，小屋中还有一个大冰箱。某进程进入小屋后执行wait操作将黑板上的数减1，这时，如果黑板上的值非负，它就进入临界段，反之它就进入冰箱内冬眠。这时，就允许另一进程进入小屋。当一个进程完成其临界段后，它进入小屋执行signal，将黑板上的值加1，这时如果黑板上的值为非正数，它就从冰箱中唤醒一个进程。57用信号量解决互斥问题用信号量解决互斥问题Vars:semaphore(:=1);ProcedureP()repeatP(s);V(s);forever58用信号量解决生产者用信号量解决生产者/消费者问题消费者问题 问题描述如下：一个生产者生产出某种类型的数据(记录、字符)，并把它送入缓冲区(缓冲区为1)，惟一的一个消费者一次从缓冲区中取走一个数据。系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。59例1.唯一生产者、唯一消费者单缓冲区问题1箱子，容量箱子，容量1 生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之60例1.唯一生产者、唯一消费者单缓冲区问题ProducerWhile(true)生产一个产品；P(s1);送入缓冲区；V(s2);s1=缓冲区空位数，初值1ConsumerWhile(true)P(s2);缓冲区取一个产品；V(s1);消费该产品；s2=产品数，初值061用信号量解决生产者用信号量解决生产者/消费者问题消费者问题 问题描述如下：一个生产者生产出某种类型的数据(记录、字符)，并把它送入缓冲区(缓冲区为n)，惟一的一个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。62例2.唯一生产者、唯一消费者多缓冲区问题生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之01k1箱子，容量箱子，容量k B:Array0.k-1Of item63环形缓冲区10K-1in(in+1)mod kout(out+1)mod k64例2.唯一生产者、唯一消费者多缓冲区问题in=0；/全局变量ProducerWhile(true)生产一个产品；P(s1);送入缓冲区bufferin；V(s2);in=(in+1)%ns1=缓冲区空位数，初值nout=0；/全局变量ConsumerWhile(true)P(s2);缓冲区bufferout取产品；V(s1);消费该产品；out=(out+1)%ns2=产品数，初值065用信号量解决生产者用信号量解决生产者/消费者问题消费者问题 问题描述如下：m个生产者生产出某种类型的数据(记录、字符)，并把它送入缓冲区(缓冲区为n)，k个消费者一次从缓冲区中取走一个数据，系统要保证缓冲区操作不发生重叠，即在任一时刻只能有一方(生产者或消费者)访问缓冲区。66例3.生产者/消费者问题01k1箱子，容量箱子，容量k B:Array0.k-1Of item生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之67例3.m生产者、k消费者n缓冲区，请问有错吗?in=0；/全局变量ProducerWhile(true)生产一个产品；P(s1);P(mutex);送入缓冲区bufferin；V(mutex);V(s2);in=(in+1)%ns1=缓冲区空位数，初值nmutex=1out=0；/全局变量ConsumerWhile(true)P(s2);P(mutex);缓冲区bufferout取产品；V(mutex);V(s1);消费该产品；out=(out+1)%ns2=产品数，初值068例3.m生产者、k消费者n缓冲区正解Program producers_consumers;Var B:Array0,k-1Of item;S1,S2,mutex:semaphore;in,out:0.k-1;Procedure producer cycle produce a product P(S1);P(mutex);Bin:=product;in:=(in+1)mod k;V(mutex);V(S2)endProcedure consumer cycle P(s2);P(mutex);x:=Bout;out:=(out+1)mod k;V(mutex);V(S1);consume x;end;69程序程序Begin S1.value:=k;S2.value:=0;mutex.value:=1;in:=0;out:=0;Cobegin P1:producer;,Pm:producer;C1:consumer;,Cn:consumer;Coend;End.70问题问题2个P操作互换位置，可否？课本P117页第7题？71总结总结P、V操作必须成对出现，有P必有V对应；互斥P、V在同一进程中出现；同步P、V不在同一进程中出现；2个P操作在一起时，P的顺序至关重要，一个同步P与一个互斥P在一起时，同步P在互斥P前；2个V操作顺序则无关紧要。72例4.读者/写者问题P.T.Courtois 1971Communication of the ACM,Vol.14,667-669.ACM:Association for Computing Machinery解法1：读者优先解法2：写者优先73例4.读者写者问题(readersandwritersproblem)Problem Statement:一组公共数据DBR1 Rm W1.Wn设有一组共享数据DB和两组并发进程,一组进程只对此组数据执行读操作,另一组进程可对此组数据执行写操作(当然同时也可以执行读操作)，我们将前一组进程称作读者，后一组进程称作写者为了保证共享数据的完整性，要求：(1)多个读者的操作可以同时进行；(2)多个写者的操作不可同时进行；(3)任何读者与写者的操作不可同时进行accessing741、读者优先、读者优先如果有读者来时，（1）无读者和写者，新读者可以读；（2）如有写者等待，但有其他读者正在读，则新读者可以读；（3）有写者写，新读者则等待。75读者优先读者优先Var wsem:semaphore;(initial value:1)Writer：while(1)P(wsem);V(wsem);76读者优先读者优先intreadCount=0;semaphorewsem=1;semaphoremutex=1;reader()：while(1)P(mutex);readCount=readCount+1;if(readCount=1)P(wsem);V(mutex);P(mutex);readCount=readCount1;if(readCount=0)V(wsem);V(mutex);变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量readCount用来记录读者的数目；变量mutex用来实现读者对于变量readCount访问的互斥.读者等待在何处？读者如何被唤醒？77分析：分析：问题问题：读者源源不断，：读者源源不断，readcount不归不归0，写者会，写者会被饿死。这是不合理的，因为写者的操作是更新被饿死。这是不合理的，因为写者的操作是更新数据，应当优先进行，否则读者将读到已经过时数据，应当优先进行，否则读者将读到已经过时的数据的数据策略策略：一旦有写者等待，新到达读者等待，正在：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。读的读者都结束后，写者进入。782、写者优先、写者优先如果有写者来时，（1）无读者，新写者可以写；（2）如有读者正在读，则新读者等待；（3）有其他写者正在写，新写者则等待。792、写者优先、写者优先intwriteCount=0;semaphorewsem,rsem=1;semaphoremutexY=1;writer()：while(1)P(mutexY);writeCount=writeCount+1;if(writeCount=1)P(rsem);V(mutexY);P(wsem);V(wsem);P(mutexY);writeCount=writeCount1;if(writeCount=0)V(rsem);V(mutex);变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量writeCount用来记录写者的数目；变量mutexY用来实现读者对于变量writeCount访问的互斥.802、写者优先、写者优先intreadCount=0;semaphorewsem,rsem=1;semaphoremutexX,mutex=1;reader()：while(1)P(mutex);P(rsem);P(mutexX);readCount=readCount+1;if(readCount=1)P(wsem);V(mutexX);V(rsem);V(mutex);P(mutexX);readCount=readCount1;if(readCount=0)V(wsem);V(mutexX);变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量readCount用来记录读者的数目；变量mutexX用来实现读者对于变量readCount访问的互斥;mutex用来实现rsem上不要有长的排队等待。读者等待在何处？读者如何被唤醒？81AND型信号量型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作，即processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=1A阻塞processB:wait(Dmutex);于是Dmutex=1B阻塞82AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在P操作中，增加了一个“AND”条件，故称为AND同步，或称为同时P操作，即Swait(Simultaneouswait)定义如下：83S.value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次P操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value =S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用V原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。84Swait(S1,S2,Sn)ifSi1andandSn1thenfor(i=1;i=n;i+)Si=Si1;endfor/满足资源要求时，才进行减操作；else/调用进程进入第一个小于1的信号量的等待队列，阻塞该进程endif85SsignalSsignal(S1,S2,Sn)for(i=1;i=n;i+)Si=Si+1;for(在Si.queue中等待的每一个进程P)从等待队列中Si.queue中取出进程P；if(判断该进程是否通过Swait中的测试)通过，进程P进入就绪队列；else进程P进入某个等待队列；86信号量集信号量集Swait(S,t,d)；Ssignal(s,d)S：信号量t：测试值d：占用值87一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。88在生产者消费者问题中应注意：首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。利用利用AND信号量解决生产者信号量解决生产者消费者消费者问题问题 892.利用利用AND信号量解决生产者信号量解决生产者消费者问题消费者问题 armutex,empty,full:semaphore=1,n,0;buffer:array0,n1ofitem;inout:integer=0,0;beginparbeginproducer:beginrepeatproduceaniteminnextp;Swait(empty,mutex);buffer(in)=nextp;in=(in+1)modn;Ssignal(mutex,full);untilfalse;end90consumer:beginrepeatSwait(empty,mutex);nextc=buffer(out);out=(out+1)modn;Ssignal(mutex,full);consumertheiteminnextc;untilfalse;endparendend91读者优先读者优先（一般信号量集）（一般信号量集）WriterSwait(wmutex,1,1;rcount,n,0);Ssignal(wmutex,1)Wmutex为读写互斥信号量，初值为1ReaderSwait(wmutex,1,0;rcount,1,1);Ssignal(rcount,1)Rcount为最大读者数，初值为n923.4.4 用信号量解决理发店问题用信号量解决理发店问题理发店问题是使用信号量实现并发的另一个例子，它同操作系统中的实际问题非常相似。如图示933.5 管程管程管程的提出信号灯及PV操作缺点是:(1)易读性差,因为如要了解对于一组共享变量及信号灯变量的操作是否正确,则必须通读整个系统或并发程序;(2)不利于修改和维护,因为程序的局部性很差,所以任一组变量或任一段代码的修改都可能影响全局;(3)正确性难以保证,因为操作系统或并发程序规模通常都很大,要保证这样一个复杂的系统没有逻辑错误是很困难的.管程的基本思想是:将共享变量以及对于共享变量所能进行的所有操作集中在一个模块中,一个操作系统或并发程序由若干个这样的模块所构成,由于一个模块通常较短,模块之间联系清晰,提高了可读性,便于修改和维护,正确性易于保证.943.5.1 带信号量的管程带信号量的管程 管程是一种并发性的结构，它包括用于分配一个特定的共享资源或一组共享资源的数据和过程。管程由三部分组成：局部于管程的共享变量说明。对该数据结构进行操作的一组过程。对局部于管程的数据设置初始值的语句。此外，还需为该管程赋予一个名字。95管程管程 96管程的语义管程的语义(1)管程中的共享变量在管程的外部是不可见的,外部只能通过调用管程中所说明的外部过程(函数)来间接地访问管程中的共享变量(2)为了保证管程共享变量的数据完整性,规定管程互斥进入;(3)管程通常是用来管理资源的,因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作,当一个进入管程的进程执行等待操作时,它应当释放管程的互斥权;当一个进入管程的进程执行唤醒操作时(如P唤醒Q),管程中便同时有了两个同时处于活动状态的进程.97管程管程因为管程是互斥进入的,所以当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待,因而在管程的入口处应当有一个进程等待队列,称作入口等待队列.在管程内部,可以说明和使用一种用于进程等待的队列变量,称作条件型变量:在进程进入管程时和离开管程时,分别应当执行如下的操作:进入管程:申请管程的互斥权.离开管程:如果紧急等待队列非空,则唤醒第一个等待者,否则释放管程的互斥权.98管程的形式管程的形式由于管程语言提出时，C语言尚未流行，因而管程大多采用扩展的pascal语言描述，管程的一般形式如下：TYPEmonitor_name=MONITOR;共享变量说明define本管程内所定义、本管程外可调用的过程(函数)名表;use本管程外所定义、本管程内将调用的过程(函数)名表;PROCEDURE过程名(形参表);过程局部变量说明;BEGIN语句序列;END;FUNCTION函数名(形参表):值类型;函数局部变量说明;BEGIN语句序列;END;BEGIN共享变量初始化语句序列END;99利用管程解决生产者利用管程解决生产者-消费者问题消费者问题 在利用管程方法来解决生产者消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer,或简称为PC。其中包括两个过程：100(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，消费者应等待。101typeproducerconsumer=monitorVarin,out,count:integer;buffer:array0,n1ofitem;notfull,notempty:condition;procedureentryput(item)beginifcountnthennotfull.wait;buffer(in)=nextp;in=(in+1)modn;count=count+1;ifnotempty.queuethennotempty.signal;end102procedureentryget(item)beginifcount0thennotempty.wait;nextc=buffer(out);out=(out+1)modn;count=count1;ifnotfull.quenethennotfull.signal;endbeginin=out=0;count=0end103在利用管程解决生产者消费者问题时，其中的生产者和消费者可描述为：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end104总结总结管程最主要的特点如下：(1)模块化,一个管程是一个模块;(2)抽象数据类型,管程是一种特