孙钟秀操作系统ch管程.ppt

操作系统教程(第4版)第三章并发进程,主讲教师：王慧娇E-mail:whj手机:13978321977QQ:248886622答疑时间：周二14:00-15:30,3.4管程,3.4.1管程和条件变量3.4.2霍尔方法实现管程3.4.3汉森方法实现管程,把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作，便于用高级语言来书写程序，也便于程序正确性验证。,3.4.1什么是管程为什么要引入管程,管程实现的基本思想,在进程共享主存的前提下，如果能集中和封装对一个共享资源的所有访问，包括所需的同步操作，即把相关的共享变量及其操作集中在一起统一控制和管理。把分散在各进程中的临界区集中起来管理，并把共享资源用数据结构抽象地表示出来，由于临界区是访问共享资源的代码段，建立一个“秘书”程序管理到来的访问。,管程定义和属性,管程的定义管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块管程的组成局部于管程的共享变量的说明；对该数据结构进行操作的一组过程；对局部于管程的数据的初始化语句管程的属性共享性：安全性：互斥性：,TYPE=MONITOR局部变量说明；条件变量说明；初始化语句；define;use；()；()；,管程的基本形式,管程的结构,管程的条件变量,当进程在资源不能满足而无法继续运行时被阻塞，同时开放管程。解决方法：引入条件变量的同步机制条件变量：用于区分等待原因的一种信号量，对管程内的过程是全局的，只能通过下面的两个原语访问。,管程的条件变量,同步原语wait和signalwait(x)：挂起调用进程并释放管程，直至另一个进程在条件变量上执行signal()signal(y)：如果有其他进程因对条件变量执行wait（）而被挂起，便释放之；如果没有进程在等待，那么信号不被保存。条件变量与P、V操作中信号量的区别?,管程的问题讨论,使用signal释放等待进程时，可能出现两个进程同时停留在管程内。假定进程P执行signal操作，条件变量队列中有一个进程Q在等待，当进程P执行signal操作后，进程Q被释放，对它们可作如下处理：进程P等待直至进程Q退出管程，或者进程Q等待另一个条件进程Q等待直至进程P退出管程，或者进程P等待另一个条件霍尔采用了第一种办法汉森选择了两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作,管程与进程作比较,管程定义的是公用数据结构，而进程定义的是私有数据结构；管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。,3.4.2管程实现：Hoare方法,霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。,Hoare管程数据结构(1),1.mutex对每个管程，使用用于管程中过程互斥调用的信号量mutex（初值为1）。进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时应执行V(mutex)开放管程，以便让其他调用者进入。为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。,Hoare管程数据结构(2),2.next和next-count对每个管程，引入信号量next（初值为0），凡发出signal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用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管程数据结构,每个管程定义如下数据结构：TYPEinterf=RECORDmutex:semaphore;/*进程调用管程过程前使用的互斥信号量*/next:semaphore;/*发出signal的进程挂起自己的信号量*/next_count:integer;/*在next上等待的进程数*/END;,Hoare管程的wait操作,Procedurewait(varx_sem:semaphore,x_count:integer,IM:interf);beginx_count:=x_count+1;ifIM.next_count0thenV(IM.next);elseV(IM.mutex);P(x_sem);X_count:=x_count1;end;,Hoare管程的signal操作,proceduresignal(varx_sem:semaphore,x_count:integer,IM:interf);beginifx_count0thenbeginIM.next_count:=IM.next_count+1;V(x_sem);P(IM.next);IM.next_count:=IM.next_count-1;end;end;,Hoare管程的外部过程形式,任何一个调用管程中过程的外部过程应组织成下列形式，确保互斥地进入管程。P(IM.mutex);ifIM.next_count0thenV(IM.next);elseV(IM.mutex);,霍尔管程实现五个哲学家吃通心面问题(1),TYPEdining-philosophers=MONITORvarstate:array0.4of(thinking,hungry,eating);s:array0.4ofsemaphore;s-count:array0.4ofinteger;definepickup,putdown;usewait,signal；,霍尔管程实现五个哲学家吃通心面问题(2),proceduretest(k:0.4);beginifstate(k-1)mod5eatingandstatek=hungryandstate(k+1)mod5eatingthenbeginstatek:=eating;signal(sk,s-countk,IM);end;end;,霍尔管程实现五个哲学家吃通心面问题(3),procedurepickup(i:0.4);beginstatei:=hungry;test(i);ifstateieatingthenwait(si,s-counti,IM)；end;,霍尔管程实现五个哲学家吃通心面问题(4),procedureputdown(i:0.4);beginstatei:=thinking;test(i-1)mod5);test(i+1)mod5);end;beginfori:=0to4dostatei:=thinking；end;,霍尔管程实现五个哲学家吃通心面问题(5),cobeginprocessphilosopher-ibeginP(IM.mutex);calldining-philosopher.pickup(i);ifIM.next-count0thenV(IM.next);elseV(IM.mutex);吃通心面；P(IM.mutex);calldining-philosopher.putdown(i);ifIM.next-count0thenV(IM.next);elseV(IM.mutex);end;coend;,管程实现：汉森方法(1),汉森方法的管程中的过程所执行的signal操作一定是过程体的最后一个操作，一个进程当所调用的过程执行了signal操作后，便立即退出了管程。汉森方法使用四条原语：wait，signal，check，re1ease实现对管程的控制。,Wait:执行这条原语后相应进程被置成等待状态，同时开放管程，允许其他进程调用管程中的过程Signal：执行这条原语后指定等待队列中的一个进程被释放，如果等待队列中没有进程，这条操作相当于空操作Check：如果管程是开放的，执行这条原语后关闭管程，如果管程是关闭的，执行这条原语后进程被置为等待状态Re1ease：如果除了发出这条原语的进程外，不再有调用了管程中的过程但又不处于等待状态的进程，那么就释放一个等待调用者，或者开放管程。,管程的实现：汉森方法(2),每个管程使用的一个数据类型：TYPEinterf=RECORDintsem:condition;/*开放管程的信号量*/count1:integer;/*等待调用的进程个数*/count2:integer;/*调用了管程中的过程且不END;处于等待状态的进程个数*/,管程的实现：汉森方法(3),调用查看原语check：如果管程是开放的，则执行这条原语后关闭管程，相应进程继续执行；如果管程是关闭的，则执行这条原语后相应进程被置成等待调用状态,管程的实现：汉森方法(4),procedurecheck(varIM:interf);beginifIM.count2=0thenIM.count2:=IM.count2+1;elsebeginIM.count1:=IM.count1+1;W(IM.intsem);end;end;,管程的实现：汉森方法(5),开放原语release：如果除了发出这条原语的进程外，不再有调用了管程中过程但又不处于等待状态的进程，那么就释放一个等待者或开放管程,管程的实现：汉森方法(6),procedurerelease(varIMinterf);beginIM.count2:=IM.count2-1;ifIM.count2=0andIM.count10thenbeginIM.count1:=IM.count1-1;IM.count2:=IM.count2+1;R(IM.intsem);end;end;,管程的实现：汉森方法(7),等待原语wait：执行这条原语后相应进程被置成等待状态，同时开放管程，允许其它进程调用管程中的过程,管程的实现：汉森方法(8),procedurewait(vars:condition;varIMinterf);begins:=s+1;IM.count2:=IM.count21;ifIM.count10thenbeginIM.count1:=IM.count11;IM.count2:=IM.count2+1;R(IM.intsem);end;W(s);end;,管程的实现：汉森方法(9),释放原语signal：执行这条原语后释放指定等待进程队列中的一个进程。如指定等待进程队列为空，本操作相当于空操作,管程的实现：汉森方法(10),proceduresignal(vars:condition;varIMinterf);beginifs0thenbegins:=s1;IM.count2:=IM.count2+1;R(s);end;end;,管程的实现：汉森方法(11),用管程实现进程同步时，进程应按下列次序工作：请求资源。使用资源。释放资源。,汉森管程实现读者写者问题(1),有两组并发进程：读者与写者，共享一个文件，要求：1）允许多个读者同时执行读操作；2）任一写者在完成写操作之前不允许其他读者和写者工作；3）写者欲工作，要等待已存在的读者完成读操作，新的读者与写者均被拒绝,汉森管程实现读者写者问题(2),typeread_writer=MONITORvarrc,wc:integer;R,W:condition;definestart_read,end_read,start_write,end_write;usewait,signal,check,release;,procedurestart-read;begincheck(IM);ifwc0thenwait(R,IM);rc:=rc+1;signal(R,IM);release(IM);end;procedureend-read;begincheck(IM);rc:=rc-1;ifrc=0thensignal(W,IM);release(IM);end;,汉森管程实现读者写者问题(2),procedurestart_write;begincheck(IM);wc:=wc+1;ifrc0orwc1thenwait(W,IM);release(IM);end;procedureend_write;begincheck(IM);wc:=wc-1;ifwc0thensignal(W,IM);elsesignal(R,IM);release(IM);end;,汉森管程实现读者写者问题(4),汉森管程实现读者写者问题(5),初始化语句beginrc:=0;wc:=0;R:=0;W:=0;end;,汉森管程实现读者写者问题(6),cobeginprocessreaderbegincallread-writer.start-read;read;callread-writer.end-read;end;processwriterbegincallread-writer.start-write;write;callrear-writer.end-write;end;coend;,汉森管程实现苹果橘子问题(1),桌上有一只盘子，每次只能放入一只水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，一个儿子专吃盘中橘子，一个女儿专吃盘中苹果,汉森管程实现苹果橘子问题(2),TYPEFMSD=MONITORvarplate:(apple,orange);full:boolean;SP,SS,SD:condition;defineput,get;usewait,signal,check,release;,汉森管程实现苹果橘子问题(3),procedureput(varfruit:(apple,orange);begincheck(IM);iffullthenwait(SP,IM);full:=true;plate:=fruit;iffruit=orangethensignal(SS,IM);elsesignal(SD,IM);release(IM);end;,汉森管程实现苹果橘子问题(4),procedureget(varfruit:(apple,orange),x:plate);begincheck(IM);ifnotfullorplatefruitthenbeginiffruit=orangethenwait(SS,IM);elsewait(SD,IM);end;x:=plate;full:=false;signal(SP,IM);release(IM);end;,汉森管程实现苹果橘子问题(5),初始化语句beginfull:=false;SP:=0;SS:=0;SD:=0;end;,汉森管程实现苹果橘子问题(6),cobeginprocessfatherbegin准备好苹果;callFMSD.put(apple);end;processmotherbegin准备好桔子;callFMSD.put(orange);end;,汉森管程实现苹果橘子问题(7),processsonbegincallFMSD.get(orange,x);吃取到的桔子;end;processdaughterbegincallFMSD.get(apple,x);吃取到的苹果;end;coend;,汉森管程实现生产者和消费者问题(1),typeproducer-consumer=MONITORvarB:array0.k-1ofitem;/*缓冲区个数in,out:integer;/*存取指针count:integer;/*缓冲中产品数*/notfull,notempty:condition;/*条件变量*/defineappend,take;usewait,signal,check,release;,汉森管程实现生产者和消费者问题(2),procedureappend(x:item);begincheck(IM);ifcount=kthenwait(notfull,IM);/*缓冲已满*/Bin:=x;in:=(in+1)modk;count:=count+1;/*增加一个产品*/signal(notempty,IM);/*唤醒等待者*/release(IM);end;,汉森管程实现生产者和消费者问题(3),proceduretake(x:item);begincheck(IM);ifcount=0thenwait(notempty,IM);/*缓冲已空*/x:=Bout;out:=(out+1)modk;count:=count-1;/*减少一个产品*/signal(notfull,IM);/*唤醒等待者*/release(IM);end;,汉森管程实现生产者和消费者问题(4),begin/*初始化*/in:=0;out:=0;count:=0;end;cobegin/*主程序*/processproducer;varx:item;beginproduce(x);append(x);end;processconsumer;varx:item;begintake(x);consume(x);end;coend.,