《管程和条件变量优秀PPT.ppt》由会员分享，可在线阅读，更多相关《管程和条件变量优秀PPT.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、管程和条件变量第一页，本课件共有49页3.4.1什么是管程?(1)为什么要引入管程把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作，便于用高级语言来书写程序，也便于程序正确性验证。第二页，本课件共有49页什么是管程?(2)管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块 第三页，本课件共有49页管程有以下属性共享性：安全性：互斥性：第四页，本课件共有49页管程的基本形式TYPE =MONITOR ;define;use；procedure();begin ；end;procedure();begin ；end;begin ；end;
2、第五页，本课件共有49页管程的结构conditionc1wait(c1)conditioncnwait(cn)Urgentqueuesignal局部数据条件变量过程1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域第六页，本课件共有49页管程的示例TYPE SSU=MONITOR var busy:boolean;nobusy:semaphore;define require,return;use wait,signal；procedure require;begin if busy then wait(nobusy);/*调用进程加入等待队列*/busy:=turebusy:=tu
3、re；end;end;procedure return;procedure return;begin begin busy:=false busy:=false；signal(nobusy);/*signal(nobusy);/*从等待队列中释放进程*/end;end;begin /*begin /*管程变量初始化*/busy:=false busy:=false；end;end;第七页，本课件共有49页管程的条件变量(1)条件变量：当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量同步原语wait：当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作
4、引起调用进程阻塞第八页，本课件共有49页管程的条件变量(2)另一个进程可以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。条件变量与P、V操作中信号量的区别?第九页，本课件共有49页管程的问题讨论 使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：执行signal的进程等待，直到被释放进程退出管程或等待另一个条件被释放进程等待，直到执行signal的进程退出管程或等待另一个条件霍尔采用了第一种办法；汉森选择了两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作 第十页，本课件共有49页管程与进程作
5、比较(1)管程定义的是公用数据结构，而进程定义的是私有数据结构；管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；第十一页，本课件共有49页管程与进程作比较(2)管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。第十二页，本课件共有49页3.4.2管程实现：Hoare方法霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管
6、理。不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。第十三页，本课件共有49页Hoare管程数据结构(1)1.mutex对每个管程，使用用于管程中过程互斥调用的信号量mutex（初值为1）。进程调用管程中的任何过程时，应执行P(mutex)；进 程 退 出 管 程 时 应 执 行V(mutex)开放管程，以便让其他调用者进入。为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。第十四页，本课件共有49页Hoare管程数据结构(2)2.next和next-co
7、unt对每个管程，引入信号量next（初值为0），凡发出signal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若 有，则 用 V(next)唤 醒 它。next-count（初值为0），用来记录在next上等待的进程个数。第十五页，本课件共有49页Hoare管程数据结构(3)3.x-sem和x-count引入信号量x-sem（初值为0），申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count（初值为0）记录等待资源的进程数
8、。执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现。第十六页，本课件共有49页Hoare管程数据结构 每个管程定义如下数据结构：TYPE interf=RECORD mutex:semaphore;/*进程调用管程过程前 使用的互斥信号量*/next:semaphore;/*发出signal的进程挂起 自己的信号量*/next_count:integer;/*在next上等待的进 程数*/END;第十七页，本课件共有49页Hoare的wait操作Procedure wait(var Procedure wait(v
9、ar x_sem:semaphore,x_count:integer,x_sem:semaphore,x_count:integer,IM:interf);IM:interf);beginbegin x_count:=x_count+1;x_count:=x_count+1;if IM.next_count 0 then V(IM.next);if IM.next_count 0 then V(IM.next);else V(IM.mutex);else V(IM.mutex);P(x_sem);P(x_sem);X_count:=x_count X_count:=x_count 1;1;en
10、d;end;第十八页，本课件共有49页Hoare的signal操作procedure signal(var procedure signal(var x_sem:semaphore,x_count:integer,x_sem:semaphore,x_count:integer,IM:interf);IM:interf);beginbegin if x_count 0 then begin if x_count 0 then begin IM.next_count:=IM.next_count+1;IM.next_count:=IM.next_count+1;V(x_sem);V(x_sem);
11、P(IM.next);P(IM.next);IM.next_count:=IM.next_count-1;IM.next_count:=IM.next_count-1;end;end;end;end;第十九页，本课件共有49页Hoare的外部过程形式 任何一个调用管程中过程的外部过程应组织成下列形式，确保互斥地进入管程。P(IM.mutex);if IM.next_count 0 then V(IM.next);else V(IM.mutex);第二十页，本课件共有49页霍尔方法实现五个哲学家吃通心面问题(1)TYPE dining-philosophers=MONITORTYPE dinin
12、g-philosophers=MONITORvar state:array0.4 of var state:array0.4 of(thinking,hungry,eating);(thinking,hungry,eating);s:array0.4 of semaphore;s:array0.4 of semaphore;s-count:array0.4 of integer;s-count:array0.4 of integer;define pickup,putdown;define pickup,putdown;use wait,signal use wait,signal；第二十一页
13、，本课件共有49页霍尔方法实现五个哲学家吃通心面问题(2)procedure test(k:0.4);procedure test(k:0.4);beginbeginif if state(k-1)state(k-1)mod mod 5eating 5eating and and statek=hungry statek=hungry and and state(k+1)state(k+1)mod mod 5eating then begin5eating then begin statek:=eating;statek:=eating;signal(sk,s-countk,IM);signa
14、l(sk,s-countk,IM);end;end;end;第二十二页，本课件共有49页霍尔方法实现五个哲学家吃通心面问题(3)procedure pickup(i:0.4);procedure pickup(i:0.4);beginbegin statei:=hungry;statei:=hungry;test(i);test(i);if if stateieating stateieating then then wait(si,s-counti,IM)wait(si,s-counti,IM)；end;end;第二十三页，本课件共有49页霍尔方法实现五个哲学家吃通心面问题(4)proced
15、ure putdown(i:0.4);procedure putdown(i:0.4);beginbegin statei:=thinking;statei:=thinking;test(i-1)mod 5);test(i-1)mod 5);test(i+1)mod 5);test(i+1)mod 5);end;end;beginbegin for for i i:=:=0 0 to to 4 4 do do statei statei:=:=thinkingthinking；end;end;第二十四页，本课件共有49页霍尔方法实现五个哲学家吃通心面问题(6)cobegincobegin pr
16、ocess philosopher-i process philosopher-ibeginbegin P(IM.mutex);P(IM.mutex);call dining-philosopher.pickup(i);call dining-philosopher.pickup(i);if IM.next-count 0 then V(IM.next);if IM.next-count 0 then V(IM.next);else V(IM.mutex);else V(IM.mutex);吃通心面；吃通心面；P(IM.mutex);P(IM.mutex);call dining-philos
17、opher.putdown(i);call dining-philosopher.putdown(i);if IM.next-count 0 then V(IM.next);if IM.next-count 0 then V(IM.next);else V(IM.mutex);else V(IM.mutex);end;end;coend;第二十五页，本课件共有49页管程实现：汉森方法(1)汉森方法的管程中的过程所执行的signal操作一定是过程体的最后一个操作，一个进程当所调用的过程执行了signal操作后，便立即退出了管程。汉森方法使用四条原语：wait，signal，check，re1ea
18、se实现对管程的控制。第二十六页，本课件共有49页管程的实现：汉森方法(2)每个管程使用的一个数据类型每个管程使用的一个数据类型：TYPE interf=RECORD intsem:semaphore;/*开放管程的信号量*/count1:integercount1:integer;/*等待调用的进程个数*/count2:integercount2:integer;/*调用了管程中的过程且不END;处于等待状态的进程个数*/第二十七页，本课件共有49页管程的实现：汉森方法(3)调用查看原语check：如如果果管管程程是是开开放放的的，则则执执行行这这条条原原语语后后关关闭闭管管程程，相相应应进
19、进程程继继续续执执行行；如如果果管管程程是是关关闭闭的的，则则执执行行这这条条原原语后相应进程被置成等待调用状态语后相应进程被置成等待调用状态第二十八页，本课件共有49页管程的实现：汉森方法(4)procedure check(var IM interf);procedure check(var IM interf);begin begin if IM.count2=0 if IM.count2=0 then IM.count2:=IM.count2+1;then IM.count2:=IM.count2+1;else else begin begin IM.count1:=IM.count1
20、+1;IM.count1:=IM.count1+1;W(IM.intsem);W(IM.intsem);end;end;end;end;第二十九页，本课件共有49页管程的实现：汉森方法(5)开放原语release：如如果果除除了了发发出出这这条条原原语语的的进进程程外外，不不再再有有调调用用了了管管程程中中过过程程但但又又不不处处于于等等待待状状态态的的进进程程，那那么么就就释释放放一一个个等等待待者或开放管程者或开放管程第三十页，本课件共有49页管程的实现：汉森方法(6)procedure release(var IM interf);procedure release(var IM int
21、erf);begin begin IM.count2:=IM.count2-1;IM.count2:=IM.count2-1;if if IM.count2 IM.count2=0 0 and and IM.count1 IM.count1 0 0 thenthen begin begin IM.count1:=IM.count1-1;IM.count1:=IM.count1-1;IM.count2:=IM.count2+1;IM.count2:=IM.count2+1;R(IM.intsem);R(IM.intsem);end;end;end;end;第三十一页，本课件共有49页管程的实现：
22、汉森方法(7)等待原语等待原语wait：执执行行这这条条原原语语后后相相应应进进程程被被置置成成等等待待状状态态，同同时时开开放放管管程程，允允许许其其它它进进程程调用管程中的过程调用管程中的过程第三十二页，本课件共有49页管程的实现：汉森方法(8)procedure wait(var s:semaphore;var IM interf);procedure wait(var s:semaphore;var IM interf);begin begin s:=s+1;s:=s+1;IM.count2:=IM.count2 IM.count2:=IM.count2 1;1;if IM.count
23、1 0 then if IM.count1 0 then begin begin IM.count1:=IM.count1 IM.count1:=IM.count1 1;1;IM.count2:=IM.count2+1;IM.count2:=IM.count2+1;R(IM.intsem);R(IM.intsem);end;end;W(s);W(s);end;end;第三十三页，本课件共有49页管程的实现：汉森方法(9)释放原语释放原语signal：执执行行这这条条原原语语后后释释放放指指定定等等待待进进程程队队列列中中的的一一个个进进程程。如如指指定定等等待待进进程程队队列列为为空空，本本操
24、操作作相相当当于于空操作空操作第三十四页，本课件共有49页管程的实现：汉森方法(10)procedure procedure signal(var signal(var s:semaphore;s:semaphore;var var IM interf);IM interf);begin begin if s 0 then if s 0 then begin begin s:=s s:=s 1;1;IM.count2:=IM.count2+1;IM.count2:=IM.count2+1;R(s);R(s);end;end;end;end;第三十五页，本课件共有49页管程的实现：汉森方法(11
25、)用管程实现进程同步时，进程应按下列次序工作：请求资源。使用资源。释放资源。第三十六页，本课件共有49页汉森方法实现读者写者问题(1)有有两两组组并并发发进进程程：读读者者与与写写者者，共共享享一一个个文文件件，要要求求：1）允允许许多多个个读读者者同同时时执执行行读读操操作作；2）任任一一写写者者在在完完成成写写操操作作之之前前不不允允许许其其他他读读者者和和写写者者工工作作；3）写写者者欲欲工工作作，要要等等待待已已存存在在的的读读者者完完成成读读操操作作，新新的的读读者者与与写者均被拒绝写者均被拒绝第三十七页，本课件共有49页汉森方法实现读者写者问题(2)type read-writer
26、=MONITORtype read-writer=MONITOR var rc,wc:integer;var rc,wc:integer;R,W:semaphore;R,W:semaphore;define define start-read,start-read,end-read,end-read,start-writer,end-writer;start-writer,end-writer;use wait,signal,check,release;use wait,signal,check,release;第三十八页，本课件共有49页汉森方法实现读者写者问题(3)procedure st
27、art-read;procedure start-read;begin begin check(IM);check(IM);if wc0 then wait(R,IM);if wc0 then wait(R,IM);rc:=rc+1;rc:=rc+1;signal(R,IM);signal(R,IM);release(IM);release(IM);end;end;procedure end-read;procedure end-read;beginbegin check(IM);check(IM);rc:=rc-1;rc:=rc-1;if rc=0 then signal(W,IM);if
28、rc=0 then signal(W,IM);release(IM);release(IM);end;end;第三十九页，本课件共有49页汉森方法实现读者写者问题(4)procedure start-write;procedure start-write;beginbegin check(IM);check(IM);wc:=wc+1;wc:=wc+1;if rc0 or wc1 then wait(W,IM);if rc0 or wc1 then wait(W,IM);release(IM);release(IM);end;end;procedure end-write;procedure e
29、nd-write;beginbegin check(IM);check(IM);wc:=wc-1;wc:=wc-1;if wc0 then signal(W,IM);if wc0 then signal(W,IM);else signal(R,IM);else signal(R,IM);release(IM);release(IM);end;end;第四十页，本课件共有49页汉森方法实现读者写者问题(5)初始化语句初始化语句beginbegin rc:=0;wc:=0;R:=0;W:=0;rc:=0;wc:=0;R:=0;W:=0;end;end;第四十一页，本课件共有49页汉森方法实现读者写
30、者问题(6)cobegincobegin process reader process readerbeginbegin call read-writer.start-read;call read-writer.start-read;read;read;call read-writer.end-read;call read-writer.end-read;end;end;process writer process writerbeginbegin call read-writer.start-write;call read-writer.start-write;write;write;cal
31、l rear-writer.end-write;call rear-writer.end-write;end;end;coend;coend;第四十二页，本课件共有49页汉森方法实现苹果橘子问题(1)桌桌上上有有一一只只盘盘子子，每每次次只只能能放放入入一一只只水水果果，爸爸爸爸专专向向盘盘中中放放苹苹果果，妈妈妈妈专专向向盘盘中中放放橘橘子子，一一个个儿儿子子专专吃吃盘中橘子，一个女儿专吃盘中苹果盘中橘子，一个女儿专吃盘中苹果第四十三页，本课件共有49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(2)(2)TYPE FMSD=MONITORTYPE FMSD=MONITOR var p
32、late:(apple,orange);var plate:(apple,orange);full:boolean;full:boolean;SP,SS,SD:semaphore;SP,SS,SD:semaphore;define put,get;define put,get;usewait,signal,check,release;第四十四页，本课件共有49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(3)(3)procedure put(var fruit:(apple,orange);procedure put(var fruit:(apple,orange);beginbegin
33、 check(IM);check(IM);if full then wait(SP,IM);if full then wait(SP,IM);full:=true;full:=true;plate:=fruit;plate:=fruit;if fruit=orange if fruit=orange then signal(SS,IM);then signal(SS,IM);else signal(SD,IM);else signal(SD,IM);release(IM);release(IM);end;end;第四十五页，本课件共有49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(4)
34、(4)procedure get(varfruit:(apple,orange),x:plate);procedure get(varfruit:(apple,orange),x:plate);beginbegin check(IM);check(IM);if not full or platefruit if not full or platefruit then begin then begin if fruit=orange if fruit=orange then wait(SS,IM);then wait(SS,IM);else wait(SD,IM);else wait(SD,IM
35、);end;end;x:=plate;x:=plate;full:=false;full:=false;signal(SP,IM);signal(SP,IM);release(IM);release(IM);end;end;第四十六页，本课件共有49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(5)(5)初始化语句初始化语句beginbegin full full:=:=false;false;SP SP:=:=0;0;SS SS:=:=0;0;SD:=0;SD:=0;end;end;第四十七页，本课件共有49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(6)(6)cobeginc
36、obegin process father process fatherbeginbegin 准备好苹果准备好苹果;call FMSD.put(apple);call FMSD.put(apple);end;end;process mother process motherbeginbegin 准备好桔子准备好桔子;call FMSD.put(orange);call FMSD.put(orange);end;end;第四十八页，本课件共有49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(7)(7)process sonprocess sonbeginbegin call FMSD.get(orange,x);call FMSD.get(orange,x);吃取到的桔子吃取到的桔子;end;end;process daughter process daughterbeginbegin call FMSD.get(apple,x);call FMSD.get(apple,x);吃取到的苹果吃取到的苹果;end;end;coend;coend;第四十九页，本课件共有49页