第二章-进程管理2

并发进程间制约关系,资源共享关系间接制约多个进程彼此无关，完全不知道或只能间接感知其它进程的存在系统须保证诸进程能互斥地访问临界资源系统资源应统一分配，而不允许用户进程直接使用相互合作关系直接制约系统应保证相互合作的诸进程在执行次序上的协调和防止与时间有关的差错,1,2.3进程同步,进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。进程互斥进程同步利用信号量机制解决具体问题,2,2.3.1进程同步的基本概念1.两种形式的制约关系并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系：1)间接制约关系（进程互斥）由于共享资源而引起的在临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约。2)直接制约关系（进程同步）由于并发进程互相共享对方的私有资源所引起的直接制约。这种制约主要源于进程间的合作。,3,2.临界资源临界资源：一次仅允许一个进程使用的资源。许多硬件资源如打印机、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享。什么叫互斥？一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。临界区：每个进程中访问临界资源的那段代码（criticalsection）。（不允许多个并发进程交叉执行的那段程序),4,例如，各种程序中经常出现的赋值语句：X=X+1；在用汇编语言书写时，就变成：LOADA，XADDIA，1STOREA，X等三条语句，这里A代表累加器。根据系统的设计和要求，在这三条语句的执行期间，也有可能发生中断或调度，从而使得与当前进程无关的程序得以执行。为了保证程序执行最终结果的正确性，必须对并发执行的各进程进行制约，以控制它们的执行速度和对资源的竞争。,5,设有两个计算进程A，B共享内存S。其中S分为三个领域，即系统区、进程工作区和数据区。这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据。系统区主要是堆栈，其中存放那些空数据块的地址（如图）,6,getspace:beginlocalggstacktoptoptop-1endrelease(ad):begintoptop+1stacktopadend,7,设时刻t0时，top=h0，则getspace和release(ad)可能按以下顺序执行：首先release(ad)的第一句执行，t0：toptop+1top=h0+1；接着getspace执行，得：t1：gstacktopg=stackh0+1；t2：toptop-1top=h0；再是release(ad)的第二句执行，得：t3：stacktopadstackh0ad；其结果是调用getspace的进程取到的是h0+1中的一个未定义值，而调用release(ad)的进程把所释放的空数据块的地址ad重复放入了h0中。,8,怎样保证上述执行结果的正确性呢？一个较为明显的答案是，如果把getspace和release(ad)抽象为两个各以一个动作完成的顺序执行单位，那么执行结果的正确性是可以保证的。把不允许多个并发进程交叉执行的一段程序称为临界部分（criticalsection）或临界区（criticalregion）。临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，例如上例中就是因为过程getspace和release(ad)共同访问栈中的数据而引起的。临界区不可能用增加硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程序。,9,临界区的管理计算机专家Dijkstra1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足：每次至多有一个进程处于临界区当若干进程同时要求进入它们的临界区时，应在有限时间内使一进程进入临界区，而不应相互堵塞而致使彼此不能进入临界区。进程仅在临界区内逗留有限的时间。简言之，同步机制的准则有：空闲让进；忙则等待；让权等待；有限等待；,10,11,一种可能的办法是对临界区加锁以实现互斥。设临界区的类名为，为了保证每一次临界区中只能有一个程序段被执行，又设锁定位KeyS，KeyS表示锁定位属于类名为的临界区。加锁后的临界区程序描述如下：lock(keyS)unlock(keyS),加锁法实现互斥,12,设keyS=1时表示类名为S的临界区可用，keyS=0时表示类名为的临界区不可用。则unlock(keyS)只用一条语句即可实现。即：keyS1不过，由于lock(keyS)必须满足keyS=0时，不允许任何进程进入临界区，而keyS=1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。,13,一种简便的实现方法是：lock(x)=beginlocalvrepeatvxuntilv=1(临界资源成为可用）x0end,14,不过，这种方法是不能保证并发进程互斥执行所要求的准则（3）的（只允许一个进程进入临界区）。因为当同时有几个进程调用lock(key)时，在x0语句执行之前，可能已有两个以上的多个进程由于key=1而进入临界区。为解决这个问题有些机器在硬件中设置了“测试与设置指令，保证第一步和第二步执行不可分离。注意：在系统实现时锁定位key总是设置在公有资源所对应的数据结构中的。,尽管用加锁的方法可以实现进程之间的互斥，但这种方法仍然存在一些影响系统可靠性和执行效率的问题。例如，循环测试锁定位将损耗较多的CPU计算时间。如果一组并发进程的进程数较多，且由于每个进程在申请进入临界区时都得对锁定位进行测试，这种开销是很大的。另外，使用加锁法实现进程间互斥时，还将导致在某些情况下出现不公平现象。某些进程可能不能进入临界区。,15,加锁法和、原语法：加锁法是采用反复测试lock而实现互斥的，存在CPU浪费和不公平现象；而、原语法是采用信号量来管理相应的临界区的共有资源，信号量的值只能由、原语操作来改变，克服了加锁法的弊端。,16,2.3.2信号量和P、V原语,信号：铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理。信号量（semaphore）：简称sem，sem是一整数，在sem大于等于零时，代表可供并发进程使用的资源实体数，但它小于零时是表示正在等待使用临界区的进程数。,17,P、V原语,信号量的数值仅能由P、V原语操作改变。一次P原语操作使得信号量sem减1，而一次V原语操作使信号量sem加1.在操作系统中，信号量sem是一整数。用于互斥的信号量sem的初值应该大于零，而建立一个信号量必须经过说明所建信号量所代表的意义，和赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进程。,18,P原语操作的主要动作S1如果S1以后仍大于等于零，则进程继续进行；如果S1以后小于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度。V原语操作的主要动作S1如果相加后结果大于零，则继续进行；相加后结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。,19,20,必须强调的一点是，当某个进程正在临界区内执行时，其他进程如果执行了原语操作，则该进程并不像调用lock时那样因进不了临界区而返回到lock的起点，等以后重新执行测试，而是在等待队列中等待有其他进程做原语操作释放资源后，进入临界区，这时，原语的执行才算真正结束。当有好几个进程执行原语未通过而进入等待状态之后，如有某进程作了原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。,21,，过程要以原语实现的原因。如果多个进程同时调用操作或操作的话，则有可能在操作刚把sem-1而未把对应进程送入等待队列时，操作开始执行。从而，操作将无法发现等待进程而返回。因此，操作都必须以原语实现，且在，原语执行期间不允许中断发生。,22,入口,s.value=s.value-1,s.value0,调度进程入等待队列,转进程调度,入口,s.value=s.value1,s.value0,唤醒等待队列中的一个进程,返回或转进程调度,返回,返回,s.value0,是,是,否,P原语操作功能流程图,V原语操作功能流程图,（sem）：begin封锁中断；lock(lockbit)valsem=valsem-1ifvalsem0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源V(S)：表示释放一个资源。信号量的初值应该大于等于0,49,信号量及P、V操作讨论,2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前，而两个V操作无关紧要。,50,信号量及P、V操作讨论,3）P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂。,51,用信号量解题的关键,步骤：信号量的设置；给信号量赋初值（常用的互斥和同步信号量值的大小）；P、V操作安排的位置（其中，P的顺序不能颠倒，V的顺序任意）注意区分1）公用信号量，互斥时使用的信号量（二元信号量）：通常取值为“”与“”，用作互斥。它联系着一组共行进程，初值为，每个进程均可对之施加、操作。2）私用信号量：一般信号量（资源信号量）：它联系着一组共行进程，但其初值为，或为某个正整数，表示资源的数目，主要用于进程同步。,52,吃水果问题1,问题描述：桌上有一只盘子，每次只能放一个水果，爸爸向盘中放水果，儿子等吃盘里的水果。只要盘子空，则爸爸可向盘中放水果，只要盘中有水果，儿子可从中取出，请给出两人之间的同步关系，并用P、V操作实现两人正确活动的程序。,53,empty初值为1,full初值为0,父亲：while(true)P(empty);放水果到盘中;V(full);,54,儿子：while(true)P(full);取水果吃;V(empty);,吃水果问题2,问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用P、V操作实现四人正确活动的程序。,55,四人之间的关系,爸爸，妈妈要互斥使用盘子，所以两者之间是互斥关系；爸爸放的苹果，女儿吃，所以两者是同步关系；妈妈放的桔子，儿子吃，所以两者也是同步关系。,56,S初值为1,Sa初值为0，So初值为0,父亲：while(true)P(s);放苹果到盘中;V(sa);母亲：while(true)P(s);放桔子到盘中;V(so);,57,女儿：while(true)P(sa);取苹果;V(s);儿子：while(true)P(so);取桔子;V(s);,司机售票员问题,汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信号量及赋初值，写出他们的同步过程。,58,司机的私用信号量s1，初值为？售票员的私用信号量s2，初值为？,59,司机：P1While(true)P(s1)开车；停车；V(s2),售票员：P2While(true)P(s2)开门；上下客；关门；V(s1),经典问题读者写者问题,有两组并发进程:读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作,60,例：利用信号量解决读者和写者问题一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。,61,为了解决读者和写者问题，需设置两个信号量：（1）读互斥信号量mutex=1,用于使读者互斥地访问共享变量readcount,这里readcount是记录有多少读者正在读;（2）写互斥信号量w=1,用于实现读写互斥和写写互斥地访问共享文件。读者写者问题进行如下描述：intreadcount:=0;,62,读者写者问题的解法,读者：while(true)P(mutex);readcount+;if(readcount=1)P(w);V(mutex);读P(mutex);readcount-;if(readcount=0)V(w);V(mutex);,写者：while(true)P(w);写V(w);,63,整型信号量,最初由Dijkstra把整型信号量定义为一个整型量整型信号量s除初始化外，仅能被两个标准的原子操作wait(s)和signal(s)亦即P/V操作来访问。wait(s):whiles0dono_op;s:=s-1;signal(s):s:=s+1;,64,有何弊端？,2.3.3其他信号量机制,记录型信号量机制信号量类型声明,typesemphore=recordvalue:integer;L:listofprocess;end,65,记录型信号量机制wait(s)操作描述,procedurewait(s)Vars:semphore;begins.value:=s.value-1;ifs.value0thenblock(s.L);end,66,记录型信号量机制signal(s)操作描述,proceduresignal(s)Vars:semphore;begins.value:=s.value+1;ifs.value0thenwakeup(s.L);end,67,68,在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value-1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value=S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,信号量要描述的前趋关系示例,69,S1,S2,S3,S4,S5,S6,a,b,c,d,e,f,g,利用信号量来描述前趋关系,Vara,b,c,d,e,f,g:semphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parendend,70,AND型信号量集机制的引入,对于多个进程要共享两个以上的资源的情况，上述机制则可能导致发生死锁例两个进程A、B要求同时访问共享数据C、DprocessA:processB:wait(Dmutex);wait(Cmutex);wait(Cmutex);wait(Dmutex);对策：若干个临界资源的分配采取原子操作方式,71,72,AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneouswait)定义如下：,Swait(s1,s2,sn)操作,procedureSwait(s1,s2,sn)Vars1,s2,sn:semphore;beginifs11andandsn1thenfori:=1tondosi:=si-1;elseblockProcessAndResetPC(sfirstless);end,73,？,fori:=1tondoif(si1)block(si.L);ResetPC();break;,Ssignal(s1,s2,sn)操作,procedureSsignal(s1,s2,sn)Vars1,s2,sn:semphore;beginfori:=1tondosi:=si+1;wakeupAllProcesses(si);endfor;end,74,？,一般信号量集机制的引入,记录型信号量集机制中，wait(s)和signal(s)操作仅能对信号量施以增1和减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需d个某类临界资源时，便需要进行d次wait(s)操作，这显然是低效的。此外，在有些情况下，要求当资源数量低于某一下限值时，便不予分配。故在每次分配之前，都必须测试该资源的数量是否不小于测试值t。基于以上两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。,75,Swait(s1,t1,d1,sn,tn,dn)操作,procedureSwait(s1,t1,d1,sn,tn,dn)Vars1,s2,sn:semphore;t1,t2,tn,d1,d2,dn:integer;beginifs1t1andandsntnthenfori:=1tondosi:=si-di;elseblockProcessAndResetPC(sfirstless);end,76,fori:=1tondoif(si1时）或互斥信号量（s=1时）。Swait(s,1,0)一种特殊且很有用的信号量，相当于可控开关。当s1时，允许多个进程进入某特定区；当s变为0后，将阻止任何进程进入该特定区。,78,哲学家进餐问题描述,哲学家进餐问题是典型的同步问题五个哲学家共用一张圆桌，分别坐在环桌均匀摆放的五张椅子上，并全部执行同为交替地进行思考和进餐的生活方式圆桌上放有五支筷子，均匀排放在哲学家之间的位置上哲学家饥饿时便试图去取用圆桌上最靠近他左右两端的两支筷子，且只有在同时拿到两支筷子时方可进餐，进餐完毕则把筷子放回原处，并继续进行思考,79,哲学家进餐问题剖析(待续),筷子是临界资源信号量数组chopstick0.4，初始值均为1第i个哲学家活动wait(chopsticki);wait(chopstick(i+1)mod5);Eat;signal(chopsticki);signal(chopstick(i+1)mod5);Think;,80,哲学家进餐问题剖析(续),上述解决方案在五个哲学家同时饥饿且各自拿起左边筷子的情况下会引起死锁,81,哲学家进餐主程序设计,82,Varchopstick:array0.4ofsemphore(1,1,1,1,1);beginparbeginphilosophy0;philosophyi;philosophy4;parendend,83,可采取以下几种解决方法：(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。,思路1解决过程如下：最多允许4个哲学家同时进餐，以保证至少有一个哲学家能够拿到两支筷子进餐，最后总会进餐完毕并释放他使用过的两支筷子，从而可使其他哲学家进餐。除设信号量c0c4,初始值均为1，分别表示i号筷子被拿（i0，1，2，3，4）外，再设置一个信号量S控制同时进餐的人数，初值为4。第i个哲学家的活动算法可以描述如下：,Send（i）：P(S)P(ci);P(c(i+1)mod5);EAT;V(ci);V(c(i+1)mod5);V(S);,84,思路（3）解决过程如下：让偶数号的哲学家先取右手边的筷子；让奇数号的哲学家先取左手边的筷子。(这样，任何一个哲学家拿到一支筷子以后，就已经阻止了他邻座的哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人饿死）设信号量c0c4,初始值均为1，分别表示i号筷子被拿（i0，1，2，3，4），Send（i）：/*第i个哲学家要吃饭*/BeginIfimod20thenP(c(i+1)mod5);P(ci);EAT;V(c(i+1)mod5);V(ci);ElseP(ci);P(c(i+1)mod5);EAT;V(ci);V(c(i+1)mod5);End,85,86,利用AND信号量机制解决哲学家进餐问题（思路2解决方案）在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Varchopsiickarray0,4ofsemaphore=(1,1,1,1,1);processirepeatthink;Swait(chopstick(i+1)mod5,chopsticki);eat;Ssignal(chopstick(i+1)mod5,chopsticki);untilfalse;,练习：1、有3个进程R,W1,W2共享一个缓冲区，缓冲区每次只能存放一个数。缓冲区无数时，进程R可以读数放入；若是奇数允许进程W1将其取出打印；若是偶数允许进程W2将其取出打印；写出三个并发进程正确工作的程序。2、有3个进程A,B,C合作解决文件打印，进程A将文件记录从磁盘读入主存缓冲区1，每次读一个记录；进程B将缓冲区1的内容复制到缓冲区2，每次复制一个记录；进程C将缓冲区2的内容打印出来，每次打印一个记录；缓冲区的大小等于一个记录大小。用pv操作来保证文件的正确打印。,87,练习1；Semaphoreempty=1;Semaphorefull1=0;Semaphorefull2=0;Main()R()cobeginwhile(true)R();W1();p(empty);W2();读数放入缓冲区；coendif奇数v(full1);elsev(full2);,88,w1()w2()while(true)while(true)p(full1);p(full2);从缓冲区中取奇数；从缓冲区中取偶数；v(empty);v(empty);打印；打印；,89,练习2：Semaphoreempty1=1;Semaphoreempty2=1;Semaphorefull1=0;Semaphorefull2=0;Main()A()cobeginwhile(true)A();B();从磁盘读一个记录；C();p(empty1);coend将记录存入缓冲区1；v(full1);,90,B()C()while(true)while(true)p(full1);p(full2);从缓冲区1取出记录；从缓冲区2取出记录；v(empty1);v(empty2);p(empty2);打印记录；将记录存入缓冲区2；v(full2);,91,练习3某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。,92,分析：这是个典型的进程互斥问题，超市内部及其出入口是临界资源，为此，若出入口为同一个，则需要设两个互斥信号量，否则需要设3个。,解答:,所用信号量设置如下：）互斥信号量S，初值为50，用以保证最多可以有50个购物者同时进入超市。）互斥信号量mutex，初值为1，用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子。用信号量机制给出的每个购物者购物过程的算法描述如下：,93,购物者i进程（解法一）：,P（S）；P（S）；P（mutex）；P（mutex1）；从入口处进超市，并取一只篮子；同左；V（mutex）；V（mutex1）；进超市内选购商品；同左；P（mutex）；P（mutex2）；到出口结帐，并归还篮子；同左；V（mutex）；V（mutex2）；从出口离开超市；同左；V（S）；V（S）；,94,购物者i进程（解法二）：,95,25、设与某资源相关联的信号量初值为3，当前值为1，若M表示该资源的可用个数，N表示等待该资源的进程数，则M，N分别是（）A、0，1B、1，0C、1，2D、2，0,27、进行PO和P1的共享变量定义及其初值为（）booleamflag2;intturn=0;flag0=false;flag1=false;若进行P0和P1访问临界资源的类C代码实现如下：voidp0()/进程p0voidp1()/进程p1while（TRUE）while（TRUE）flag1=TRUE;turn=1;flag0=TRUE;turn=0;Whileflag1则并发执行进程PO和P1时产生的情况是（）A、不能保证进程互斥进入临界区，会出现“饥饿”现象B、不能保证进程互斥进入临界区，不会出现“饥饿”现象C、能保证进程互斥进入临界区，会出现“饥饿”现象D、能保证进程互斥进入临界区，不会出现“饥饿”现象,管程的引入虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait(s)和signal(s)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具管程(monitors)。,100,2.3.4管程机制,管程（Monitor）代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，我们称之为管程。构成部分（1）管程的名称；（2）局部于管程内部的共享数据结构说明；（3）对该数据结构进行操作的一组过程；（4）对局部于管程内部的共享数据设置初始值的语句。是一种程序设计语言结构成分，它和信号量有同等的表达能力。,101,1.管程的定义,102,管程的语法如下：typemonitor-name=monitorvariabledeclarationsprocedureentryP1();beginend;procedureentryP2();beginend;procedureentryPn();beginend;begininitializationcode;end,管程的结构,103,conditionc1,wait(c1),conditioncn,wait(cn),局部数据,条件变量,过程1,过程k,出口,初始化代码,入口,管程,等待调用的进程队列,管程等待区域,管程的条件变量,条件变量当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量。同步原语wait,signal当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作引起调用进程阻塞。另一个进程可以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。,104,105,管程中对每个条件变量，都须予以说明，其形式为：Varx,y:condition。对条件变量的操作仅仅是wait和signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为X.wait和X.signal，其含义为：（1）X.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用X.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。（2）X.signal：正在调用管程的进程发现x条件发生了变化，则调用X.signal，重新启动一个因x条件被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s:=s+1操作，因而总会改变信号量的状态。,106,如果有进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了X.signal操作后，进程Q被重新启动，此时两个进程P和Q，如何确定哪个执行，哪个等待，可采用下述两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执一词。但是Hansan却采用了第一种处理方式。,107,2.5进程通信,2.5.1进程通信的类型,1.共享存储器系统(Shared-MemorySystem),基于共享数据结构的通信方式。(2)基于共享存储区的通信方式。,低级通信高级通信,108,2.消息传递系统(Messagepassingsystem)不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。,109,3.管道(Pipe)通信所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。,管道通信方式Pipe也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质,110,字符流方式写入读出先进先出顺序,111,为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。同步，指当写(输入)进程把一定数量(如4KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。确定对方是否存在，只有确定了对方已存在时，才能进行通信。,在UNIX、MS-DOS系统中，用户可以在命令级使用管道，这时管道是一个程序的标准输出和另一个程序的标准输入之间的连接，管道命令用符号“|”表示。如ls|wc-lpipe使用pipe系统调用的语法格式是：intpipe(filedes)intfiledes2；,112,实验：编写一个程序使用系统调用fork生成2个子进程，并使用系统调用pipe创建一管道，使得这2个子进程和父进程公用同一管道进行信息通信。#includestdio.hmain()inti，r，p1，p2，fd2；charbuf50，s50；pipe(fd)；/*父进程建立管道*/while(p1=fork()=-1)；/*创建子进程P1，失败时循环*/if(p1=0)/*由子进程P1返回，执行子进程P1*/lockf(fd1，1，0)；/*加锁锁定写入端*/sprintf(buf，childprocessP1issendingmessages!n)；printf(childprocessP1!n)；write(fd1，buf，50)；/*把buf中的50个字符写入管道*/sleep(5)；/*睡眠5秒，让父进程读*/lockf(fd1，0，0)；/*释放管道写入端*/exit(0)；/*关闭P1*/,113,else/*从父进程返回，执行父进程*/while(p2=fork()=-1)；/*创建子进程P2，失败时循环*/if(p2=0)/*从子进程P2返回，执行P2*/lockf(fd1，1，0)；/*锁定写入端*/sprintf(buf，childprocessP2issendingmessagesn)；printf(childprocessP2!n)；write(fd1，buf，50)；/*把buf中字符写入管道*/sleep(5)；/*睡眠等待*/lockf(fd1，0，0)；/*释放管道写入端*/exit(0)；/*关闭P2*/wait(0)；if(r=read(fd0，s，50)=-1)printf(cantreadpipen)；elseprintf(%sn,s)；wait(0)；if(r=read(fd0，s，50)=-1)printf(cantreadpipen)；elseprintf(%sn,s)；exit(0)；,114,115,2.5.2消息传递通信的实现方法,1.直接通信方式这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：Send(Receiver,message);发送一个消息给接收进程；Receive(Sender,message);接收Sender发来的消息；例如，原语Send(P2,m1)表示将消息m1发送给接收进程P2;而原语Receive(P1，m1)则表示接收由P1发来的消息m1。,116,在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：Receive(id,message);,117,我们还可以利用直接通信原语，来解决生产者-消费者问题。当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。生产者-消费者的通信过程可分别描述如下：,repeatproduceaniteminnextp;send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);consumetheiteminnextc;untilfalse;,118,2.间接通信方式,(1)信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱，还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。(2)消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。Send(mailbox,message);将一个消息发送到指定信箱；Receive(mailbox,message);从指定信箱中接收一个消息；,119,信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。1)私用信箱用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。当拥有该信箱的进程结束时，信箱也随之消失。,120,2)公用信箱它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。3)共享信箱它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。,121,在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系：(1)一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。(2)多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/serverinteraction)。(3)一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。(4)多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。,122,2.5.3消息传递系统实现中的若干问题,1.通信链路(communicationlink)为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是：由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除链路。这种方式主要用于计算机网络中。第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。,123,根据通信链路的连接方法，又可把通信链路分为两类：点点连接通信链路，这时的一条链路只连接两个结点(进程)；多点连接链路，指用一条链路连接多个(n2)结点(进程)。根据通信方式的不同，则又可把链路分成两种：单向通信链路，只允许发送进程向接收进程发送消息；双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。,124,2.消息的格式,在某些OS中，消息是采用比较短的定长消息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。在有的OS中，采用另一种变长的消息格式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。,125,3.进程同步方式,发送进程阻塞、接收进程阻塞。(2)发送进程不阻塞、接收进程阻塞。(3)发送进程和接收进程均不阻塞。,126,2.5.4消息缓冲队列通信机制,1.消息缓冲队列通信机制中的数据结构(1)消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：typemessagebuffer=recordsender;发送者进程标识符size;消息长度text;消息正文next;指向下一个消息缓冲区的指针end,127,(2)PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCB中应增加的数据项可描述如下：typeprocesscontrolblock=recordmq;消息队列队首指针mutex;消息队列互斥信号量sm;消息队列资源信号量end,128,2.发送原语发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，见图2-12所示，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源，故在执行insert操作的前后，都要执行wait和signal操作。,129,图2-12消息缓冲通信,130,proceduresend(receiver,a)begingetbuf(a.size,i);根据a.size申请缓冲区；i.sender=a.sender;将发送区a中的信息复制到消息缓冲区之中；i.size=a.size;i.text=a.text;i.next=0;getid(PCBset,receiver.j);获得接收进程内部标识符；wait(j.mutex);insert(j.mq,i);