互斥、同步及通讯

1、1 1第四章 互斥、同步与通讯4.1并发进程并发进程(concurrent processes)4.2进程互斥进程互斥(mutual exclusion)4.3进程同步进程同步(synchronization)（重点（重点）4.4进程高级通讯进程高级通讯(communication)2 24.1并发进程4.1.1前趋图的定义前趋图的定义前趋图（前趋图（precedence graph）有向无环图，图中每个结点表示一个语句、一个计算步骤、有向无环图，图中每个结点表示一个语句、一个计算步骤、或一个进程。或一个进程。结点间的有向边表示偏序或前趋（结点间的有向边表示偏序或前趋（precedence r

2、elation)关系关系“” 。=（Pi，Pj）| Pj启动之前启动之前Pi必须已经完成必须已经完成。（Pi，Pj）可记作可记作PiPj, 称称Pi是是Pj的前趋，的前趋，Pj是是Pi的后的后继。继。在前趋图中，没有前趋的结点称为初始结点，没有后继的结在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。点称为终止结点。每个结点可以有一个权重每个结点可以有一个权重(weight)，它可以表示该结点所包，它可以表示该结点所包含的程序量或计算时间。含的程序量或计算时间。3 34.1并发进程前趋图的例子前趋图的例子P1P2，P1P3，P1P4，P2P5，P3P5，P4P5，P4P6，P

3、5P7，P6P714326574 44.1.2顺序程序及其特性4.1.2.1 程序的顺序执行程序的顺序执行(1)内部顺序性：对于一个进程来说，它内部顺序性：对于一个进程来说，它的所有指令是按序执行的。的所有指令是按序执行的。S1：a:=x+yS2：b:=a-zS3：c:=a+bS4：d:=c+5S1S2S3S45 54.1.2顺序程序及其特性(2)外部顺序性：对于多个进程来说，所外部顺序性：对于多个进程来说，所有进程的活动是依次执行的。有进程的活动是依次执行的。例例: 输入输入(I)、计算、计算(C)、打印、打印(P)三个活动构三个活动构成的进程，每个进程的内部活动是顺序的，成的进程，每个进程

4、的内部活动是顺序的，即即IiCiPi，多个进程的活动也是顺序的。，多个进程的活动也是顺序的。I1C1P1I2C2P26 64.1.2顺序程序及其特性4.1.2.2顺序程序特性顺序程序特性: (1)顺序性顺序性: 指令逐条执行指令逐条执行 (2)封闭性封闭性: 不受其它程序及外界因素影响不受其它程序及外界因素影响 (3)可再现性可再现性: 结果与推进速度无关结果与推进速度无关7 7 顺序程序设计的例顺序程序设计的例 while(1) input while(1) input，processprocess，output output 7878输入机输入机处理器处理器磁带机磁带机1301301501

5、50228228280280300300378378430430450450时时 间间处理器利用率：处理器利用率：52/(78+52+20)35%52/(78+52+20)35%8 84.1.3 并发程序及其特性4.1.3.1 程序的并发执行程序的并发执行(1)内部并发性内部并发性: 指一个程序内部的指一个程序内部的并发性。例：并发性。例：S1：a:=x+2；S2：b:=y+4；S3：c:=a+b；S4：d:=c+6；S5：e:=c-d；214359 94.1.3 并发程序及其特性4.1.3.1 程序的并发执行(2)外部并发性外部并发性: 指多个程序活动的重叠执行。指多个程序活动的重叠执行。I

6、1I2I3I4C1C2C3C4P1P2P3P41010 两个无关的进程并发执行的例两个无关的进程并发执行的例处理器利用率：处理器利用率：(52+42)/(78+52+20)63%(52+42)/(78+52+20)63%7878输入机输入机处理器处理器磁带机磁带机130130150150228228280280300300378378430430450450时时 间间磁带机磁带机打印机打印机2020626217017032032011114.1.3 并发程序及其特性4.1.3.2 并发程序的特性并发程序的特性（1）并发性：程序并发执行对应某一种交叉，不）并发性：程序并发执行对应某一种交叉，不同

7、的交叉可能导致不同的计算结果，操作系统应当同的交叉可能导致不同的计算结果，操作系统应当保证只产生导致正确结果的交叉，去除那些可能导保证只产生导致正确结果的交叉，去除那些可能导致不正确结果的交叉。致不正确结果的交叉。（2）非封闭性：一个进程的运行环境可能被其它）非封闭性：一个进程的运行环境可能被其它进程所改变，从而相互影响。进程所改变，从而相互影响。（3）不可再现性：由于交叉的随机性，并发程序）不可再现性：由于交叉的随机性，并发程序的多次执行可能对应不同的交叉，因而不能期望重的多次执行可能对应不同的交叉，因而不能期望重新运行的程序能够再现上次运行的结果。新运行的程序能够再现上次运行的结果。121

8、24.1.3 并发程序及其特性并发程序及其特性不可再现性的例子不可再现性的例子进程进程P： 进程进程Q：A1: N=0； B1: PRINT（N）；）；A2: N=:N+1； B2: N:=0；A3: GOTO A2； B3: GOTO B1；此例中进程此例中进程P累积计数，进程累积计数，进程Q将累计的结果打印出来。将累计的结果打印出来。希望打印出的数是累计数的和。希望打印出的数是累计数的和。两个进程并发执行时有许多可能的交叉两个进程并发执行时有许多可能的交叉:如进程如进程P循环循环5次进程次进程Q循环循环1次，然后进程次，然后进程P又循环又循环3次进程次进程Q循环循环1次，则输出结果是次，则

9、输出结果是5，3；如进程如进程P循环循环2次进程次进程Q循环循环1次，然后进程次，然后进程P又循环又循环6次进程次进程Q循环循环1次，则输出结果是次，则输出结果是2，6。两次执行结果完全不同。两次执行结果完全不同。进程进程Q执行完执行完B1后被中断，进程后被中断，进程P对对N执行加执行加1操作，然后进程操作，然后进程Q执行执行B2，在这种情况下进程，在这种情况下进程P的累计数将被丢失。的累计数将被丢失。13134.1.4 程序并发执行的条件程序并发执行的条件 在失去封闭性的条件下，保持可再现性。在失去封闭性的条件下，保持可再现性。R(pi)=a1,a2,am表示程序表示程序pi在执行期间所需读

10、在执行期间所需读取的所有变量的集合，称为取的所有变量的集合，称为“读集读集”；W(pi)=b1,b2,bn表示程序表示程序pi在执行期间所需改在执行期间所需改变的所有变量的集合，称为变的所有变量的集合，称为“写集写集”。若有两条语句若有两条语句c=a+b和和v=c-1，则它们的，则它们的“读集读集”和和“写集写集”分别为：分别为：R(c:=a+b)=a,b，R(v:=c-1)=cW(c:=a+b)=c，W(v:=c-1)=v14144.1.4 程序并发执行的条件程序并发执行的条件若两个程序若两个程序p1，p2满足如下条件，则能满足如下条件，则能够保持可再现性，因而可以并发执行。够保持可再现性，

11、因而可以并发执行。该条件是该条件是1966年首先由年首先由Bernstein提出的，提出的，称为称为Bernstein条件。条件。 R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=154.1.4 程序并发执行的条件程序并发执行的条件 例如，有如下四条语句：例如，有如下四条语句： S1: a:=x+y S2: b:=z+1 S3: c:=a-b S4: w:=c+1 R(S1)=x,y，R(S2)=z，R(S3)=a,b，R(S4)=c W(S1)=a，W(S2)=b，W(S3)=c，W(S4)=w 可见，可见，R(S1)W(S2)R(S2)W(S1)W(S1)W(S2)=，因，因

12、而而S1和和S2可以并发执行；而可以并发执行；而S1 和和S3不能并发执行，因不能并发执行，因为为W(S1)R(S3)=a；S2和和S3也不能并发执行，因为也不能并发执行，因为W(S2) R(S3)=b；同样，；同样，S3和和S4不能并发执行，因不能并发执行，因为为W(S3)R(S4)=c。16164.1.5 与时间有关的错误例：图书借阅系统例：图书借阅系统 （x: :某种书册数，设当前某种书册数，设当前x=1.=1.）终端终端1： 终端终端2：Do do 等待借书者；等待借书者； 等待借书者；等待借书者； IF x=1 IF (x=1) x:=x-1; x:=x-1; 借书借书 借书借书 E

13、lse 无书无书 Else 无书无书 while(1); while(1);1234(a) 程序段程序段CR1(b) 程序段程序段CR217174.1.5 与时间有关的错误(Cont.)错误原因之错误原因之1： 进程执行交叉进程执行交叉(interleave);错误原因之错误原因之2： 涉及公共变量涉及公共变量(x)。Remarks: 某些交叉结果不正确某些交叉结果不正确; 必须去掉导致不正确结果的交叉。必须去掉导致不正确结果的交叉。1818与时间有关的错误问题(2)问题描述：设一个飞机航班售票系统有问题描述：设一个飞机航班售票系统有n n个售个售票点，每个售票处通过终端访问系统公共数据票点，

14、每个售票处通过终端访问系统公共数据区，假定公共数据区中的一些单元区，假定公共数据区中的一些单元AjAj（j=1j=1，2 2，）分别存放某年某月某日某次航班的）分别存放某年某月某日某次航班的剩余票数剩余票数。设。设P1P1，P2P2，PnPn表示各个售票点表示各个售票点的处理进程，的处理进程，R1R1，R2R2，RnRn表示各进程执行表示各进程执行时所用的工作单元，当各售票点有旅客买票时，时所用的工作单元，当各售票点有旅客买票时，进程工作如下：进程工作如下：1919与时间有关的错误问题与时间有关的错误问题(2)(2)可能产生的可能产生的错误结果错误结果 可能有若干个旅客在几可能有若干个旅客在几

15、乎相同的时间里到不同的售乎相同的时间里到不同的售票处要求购买票处要求购买同一航班同一航班的机的机票。于是，若干进程需要同票。于是，若干进程需要同时时访问同一个访问同一个AjAj，则结果可，则结果可能出现同一张票卖给几个不能出现同一张票卖给几个不同的旅客同的旅客Process Pi（i=1，2，n） 根据用户需求根据用户需求找到找到Aj; Ri=Aj; if ( Ri = 1) Ri=Ri-1; Aj=Ri; 提示已卖出一张票信息；提示已卖出一张票信息； else 输出输出“票已售完票已售完”； 2020与时间有关的错误问题与时间有关的错误问题(2)(2)某一个时刻三个客户在某一个时刻三个客户在

16、不同网点、几乎同时不同网点、几乎同时购购票的情况票的情况进程进程t1t1t2t2t3t3t4t4t5t5P1P1R1=AjR1=AjR1=R1-1R1=R1-1Aj=R1Aj=R1P2P2R2=AjR2=AjR2=R2-1R2=R2-1Aj=R2Aj=R2P3P3R3=AjR3=AjR3=R3-1R3=R3-12121与时间有关的错误问题分析产生错误的可能原因分析产生错误的可能原因并发进程并发进程共享变量共享变量一个进程运行时由于自身或外界的原因可能一个进程运行时由于自身或外界的原因可能被中断，且被中断，且断点是随机断点是随机的。的。并发进程执行的并发进程执行的相对速度不能控制相对速度不能控制

17、22224.2 进程互斥(mutual exclusion)4.2.1 共享变量与临界区共享变量与临界区4.2.2 临界区域与进程互斥临界区域与进程互斥4.2.3 进程互斥的实现进程互斥的实现4.2.4 多处理机环境下的互斥多处理机环境下的互斥23234.2.1 4.2.1 共享变量与临界区域共享变量（共享变量（shared variable）多个进程都需要访问的变量。多个进程都需要访问的变量。临界区域（临界区域（critical region）访问共享变量的程序段。访问共享变量的程序段。 一组公共变量一组公共变量CR1CR2CRn.2424共享变量与临界区的表示共享变量共享变量: share

18、d 临界区域临界区域: region do value-; if (s-valuequeue)asleep(s-queue):(1) 执行此操作进程的执行此操作进程的PCB入入s.queue尾（状态改为等待）；尾（状态改为等待）；(2) 转处理机调度程序。转处理机调度程序。 Primitive: a piece of code un-interruptible具体请见教材具体请见教材101页页4141V V操作原语V操作原语：操作原语：void V(semaphore*s) s-value+; if (s-valuequeue)wakeup(s-queue)s.queue链头链头PCB出等待队

19、列，进入就绪队列（状态改为出等待队列，进入就绪队列（状态改为就绪）。就绪）。 一段不可间断执行的一段不可间断执行的程序称为原语程序称为原语4242规定和结论对于信号灯变量的规定：对于信号灯变量的规定：必须置一次初值，只能置一次初值，初值必须置一次初值，只能置一次初值，初值=0;=0;只能执行只能执行P P操作和操作和V V操作，所有其它操作非法。操作，所有其它操作非法。几个有用的结论：几个有用的结论：当当s-value=0时，时，s-queue为空；为空；当当s-valuevalue|为队列为队列s-queue的长度；的长度；当当s-value初初=1时，可以实现进程互斥；时，可以实现进程互斥

20、；当当s-value初初=0时，可以实现进程同步。时，可以实现进程同步。4343 semaphore mutex; (初值初值=1） shared x,y,z:integer; CR1 CR2 CRn4444用信号灯实现进程互斥Var mutex: semaphore; (初值初值=1） shared x,y,z:integer;P(mutex) P(mutex) P(mutex) CR1 CR2 CRnV(mutex) V(mutex) V(mutex)4545在利用信号量机制实现进程互斥应注意，在利用信号量机制实现进程互斥应注意，P(mutex)P(mutex)和和V(mutex)V(mu

21、tex)必须成对地出现，缺少必须成对地出现，缺少P(mutex)P(mutex)将会导致系统混乱，不能保证对临界将会导致系统混乱，不能保证对临界资源的互斥访问；而缺少资源的互斥访问；而缺少V(mutex)V(mutex)将会使临界将会使临界资源不被释放，资源不被释放，从而使因等待资源而阻塞的进从而使因等待资源而阻塞的进程不能被唤醒。程不能被唤醒。4646互斥例子：借书系统(revisited)(revisited)Var mutex:semaphore; (initial value is 1)Var mutex:semaphore; (initial value is 1)终端终端1 1：

22、终端终端2 2：CYCLE CYCLECYCLE CYCLE 等待借书者；等待借书者； 等待借书者；等待借书者； IF x=1 Then IF x=1 ThenIF x=1 Then IF x=1 Then Begin Begin Begin Begin x:=x-1; x:=x-1; x:=x-1; x:=x-1; 借书借书 借书借书 End End End End Else Else 无书无书; Else ; Else 无书无书; ; End EndEnd End47互斥例子：借书系统互斥例子：借书系统(revisited)Var mutex:semaphore; (initial val

23、ue is 1)终端终端1： 终端终端2：CYCLE CYCLE 等待借书者；等待借书者； 等待借书者；等待借书者； P(mutex) P(mutex) IF x=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; V(mutex) V(mutex) 借书借书 借书借书 End End Else V(mutex);无书无书; Else V(mutex);无书无书; End End48补充例题：过独木桥。补充例题：过独木桥。进程的互斥进程的互斥P1 P2 由西向东过独木桥；由西向东过独木桥； 由东向西过独木桥；由东向西过独木桥； P1P249分析：分析：

24、进程进程P1、P2因竞争独木桥这个资源而成为互斥关系。因竞争独木桥这个资源而成为互斥关系。设：设：信号量信号量m表示独木桥资源，初值为表示独木桥资源，初值为1表示资源可用。表示资源可用。 int m=1; cobegin p1() / p2() coend进程的互斥进程的互斥50练习：过十字路口（单道）。练习：过十字路口（单道）。进程的互斥进程的互斥P1 P2 P3 P4 通过路口；通过路口； 通过路口；通过路口； 通过路口；通过路口； 通过路口；通过路口； P2P3P4P151分析分析：进程：进程P1、P2、P3、P4因竞争十字路口这个资源而成因竞争十字路口这个资源而成为互斥关系。为互斥关系

25、。设设：信号量：信号量m表示十字路口资源，初值为表示十字路口资源，初值为1表示资源可用。表示资源可用。 int m=1; cobegin p1() / p2() /p3() / p4() coend进程的互斥进程的互斥通过路口；通过路口； 通过路口；通过路口；通过路口；通过路口； 通过路口；通过路口；52补充：补充： 利用信号量实现前趋关系利用信号量实现前趋关系(掌握掌握) 前趋图举例前趋图举例 S4S5S3S1S6S2abgfdce53 Var a,b,c,d,e,f,g; semaphore =0,0,0,0,0,0,0; begin parbegin begin S1; signal(a

26、); 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 545556设设S1,S2,S3,S4为一组合作进程，其前趋图如图所示，用为一组合作进程，其前趋图如图所示，用P、V操作实现其同步。操作实现其同步。 va

27、r a,b,c,d:semaphore:=0,0,0,0; /*表示进程是否执行完表示进程是否执行完*/ main( ) s1s2s3s4abcdS1() . . . v(a); S2() . . . v(c); v(b); S3() p(a); p(b); . . . v(d); S4() p(d); p(c); . . . 5757用信号灯实现进程同步 后动作后动作先动作先动作 P1:P2:5858用信号灯实现进程同步 P(S)后动作后动作先动作先动作 V(S)P1:P2:5959补充：实现进程补充：实现进程同步同步方法方法模型：一类资源模型：一类资源一个公用信号量一个公用信号量s（初值（

28、初值=0.n）请求资源的进程中：请求资源的进程中：P(s);释放资源的进程中：释放资源的进程中：V(s);实例：进程实例：进程A和和B合作。合作。A. . . .取数据；取数据；计算数据；计算数据；. . . .送数据送数据B. . . . . . . . . .6060var s:semaphore:=0;parbeginprocessA:begin wait(s); 取数据；取数据； 计算数据计算数据; endprocessB:begin 送数据；送数据； signal(s); endparend执行时两种可能性：执行时两种可能性：1. 在进程在进程B还没有送数据之前，进程还没有送数据之前

29、，进程A先执行了先执行了wait(s)，结果会怎样？，结果会怎样？2. 进程进程B的的signal(s)操作已经完成，进操作已经完成，进程程A才执行了才执行了wait(s)，结果会怎样？，结果会怎样？.1.进程进程A执行执行wait(s)，会使自己，会使自己进入阻塞状态，直至进程进入阻塞状态，直至进程B送数送数据后执行据后执行signal(s) ，才能将它唤，才能将它唤醒。醒。2. 若进程若进程B的的signal(s)操作已经完操作已经完成，进程成，进程A才执行了才执行了wait(s)，则，则进程进程A不会阻塞。它可以顺利地不会阻塞。它可以顺利地取到数据，完成下面的操作。取到数据，完成下面的操

30、作。6161用信号灯实现进程同步例子例子4-14-1：司机：司机- -售票员问题：售票员问题：司机活动：司机活动： 售票员活动：售票员活动： Do DoDo Do 关车门关车门 启动车辆启动车辆 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 While(1) While(1)While(1) While(1)6262分析：分析：此问题有两个同步点：司机此问题有两个同步点：司机“启动车辆启动车辆”之前与售票员之前与售票员“关车门关车门”之后，用之后，用初值为初值为0 0的信的信号量变量号量变量S1S1实现二者之间的同步；司机实现二者之间的同步；司机“到站到站停车停车”之后与售票员

31、之后与售票员“开车门开车门”之前，用之前，用初值初值为为0 0的信号量变量的信号量变量S2S2实现二者之间的同步。实现二者之间的同步。6363用信号灯实现进程同步例子：司机例子：司机-售票员问题：售票员问题：semaphore : s1,s2 (initial value 0)司机活动：司机活动： 售票员活动：售票员活动： Do Do P(S1) 关车门关车门 启动车辆启动车辆 V(S1) 正常行驶正常行驶 售售 票票 到站停车到站停车 P(S2) V(S2) 开车门开车门 While(1) While(1)6464Classical synchronization problemsProdu

32、cers and consumers problem生产者消费者问题生产者消费者问题2. Readers and writers problem读者写者问题读者写者问题3. Dining philosophers problem 哲学家进餐问题哲学家进餐问题4. Cigarette smokers problem 吸烟者问题吸烟者问题etc. 6565例4-2. 生产者/消费者问题预备知识：预备知识：组合资源组合资源：若干相对独立的资源构成的资源集合，其中：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。每个相对独立的资源称为子资源。同种组合资源同种组合资源：相同类型子资源

33、构成的组合资源。：相同类型子资源构成的组合资源。管理：管理： semaphore: S (初值初值=子资源个数）子资源个数）例子：例子：2台打印机台打印机 semaphore: S S.value=2; 申请：申请：P（S）；）； 释放：释放：V（S）；）；6666例4-2. 生产者/消费者问题 0 1 k-1箱子，容量箱子，容量k B:Array0.k-1Of item生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之6767环形缓冲区10K-1in(in+1)mod kout(out+1)mod k6868利用信号量解决生产者利用信号量解决生产者消费者问题

34、消费者问题 假定在生产者和消费者之间的公用缓冲池中，具有假定在生产者和消费者之间的公用缓冲池中，具有n个个缓冲区，这时可缓冲区，这时可:v 利用互斥信号量利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；实现诸进程对缓冲池的互斥使用；v 利用信号量利用信号量empty和和full分别表示缓冲池中空缓冲区和分别表示缓冲池中空缓冲区和满缓冲区的数量。满缓冲区的数量。对生产者对生产者消费者问题可描述如下：消费者问题可描述如下： 69697070问题分析问题分析生产者活动生产者活动： 消费者活动消费者活动： do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中

35、消耗这件物品消耗这件物品 while(1) while(1)资源：箱子（同种组合）资源：箱子（同种组合） 资源：物品（同种组合）资源：物品（同种组合） semaphore:S1 semaphore:S2 S1.value=k; S2.value=0;放前：放前：P（S1） 取前：取前：P（S2）放后：放后：V（S2） 取后：取后：V（S1）7171同步生产者活动生产者活动： 消费者活动消费者活动： Do Do 加工一件物品加工一件物品 P(S2) P(S1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(S1) V(S2) 消耗这件物品消耗这件物品 While(1) While(1)

36、对对B和和in,out的互斥的互斥：semaphore:mutex (mutex.value=1)7272互斥生产者活动：生产者活动： 消费者活动：消费者活动： Do Do 加工一件物品加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品消耗这件物品 While(1) While(1)7373程序程序( (具体请见教材具体请见教材105105页页) )Program producers_consumers;Var B:Array0,k-1Of ite

37、m; 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;7474程序Begin S1.value:=k; S2.value:=0; mutex.value

38、:=1; in:=0; out:=0; Cobegin P1: producer; , Pm: producer; C1: consumer; , Cn: consumer; Coend;End.7575 在生产者在生产者消费者问题中应注意：消费者问题中应注意：首先，在每个程首先，在每个程序中用于实现互斥的序中用于实现互斥的P(mutex)和和V(mutex)必须成对地出必须成对地出现；现； 其次，对资源信号量其次，对资源信号量empty和和full的的P和和V操作，同样操作，同样需要成对地出现，但它们分别处于不同的程序中。需要成对地出现，但它们分别处于不同的程序中。例如，例如，P(empty

39、)在计算进程中，而在计算进程中，而V(empty)则在打印进程中，则在打印进程中，计算进程若因执行计算进程若因执行P(empty)而阻塞，而阻塞， 则以后将由打印进则以后将由打印进程将它唤醒；最后，在每个程序中的多个程将它唤醒；最后，在每个程序中的多个wait操作顺序操作顺序不能颠倒。不能颠倒。应先执行对资源信号量的应先执行对资源信号量的wait操作，然后再操作，然后再执行对互斥信号量的执行对互斥信号量的wait操作，否则可能引起进程死锁。操作，否则可能引起进程死锁。76767777并发性提高策略生产者和消费者：不操作生产者和消费者：不操作B的相同分量的相同分量生产者的共享变量生产者的共享变量

40、： Bin, in消费者的共享变量消费者的共享变量： Bout, outin=out: 满或空满或空,Var mutex1,mutex2:semaphore; (init 1)请见教材请见教材105页分析页分析7878并发性提高策略生产者活动：生产者活动： 消费者活动：消费者活动： Repeat Repeat 加工一件物品加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗这件物品消耗这件物品 Until false Until false7979“

41、哲学家进餐哲学家进餐”问题问题5 5个哲学家围坐在圆个哲学家围坐在圆桌旁，每人面前有一只空桌旁，每人面前有一只空盘子，每盘子，每2 2人之间放一只人之间放一只筷子，如图所示。筷子，如图所示。为了就餐，每个哲学为了就餐，每个哲学家必须拿到两只筷子，并家必须拿到两只筷子，并且只能直接从自己的左边且只能直接从自己的左边或右边去取筷子。或右边去取筷子。12345123458080 semaphore chopstick5=1,1,1,1,1; /5支筷子支筷子main( )cobegin philosopher(0); philosopher(1); philosopher(2); philosoph

42、er(3); philosopher(4); coend问题求解8181哲学家哲学家i的活动为的活动为: philosopher(i)while (true) 思考思考; P(chopsticki) ; /取左边筷子取左边筷子 P(chopstick(i+1) % 5); /取右边筷子取右边筷子 进食进食; V(chopsticki); /放左边筷子放左边筷子 V(chopstick(i+1) % 5); /放右边筷子放右边筷子12345123408282如果：如果：5 5人同时拿起左边筷子，再企图人同时拿起左边筷子，再企图拿起右边的筷子时，会如何？拿起右边的筷子时，会如何？死锁！死锁！ 83

43、83如何防止死锁？如何防止死锁？n仅当一个哲学家左右两边的筷子都可用时，仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子才允许他拿筷子n给所有哲学家编号，奇数号的哲学家必须首给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之先拿左边的筷子，偶数号的哲学家则反之n 限制桌边的哲学家的数量最多为限制桌边的哲学家的数量最多为4 48484哲学家就餐问题解法#define THINKING 0#define HUNGRY 1#define EATING 2semaphore stick5;筷子状态：筷子状态：初始为初始为18585限制桌边的哲学家数量最多为限制桌边的哲学家数

44、量最多为4 4 semaphore room=4; void philosopher(int i) while(true) statei=THINKING; P(room); /请求进入房间进餐请求进入房间进餐 P(sticki); /请求左手边的筷子请求左手边的筷子 P(stick(i+1)%5); /请求右手边的筷子请求右手边的筷子 就餐就餐; V(stick(i+1)%5); /释放右手筷子释放右手筷子 V(sticki); /释放左手筷子释放左手筷子 V(room); /退出房间退出房间8686左右两支筷子都可用时才能进餐左右两支筷子都可用时才能进餐 semaphore mutex=1

45、; void philosopher(int i) while(true) statei=THINKING; P(mutex); /请求进餐请求进餐 P(sticki); /请求左手边的筷子请求左手边的筷子 P(stick(i+1)%5); /请求右手边的筷子请求右手边的筷子 V(mutex); 就餐就餐; V(stick(i+1)%5); /释放右手筷子释放右手筷子 V(sticki); /释放左手筷子释放左手筷子8787奇数号哲学家先拿左边的筷子，偶数号相反奇数号哲学家先拿左边的筷子，偶数号相反void philosopher(int i) while(true) statei=THINK

46、ING; /请求左手筷子请求左手筷子 P(sticki); /请求右手筷子请求右手筷子 P(stick(i+1)%5); 就餐就餐; /释放右手筷子释放右手筷子 V(stick(i+1)%5); /释放左手筷子释放左手筷子 V(sticki);void philosopher(int i) while(true) statei=THINKING; /请求右手筷子请求右手筷子 P(stick(i+1)%5); /请求左手筷子请求左手筷子 P(sticki); 就餐就餐; /释放左手筷子释放左手筷子 V(sticki); /释放右手筷子释放右手筷子 V(stick(i+1)%5); 奇数号奇数号偶

47、数号偶数号8888例4-3. 读者/写者问题设有一组共享数据和两组并发进程，一组进程只对此数设有一组共享数据和两组并发进程，一组进程只对此数据执行读操作，另一组进程可对此组数据执行写操作据执行读操作，另一组进程可对此组数据执行写操作(当当然同时也可以执行读操作然同时也可以执行读操作),将前一组进程称为读者，后将前一组进程称为读者，后一组称为写者。一组称为写者。为了保证共享数据的完整性，要求：多为了保证共享数据的完整性，要求：多个读者的操作可以同时进程，多个写者的操作不能同时个读者的操作可以同时进程，多个写者的操作不能同时进行，读者与写者的任何操作都不能同时进行。进行，读者与写者的任何操作都不能

48、同时进行。具体请见教材具体请见教材106页分析页分析898990909191读者读者-写者问题写者问题 利用信号量解决读者利用信号量解决读者-写者问题写者问题v设置了一个互斥信号量设置了一个互斥信号量r_w_w。用来保证读者与写者之间。用来保证读者与写者之间的互斥，以及写者与写者之间的互斥的互斥，以及写者与写者之间的互斥v设置一个整型变量设置一个整型变量readCount表示正在读的进程数目。表示正在读的进程数目。 由于只要有一个由于只要有一个reader进程在读，便不允许进程在读，便不允许writer进程进程去写。因此，仅当去写。因此，仅当readCount加加1等于等于1时时, 表示尚无表

49、示尚无reader进进程在读时，程在读时，reader进程才需要执行进程才需要执行P(r_w_w)操作。操作。9292若若P(r_w_w)操作成功，操作成功，reader进程便可去读，进程便可去读，同理，仅当同理，仅当reader进程在执行了进程在执行了readCount减减1操作后其值为操作后其值为0时，才须执行时，才须执行V(r_w_w)操作，操作，以便让以便让writer进程写。进程写。因为因为readCount是一个可被多个是一个可被多个reader进程访进程访问的临界资源，因此，应该为它设置一个互斥问的临界资源，因此，应该为它设置一个互斥信号量信号量mutex。 具体算法请见教材具体

50、算法请见教材106页页9393int readCount=0;semaphore r_w_w=1;semaphore mutex=1;reader( ) while (1) P(&mutex);readCount=readCount+1;if(readCount=1) P(&r_w_w);V(&mutex);P(&mutex);readCount=readCount-1;if(readCount=0) V(&mutex);writer( )while(1)P(&r_w_w);V(&r_w_w);9494例例4-4 34-4 3台打印机的管

51、理。台打印机的管理。Var lp:array1.3of (free,used); (initial value is free) S: semaphore; (initial value is 3) mutex: semaphore; (initial value is 1)function require:1.3; procedure return(i:1.3); P(S); P(mutex); P(mutex); lpi:=free; for i:=1 to 3 do V(mutex); if lpi=free then V(S); break; lpi:=used; V(mutex);

52、return(i);9595上述的进程互斥问题上述的进程互斥问题, ,是针对各进程之是针对各进程之间要共享一个临界资源而言的。在有些间要共享一个临界资源而言的。在有些应用场合，是一个进程需要先获得两个应用场合，是一个进程需要先获得两个或更多的共享资源后或更多的共享资源后, ,方能执行其任务。方能执行其任务。假定现有两个进程假定现有两个进程A A和和B,B,他们都要求访他们都要求访问共享数据问共享数据D D和和E E，此时共享数据都应作，此时共享数据都应作为临界资源。为此，可为这两个数据分为临界资源。为此，可为这两个数据分别设置用于互斥的信号量别设置用于互斥的信号量DmutexDmutex和和E

53、mutexEmutex，并令他们的初值都是，并令他们的初值都是1 1。信号量集、信号量集、AND型信号量型信号量 9696AND型信号量型信号量 例例:在两个进程中都要包含两个对在两个进程中都要包含两个对Dmutex和和Emutex的操作，的操作，它们的初值均为它们的初值均为1。process A: process B:P(Dmutex); P(Emutex);P(Emutex); P(Dmutex);若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：process A: wait(Dmutex); 于是于是Dmutex=0process B: wait(Emutex

54、); 于是于是Emutex=0process A: wait(Emutex); 于是于是Emutex=-1 A阻塞阻塞process B: wait(Dmutex); 于是于是Dmutex=-1 B阻塞阻塞 9797 AND同步机制的基本思想是：同步机制的基本思想是：将进程在整个运行过程将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对其它所有可能为之分配的资源，也不分配给他。

55、亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。配到进程，要么一个也不分配。 由死锁理论可知，这样就由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在可避免上述死锁情况的发生。为此，在P操作中，增加了操作中，增加了一个一个“AND”条件，故称为条件，故称为AND同步，或称为同时同步，或称为同时P操作。操作。9898例4-5. 吸烟者问题具体描述请见教材具体描述请见教材107-108页页3 supplier processes: X: supplies tobacco(烟草烟草) and match(火

56、柴火柴); Y: supplies match(火柴火柴) and wrapper(纸纸); Z: supplies wrapper(纸纸) and tobacco(烟草烟草).3 smoker processes: A: possess tobacco(烟草烟草); B: possess match(火柴火柴); C: possess wrapper(纸纸).only one of X,Y,Z can supply at a time;(同一时刻只有同一时刻只有x,y,z之一可以供应资源；之一可以供应资源；)(2) X,Y,Z can proceed only after consumpti

57、on.(所提供的资源被耗尽之后，所提供的资源被耗尽之后，x,y,z之一可以继续。之一可以继续。)9999Traditional semaphore:Traditional semaphore:Var t,m,w,s:semaphore; (0,0,0,1)Process X process Y process Z P(s); P(s); P(s); V(t); V(m); V(w); V(m); V(w); V(t);Process A Process B process C P(m); P(w); P(t); P(w); P(t); P(m); smoke; smoke; smoke; V(

58、s); V(s); V(s);100100问题：进程问题：进程x提供的提供的tobacco和和match分别被进程分别被进程A和进程和进程C获得，将导致死锁。任意改变吸烟者进获得，将导致死锁。任意改变吸烟者进程的两个程的两个p操作的次序，不能防止死锁的发生。原操作的次序，不能防止死锁的发生。原因：吸烟者进程所需要的另外两种资源是通过两因：吸烟者进程所需要的另外两种资源是通过两个个p操作分别申请的，如果两种资源同时申请操作分别申请的，如果两种资源同时申请(同同时执行时执行P操作操作),则可防止这一问题。则可防止这一问题。101101为此再进行扩展为此再进行扩展P操作，使其能对多个信号量变操作，使

59、其能对多个信号量变量同时执行量同时执行P操作和操作和V操作，这就是操作，这就是SP(Simultaneous P,同时执行同时执行P操作操作)和和SV (Simultaneous V,同时执行同时执行V操作操作)，它们作，它们作用在信号量集合上。用在信号量集合上。具体请见教材具体请见教材108页页练习练习1021024.3.4 4.3.4 条件临界区条件临界区Conditional Critical RegionConditional Critical Region背景背景PVPV操作低级，容易用错操作低级，容易用错条件临界区形式条件临界区形式regionregion r r whenwhen

60、 B B dodo S S其中其中r r为一组相关的共享变量，为一组相关的共享变量，b b为条件表达式为条件表达式,s,s为为语句。进程能够进入条件临界区执行语句。进程能够进入条件临界区执行s s语句的条件语句的条件是：没有其它进程处于与是：没有其它进程处于与r r相关的条件临界区中，相关的条件临界区中，进入条件临界区时进入条件临界区时b b为真。为真。103103条件临界区实现互斥实现互斥region region r r when true do when true do s sCCRCCR与与PVPV操作的等价性操作的等价性( (证明从略）证明从略）用用CCRCCR可以实现可以实现PVPV操作操作用用PVPV操作可以实现操作可以实现CCR