《管程和条件变量》PPT课件.ppt
《《管程和条件变量》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《管程和条件变量》PPT课件.ppt(50页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、3.4 管程3.4.1 管程和条件变量 3.4.2 霍尔方法实现霍尔方法实现管程3.4.3 汉森方法实现汉森方法实现管程3.4.1什么是管程?(1)为什么要引入管程把分散在各进程中的临界区集中起来进行管理;防止进程有意或无意的违法同步操作,便于用高级语言来书写程序,也便于程序正确性验证。什么是管程?(2)管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块 管程有以下属性共享性:安全性:互斥性:管程的基本形式TYPE =MONITOR ;define;use;procedure();begin ;end;procedure();begin ;end;begin
2、;end;管程的结构condition c1wait(c1)condition cn wait(cn)Urgent queue signal局部数据条件变量过程1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域管程的示例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;pro
3、cedure return;procedure return;begin begin busy:=false busy:=false;signal(nobusy);/*signal(nobusy);/*从等待队列中释放进程*/end;end;begin /*begin /*管程变量初始化*/*/busy:=false busy:=false;end;end;管程的条件变量(1)条件变量:当调用管程过程的进程无法运行时,用于阻塞进程的一种信号量同步原语wait:当一个管程过程发现无法继续时,它在某些条件变量condition上执行wait,这个动作引起调用进程阻塞管程的条件变量(2)另一个进程可
4、以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。条件变量与P、V操作中信号量的区别?管程的问题讨论 使用signal释放等待进程时,可能出现两个进程同时停留在管程内。解决方法:执行signal的进程等待,直到被释放进程退出管程或等待另一个条件被释放进程等待,直到执行signal的进程退出管程或等待另一个条件霍尔采用了第一种办法;汉森选择了两者的折衷,规定管程中的过程所执行的signal操作是过程体的最后一个操作 管程与进程作比较(1)管程定义的是公用数据结构,而进程定义的是私有数据结构;管程把共享变量上的同步操作集中起来,而临界区却分散在每个
5、进程中;管程是为管理共享资源而建立的,进程主要是为占有系统资源和实现系统并发性而引入的;管程与进程作比较(2)管程是被欲使用共享资源的进程所调用的,管程和调用它的进程不能并行工作,而进程之间能并行工作,并发性是其固有特性;管程是语言或操作系统的成分,不必创建或撤销,而进程有生命周期,由创建而产生至撤销便消亡。3.4.2管程实现:Hoare方法霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用,及实现对共享资源互斥使用的管理。不要求signal操作是过程体的最后一个操作,且wait和signal操作可被设计成可以中断的过程。Hoare管程数据结构(1)1.mutex对每个管程,使用用于管程中
6、过程互斥调用的信号量mutex(初值为1)。进程调用管程中的任何过程时,应执行P(mutex);进 程 退 出 管 程 时 应 执 行V(mutex)开放管程,以便让其他调用者进入。为了使进程在等待资源期间,其他进程能进入管程,故在wait操作中也必须执行V(mutex),否则会妨碍其他进程进入管程,导致无法释放资源。Hoare管程数据结构(2)2.next和next-count对每个管程,引入信号量next(初值为0),凡发出signal操作的进程应该用P(next)挂起自己,直到被释放进程退出管程或产生其他等待条件。进程在退出管程的过程前,须检查是否有别的进程在信号量next上等待,若 有
7、,则 用 V(next)唤 醒 它。next-count(初值为0),用来记录在next上等待的进程个数。Hoare管程数据结构(3)3.x-sem和 x-count引入信号量x-sem(初值为0),申请资源得不到满足时,执行P(x-sem)挂起。由于释放资源时,需要知道是否有别的进程在等待资源,用计数器x-count(初值为0)记录等待资源的进程数。执行signal操作时,应让等待资源的诸进程中的某个进程立即恢复运行,而不让其他进程抢先进入管程,这可以用V(x-sem)来实现。Hoare管程数据结构 每个管程定义如下数据结构:TYPE interf=RECORD mutex:semaphor
8、e;/*进程调用管程过程前 使用的互斥信号量*/next:semaphore;/*发出signal的进程挂起 自己的信号量*/next_count:integer;/*在next上等待的进 程数*/END;Hoare的wait操作Procedure wait(var Procedure wait(var 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_c
9、ount 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 1;X_count:=x_count 1;end;end;Hoare的signal操作procedure signal(var procedure signal(var x_sem:semaphore,x_count:integer,x_sem:semaphore,x_count:integer,IM:interf);IM:interf);be
10、ginbegin 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;Hoare的外部过程形式 任何一个调用管程中过程的外部过程应组织成下列形式,确保互斥地进入管程。P(IM.mutex);if
11、IM.next_count 0 then V(IM.next);else V(IM.mutex);霍尔方法实现五个哲学家吃通心面问题(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 intege
12、r;s-count:array0.4 of integer;define pickup,putdown;define pickup,putdown;use wait,signal use wait,signal;霍尔方法实现五个哲学家吃通心面问题(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 mo
13、d 5eating then begin5eating then begin statek:=eating;statek:=eating;signal(sk,s-countk,IM);signal(sk,s-countk,IM);end;end;end;霍尔方法实现五个哲学家吃通心面问题(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(s
14、i,s-counti,IM)wait(si,s-counti,IM);end;end;霍尔方法实现五个哲学家吃通心面问题(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:=:=thinkin
15、gthinking;end;end;霍尔方法实现五个哲学家吃通心面问题(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.mute
16、x);吃通心面;吃通心面;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;管程实现:汉森方法(1)汉森方法的管程中的过程所执行的signal操作一定是过程体的最后一个操作,一个进程当所调用的过程执行了signal操作后,便立
17、即退出了管程。汉森方法使用四条原语:wait,signal,check,re1ease实现对管程的控制。管程的实现:汉森方法(2)每个管程使用的一个数据类型每个管程使用的一个数据类型:TYPE interf=RECORD intsem:semaphore;/*开放管程的信号量*/count1:integercount1:integer;/*等待调用的进程个数*/count2:integercount2:integer;/*调用了管程中的过程且不END;处于等待状态的进程个数*/管程的实现:汉森方法(3)调用查看原语check:如如果果管管程程是是开开放放的的,则则执执行行这这条条原原语语后后关
18、关闭闭管管程程,相相应应进进程程继继续续执执行行;如如果果管管程程是是关关闭闭的的,则则执执行行这这条条原原语语后后相相应应进进程程被被置置成成等等待待调用状态调用状态管程的实现:汉森方法(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+
19、1;IM.count1:=IM.count1+1;W(IM.intsem);W(IM.intsem);end;end;end;end;管程的实现:汉森方法(5)开放原语release:如如果果除除了了发发出出这这条条原原语语的的进进程程外外,不不再再有有调调用用了了管管程程中中过过程程但但又又不不处处于于等等待待状状态态的的进进程程,那那么么就就释释放放一一个等待者或开放管程个等待者或开放管程管程的实现:汉森方法(6)procedure release(var IM interf);procedure release(var IM interf);begin begin IM.count2:=
20、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;管程的实现:汉森方法(7)等待原语等待原语wait:执执行行这这条条原原语语后后相相应应进进程程
21、被被置置成成等等待待状状态态,同同时时开开放放管管程程,允允许许其它进程调用管程中的过程其它进程调用管程中的过程管程的实现:汉森方法(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 1;IM.count2:=IM.count2 1;if IM.count1 0 then if IM.count1 0 then begin begin IM.count1:=IM.c
22、ount1 1;IM.count1:=IM.count1 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;管程的实现:汉森方法(9)释放原语释放原语signal:执执行行这这条条原原语语后后释释放放指指定定等等待待进进程程队队列列中中的的一一个个进进程程。如如指指定定等等待待进进程程队队列列为为空空,本本操操作作相相当当于于空操作空操作管程的实现:汉森方法(10)procedure procedure signal(var signal(var
23、 s:semaphore;s:semaphore;var var IM interf);IM interf);begin begin if s 0 then if s 0 then begin begin s:=s 1;s:=s 1;IM.count2:=IM.count2+1;IM.count2:=IM.count2+1;R(s);R(s);end;end;end;end;管程的实现:汉森方法(11)用管程实现进程同步时,进程应按下列次序工作:请求资源。使用资源。释放资源。汉森方法实现读者写者问题(1)有有两两组组并并发发进进程程:读读者者与与写写者者,共共享享一一个个文文件件,要要求求:1
24、)允允许许多多个个读读者者同同时时执执行行读读操操作作;2)任任一一写写者者在在完完成成写写操操作作之之前前不不允允许许其其他他读读者者和和写写者者工工作作;3)写写者者欲欲工工作作,要要等等待待已已存存在在的的读读者者完完成成读读操操作作,新新的的读读者与写者均被拒绝者与写者均被拒绝汉森方法实现读者写者问题(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,star
25、t-read,end-read,end-read,start-writer,end-writer;start-writer,end-writer;use wait,signal,check,release;use wait,signal,check,release;汉森方法实现读者写者问题(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);s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管程和条件变量 管程 条件 变量 PPT 课件
限制150内