操作系统汤子英课件第3章进程同步.ppt

第三章 进程同步与通信,3.1 进程同步 3.2 经典进程的同步问题 3.3 管程机制 3.4 进程通信,回顾操作系统的特性：并发资源共享异步性（不确定性 或 随机性）虚拟性,3.1 进 程 同 步(重点),3.1.1 进程同步的基本概念,1.一组并发进程执行时存在两种相互制约关系：,进程互斥资源共享关系（间接相互制约关系）进程本身之间不存在直接联系。进程同步相互合作关系（直接相互制约关系）进程本身之间存在着相互制约的关系。,在多道程序系统中，进程之间存在2种不同的制约关系:(互斥/间接制约关系)、(同步/直接制约关系),进程互斥资源共享关系（间接相互制约关系）进程本身之间不存在直接联系。处于同一系统中的进程，必然是共享着某种系统资源，如共享CPU、I/O设备。例如，在仅有一台打印机的系统中，有两个进程A和B，如果在A进程提出打印请求时，系统已将打印机分配给进程B，则系统让A进程等待，直至B将打印机用完并释放后，系统才将打印机分配给进程A。,进程同步相互合作关系（直接相互制约关系）进程本身之间存在着相互制约的关系。例如，有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时，计算进程B因不能获得所需数据而等待。当进程A把数据送入缓冲时，便应向进程B发送一信号，将它唤醒；（接力棒）,2.临界资源(Critical Resouce),临界资源:在一段时间内只允许一个进程访问 的资源。诸进程间应采取互斥方式，实现对资源的共享。共享变量，打印机 等均属于此类资源。,进程间的关系进程间并发举例,例1：一飞机订票系统，两个终端，运行T1、T2进程 T1:T2:.Read(x);Read(x);y1:=x;y2:=x;if y1=1 then if y2=1 then y1:=y1-1;y2:=y2-1;x:=y1;x:=y2;write(x);write(x);.,设x的当前值为：100,1.若执行顺序为：先T1;后T2;则结果：x=982.若执行顺序为：T1:Read(x);T2:Read(x);T1:if y1=1 then y1:=y1-1;T2:if y2=1 then y2:=y2-1;T1:write(x);T2:write(x);则结果 x=99,分析：产生错误的原因是不加控制地访问共享变量x,例2,司机 P1 售票员 P2 REPEAT REPEAT 启动 关门 正常运行 售票 到站停 开门 UNTIL FALSE UNTIL FALSE,进程间的关系进程间并发举例,进程间的关系并发执行举例例3：与进程的执行顺序有关的错误,复制一个记录 Cobegin get;copy;put;Coend,get,copy,put,f,s,t,g,源记录,目标记录,进程间的关系并发执行举例例3：与进程的执行顺序有关的错误,f s t g 0 初始状态 3,4,.,m 2 2(1,2)1 g,c,p 4,5,.,m 3 3(1,2,3)2 g,p,c 4,5,.,m 3 3(1,2,2)X3 c,g,p 4,5,.,m 3 2(1,2,2)X4 c,p,g 4,5,.,m 3 2(1,2,2)X5 p,c,g 4,5,.,m 3 2(1,2,2)X6 p,g,c 4,5,.,m 3 3(1,2,2)X,序 初始状态 源记录的 目标记录 结果正确性 号 及执行顺序 剩余部分 的当前值,注：从1到6的各个执行，是在0（初始状态）的基础上进行的,错误的原因是get,copy,put 过程没有按照应该的顺序执行,进程间的关系并发执行举例例3：与进程的执行顺序有关的错误正确执行顺序,例4 生产者消费者问题(Producer-Consumer)有一个生产者进程和一个消费者进程。他们共享一个缓冲区。生产者进程每生产一件物品就要存入缓冲区，但缓冲区每次只能存放一件物品，只有消费者取走物品，才能放入第二件物品。缓冲区中有物品消费者进程就可以去取，每取走一件物品后必须等生产者再放入物品后才可以去取。生产者进程与消费者进程是以异步方式进行的，但它们之间必须保持同步；即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个装满产品的缓冲区中投放产品。,生产者进程Buffer：intergerProcesser producerBegin L1：produce a product；Buffer：=product；go to L1end,消费者进程Buffer：intergerProcesser consumerBegin L2：take a product；consumer；go to L2end,生产者消费者问题(Producer-Consumer)有一群生产者进程在生产产品，并将产品提供给消费者进程去消费，为使生产者进程和消费者进程能并发执行，在他们之间设置了一个具有n个缓冲区的缓冲池，生产者进程将他所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。生产者进程与消费者进程是以异步方式进行的，但它们之间必须保持同步；即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个装满产品的缓冲区中投放产品。,in,out,1、用一个数组来表示上述的具有n个缓冲区的缓冲 池，用0,1,n-1表示。2、用输入指针in来指示下一个可投放产品的缓冲，每当生产者投放一个产品，输入指针加1；3、用输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。这里的缓冲池是组织成循环缓冲的，故应 把输入指针加1表示成in:=(in+1)modn;把输出指针加1表示成out:=(out+1)modn.当(in+1)=out时表示缓冲池满；in=out时表示缓冲池空。,？,还引入一个整型变量counter，初值为0，生产者进程向缓冲池投放一个产品后，counter加1；消费者进程从中取走一个产品时，使counter减1；生产者和消费者共享下面的变量：var n:integer;type item=;var buffer:array0,1,n-1 of item;in,out:0,1,n-1;counter:0,1,n-1;,producer:repeat produce an item in nextp;while counter=n do no_op;bufferin=nextp;in:=(in+1)modn;counter=counter+1;until false;,consumer:repeat while counter=0 do no_op;nextc:=bufferout;out:=(out+1)modn;counter=counter-1;consume the item in nextc;until false;,表示目前缓冲区产品已放满,刚生产出来的产品,虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register1=counter;register2=counter;register1=register1+1;register2=register2-1;counter=register1;counter=register2;假设：counter的当前值是5。无论是先执行生产者的语句还是先执行消费者的语句，counter都为5,但是，如果按下述顺序执行：register1=counter;(register1=5)register1=register1+1;(register1=6)register2=counter;(register2=5)register2=register2-1;(register2=4)counter=register1;(counter=6)counter=register2;(counter=4)最后counter 的值为4,并且结果不可预见.解决问题的关键是,把counter作为临界资源来处理,即令生产者和消费者进程互斥访问变量counter.,执行过程相当于生产一点拿一点,而不是消费完整的产品,3.1、临界区的定义与进入临界区：把在每个进程中访问临界资源的那段代码称为临界区(critical section)。进入区：在临界区前面增加一段用于进行临界资源检查的代码，称为进入区。,3.临界区(critical section),退出区：将临界区正被访问的标志恢复为未被访问的标志。剩余区：其余部分。,repeat,Entry section,Critical section;,Remainder section,Until false;,exit section,进入区，P、V操作,临界区,退出区，P、V操作,剩余区,P：wait(S),P(S)可理解为关锁V：signal(S),V(S)可理解为开锁,图 3.12 资源互斥使用例,4、互斥算法使用临界区遵循的原则空闲则入：其他进程均不处于临界区；忙则等待：已有进程处于其临界区；有限等待：等待进入临界区的进程不能死等；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）临界区的使用原则是什么？上面4条。,5 进程互斥的软件方法,有两个进程Pi,Pj，其中:,算法1：单标志,设立一个公用整型变量 turn：描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入：turn为i时，进程Pi可进入；在退出区修改允许进入进程标识：进程Pi退出时，改turn为进程Pj的标识j；,在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区,缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区；,算法2：双标志、先检查,设立一个标志数组flag：描述进程是否在临界区，初值均为FALSE。先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；在退出区修改本进程在临界区的标志；,其中Pi,请写出Pj,While(flagj);Flagi=TRUE;,Flagi=FALSE;,Critical section,Remainder section,While(flagi);Flagj=TRUE;,Flagj=FALSE;,Critical section,Remainder section,flagi=flagj=FALSE,优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按下面序列执行时，会同时进入：Pi Pj Pi Pj。即在检查对方flag之后和切换自己flag之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能连续进行。,算法3：双标志、后检查,类似于算法2，与互斥算法2的区别在于先修改后检查。可防止两个进程同时进入临界区。flag初值均为FALSE,其中的Pi:,flagi=TRUE;while(flagj);,flagi=FALSE;,critical section,remainder section,flagi=flagj=FALSE,其中的Pj:,缺点：Pi和Pj可能都进入不了临界区。按下面序列执行时，会都进不了临界区：Pi Pj Pi Pj。即在切换自己flag之后和检查对方flag之前有一段时间，结果都切换flag，都检查不通过。,信号量(semaphore),前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。,3.1.2 信号量机制,1.整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：wait(S):while S0 do no-op S=S-1;signal(S):S=S+1;,信号量,P操作，又称关锁,V操作，又称开锁,占用资源，所以减一,释放资源，所以加一,S代表资源个数,不放弃处理机,2.记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：,S代表资源个数,s:=s+1,Wait(s):,Signal(s):,Block,自我阻塞，放弃处理机,S 0,Wake Up,Y,N,信号量和P、V原语的另一种解释,每个信号量s除一个整数值s.count（计数）外，还有一个进程阻塞队列s.queue，其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断。初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）*若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数二进制信号量(binary semaphore)：只允许信号量取0或1值,1.P原语wait(s),-s.count;/表示申请一个资源;if(s.count 0)/表示没有空闲资源;调用进程进入阻塞队列s.queue;阻塞调用进程;,记录型信号量,2.V原语signal(s),+s.count;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;,V原语通常唤醒进程等待队列中的头一个进程,记录型信号量,P、V操作是定义在信号量S上的两个操作，其定义如下：P(S)：S=S-1;若S0，则调用P(S)的进程继续运行；若S0，则调用V(S)的进程继续运行；若S0，从等待信号量S的阻塞队列中唤醒头一个进程，然后调用V(S)的进程继续运行。,S代表资源个数,type semaphore=record value:integer;L:list of process;end相应地，wait(S)和signal(S)操作可描述为：procedure wait(S)var S:semaphore;begin S.value=S.value-1;if S.value0 then block(S,L)end procedure signal(S)var S:semaphore;begin S.value=S.value+1;if S.value0 then wakeup(S,L);end,系统中某类资源的数目,每次wait操作，意味着进程请求一个单位的该类资源1,资源已分配完毕，因此进程应调用block原语，进行自我阻塞,信号量链表中，仍有等待该资源的进程被阻塞，应将进程唤醒,S代表资源个数,如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,3.AND型信号量,在两个进程中都要包含两个对Dmutex和Emutex的操作，即process A:process B:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行wait操作：process A:wait(Dmutex);于是Dmutex=0process B:wait(Emutex);于是Emutex=0process A:wait(Emutex);于是Emutex=-1 A阻塞process B:wait(Dmutex);于是Dmutex=-1 B阻塞,2个共享数据，初值为1,P操作，1，S0阻塞,谁也不释放，死锁状态,AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneous wait)定义如下：,Swait(S1,S2,Sn)if Si1 and and Sn1 then for i=1 to n do Si=Si-1;endfor else place the process in the waiting queue associated with the first Si found with Si1,and set the program count of this process to the beginning of Swait operation endifSsignal(S1,S2,Sn)for i=1 to n do Si=Si+1;Remove all the process waiting in the queue associated with Si into the ready queue.endfor;,N类资源,每类资源只申请1个,在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需N个某类临界资源时，便需要进行N次wait(s)操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下限值时，便不予分配。因而，在每次分配之前，都必须测试该资源的数量是否大于测试值t。基于上述两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。,4.信号量集,S代表资源个数,Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and Sntn then for i=1 to n do Si=Si-di;endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation.endif signal(S1,d1,Sn,dn)for i=1 to n do Si=Si+di;Remove all the process waiting in the queue associated with Si into the ready queue endfor;,S为信号量t为下限值d为需求值,一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。,S代表资源个数,Swait(S1,S2,Sn)/P原语；while(TRUE)if(S1=1,AND信号量,Ssignal(S1,S2,Sn)for(i=1;i=n;+i)+Si;/释放占用的资源；for(each process P waiting in Si.queue)/检查每种资源的等待队列的所有进程；从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)/注：与signal不同，这里要进行重新判断；/通过检查（资源够用）时的处理；进程P进入就绪队列;else/未通过检查（资源不够用）时的处理；进程P进入某等待队列；,三种信号量的比较,整型信号量：只有一个资源，只能互斥访问这个资源记录型信号量：只可申请一类资源，该资源有n个，一次只可申请一个。AND型信号量：可申请n类资源，每类资源有m个，每次可申请每类资源中的一个。信号量集：可申请n类资源，每类资源有m个，每次可申请每类资源中的多个。,1、应用（一）：利用信号量实现互斥,为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏,3.1.3 信号量的应用,信号量代表资源个数,利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore=1;begin parbegin process 1:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end,process 2:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end parend,只能有一个进程进入执行,作用?,注意：wait(mutex);signal(mutex);必须成对出现。缺少wait(mutex)将导致系统混乱，不能保证对临界资源的互斥访问。缺少signal(mutex)将使临界资源永远不释放，从而使等待该进程资源而阻塞的进程不在被唤醒。,2、应用（二）：利用信号量实现互斥互斥举例：n个进程共用一个临界区,const int n=进程数；Semaphore s=1;Void Process(int i)while(true)P(s);/wait(s)V(s)/signal(s)remainder section,void main()parbegin(Process(1),Process(2),.,Process(n);,2、应用（二）：利用信号量实现互斥互斥举例：n个进程共用一个临界区,设有两个并发执行的进程P1和P2。P1中有语句S1，P2中有语句S2，如果我们希望S1执行后再执行S2，只需使进程Pl和P2共享一个公用信号量S，并赋予其初值为0，将signal(s)操作放在S1后面；而在S2语句前面插入wait(s)操作，即：,3、应用（三）：利用信号量实现前趋关系,得到所需的资源才能执行S2,在进程P1中，用Sl；signal(s)；,在进程P2中，用wait(s)；S2；,执行完S1后才释放资源,P2不可能先执行。因为S0,进程代码？,图 2-10 前趋图举例,a,b,c,d,g,f,e,Var a,b,c,d,e,f,g;semaphore=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end;begin wait(a);S2;signal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parend end,3.2 经典进程的同步问题,进程互斥：指的是一个进程正在使用某个系统资源，另外一个想用该资源的进程就必须等待，而不能同时使用。,进程同步：指的是两个或多个进程为了合作完成同一个任务，在执行速度或某个确定的时序点上必须相互协调，即一个进程的执行必须依赖另一个进程。多个进程之间通信使用阻塞和唤醒消息进行通信。,往往一个实际问题多个进程既有同步也有互斥。,生产者/消费者问题(the producer/consumer problem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。,缓冲区不满，生产者才能写入；缓冲区不空，消费者才能读出同步,互斥,3.2 经典进程的同步问题,设信号量：full是“满”数目，初值为0，empty是“空”数目，初值为N。实际上，full和 empty是同一个含义：full+empty=N mutex用于访问缓冲区时的互斥，初值是1,每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？),P1.Pn,C1.Cn,变量：Empty=5Full=0Mutex=1,缓冲区,P1.Pn,C1.Cn,变量：Empty=5Full=0Mutex=1,缓冲区,Producer makes a new unit,P1.Pn,C1.Cn,变量：Empty=4Full=0Mutex=1,缓冲区,Producer applies a“empty”,P1.Pn,C1.Cn,变量：Empty=4Full=0Mutex=0,缓冲区,Producer applies critical section,P1.Pn,C1.Cn,变量：Empty=4Full=0Mutex=0,缓冲区,Producer puts unit into buffer,P1.Pn,C1.Cn,变量：Empty=4Full=0Mutex=1,缓冲区,Producer goes out critical section,P1.Pn,C1.Cn,变量：Empty=4Full=1Mutex=1,缓冲区,Producer releases a“full”,P1.Pn,C1.Cn,变量：Empty=0Full=5Mutex=1,缓冲区,Repeat 4 times again,P1.Pn,C1.Cn,变量：Empty=0Full=5Mutex=1,缓冲区,Producer makes new unit again,P1.Pn,C1.Cn,变量：Empty=-1Full=5Mutex=1,缓冲区,Producer applies a“empty”,P1,P1.Pn,C1.Cn,变量：Empty=-1Full=4Mutex=1,缓冲区,Consumer applies a“full”,P1,P1.Pn,C1.Cn,变量：Empty=-1Full=4Mutex=0,缓冲区,Consumer applies critical section,P1,P1.Pn,C1.Cn,变量：Empty=-1Full=4Mutex=0,缓冲区,Consumer gets a unit from buffer,P1,P1.Pn,C1.Cn,变量：Empty=-1Full=4Mutex=1,缓冲区,Consumer goes out critical section,P1,P1.Pn,C1.Cn,变量：Empty=0Full=4Mutex=1,缓冲区,Consumer releases a“empty”,P1,P1.Pn,C1.Cn,变量：Empty=0Full=4Mutex=0,缓冲区,Producer applies critical section,P1.Pn,C1.Cn,变量：Empty=0Full=4Mutex=0,缓冲区,Producer puts unit into buffer,P1.Pn,C1.Cn,变量：Empty=0Full=4Mutex=0,缓冲区,生产者与生产者互斥消费者与消费者互斥生产者与消费者同步,作业：以该图为基础，写（画）出缓冲区已空时，一个消费者进程执行P(full)后；又一个消费者进程执行P(full)后；一个生产者进程执行V(full)后；各变量的值及等待队列的情况。,操作的顺序很重要，不当会产生死锁。如假定Producer和Consumer如下：,当full=0,mutex=1时，执行顺序：Consumer.P(mutex);Consumer.P(full);/C阻塞，等待Producer 发出的full信号 Producer.P(empty);Producer.P(mutex);/P 阻塞，等待Consumer发出的empty信号死锁，还有其他的执行序列可以产生死锁吗？,思考与作业：上述的生产者和消费者之间是互斥的，生产者与生产者之间以及消费者与消费者之间也是互斥的，是否可以实现生产者和消费者之间的并行？如何实现？用P.V操作解决司机与售票员的问题3.用P.V操作解决下图之同步问题:,3.2 经典进程的同步问题,3.2.1 生产者消费者问题,用PV操作实现简单生产者和消费者的同步：设两个信号量SP和SGSP表示是否允许把物品放入缓冲区，1允许，0不许，初值设为1SG表缓冲区是否存有物品，初值为0，表示还没有物品,生产一种产品,产品送入缓冲区,P(SP),V(SG),V(SP),P(SG),从缓冲区取走一个产品,消耗该产品,SP,SG:semaphore=1,0;buffer:integer;parbegin proceducer:begin L1：producer an product;P(SP);buffer=product;V(SG);go to L1;end；proceducer:begin L2：P(SG);take a product from buffer;V(SP);consum an product;go to L2;end；parend；,判断是否允许把物品放入缓冲区,通知消费者，缓冲区有东西了,通知生产者者，可以向缓冲区放东西了,判断缓冲区是否有物品,1.利用记录型信号量解决生产者消费者问题信号量有：Mutex：实现读和取诸进程对缓冲池的互斥访问，初值为1Empty：表示缓冲池中空缓冲区的数量，初值为n，表全空Full：表示缓冲池中产品的数量，初值为0，没产品又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下：,Var mutex,empty,full:semaphore=1,n,0;buffer:array0,n-1 of item;in,out:integer=0,0;begin parbegin proceducer:begin repeat producer an item nextp;wait(empty);wait(mutex);buffer(in)=nextp;in=(in+1)mod n;signal(mutex);signal(full);until false;end,就是一把锁，防其它生产者进程影响不允许多个进程同时用一个输入指针，每一时刻只允许一个生产者进程使用该指针，否则会冲突,判断是否允许向缓冲区放东西，初值允许放n个,放入了产品，加1操作，初值为0，表示没有产品,保证存和取互斥,P(mutex)锁的作用?,consumer:begin repeat wait(full);wait(mutex);nextc=buffer(out);out=(out+1)mod n;signal(mutex);signal(empty);consumer the item in nextc;until false;end parend end,判断缓冲区是否有产品，初值为0,消费了一个产品，空出一个空缓冲区，所以个数加1,？,不允许多个进程同时用一个输出指针，每一时刻只允许一个消费者进程使用该指针，否则会冲突类似于只有1台自行车，多个人,首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在计算进程中，而signal(empty)则在打印进程中，计算进程若因执行wait(empty)而阻塞，则以后将由打印进程将它唤醒；最后，在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。如果这2个顺序颠倒呢？wait(full);wait(mutex);,注意：,wait(mutex);wait(empty);buffer(in)=nextp;in=(in+1)mod n;signal(full);signal(mutex);,wait(mutex);wait(full);nextc=buffer(out);out=(out+1)mod n;signal(empty);signal(mutex);,2.利用AND信号量解决生产者消费者问题,var mutex,empty,full:semaphore=1,n,0;buffer:array0,n-1 of item;in out:integer=0,0;begin parbegin producer:begin repeat produce an item in nextp;Swait(empty,mutex);/P(empty,mutex);buffer(in)=nextp;in=(in+1)mod n;Ssignal(mutex,full);/V(mutex,full);until false;end,consumer:begin repeat Swait(full,mutex);nextc=buffer(out);out=(out+1)mod n;Ssignal(mutex,empty);consumer the item in nextc;until false;end parend end,例 1 用信号量实现司机和售票员的同步。,设S1为司机的私用信号量，0表不许开车，1允许开车，初值为0S2为售票员的私用信号量，0表不许开门，1允许开门，初值为0由于初始状态是汽车行车和售票员售票。所以初值都为0则司机和售票员的同步过程描述如下：,例2：桌子上有一只盘子，每次只能放入一只水果，爸爸专向盘子中放苹果，妈妈专向盘子中放桔子，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。只有盘子空则爸爸或妈妈就可向盘子中放一只水果，仅当盘子中有自己需要的水果时，儿子或女儿可从盘子中取出。把爸爸、妈妈、儿子、女儿看作四个进程，用PV操作进行管理，使这四个进程能正确的并发执行。,爸爸和妈妈存放水果时必须互斥。临界资源为盘子儿子和女儿分别吃桔子和苹果。爸爸放了苹果后，应把“盘中有苹果”的消息发送给女儿；妈妈放了桔子后，应把“盘中有桔子”的消息发送给儿子；取走果品后应该发送“盘子可放水果”的消息，但不特定发给爸爸或妈妈，应该通过竞争资源(盘子)的使用权来决定。,如何定义信号量？,S 是否允许向盘子中放入水果，初值为1，表示允许放入，且只允许放入一只,SP表示盘子中是否有苹果，初值为0，表示盘子为空，不许取，SP1时可以取,SO表示盘子中是否有桔子，初值为0，表示盘子为空，不许取，SP1时可以取,至于儿子或女儿取走水果后要发送“盘子中可存放水果”的消息，只要调用V(S)就可达到目的，不必在增加信号量了。,Begain S,SP,SO:semaphore S:=1;SP:=0;SO:=0;Cobegain process father begain L 1:have an apple;P(S);put an apple;V(SP);go to L 1 end;,process mother begain L 2:have an orange;P(S);put an orange;V(SO