操作系统教程(第3版)解析

1、操作系统教程(第3版) 第三章 并发进程,面向21世纪课程教材 高等教育出版社 2003年8月,第三章 并发进程,3.1 并发进程 3.2 临界区管理 3.3 信号量与PV操作 3.4 管程 3.5 进程通信 3.6 死锁,3.1并发进程,3.1.1顺序程序设计 3.1.2进程的并发性 3.1.3与时间有关的错误 3.1.4进程的交互（Interaction Among Processes）：协作和竞争,进程的顺序性,一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作 顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，

2、也指两个程序模块之间。,顺序程序设计特点,程序执行的顺序性 程序环境的封闭性 程序执行结果的确定性 计算过程的可再现性,顺序程序设计例子,while(1) input，process，output ,进程的并发性(1),进程执行的并发性：一组进程的执行在时间上是重叠的 并发性举例：例如：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行 从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态， 从微观上看，任一时刻仅有一个进程在处理器上运行。,进程的并发性(2),并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享

3、，消除计算机部件之间的互等现象，以提高系统资源利用率。,无关的并发进程,并发进程分类：无关的，交往的。 无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。 并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。,Bernstein条件,R(pi)=a1,a2,an，程序pi在执行期间引用的变量集 W(pi)=b1,b2,bm，程序pi在执行期间改变的变量集 若两个程序的变量集交集之和为空集： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= 则并发进程的执行与时间无关。,Bernstein条件举例,例如，

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。 S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。,交往的并发进程(1),交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。,并发程序设计的例子,while(1) input，send while(1) receive，process，s

5、end while(1) receive，output ,处理器利用率：（52 * n） /（78*n+52+20）= 67%,并发程序设计特征,并发程序设计是：把一个程序设计成若干个可同时执行的程序模块的方法。 并发程序设计的特征： 并发性、 共享性、 制约性、 交互性。,并发程序设计的优点,对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。 对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。 简化了程序设计任务。,采用并发程序设计的目的,充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和

6、发挥，这种软件技术就是并发程序设计。 并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。,与时间有关的错误,对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。 与时间有关错误的表现形式： 结果不唯一 永远等待,（结果不唯一）机票问题,process Ti ( i = 1, 2 ) var Xi:integer; begin 按旅客定票要求找到Aj； Xi := Aj; if Xi=1 then begin Xi:=Xi-1; Aj:=Xi;输出一张票；end else 输出票已售完； end;,（永远等待）内存管理问题,proce

7、dure borrow (var B:integer) begin if Bx then 申请进程进入等待队列等主存资源 x:=x-B; 修改主存分配表，申请进程获得主存资源 end; procedure return (var B:integer) begin x:=x+B; 修改主存分配表 释放等主存资源的进程 end;,进程的交往：竞争与协作(1) 第一种是竞争关系,系统中的多个进程之间彼此无关 系统中的多个进程之间彼此相关 资源竞争的两个控制问题： 一个是死锁(Deadlock)问题， 一个是饥饿(Starvation) 问题，既要解决饥饿问题，又要解决死锁问题。,进程的交往：竞争与协

8、作(2) 进程互斥(Mutual Exclusion),解决进程间竞争关系(间接制约关系)的手段。 进程互斥指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直到占有资源的进程释放该资源。,进程的交往：竞争与协作(3)第二种是协作关系(1),某些进程为完成同一任务需要分工协作。 进程的同步是解决进程间协作关系(直接制约关系)的手段。,进程的交往：竞争与协作(4)第二种是协作关系(2), 进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。,进

9、程的交往：竞争与协作(5)第二种是协作关系(3),进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。,3.2 临界区管理,3.2.1 互斥与临界区 3.2.2 实现临界区管理的几种尝试 3.2.3 实现临界区管理的软件方法 3.2.4 实现临界区管理的硬件设施,3.2.1互斥与临界区(1),并发进程中与共享变量有关的程序段叫“临界区”(Critical Section) ， 共享变量代表的资源叫“临界资源”(Critical Resource)。 与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。 如果保证进程在临界区执行时

10、，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。,互斥与临界区(2),临界区的调度原则： 一次至多允许一个进程进入临界区内 一个进程不能无限地停留在临界区内 一个进程不能无限地等待进入临界区 即-有空让进、无空等待、 择一而入、算法可行。,临界区管理的尝试 (1),inside1,inside2:Boolean inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 Begin while inside2 do begin end; i

11、nside1 := true; 临界区; inside1 := false; end; process P2 begin while inside1 do begin end; inside2 = true; 临界区; inside2 := false; end; coend,临界区管理的尝试 (2),inside1,inside2:boolean; inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 begin inside1 := true; while inside2

12、 do begin end; 临界区; inside1 := false; end; process P2 begin inside2 := true; while inside1 do begin end; 临界区; inside2 := false; end; coend,Dekker算法(1),Dekker算法用一个指示器turn来指示应该哪一个进程进入临界区。 var inside : array1.2 of boolean; turn :integer; turn := 1 or 2; inside1:=false; inside2:=false;,cobegin process P

13、1 begin inside1:=true; while inside2 do if turn=2 then begin inside1:=false; while turn=2 do begin end; inside1:=true; end 临界区; turn = 2； inside1:=false; end;,Dekker算法(2),Dekker算法(3),process P2 begin inside2:=true; while inside1 do if turn=1 then begin inside2:=false; while turn=1 do begin end; insi

14、de2:=true; end 临界区; turn = 1； inside2:=false; end; coend,Peterson算法(1),var inside:array1.2 of boolean; turn:integer; turn := 1 or 2; inside1 := false;/* P1不在其临界区内 */ inside2 := false;/* P2不在其临界区内 */,Peterson算法(2),cobegin process P1 begin inside1:= true; turn := 2; while (inside2 and turn=2) do begin

15、 end; 临界区; inside1 := false; end;,Peterson算法(3),process P2 begin inside2 := true; turn := 1; while (inside1 and turn=1) do begin end; 临界区; inside2 := false; end; coend,实现临界区管理的硬件设施,关中断 测试并建立指令 对换指令,关中断,实现互斥的最简单方法 关中断方法的缺点,测试并建立指令(1),TS指令的处理过程 TS(x): 若x=true，则x:=false； return true；否则 return false； TS

16、指令管理临界区时，可把一个临区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。,测试并建立指令(2),s : boolean; s := true; process Pi /* i = 1,2,n */ pi : boolean; begin repeat pi := TS(s) until pi； 临界区; s := true； end;,对换指令(1),对换（Swap）指令的功能是交换两个字的内容： Swap (a,b): temp:=a; a:=b; b:=temp;,对换指令(2),lock : boolean; lock := false; process P

17、i /* i = 1,2,n */ pi : boolean; begin pi := true; repeat swap(lock, pi) until pi = false； 临界区; lock := false； end;,3.3 信号量与PV操作,3.3.1同步与同步机制 3.3.2记录型信号量与PV操作 3.3.3用记录型信号量实现互斥 3.3.4记录型信号量解决生产者-消费者问题 3.3.5记录型信号量解决读者-写者问题 3.3.6记录型信号量解决理发师问题,3.3.1 同步和同步机制,著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。 在

18、操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。 解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,生产者-消费者问题表述,有界缓冲问题 有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,生产者-消费者问题算法描述(1),var k:integer; nextp,nextc: item; buffer:array0.k-1 of item; in,out:integer:=0; coum

19、ter:integer:=0;,生产者-消费者问题算法描述(2),process producer begin while (TRUE) /* 无限循环*/ produce an item in nextp;/* 生产一个产品*/ if (counter=k) sleep( );/* 缓冲满时，生产者睡眠*/ bufferin:=nextp; /* 将一个产品放入缓冲区*/ in:=(in+1) mod k; /* 指针推进*/ counter:=counter+1; /* 缓冲内产品数加1*/ if (counter=1) wakeup( consumer); /* 缓冲空了，加进一件产品并

20、唤醒消费者*/ end,生产者-消费者问题算法描述(3),process consumer begin while (TRUE) /* 无限循环*/ if (counter=0) sleep ( ); /* 缓冲区空消费者睡眠*/ nextc:=bufferout; /*取一个产品到nextc*/ out:=(out+1) mod k; /* 指针推进*/ counter:=counter-1; /* 取走一个产品，计数减1*/ if (counter=k-1) wakeup( producer); /* 缓冲满了，取走一件产品并唤醒生产者*/ consume thr item in next

21、c;/* 消耗产品*/ end,生产者-消费者问题的算法描述(4),生产者和消费者进程对counter的交替执行会使其结果不唯一 生产者和消费者进程的交替执行会导致进程永远等待,记录型信号量与PV操作(1),前节种种方法解决临界区调度问题的缺点: 1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。 2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。 1965年E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。,记录型信号量与PV操作(2),信号量：一种软件资源 原语：内核中执行时不可被中断的过程 P操作原语和V操作原语 一个进程

22、在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,记录型信号量与PV操作(3),操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。 实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,信号量分类,信号量按其用途分为 公用信号量： 私有信号量： 信号量按其取值分为 二元信号量： 一般信号量：,整型信号量,设s为一个整形量，除初始化外，仅能通过P、V操作访问，P和V操作原语定义： P(s)：while s0 do null op

23、eration s：=s-1； V(s)： s：=s+1；,记录型信号量(1),设s为一个记录型数据结构,一个分量为整形量value,另一个为信号量队列queue, P和V操作原语定义： P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。 V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,记录型信号量(2),type semaphore = record value:integer; queue: list of process; End procedure P(var s:semaphore); begin s := s 1; /

24、* 把信号量减去1 */ if s =1 then begin Xi:=Xi-1; Aj:=Xi; V(sj); 输出一张票； end; else begin V(sj);输出票已售完； end; goto L1; end; coend;,哲学家吃通心面问题(1),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子,哲学家吃通心面问题(2),3,0,1,2,4,4,1,3,0,2,哲学家吃通心面问题(3),var forki :array0.

25、4 of semaphore; forki := 1; cobegin process Pi / i=0,1,2,3,4, begin L1: 思考； P(forki)； P(fork(i+1)mod 5)； 吃通心面； V(forki)； V(fork(i+1)mod 5)； goto L1; end; coend;,有若干种办法可避免这类死锁,上述解法可能出现永远等待，有若 干种办法可避免死锁： 至多允许四个哲学家同时吃； 奇数号先取左手边的叉子，偶数号先取右手边的叉子； 每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,哲学家吃通心面问题的一种正确解,var forki :arra

26、y0.4 of semaphore; forki := 1; cobegin process Pi /* i=0,1,2,3 */ begin L1: 思考； P(forki)； /*i=4,P(fork0)*/ P(forki+1 mod5) /*i=4,P(fork4)*/ 吃通心面； V(forki)； V(fork(i+ 1 mod 5)； goto L1; end; coend;,生产者消费者问题,一个生产者、一个消费者共享一个缓冲区 一个生产者、一个消费者共享多个缓冲区 多个生产者、多个消费者共享多个缓冲区 多个生产者、多个消费者共享一个缓冲区 多个生产者、一个消费者共享多个缓冲区

27、 一个生产者、多个消费者共享多个缓冲区,一个生产者、一个消费者共享一个缓冲区的解,var B : integer; empty:semaphore; /* 可以使用的空缓冲区数 */ full:semaphore; /* 缓冲区内可以使用的产品数 */ empty := 1; /* 缓冲区内允许放入一件产品 */ full := 0; /* 缓冲区内没有产品 */ cobegin Process producer process consumer begin begin L1: L2: Produce a product; P(full); P(empty); Product:= B; B :

28、= product; V(empty); V(full); Consume a product; Goto L1; Goto L2; end; end; coend,多个生产者、多个消费者、共享多个缓冲区的解,var B : array0.k-1 of item; empty:semaphore:=k; /* 可以使用的空缓冲区数 */ full:semaphore:=0; /* 缓冲区内可以使用的产品数 */ mutex:semaphore:=1; in , out:integer:= 0; /* 放入/取出缓冲区指针*/ cobegin process producer_i process

29、 consumer_j Begin begin L1:produce a product; L2:P(full); P(empty); P(mutex); P(mutex); Product:= Bout; Bin := product; out:=(out+1) mod k; in:=(in+1) mod k; V(mutex); V(mutex); V(empty); V(full); Consume a product; Goto L1; Goto L2; end; end; coend,苹果桔子问题,桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子

30、中放桔于(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果,记录型信号量解决苹果桔子问题,读者写者问题,有两组并发进程：读者和写者，共享一个文件F，要求： 允许多个读者同时执行读操作 任一写者在完成写操作之前不允许其它读者或写者工作 写者执行写操作前，应让已有的写者和读者全部退出,记录型信号量解决读者 写者问题(1),var rc : integer:=0; W，R: semaphore; Rc := 0; /* 读进程计数 */ W := 1; R := 1;,记录型信号量解决读者 写者问题(2),procedure read; procedure write; beg

31、in begin P(R); P(W); rc := rc + 1; 写文件; if rc=1 then P(W)； V(W); V(R); end; 读文件； P(R); rc := rc - 1; if rc = 0 then V(W)； V(R); end;,理发师问题,理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子 如果没有顾客，理发师便在理发椅上睡觉 一个顾客到来时，它必须叫醒理发师 如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开,记录型信号量解决理发师问题,3.4 管程,3.4.1 管程和条件变量 3.4.2 霍尔方法实现管程 3.4

32、.3 汉森方法实现管程,3.4.1 什么是管程 为什么要引入管程,把分散在各进程中的临界区集中起来进行管理 ； 防止进程有意或无意的违法同步操作， 便于用高级语言来书写程序，也便于程序正确性验证。,管程定义和属性,管程的定义 管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块 管程的属性 共享性： 安全性： 互斥性：,管程的基本形式,TYPE = MONITOR ; define ; use ； procedure (); begin ； end; procedure (); begin ； end; begin ； end;,管程的结构,管程的示例,TYPE

33、 SSU = MONITOR var busy : boolean; nobusy : condition; define require, return; use wait, signal； procedure require; begin if busy then wait(nobusy); /*调用进程加入等待队列*/ busy := ture； end; procedure return; begin busy := false； signal(nobusy); /*从等待队列中释放进程*/ end; begin /*管程变量初始化*/ busy := false； end;,管程的条

34、件变量(1),条件变量：当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量 同步原语wait：当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作引起调用进程阻塞 另一个进程可以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。 条件变量与P、V操作中信号量的区别?,管程的问题讨论,使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法： 执行signal的进程等待，直到被释放进程退出管程或等待另一个条件 被释放进程等待，直到执行signal的进程退出管程或等待另一个条件 霍尔采用了第

35、一种办法 汉森选择了两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作,管程与进程作比较(1),管程定义的是公用数据结构，而进程定义的是私有数据结构； 管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中； 管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的； 管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性； 管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。,3.4.2管程实现：Hoare方法,霍尔方法使用P和V操作原语来实现对管

36、程中过程的互斥调用，及实现对共享资源互斥使用的管理。 不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。,Hoare管程数据结构(1),1. mutex 对每个管程，使用用于管程中过程互斥调用的信号量mutex（初值为1）。 进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时应执行V(mutex)开放管程，以便让其他调用者进入。 为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。,Hoare管程数据结构(2),2. next和next-cou

37、nt 对每个管程，引入信号量next（初值为0），凡发出signal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。 进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count（初值为0），用来记录在next上等待的进程个数。,Hoare管程数据结构(3),3. x-sem和 x-count 引入信号量x-sem（初值为0），申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count（初值为0）记录等待资源的进程数。 执行signal操作

38、时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现。,Hoare管程数据结构,每个管程定义如下数据结构 ： TYPE interf = RECORD mutex:semaphore; /*进程调用管程过程前 使用的互斥信号量*/ next:semaphore; /*发出signal的进程挂起 自己的信号量*/ next_count:integer;/*在next上等待的进 程数*/ END;,Hoare管程的wait操作,Procedure wait(var x_sem:semaphore,x_count:integer, IM:int

39、erf); begin x_count := x_count + 1; if IM.next_count 0 then V(IM.next); else V(IM.mutex); P(x_sem); X_count := x_count 1; end;,Hoare管程的signal操作,procedure signal(var x_sem:semaphore,x_count:integer, IM:interf); begin if x_count 0 then begin IM.next_count := IM.next_count + 1; V(x_sem); P(IM.next); IM

40、.next_count := IM.next_count - 1; end; end;,Hoare管程的外部过程形式,任何一个调用管程中过程的外部过程应组织成下列形式，确保互斥地进入管程。 P(IM.mutex); ; if IM.next_count 0 then V(IM.next); else V(IM.mutex);,霍尔管程实现五个哲学家吃通心面问题(1),TYPE dining-philosophers = MONITOR var state : array0.4 of (thinking, hungry, eating); s : array0.4 of semaphore; s

41、-count : array0.4 of integer; define pickup, putdown; use wait, signal；,霍尔管程实现五个哲学家吃通心面问题(2),procedure test(k : 0.4); begin if state(k-1) mod 5eating and statek=hungry and state(k+1) mod 5eating then begin statek := eating; signal(sk, s-countk, IM); end; end;,霍尔管程实现五个哲学家吃通心面问题(3),procedure pickup(i:

42、0.4); begin statei := hungry; test(i); if stateieating then wait(si,s-counti,IM)； end;,霍尔管程实现五个哲学家吃通心面问题(4),procedure putdown(i:0.4); begin statei := thinking; test(i-1) mod 5); test(i+1) mod 5); end; begin for i := 0 to 4 do statei := thinking； end;,霍尔管程实现五个哲学家吃通心面问题(5),cobegin process philosopher-

43、i begin P(IM.mutex); call dining-philosopher.pickup(i); if IM.next-count 0 then V(IM.next); else V(IM.mutex); 吃通心面； P(IM.mutex); call dining-philosopher.putdown(i); if IM.next-count 0 then V(IM.next); else V(IM.mutex); end; coend;,管程实现：汉森方法(1),汉森方法的管程中的过程所执行的signal操作一定是过程体的最后一个操作，一个进程当所调用的过程执行了signa

44、l操作后，便立即退出了管程。 汉森方法使用四条原语：wait，signal，check，re1ease实现对管程的控制。,管程的实现：汉森方法(2),每个管程使用的一个数据类型： TYPE interf = RECORD intsem : condition; /* 开放管程的信号量 */ count1 : integer; /* 等待调用的进程个数 */ count2 : integer; /* 调用了管程中的过程且不 END; 处于等待状态的进程个数 */,管程的实现：汉森方法(3),调用查看原语check： 如果管程是开放的，则执行这条原语后关闭管程，相应进程继续执行；如果管程是关闭的，

45、则执行这条原语后相应进程被置成等待调用状态,管程的实现：汉森方法(4),procedure check(var IM interf); begin if IM.count2 = 0 then IM.count2 := IM.count2 + 1; else begin IM.count1 := IM.count1 + 1; W(IM.intsem); end; end;,管程的实现：汉森方法(5),开放原语release： 如果除了发出这条原语的进程外，不再有调用了管程中过程但又不处于等待状态的进程，那么就释放一个等待者或开放管程,管程的实现：汉森方法(6),procedure release

46、(var IM interf); begin IM.count2 := IM.count2 - 1; if IM.count2 = 0 and IM.count1 0 then begin IM.count1 := IM.count1 - 1; IM.count2 := IM.count2 + 1; R(IM.intsem); end; end;,管程的实现：汉森方法(7),等待原语wait： 执行这条原语后相应进程被置成等待状态，同时开放管程，允许其它进程调用管程中的过程,管程的实现：汉森方法(8),procedure wait(var s:condition; var IM interf)

47、; begin s := s + 1; IM.count2 := IM.count2 1; if IM.count1 0 then begin IM.count1 := IM.count1 1; IM.count2 := IM.count2 + 1; R(IM.intsem); end; W(s); end;,管程的实现：汉森方法(9),释放原语signal： 执行这条原语后释放指定等待进程队列中的一个进程。如指定等待进程队列为空，本操作相当于空操作,管程的实现：汉森方法(10),procedure signal(var s:condition; var IM interf); begin i

48、f s 0 then begin s := s 1; IM.count2 := IM.count2 + 1; R(s); end; end;,管程的实现：汉森方法(11),用管程实现进程同步时，进程应按下列次序工作： 请求资源。 使用资源。 释放资源。,汉森管程实现读者写者问题(1),有两组并发进程：读者与写者，共享一个文件，要求：1）允许多个读者同时执行读操作；2）任一写者在完成写操作之前不允许其他读者和写者工作；3）写者欲工作，要等待已存在的读者完成读操作，新的读者与写者均被拒绝,汉森管程实现读者写者问题(2),type read_writer = MONITOR var rc, wc :

49、 integer; R, W : condition; define start_read, end_read, start_write, end_write; use wait, signal, check, release;,汉森管程实现读者写者问题(3),procedure start-read; begin check(IM); if wc0 then wait(R,IM); rc := rc + 1; signal(R, IM); release(IM); end; procedure end-read; begin check(IM); rc := rc - 1; if rc=0

50、then signal(W,IM); release(IM); end;,汉森管程实现读者写者问题(4),procedure start_write; begin check(IM); wc := wc + 1; if rc0 or wc1 then wait(W,IM); release(IM); end; procedure end_write; begin check(IM); wc := wc - 1; if wc0 then signal(W,IM); else signal(R, IM); release(IM); end;,汉森管程实现读者写者问题(5),初始化语句 begin

51、rc := 0; wc := 0; R := 0; W := 0; end;,汉森管程实现读者写者问题(6),cobegin process reader begin call read-writer.start-read; read; call read-writer.end-read; end; process writer begin call read-writer.start-write; write; call rear-writer.end-write; end; coend;,汉森管程实现苹果橘子问题(1),桌上有一只盘子，每次只能放入一只水果，爸爸专向盘中放苹果，妈妈专向盘中

52、放橘子，一个儿子专吃盘中橘子，一个女儿专吃盘中苹果,汉森管程实现苹果橘子问题(2),TYPE FMSD = MONITOR var plate : (apple, orange); full : boolean; SP, SS, SD : condition; define put, get; use wait, signal, check, release;,汉森管程实现苹果橘子问题(3),procedure put(var fruit:(apple, orange); begin check(IM); if full then wait(SP,IM); full := true; plat

53、e := fruit; if fruit=orange then signal(SS,IM); else signal(SD,IM); release(IM); end;,汉森管程实现苹果橘子问题(4),procedure get(varfruit:(apple,orange),x:plate); begin check(IM); if not full or platefruit then begin if fruit = orange then wait(SS,IM); else wait(SD,IM); end; x := plate; full := false; signal(SP,

54、 IM); release(IM); end;,汉森管程实现苹果橘子问题(5),初始化语句 begin full := false; SP := 0; SS := 0; SD := 0; end;,汉森管程实现苹果橘子问题(6),cobegin process father begin 准备好苹果; call FMSD.put(apple); end; process mother begin 准备好桔子; call FMSD.put(orange); end;,汉森管程实现苹果橘子问题(7),process son begin call FMSD.get(orange,x); 吃取到的桔子;

55、 end; process daughter begin call FMSD.get(apple,x); 吃取到的苹果; end; coend;,汉森管程实现生产者和消费者问题(1),type producer-consumer = MONITOR var B:array0.k-1 of item; /*缓冲区个数 in,out:integer; /*存取指针 count:integer; /*缓冲中产品数*/ notfull,notempty:condition;/*条件变量*/ define append,take; use wait, signal, check, release;,汉森管程实现生产者和消费者问题(2),procedure append(x:item); begin check(IM); if count=k then wait(notfull,IM);/*缓冲已满*/ Bin:=x; in:=(in+1) mod k; count:=count+1; /*增加一个产品*/ signal(notempty,IM);