操作系统课件Chapter 04-1.ppt

1、第四章 互斥、同步与通讯,并发进程(concurrent processes) 进程互斥(mutual exclusion) 进程同步(synchronization) 进程高级通讯(communication),4.1 并发进程,4.1.1 顺序性与并发性 顺序性 内部顺序性：P1: a1,a2,a3; P2: b1,b2,b3 外部顺序性：a1,a2,a3,b1,b2,b3; b1,b2,b3,a1,a2,a3 特征：顺序性、封闭性、可再现性 并发性 内部并发性：P2: b1,b2,b3; P2: b1,b3,b2 外部并发性：a1,b1,b2,a2,a3,b3; b1,b2,a1,b3,

2、a2,a3 特征：交叉性、开放性、不可再现性,4.1.2 与时间有关的错误,例：图书借阅系统 （x:某种书册数，设当前x=1.） 终端1： 终端2： CYCLE CYCLE 等待借书者； 等待借书者； IF x=1 Then IF x=1 Then Begin Begin x:=x-1; x:=x-1; 借书 借书 End End Else 无书 Else 无书 End End,1,2,3,4,4.1.2 与时间有关的错误(Cont.),错误原因之1： 进程执行交叉(interleave); 错误原因之2： 涉及公共变量(x)。 Remarks: 某些交叉结果不正确; 必须去掉导致不正确结果的

3、交叉。,4.2 进程互斥(mutual exclusion),4.2.1 共享变量与临界区 4.2.2 临界区与进程互斥 4.2.3 进程互斥的实现,4.2.1 共享变量与临界区域,共享变量（shared variable） 多个进程都需要访问的变量。 临界区域（critical region） 访问共享变量的程序段。,一组公共变量,CR1,CR2,CRn,.,表示,共享变量: shared 临界区域: region do 语句 例子：shared B:array0,.,n-1of integer; region B do region B do begin begin (访问B） .（访问B

4、）. end; end;,4.2.2 临界区域与进程互斥,定义：多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。 二层涵义： （1）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域； （2）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。 Remarks: 1.共享变量所代表的资源称为”临界资源” 2.互斥是相对于临界资源而言的。,嵌套临界区域,shared x1,x2; shared y1,y2; region x1,x2 do region y1,y2 do begin begin . region y1,y2

5、 do region x1,x2 do begin begin . . end end end; end; 有可能发生死锁,4.2.3 进程互斥的实现,算法框架,Repeat critical section remainder section Until false,entry section,exit section,4.2.3 进程互斥的实现,Requirements: 正确性原则: 一次只允许一个进程活动在关于同一组公共变量的临界区中； 进展性原则: 临界区空闲时，多个竞争者在有限时间内确定下一个进入者； 公平性原则: 一个想要进入临界区的进程在等待有限个进程进入并离开临界区后获得进入

6、临界区的机会。,4.2.3.1 进程互斥的软件实现,完全用程序实现，不需特殊硬件指令支持。 可用于单CPU和多CPU环境中。 有忙式等待问题。 不进入等待状态的等待,Busy waiting “运行”或“就绪”,Lamport面包店算法,算法思想：设置一个发号者，按0,1,2, 发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入。 Problem: 两个进程可能抓到相同的号。 Why? 为保证抓到不同的号，需要互斥机制。 Resolution: 若抓到相同的号，按进程编号依次进入。 Definition: (a,b)(c,d) if(ac)or(a=c and bd),Lampo

7、rt面包店算法,VAR choosing: Array0,n-1Of Boolean;（false) number: Array0,n-1Of integer; (0) Pi 进入： 1. choosingi:=true; 2. numberi:=maxnumber0,numbern-1+1; 3. choosingi:=false; 4. For j:=0 To n-1 Do 5. While choosingj Do skip; 6. While (numberj0)and 7. (numberj,j)(numberi,i) Do skip 8. Endfor,Lamport面包店算法(C

8、ont.),临界区 Pi离开： numberi:=0： 变量choosing的作用： 表示进程是否正在抓号 变量number的作用： 正确次序：P1，P2，P3 记录各个进程抓到的号码,可能按P2,P3,P1次序进入！,Lamport面包店算法(Cont.),思考： 1.为何不同的进程可能抓到相同的号？结合算法第二步思考 2.如果将算法第五步去掉，会发生什么情况？,Eisenberg/Mcguire算法,Var flag Array0,n-1Of (idle, want_in, in_cs); turn: 0.n-1; 初始任意,flagi=idle: 进程Pi不想进入临界区 flagi=wa

9、nt_in: 进程Pi想进入临界区 flagi=in_cs: 进程Pi已进入临界区 初始时，flag的所有元素都为idle，turn的初值为0到n-1的任意一个数 每个进程有局部变量j,Eisenberg/Mcguire算法,Pi进入: Repeat flagi:=want_in; j:=turn; While j!=i do If flagj!=idle Then j:=turn Else j:=(j+1)mod n; flagi:=in_cs; j:=0; While (jn)and(j=i or flagj!=in_cs) do j:=j+1; Until j=n； turn:=i;,当

10、其他进程的状态都不为in_cs 时，进程i才能进入临界区,当前运行进程状态变为idle且进程i 被选中作为下一个运行的进程时， 进程i的状态才能置为in_cs,Eisenberg/Mcguire算法,Pi离开： j:=(turn+1)mod n; While (flagj=idle)do j:=(j+1)mod n; turn:=j; flagi:=idle;,临界区,从状态为want_in的进程中，选 择下一个进入临界区的进程,4.2.3.2 进程互斥的硬件实现,1. 硬件提供“测试并建立”指令 int test_and_set(int ,4.2.3.2 进程互斥的硬件实现,2. 硬件提供“

11、交换”指令 void swap(int ,4.2.3.2 进程互斥的硬件实现,基于swap指令的互斥算法 do key=1; do swap(,4.2.3.2 进程互斥的硬件实现,Remarks： (1) test_and_set指令和swap指令是原子的，不可中断的。（为何？） (2) test_and_set实际上是：将内存中一个单元的内容取出，再送一个新值。 (3) swap实际上是：交换内存两个单元的内容。,4.2.3.2 进程互斥的硬件实现,思考： 1.用test_and_set指令和swap指令实现互斥，满足公 平性原则吗？ 2.可以通过下面的方式实现互斥吗？ while(lock

12、); lock=1; 临界区 lock=0;,4.2.3.2 进程互斥的硬件实现,3. 硬件提供“关中断”和“开中断”指令 关中断 Critical Region 开中断 Remarks: (1) 开关中断只在单CPU系统中有效;(why?) (2) 影响并发性。,4.3 进程同步,4.3.1 进程同步的概念 例：司机-售票员问题 司机活动： 售票员活动： do do (1) 关车门 启动车辆 (2) 正常行驶 售 票 到站停车 (3) (4) 开车门 while(1) while(1),4.3.1 进程同步的概念,定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之

13、间这种相互制约的关系称为进程同步。,P1:,P2:,synchronize,后,先,4.3.2 进程同步机制,进程同步和进程互斥的区别： 进程同步仅发生在有逻辑关系的进程间 进程互斥可发生在任意两个进程之间 定义：一组进程，如果它们单独不能正常运行，但并发可以正常运行，这种现象为进程合作，参与合作的进程为合作进程,4.3.2 进程同步机制,定义：用于实现进程同步的工具称为同步机制（synchronization mechanism） 同步机制要求： 描述能力够用; 可实现; 高效; 使用方便.,典型同步机制,信号灯与PV操作(semaphore and PV operations) 管程(mo

14、nitor) 会合(rendezvous) 条件临界区(conditional critical region),4.3.3 信号灯与PV操作,E.W.Dijkstra, 1965. 4.3.3.1 信号灯与PV操作的定义 信号灯类型定义： typedef semaphore struct int value; pointer_to_PCB queue; 信号灯变量说明：semaphore s; Remarks: (1) semaphore is pre-defined data type, (2) s can be declared as needed, eg. semaphore s1,s

15、2;,信号灯变量,S.value S.queue,semaphore S;,FIFO,P操作原语,P操作原语： void P(semaphore s) s-value-; if (s-valuequeue) asleep(s-queue): (1) 执行此操作进程的PCB进入s-queue尾部（状态改为等待）； (2) 转处理机调度程序。,原语: 一段不可间断执行的程序,V操作原语,V操作原语： void V(semaphore s) s-value+; if (s-valuequeue) wakeup(s-queue)： s-queue链头PCB出等待队列，进入就绪队列（状态改为就绪）。,规

16、定和结论,对于信号灯变量的规定： 必须置一次初值，只能置一次初值，初值=0; 只能执行P操作和V操作，所有其它操作非法。 几个有用的结论： 当s.value=0时，s.queue为空； 当s.value0时，可以管理多个实例的同类资源。,用信号灯实现进程互斥,Var mutex: semaphore; (初值=1） shared x,y,z:integer; CR1 CR2 CRn,用信号灯实现进程互斥,Var mutex: semaphore; (初值=1） shared x,y,z:integer; P(mutex) P(mutex) P(mutex) CR1 CR2 CRn V(mute

17、x) V(mutex) V(mutex),互斥例子：借书系统(revisited),Var mutex:semaphore; (initial value 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 End,用信号灯实现进程互斥练习,试用P、V操作实现火车票联网订票系统中北京

18、和上海两地的两个终端售票进程发售同一班次车票的过程(Try!),(1)分析进程间的制约关系 (2)设置信号量的个数和初值 (3)给出进程的算法描述，在适当地方加上P，V操作,解法,设置一个互斥信号量S，其初值为1 do 根据顾客订票要求找到公共数据单元k； P(S)； 读取k值，保存到变量R中； 若(R=顾客订票数)，则执行 (1) 将R的值减去顾客订票数 (2) 将R的值回写到k中 (3) V(S); (4) 售出顾客所订的票； 否则，执行： (1) V(S); (2) 屏幕打印”票已售完”，返回； while(1),用信号灯实现进程同步,General Case: VAR S:semaph

19、ore; (initial value 0),P(S) 后动作,先动作 V(S),P1:,P2:,用信号灯实现进程同步,例子：司机-售票员问题： VAR s1,s2: semaphore; (initial value 0) 司机活动： 售票员活动： Repeat Repeat P(S1) 关车门 启动车辆 V(S1) 正常行驶 售 票 到站停车 P(S2) V(S2) 开车门 Until false Until false,Classical synchronization problems,1. Producers and consumers problem 2. Readers and

20、writers problem 3. Dining philosophers problem etc.,例1. 生产者/消费者问题,预备知识： 组合资源：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。 同种组合资源：相同类型子资源构成的组合资源。 管理：Var S:semaphore; (初值=子资源个数） 例子：2台打印机 Var S:semaphore; S.value=2; 申请：P（S）； 释放：V（S）；,例1. 生产者/消费者问题,0 1 k-1,箱子，容量k B:Array0.k-1Of item,生产者,消费者,生产物品 放入B中,B中取物品 消费之,环形

21、缓冲区,1,0,K-1,in,(in+1)mod k,out,(out+1)mod k,问题分析,生产者活动： 消费者活动： do do 加工一件物品 (3) (1) 箱中取一物品 物品放入箱中 (4) (2) 消耗这件物品 while(1) while(1),资源：箱子中的位置 资源：物品（同种组合） （同种组合） Var S1:semaphore; Var S2:semaphore; S1.value=k; S2.value=0; 放前：P（S1） 取前：P（S2） 放后：V（S2） 取后：V（S1）,同步,生产者活动： 消费者活动： Repeat Repeat 加工一件物品 P(S2)

22、P(S1) 箱中取一物品 物品放入箱中 V(S1) V(S2) 消耗这件物品 Until false Until false 对B和in,out的互斥： Var mutex:semaphore; (mutex.value=1),互斥,生产者活动： 消费者活动： Repeat Repeat 加工一件物品 P(S2) P(S1) P(mutex) P(mutex) 箱中取一物品 物品放入箱中 V(mutex) V(mutex) V(S1) V(S2) 消耗这件物品 Until false Until false,程序,Program producers_consumers; Var B:Array

23、0,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) end,Procedure consumer cycle P(s2); P(mutex); x:=Bout; out:=(out+1)mod k; V(mutex); V(S1); consume x; end;,程序,Begin S1.value:=k; S2.value:=0;

24、mutex.value:=1; in:=0; out:=0; Cobegin P1: producer; , Pm: producer; C1: consumer; , Cn: consumer; Coend; End.,并发性提高策略,生产者和消费者：不操作B的相同分量,生产者的共享变量： Bin， in,消费者的共享变量： Bout，out,in=out: 满或空, Var mutex1,mutex2:semaphore; (初值为1),并发性提高策略,生产者活动： 消费者活动： Repeat Repeat 加工一件物品 P(S2) P(S1) P(mutex2) P(mutex1) 箱中

25、取一物品 物品放入箱中 V(mutex2) V(mutex1) V(S1) V(S2) 消耗这件物品 Until false Until false,练习,桌上有个只能装得下一个水果的空盘子。爸爸可向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和P、V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。,分析,该题为生产者-消费者问题的变形 同步关系： 1、爸爸和儿子之间：仅当儿子取走桔子时，爸爸才能向盘中放水果；仅当爸爸把桔子放入盘中，儿子才能拿到桔子吃 2、爸爸和女儿之间：仅当女儿取走苹果时，爸爸才能向盘中放水果；

26、仅当爸爸把苹果放入盘中，女儿才能拿到苹果吃,解法,所需信号量： 同步信号量empty，初值为1，表明盘子是空的 同步信号量orange，初值为0，表明爸爸尚未将桔子放入盘中 同步信号量apple，初值为0，表明爸爸尚未将苹果放入盘中,解法,爸爸进程(生产者) 儿子进程 女儿进程 do do do P(empty); P(orange); P(apple); 将水果放入盘中; 从盘中取出桔子；从盘中取出苹果； 若放入的是桔子， V(empty); V(empty); 则V(orange); 吃桔子; 吃苹果; 否则V(apple); while(1) while(1) while(1),例2.

27、读者/写者问题,P. T. Courtois 1971 Communication of the ACM, Vol.14, 667-669. ACM: Association for Computing Machinery 解法1：写者可能饿死 解法2：写者优先,例2. 读者/写者问题,Problem Statement: 一组公共数据DB R1 Rm W1 . Wn 要求：（1）R-R可以同时 （2）R-W不可同时 （3）W-W不可同时,accessing,Solution1: 不考虑R-R不互斥,Var r_w_w:semaphore; (initial value: 1) Reader：

28、 Writer: P（r_w_w); P(r_w_w) 读操作 写操作 V（r_w_w); V（r_w_w) 分析：（1）写者活动正确；（2）R-R不能同时。 改进：最先进入的R执行P；最后离开的R执行V；,Solution2: 考虑R-R不互斥,Var read_count:integer; (initial value is 0) Reader: read_count:=read_count+1; If read_count=1 Then P(r_w_w); 读操作 read_count:=read_count-1; If read_count=0 Then V(r_w_w); 问题：对R

29、ead_count操作的互斥问题。,Solution3: 正确解法,Var mutex:semaphore; (initial value is 1) Reader: P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); 读操作 P(mutex); read_count:=read_count-1; If read_count=0 Then V(r_w_w); V(mutex);,读者等待在何处？ 读者如何被唤醒？,程序,Program readers_writers; Var r_w_w: s

30、emaphore; mutex:semaphore; read_count: integer; procedure writer; begin P(r_w_w); write ops V(r_w_w) end;,程序（Cont.）,Procedure reader; begin P(mutex); read_count:=read_count+1; If read_count=1 Then P(r_w_w); V(mutex); read ops P(mutex); read_count:=read_count-1; If read_count=0 Then V(r_w_w); V(mutex

31、); end;,程序（Cont.）,begin read_count:=0; r_w_w.value:=1; mutex.value:=1; cobegin r1: reader; ; rm: reader; w1: writer; ; wn: writer coend end.,分析：,问题：读者源源不断，read_count不为0，写者会被饿死。 策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。,Further improvement is left to interested students.,例3. 哲学家就餐问题,Dining Philosophers Pro

32、blem Proposed and solved by E.W. Dijkstra, in 1965,例3. 哲学家就餐问题,Room,ph0,ph4,ph3,ph2,ph1,f0,f4,f3,f2,f1,例3. 哲学家就餐问题,哲学家活动： Repeat 思考 进食 Until false 进食：需要“叉子” 叉子：不同种组合资源,哲学家活动（包含资源活动） Repeat 思考 取左叉，取右叉 进食 放左叉，放右叉 Until false,死锁情况：每位哲学家拿到左叉，等待右叉。,例3. 哲学家就餐问题,Room,ph0,ph4,ph3,ph2,ph1,f0,f4,f3,f2,f1,死锁预防

33、策略,死锁解决方法：同时申请左、右两把叉子（预先分配）。 哲学家状态描述（增加了hungry状态）： State: Array0.4Of (thinking,hungry,eating); 每个哲学家一个信号量： Self: Array0.4Of semaphore; (initial value is 0);,就餐条件测试,测试I号哲学家是否具备进食条件： Procedure test(I:0.4) If (stateI=hungry) and (state(I-1)mod 5eating) and (state(I+1)mod 5eating) Then stateI:=eating; V

34、(selfI) Remark: 自测试不需要stateI=hungry, 但测试左邻右舍需要此条件。,未考虑互斥问题,I号哲学家活动： 1. Repeat 2. 思考 3. stateI:=hungry; 4. test(I); 5. P(selfI); 6. 取左叉，取右叉； 7. 进食; 8. 放左叉，放右叉； 9. stateI:=thinking; 10 test(I-1)mod 5); 11. test(I+1)mod 5); 12. Until false;,共享变量：state; 临界区域：3-4, 9-11 Var mutex:semaphore;(1),考虑互斥问题,I号哲学

35、家活动： 1. Repeat 2. 思考 3. P(mutex); 4. stateI:=hungry; 5. test(I); 6. V(mutex); 7. P(selfI); 8. 取左叉，取右叉； 9. 进食 10. 放左叉，放右叉；,11. P(mutex); 12. stateI:=thinking; 13 test(I-1)mod 5); 14. test(I+1)mod 5); 15. V(mutex) 16. Until false;,问题,饿死情况： 某哲学家左右邻居至少有一个处于eating状态。,程序,Program dining_philosophers var st

36、ate:array0.4of (thinking,hungry,eating); self:array0.4of semaphore; mutex:semaphore; procedure test(I:0.4) begin if (stateI=hungry)and (state(I-1)mod 5eating) and(state(I+1)mod 5eating) then begin stateI:=eating; V(selfI) end end;,程序(Cont.),Procedure philosopher(I:0.4) begin cycle thinking P(mutex);

37、 stateI:=hungry; test(I); V(mutex); P(selfI);,pick_up_fork(I);pick_up_fork(I+1)mod 5); Eating; put_down_fork(I);put_down_fork(I+1)mod 5); P(mutex); stateI:=thinking; test(I-1)mod 5); test(I+1)mod 5); V(mutex); end end,程序(Cont.),程序(Cont.),begin for I:=0 to 4 do begin stateI:=thinking; selfI.value:=0

38、end; mutex.value:=1; cobegin ph0: philosopher(0); . Ph4: philosopher(4); coend end.,例3. 哲学家就餐问题,Room,ph0,ph3,ph3,ph2,ph1,f0,f4,f3,f2,f1,例3. 哲学家就餐问题,Room,ph0,ph4,ph3,ph2,ph1,f0,f4,f3,f2,f1,例4. 3台打印机管理,Var lp:array1.3of (free,used); (initial value is free) S: semaphore; (initial value is 3) mutex: sem

39、aphore; (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); return(i);,进程互斥与同步练习,某寺庙，有小和尚、老和尚若干。庙内有一水缸，由小和尚提水入缸，供老和尚饮用水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一

40、个水桶取水。设水桶个数为5个，试用信号灯和 PV 操作给出老和尚和小和尚的活动。,解答,semaphore empty=30; / 表示缸中目前还能装多少桶水，初始时能装 30 桶水 semaphore full=0; / 表示缸中有多少桶水，初始时缸中没有水 semaphore buckets=5; / 表示有多少只空桶可用，初始时有 5 只桶可用 semaphore mutex_well=1; / 用于实现对井的互斥操作 semaphore mutex_bigjar=1; / 用于实现对缸的互斥操作,小和尚,while(1) P(empty); P(buckets); get a buck

41、et; go to the well; P(mutex_well); get water; V(mutex_well); go to the temple; P(mutex_bigjar); pure the water into the big jar; V(mutex_bigjar); V(buckets); V(full); ,老和尚,while() P(full); P(buckets); get a bucket; go to the jar; P(mutex_bigjar); get water; V(mutex_bigjar); drink water; V(buckets);

42、V(empty); ,4.3.4 条件临界区Conditional Critical Region,背景 PV操作低级，容易用错 条件临界区形式 region V when B do S 执行S条件 没有其它进程处于与V相关的条件临界区中 进入S时B为true,条件临界区,实现互斥 region v when true do s CCR与PV操作的等价性(证明从略） 用CCR可以实现PV操作 用PV操作可以实现CCR,4.3.5 管程（Monitor）,信号灯和PV操作： 分散式同步机制：对共享变量和信号灯变量的操作分散在整个系统中或各个进程中。 缺点： 可读性差； 正确性不易保证； 不易修改

43、。 优点： 高效，灵活。,管程： 集中式同步工具：共享变量及其所有相关操作集中在一个模块中。 优点： 可读性好； 正确性易于保证； 易于修改。 缺点： 不甚灵活，效率略低。,4.3.5.1 管程的提出,70年代初, By E.W.Dijkstra, C.A.R.Hoare, P.B.Hansen. 背景: Structured programming 基于管程的语言 Concurrent Pascal (Hansen) Modula (With) Mesa Mod* Concurrent Euclid XCY,Java: synchronized method,4.3.5.2 管程形式,Typ

44、e monitor_name=MONITOR; 共享变量说明 define 本管程内定义，本管程外使用的过程(函数)名表； use 本管程外定义，本管程内使用的过程(函数)名表； Procedure 过程名（形参表）； 局部变量说明 Begin 语句序列 End; ,4.3.5.2 管程形式(Cont.),Function 函数名（形参表）:返回值类型； 局部变量说明 Begin 语句序列 End; . Begin 共享变量初始化语句序列 End; 语言特点： (1) 模块化 (2) 抽象数据类型 (3) 信息隐藏,4.3.5.3 管程语义,管程的共享变量在管程外部不可见，外部只能通过调用管程

45、中的外部子程序访问共享变量； 为保证对共享变量操作的数据完整性，规定管程互斥进入； 管程中有等待/唤醒机制，等待时释放管程的互斥权，唤醒时（P唤醒Q）： P等待，Q继续，直到Q退出或等待；(Hoare) Q等待，P继续，直到P退出或等待；(Java) 唤醒是管程中可执行的最后一个操作。（Hansen),Hoare管程设施,入口等待队列： 每个管程变量一个，用于排队进入； 紧急等待队列： 每个管程变量一个，用于唤醒等待； 内部等待队列： var c: condition; 可根据需要定义多个，用于设置等待条件。,管程队列,c1,c2,PCB,PCB,PCB,PCB,入口队列,紧急队列,Monitor,进入与离开,进入管程： 申请管程互斥权。 离开管程： 如紧急等待队列非空，唤醒第一个等待者；否则释放管程的互斥权。,条件变量操作,Var c:condition; wait(c): 如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权; 执行此操作的进程（线程）进入c链尾。 signal(c): 如c链空，相当空操作