管程和条件变量优秀课件.ppt

管程和条件变量第1页，本讲稿共49页3.4.1什么是管程?(1)为什么要引入管程把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作，便于用高级语言来书写程序，也便于程序正确性验证。第2页，本讲稿共49页什么是管程?(2)管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块 第3页，本讲稿共49页管程有以下属性共享性：安全性：互斥性：第4页，本讲稿共49页管程的基本形式TYPE =MONITOR ;define;use；procedure();begin ；end;procedure();begin ；end;begin ；end;第5页，本讲稿共49页管程的结构condition c1wait(c1)condition cn wait(cn)Urgent queue signal局部数据条件变量过程1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域第6页，本讲稿共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:=ture；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;第7页，本讲稿共49页管程的条件变量(1)条件变量：当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量同步原语wait：当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作引起调用进程阻塞第8页，本讲稿共49页管程的条件变量(2)另一个进程可以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。条件变量与P、V操作中信号量的区别?第9页，本讲稿共49页管程的问题讨论 使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：执行signal的进程等待，直到被释放进程退出管程或等待另一个条件被释放进程等待，直到执行signal的进程退出管程或等待另一个条件霍尔采用了第一种办法；汉森选择了两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作 第10页，本讲稿共49页管程与进程作比较(1)管程定义的是公用数据结构，而进程定义的是私有数据结构；管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；第11页，本讲稿共49页管程与进程作比较(2)管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。第12页，本讲稿共49页3.4.2管程实现：Hoare方法霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。第13页，本讲稿共49页Hoare管程数据结构(1)1.mutex对每个管程，使用用于管程中过程互斥调用的信号量mutex（初值为1）。进程调用管程中的任何过程时，应执行P(mutex)；进 程 退 出 管 程 时 应 执 行V(mutex)开放管程，以便让其他调用者进入。为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。第14页，本讲稿共49页Hoare管程数据结构(2)2.next和next-count对每个管程，引入信号量next（初值为0），凡发出signal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若 有，则 用 V(next)唤 醒 它。next-count（初值为0），用来记录在next上等待的进程个数。第15页，本讲稿共49页Hoare管程数据结构(3)3.x-sem和x-count引入信号量x-sem（初值为0），申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count（初值为0）记录等待资源的进程数。执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现。第16页，本讲稿共49页Hoare管程数据结构 每个管程定义如下数据结构：TYPE interf=RECORD mutex:semaphore;/*进程调用管程过程前 使用的互斥信号量*/next:semaphore;/*发出signal的进程挂起 自己的信号量*/next_count:integer;/*在next上等待的进 程数*/END;第17页，本讲稿共49页Hoare的wait操作Procedure wait(var Procedure wait(var x_sem:semaphore,x_count:integer,IM:interf);x_sem:semaphore,x_count:integer,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;end;end;第18页，本讲稿共49页Hoare的signal操作procedure signal(var procedure signal(var x_sem:semaphore,x_count:integer,IM:interf);x_sem:semaphore,x_count:integer,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);P(IM.next);P(IM.next);IM.next_count:=IM.next_count-1;IM.next_count:=IM.next_count-1;end;end;end;end;第19页，本讲稿共49页Hoare的外部过程形式 任何一个调用管程中过程的外部过程应组织成下列形式，确保互斥地进入管程。P(IM.mutex);if IM.next_count 0 then V(IM.next);else V(IM.mutex);第20页，本讲稿共49页霍尔方法实现五个哲学家吃通心面问题(1)TYPE dining-philosophers=MONITORTYPE dining-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；第21页，本讲稿共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);signal(sk,s-countk,IM);end;end;end;第22页，本讲稿共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;第23页，本讲稿共49页霍尔方法实现五个哲学家吃通心面问题(4)procedure 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;第24页，本讲稿共49页霍尔方法实现五个哲学家吃通心面问题(6)cobegincobegin process 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-philosopher.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;第25页，本讲稿共49页管程实现：汉森方法(1)汉森方法的管程中的过程所执行的signal操作一定是过程体的最后一个操作，一个进程当所调用的过程执行了signal操作后，便立即退出了管程。汉森方法使用四条原语：wait，signal，check，re1ease实现对管程的控制。第26页，本讲稿共49页管程的实现：汉森方法(2)每个管程使用的一个数据类型每个管程使用的一个数据类型：TYPE interf=RECORD intsem:semaphore;/*开放管程的信号量*/count1:integercount1:integer;/*等待调用的进程个数*/count2:integercount2:integer;/*调用了管程中的过程且不END;处于等待状态的进程个数*/第27页，本讲稿共49页管程的实现：汉森方法(3)调用查看原语check：如如果果管管程程是是开开放放的的，则则执执行行这这条条原原语语后后关关闭闭管管程程，相相应应进进程程继继续续执执行行；如如果果管管程程是是关关闭闭的的，则则执执行行这这条条原原语语后后相应进程被置成等待调用状态相应进程被置成等待调用状态第28页，本讲稿共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+1;IM.count1:=IM.count1+1;W(IM.intsem);W(IM.intsem);end;end;end;end;第29页，本讲稿共49页管程的实现：汉森方法(5)开放原语release：如如果果除除了了发发出出这这条条原原语语的的进进程程外外，不不再再有有调调用用了了管管程程中中过过程程但但又又不不处处于于等等待待状状态态的的进进程程，那那么么就就释释放放一一个等待者或开放管程个等待者或开放管程第30页，本讲稿共49页管程的实现：汉森方法(6)procedure release(var IM interf);procedure release(var IM interf);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;第31页，本讲稿共49页管程的实现：汉森方法(7)等待原语等待原语wait：执执行行这这条条原原语语后后相相应应进进程程被被置置成成等等待待状状态态，同同时时开开放放管管程程，允允许许其其它它进程调用管程中的过程进程调用管程中的过程第32页，本讲稿共49页管程的实现：汉森方法(8)procedure procedure wait(var wait(var s:semaphore;s:semaphore;var var IM IM interf);interf);begin begin s:=s+1;s:=s+1;IM.count2:=IM.count2 IM.count2:=IM.count2 1;1;if IM.count1 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;第33页，本讲稿共49页管程的实现：汉森方法(9)释放原语释放原语signal：执执行行这这条条原原语语后后释释放放指指定定等等待待进进程程队队列列中中的的一一个个进进程程。如如指指定定等等待待进进程程队队列为空，本操作相当于空操作列为空，本操作相当于空操作第34页，本讲稿共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;第35页，本讲稿共49页管程的实现：汉森方法(11)用管程实现进程同步时，进程应按下列次序工作：请求资源。使用资源。释放资源。第36页，本讲稿共49页汉森方法实现读者写者问题(1)有有两两组组并并发发进进程程：读读者者与与写写者者，共共享享一一个个文文件件，要要求求：1）允允许许多多个个读读者者同同时时执执行行读读操操作作；2）任任一一写写者者在在完完成成写写操操作作之之前前不不允允许许其其他他读读者者和和写写者者工工作作；3）写写者者欲欲工工作作，要要等等待待已已存存在在的的读读者者完完成成读读操操作作，新新的的读读者者与与写写者均被拒绝者均被拒绝第37页，本讲稿共49页汉森方法实现读者写者问题(2)type read-writer=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;第38页，本讲稿共49页汉森方法实现读者写者问题(3)procedure start-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 rc=0 then signal(W,IM);release(IM);release(IM);end;end;第39页，本讲稿共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 end-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;第40页，本讲稿共49页汉森方法实现读者写者问题(5)初始化语句初始化语句beginbegin rc:=0;wc:=0;R:=0;W:=0;rc:=0;wc:=0;R:=0;W:=0;end;end;第41页，本讲稿共49页汉森方法实现读者写者问题(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;call rear-writer.end-write;call rear-writer.end-write;end;end;coend;coend;第42页，本讲稿共49页汉森方法实现苹果橘子问题(1)桌桌上上有有一一只只盘盘子子，每每次次只只能能放放入入一一只只水水果果，爸爸爸爸专专向向盘盘中中放放苹苹果果，妈妈妈妈专专向向盘盘中中放放橘橘子子，一一个个儿儿子子专专吃吃盘盘中中橘橘子，一个女儿专吃盘中苹果子，一个女儿专吃盘中苹果第43页，本讲稿共49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(2)(2)TYPE FMSD=MONITORTYPE FMSD=MONITOR var plate:(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;第44页，本讲稿共49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(3)(3)procedure put(var fruit:(apple,orange);procedure put(var fruit:(apple,orange);beginbegin 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;第45页，本讲稿共49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(4)(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);end;end;x:=plate;x:=plate;full:=false;full:=false;signal(SP,IM);signal(SP,IM);release(IM);release(IM);end;end;第46页，本讲稿共49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(5)(5)初始化语句初始化语句beginbegin full full:=:=false;false;SP SP:=:=0;0;SS SS:=:=0;SD:=0;0;SD:=0;end;end;第47页，本讲稿共49页汉森方法实现汉森方法实现苹果橘子苹果橘子问题问题(6)(6)cobegincobegin 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;第48页，本讲稿共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页，本讲稿共49页