孙钟秀操作系统ch管程课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,孙钟秀操作系统ch管程,*,P,o,w,e,r,B,a,r,中国专业,PPT,设计交流论坛,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,孙钟秀操作系统ch管程,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,孙钟秀操作系统ch管程,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,孙钟秀操作系统ch管程,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,孙钟秀操作系统ch管程,*,操作系统教程,(,第,4,版,),第三章 并发进程,主讲教师：王慧娇,E-mail:,手机,:,QQ: 248886622,答疑时间：周二,14:00-15:30,孙钟秀操作系统ch管程,3.4,管程,3.4.1,管程和条件变量,3.4.2,霍尔方法实现管程,3.4.3,汉森方法实现管程,孙钟秀操作系统ch管程,把分散在各进程中的临界区集中起来进行管理 ；,防止进程有意或无意的违法同步操作，,便于用高级语言来书写程序，也便于程序正确性验证。,3.4.1,什么是管程,为什么要引入管程,孙钟秀操作系统ch管程,管程实现的基本思想,在进程共享主存的前提下，如果能集中和封装对一个共享资源的所有访问，包括所需的同步操作，即把相关的共享变量及其操作集中在一起统一控制和管理。,把分散在各进程中的临界区集中起来管理，并把共享资源用数据结构抽象地表示出来，由于临界区是访问共享资源的代码段，建立一个“秘书”程序管理到来的访问。,孙钟秀操作系统ch管程,管程定义和属性,管程的定义,管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块,管程的组成,局部于管程的共享变量的说明；,对该数据结构进行操作的一组过程；,对局部于管程的数据的初始化语句,管程的属性,共享性：,安全性：,互斥性：,孙钟秀操作系统ch管程,TYPE = MONITOR,局部变量说明；,条件变量说明；,初始化语句；,define ;,use ,；,(),；,(),；,管程的基本形式,孙钟秀操作系统ch管程,管程的结构,condition c1,wait(c1),condition cn,wait(cn),urgent queue,signal,局部数据,条件变量,过程,1,过程,k,出口,初始化代码,入口,管程,等待调用的进程队列,管程等待区域,孙钟秀操作系统ch管程,管程的条件变量,当进程在资源不能满足而无法继续运行时被阻塞，同时开放管程。,解决方法：引入条件变量的同步机制,条件变量：用于区分等待原因的一种信号量，对管程内的过程是全局的，只能通过下面的两个原语访问。,孙钟秀操作系统ch管程,管程的条件变量,同步原语,wait,和,signal,wait(x),：挂起调用进程并释放管程，直至另一个进程在条件变量上执行,signal(),signal(y),：如果有其他进程因对条件变量执行,wait,（）而被挂起，便释放之；如果没有进程在等待，那么信号不被保存。,条件变量与,P,、,V,操作中信号量的区别,?,孙钟秀操作系统ch管程,管程的问题讨论,使用,signal,释放等待进程时，可能出现两个进程同时停留在管程内。,假定进程,P,执行,signal,操作，条件变量队列中有一个进程,Q,在等待，当进程,P,执行,signal,操作后，进程,Q,被释放，对它们可作如下处理：,进程,P,等待直至进程,Q,退出管程，或者进程,Q,等待另一个条件,进程,Q,等待直至进程,P,退出管程，或者进程,P,等待另一个条件,霍尔采用了第一种办法,汉森选择了两者的折衷，规定管程中的过程所执行的,signal,操作是过程体的最后一个操作,孙钟秀操作系统ch管程,管程与进程作比较,管程定义的是公用数据结构，而进程定义的是私有数据结构；,管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；,管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；,管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；,管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。,孙钟秀操作系统ch管程,3.4.2,管程实现：,Hoare,方法,霍尔方法使用,P,和,V,操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。,不要求,signal,操作是过程体的最后一个操作，且,wait,和,signal,操作可被设计成可以中断的过程。,孙钟秀操作系统ch管程,Hoare,管程数据结构,(1),1.mutex,对每个管程，使用用于管程中过程互斥调用的信号量,mutex,（初值为,1,）。,进程调用管程中的任何过程时，应执行,P(mutex),；进程退出管程时应执行,V(mutex),开放管程，以便让其他调用者进入。,为了使进程在等待资源期间，其他进程能进入管程，故在,wait,操作中也必须执行,V(mutex),，否则会妨碍其他进程进入管程，导致无法释放资源。,孙钟秀操作系统ch管程,Hoare,管程数据结构,(2),2.next,和,next-count,对每个管程，引入信号量,next,（初值为,0,），凡发出,signal,操作的进程应该用,P(next),挂起自己，直到被释放进程退出管程或产生其他等待条件。,进程在退出管程的过程前，须检查是否有别的进程在信号量,next,上等待，若有，则用,V(next),唤醒它。,next-count,（初值为,0,），用来记录在,next,上等待的进程个数。,孙钟秀操作系统ch管程,Hoare,管程数据结构,(3),3.x-sem,和,x-count,引入信号量,x-sem,（初值为,0,），申请资源得不到满足时，执行,P(x-sem),挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器,x-count,（初值为,0,）记录等待资源的进程数。,执行,signal,操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用,V(x-sem),来实现。,孙钟秀操作系统ch管程,Hoare,管程数据结构,每个管程定义如下数据结构,：,TYPE interf = RECORD,mutex:semaphore; /*,进程调用管程过程前,使用的互斥信号量*,/,next:semaphore; /*,发出,signal,的进程挂起,自己的信号量*,/,next_count:integer;/*,在,next,上等待的进,程数*,/,END;,孙钟秀操作系统ch管程,Hoare,管程的,wait,操作,Procedure wait(var x_sem:semaphore,x_count:integer, IM:interf);,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;,孙钟秀操作系统ch管程,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.next_count := IM.next_count - 1;,end;,end;,孙钟秀操作系统ch管程,Hoare,管程的外部过程形式,任何一个调用管程中过程的外部过程应组织成下列形式，确保互斥地进入管程。,P(IM.mutex);,;,if IM.next_count 0 then V(IM.next);,else V(IM.mutex);,孙钟秀操作系统ch管程,霍尔管程实现五个哲学家吃通心面问题,(1),TYPE dining-philosophers = MONITOR,var state : array0.4 of (thinking, hungry, eating);,s : array0.4 of semaphore;,s-count : array0.4 of integer;,define pickup, putdown;,use wait, signal,；,孙钟秀操作系统ch管程,霍尔管程实现五个哲学家吃通心面问题,(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;,孙钟秀操作系统ch管程,霍尔管程实现五个哲学家吃通心面问题,(3),procedure pickup(i:0.4);,begin,statei := hungry;,test(i);,if stateieating then wait(si,s-counti,IM),；,end;,孙钟秀操作系统ch管程,霍尔管程实现五个哲学家吃通心面问题,(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;,孙钟秀操作系统ch管程,霍尔管程实现五个哲学家吃通心面问题,(5),cobegin,process philosopher-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;,孙钟秀操作系统ch管程,管程实现：汉森方法,(1),汉森方法的管程中的过程所执行的,signal,操作一定是过程体的最后一个操作，一个进程当所调用的过程执行了,signal,操作后，便立即退出了管程。,汉森方法使用四条原语：,wait,，,signal,，,check,，,re1ease,实现对管程的控制。,孙钟秀操作系统ch管程,Wait:,执行这条原语后相应进程被置成等待状态，同时开放管程，允许其他进程调用管程中的过程,Signal,：执行这条原语后指定等待队列中的一个进程被释放，如果等待队列中没有进程，这条操作相当于空操作,Check,：如果管程是开放的，执行这条原语后关闭管程，如果管程是关闭的，执行这条原语后进程被置为等待状态,Re1ease,：如果除了发出这条原语的进程外，不再有调用了管程中的过程但又不处于等待状态的进程，那么就释放一个等待调用者，或者开放管程。,孙钟秀操作系统ch管程,管程的实现：汉森方法,(2),每个管程使用的一个数据类型,：,TYPE interf = RECORD,intsem : condition; /*,开放管程的信号量 *,/,count1 : integer; /*,等待调用的进程个数 *,/,count2 : integer; /*,调用了管程中的过程且不,END;,处于等待状态的进程个数 *,/,孙钟秀操作系统ch管程,管程的实现：汉森方法,(3),调用查看原语,check,：,如果管程是开放的，则执行这条原语后关闭管程，相应进程继续执行；如果管程是关闭的，则执行这条原语后相应进程被置成等待调用状态,孙钟秀操作系统ch管程,管程的实现：汉森方法,(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;,孙钟秀操作系统ch管程,管程的实现：汉森方法,(5),开放原语,release,：,如果除了发出这条原语的进程外，不再有调用了管程中过程但又不处于等待状态的进程，那么就释放一个等待者或开放管程,孙钟秀操作系统ch管程,管程的实现：汉森方法,(6),procedure release(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;,孙钟秀操作系统ch管程,管程的实现：汉森方法,(7),等待原语,wait,：,执行这条原语后相应进程被置成等待状态，同时开放管程，允许其它进程调用管程中的过程,孙钟秀操作系统ch管程,管程的实现：汉森方法,(8),procedure wait(var s:condition; var IM interf);,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;,孙钟秀操作系统ch管程,管程的实现：汉森方法,(9),释放原语,signal,：,执行这条原语后释放指定等待进程队列中的一个进程。如指定等待进程队列为空，本操作相当于空操作,孙钟秀操作系统ch管程,管程的实现：汉森方法,(10,),procedure signal(var s:condition; var IM interf);,begin,if s 0 then,begin,s := s 1;,IM.count2 := IM.count2 + 1;,R(s);,end;,end;,孙钟秀操作系统ch管程,管程的实现：汉森方法,(11),用管程实现进程同步时，进程应按下列次序工作：,请求资源。,使用资源。,释放资源。,孙钟秀操作系统ch管程,汉森管程实现读者写者问题,(1),有两组并发进程：读者与写者，共享一个文件，要求：,1,）允许多个读者同时执行读操作；,2,）任一写者在完成写操作之前不允许其他读者和写者工作；,3,）写者欲工作，要等待已存在的读者完成读操作，新的读者与写者均被拒绝,孙钟秀操作系统ch管程,汉森管程实现读者写者问题,(2),type read_writer = MONITOR,var rc, wc : integer;,R, W : condition;,define start_read, end_read, start_write, end_write;,use wait, signal, check, release;,孙钟秀操作系统ch管程,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 then signal(W,IM);,release(IM);,end;,汉森管程实现读者写者问题,(2),孙钟秀操作系统ch管程,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;,汉森管程实现读者写者问题,(4),孙钟秀操作系统ch管程,汉森管程实现读者写者问题,(5),初始化语句,begin,rc := 0; wc := 0; R := 0; W := 0;,end;,孙钟秀操作系统ch管程,汉森管程实现读者写者问题,(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;,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(1),桌上有一只盘子，每次只能放入一只水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，一个儿子专吃盘中橘子，一个女儿专吃盘中苹果,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(2),TYPE FMSD = MONITOR,var plate : (apple, orange);,full : boolean;,SP, SS, SD : condition;,define put, get;,use wait, signal, check, release;,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(3),procedure put(var fruit:(apple, orange);,begin,check(IM);,if full then wait(SP,IM);,full := true;,plate := fruit;,if fruit=orange,then signal(SS,IM);,else signal(SD,IM);,release(IM);,end;,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(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, IM);,release(IM);,end;,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(5),初始化语句,begin,full := false; SP := 0; SS := 0; SD := 0;,end;,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(6),cobegin,process father,begin,准备好苹果,;,call FMSD.put(apple);,end;,process mother,begin,准备好桔子,;,call FMSD.put(orange);,end;,孙钟秀操作系统ch管程,汉森管程实现苹果橘子问题,(7),process son,begin,call FMSD.get(orange,x);,吃取到的桔子,;,end;,process daughter,begin,call FMSD.get(apple,x);,吃取到的苹果,;,end;,coend;,孙钟秀操作系统ch管程,汉森管程实现生产者和消费者问题,(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;,孙钟秀操作系统ch管程,汉森管程实现生产者和消费者问题,(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); /*,唤醒等待者*,/,release(IM);,end;,孙钟秀操作系统ch管程,汉森管程实现生产者和消费者问题,(3),procedure take(x:item);,begin,check(IM);,if count=0 then wait(notempty,IM);,/*,缓冲已空*,/,x:=Bout;,out:=(out+1) mod k;,count:=count-1;,/*,减少一个产品*,/,signal(notfull,IM);,/*,唤醒等待者*,/,release(IM);,end;,孙钟秀操作系统ch管程,汉森管程实现生产者和消费者问题,(4),begin /*,初始化*,/,in := 0; out := 0; count:= 0;,end;,cobegin /*,主程序*,/,process producer;,var x:item;,begin,produce(x);,append(x);,end;,process consumer;,var x:item;,begin,take(x);,consume(x);,end;,coend.,孙钟秀操作系统ch管程,