进程管理44课件

进程的同步与通信1进程互斥2信号量和Ｐ、Ｖ操作3进程同步4经典的进程同步问题5进程通信要求：掌握进程同步与互斥，灵活运用信号量描述同步与互斥问题。3/9/20231第二章进程管理1.1互斥的基本概念与时间有关的错误:飞机订票系统中，两个终端，运行T1、T2进程

T1:T2: ...... Read(x);Read(x); ifx>=1thenifx>=1then x:=x-1;x:=x-1; write(x);write(x); ......3/9/20232第二章进程管理

同步：对于进程操作的时间顺序所加的某种限制，如操作Ａ应在Ｂ之前执行。互斥：同步的特例，多个操作决不能同时执行，

如：操作Ａ和操作Ｂ不能在同时执行。3/9/20233第二章进程管理临界区(criticalsection)：临界段，在每个程序中，访问临界资源的那段程序。 注意：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。3/9/20235第二章进程管理解决互斥的准则1、空闲让进2、忙则等待3、有限等待4、让权等待3/9/20236第二章进程管理1.2软件方法解决进程互斥

假如有两个进程Pi和Pj，它们共享一个临界资源R。如何用软件方法使进程Pi和Pj能互斥地访问R。下面介绍四个算法。3/9/20237第二章进程管理进程Pi:RepeatWhileturn<>idono_op;Criticalsectionturn:=j;

OthercodeUntilfalse;

该算法可确保每次只允许一个进程进入临界区。但它强制两个进程轮流进入。如当Pi退出时将turn置为j，以便

Pj能进入，但Pj暂不需要进入，而这时Pi又需要进入时，它无法进入。违反：空闲让进3/9/20239第二章进程管理算法2设varflag:array[0..1]ofboolean，flag[i]=true，表示进程Pi正在临界区内。flag[i]=false，表示进程Pi不在临界区内。flag[j]=true，表示进程Pj正在临界区内。flag[j]=false，表示进程Pj不在临界区内。3/9/202310第二章进程管理Pi进程：RepeatWhileflag[j]dono_op;

flag[i]:=true;

Criticalsectionflag[i]:=false;OthercodeUntilfalse;该算法可确保空闲让进。但当pi和pj都未进入时，它们各自的访问标志都为false。如果pi和pj几乎同时要求进入，它们都发现对方的标志为false，于是都进入了。问题在于：当进程Pi观察到进程Pj的标志为false后，便将自己的标志由false改为true，而正是在这两步之间，可能发生进程切换。当Pj运行时，它会观察到Pi的标志为false，从而可以将自己的标志设为true，并进入临界区。3/9/202311第二章进程管理Pi进程：Repeat

flag[i]:=true;//希望进入While(flag[j])dono_op;Criticalsectionflag[i]:=false;OthercodeUntilfalse; 该算法又出现新问题。它可能造成谁也不能进入。如，当pi和pj几乎同时都要进入，分别把自己的标志置为true，都立即检查对方的标志，发现对方为true.最终谁也不能进入。3/9/202313第二章进程管理算法4（正确算法）组合算法1、3为每一进程设标志位flag[i]，当flag[i]=true时，表示进程pi要求进入，或正在临界区中执行。再设一个变量turn，用于指示允许进入的进程编号。3/9/202314第二章进程管理进程为了进入先置flag[i]=true，并置turn为j，表示应轮到pj进入。接着再判断flag[j]andturn=j的条件是否满足。若不满足则可进入。或者说，当flag[j]=false或者turn=i时，进程可以进入。前者表示pj未要求进入，后者表示仅允许pi进入。3/9/202315第二章进程管理软件解法的缺点1.忙等待2.实现过于复杂，需要较高的编程技巧3/9/202317第二章进程管理3用原语实现进程互斥锁即操作系统中的一标志位，０表示资源可用，１表示资源已被占用。用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。通常锁用w表示，上锁开锁原语分别用lock(w)、unlock(w)来表示。3/9/202318第二章进程管理上锁和开锁原语上锁原语lock(w)可描述为：L：if(w==1)gotoLelsew=1；上述上锁原语中存在忙等待。开锁原语unlock(w)可描述为：w=0；3/9/202319第二章进程管理改进的上锁原语3/9/202321第二章进程管理改进的开锁原语3/9/202322第二章进程管理1965年，由荷兰学者Dijkstra提出（P、V分别是荷兰语的test(proberen)和increment(verhogen)）一种卓有成效的进程同步机制最初提出的是二元信号量（互斥）后来推广到一般信号量（多值）（同步）P、V操作是原语2信号量及P、V操作3/9/202323第二章进程管理P操作P(s){s.value=s.value-1;if(s.value<0){ 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s.queue;}}3/9/202325第二章进程管理V操作V(s){s.value=s.value+1;if(s.value<=0){唤醒相应等待队列s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列}}3/9/202326第二章进程管理用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)3/9/202329第二章进程管理信号量及P、V操作讨论对两个并发进程，互斥信号量MUTEX仅取1、0和－1三个值若MUTEX＝1表示没有进程进入临界区若MUTEX＝0表示有一个进程进入临界区若MUTEX＝－1表示一个进程进入临界区，另一个进程等待进入。3/9/202330第二章进程管理1)信号量的物理含义： S>0表示有S个资源可用 S=0表示无资源可用 S<0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源V(S)：表示释放一个资源。信号量的初值应该大于等于0信号量及P、V操作讨论3/9/202331第二章进程管理2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要信号量及P、V操作讨论3/9/202332第二章进程管理3）P、V操作的优缺点优点：简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂。信号量及P、V操作讨论3/9/202333第二章进程管理3进程同步同步问题可分为两类：

保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步。

3/9/202334第二章进程管理合作进程的执行次序若干个进程为了完成一个共同任务而并发执行，有些进程之间有次序的要求，有些进程之间没有次序的要求为了描述方便，可以用一个图来表示进程集合的执行次序。3/9/202335第二章进程管理例如图，试用信号量实现这三个进程的同步。

设有两个信号量SB、SC，初值均为０Pa：Pb：Pc：…P(SB);

P(SC)

V(SB);……V(SC);3/9/202336第二章进程管理【思考题1】如图，试用信号量实现这三个进程的同步。3/9/202337第二章进程管理解设有两个信号量S1、S2，初值均为０P1：P2：P3：……P(S1)

V(S1);V(S2);P(S2)…3/9/202338第二章进程管理【思考题2】如图，试用信号量实现这6个进程的同步3/9/202339第二章进程管理解设有5个信号量S2、S3、S4、S5、S6，初值均为０P1：P2：P3：…P(S2);P(S3)

V(S2);……V(S3)；V(S4);V(S6);V(S5)P4：P5：P6：P(S4);P(S5);P(S6);…P(S5);P(S6);……V(S5)；V(S6);

3/9/202340第二章进程管理【思考题】司机进程：while(1){启动车辆正常驾驶到站停车}…售票员进程：while(1){关门售票开门}…用P.V操作解决司机与售票员的问题3/9/202341第二章进程管理解设有两个信号量S1，S2，初值均为0。司机进程：while(1){

P(S1)启动车辆正常驾驶

到站停车

V(S2)}…售票员进程：while(1){关门

V(S1)售票

P(S2)开门}…3/9/202342第二章进程管理共享缓冲区的进程的同步设某计算进程CP和打印进程IOP共用一个单缓冲区，CP进程负责不断地计算数据并送入缓冲区T中，IOP进程负责不断地从缓冲区T中取出数据去打印。3/9/202343第二章进程管理分析通过分析可知，CP、IOP必须遵守以下同步规则：

当CP进程把计算结果送入缓冲区时，IOP进程才

能从缓冲区中取出结果去打印;当IOP进程把缓冲区中的数据取出打印后，CP进程才能把下一个计算结果送入缓冲区3/9/202344第二章进程管理解为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。两个进程的同步可以描述如下：3/9/202345第二章进程管理【思考题】1.用P.V操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyputst3/9/202346第二章进程管理get：while（1）{

P(Sin）;将数放入S;

V(Sout);}copy：while（1）{

P(Sout）;

P(Tin）;将数从S取出放入T;

V(Tout);V(Sin);}put：while（1）{

P(Tout）;将数从T取走;

V(Tin);}3/9/202347第二章进程管理【思考题】桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。 试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。3/9/202348第二章进程管理解 设置三个信号量S,So,Sa，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。3/9/202349第二章进程管理Father(){while(1){

p(S);

将水果放入盘中;if(是桔子)v(So);elsev(Sa);}}Son(){while(1){p(So)取桔子

v(S);吃桔子;}}Daughter(){while(1){p(Sa)取苹果

v(S);吃苹果;}}3/9/202350第二章进程管理2.4经典的进程同步问题

4.1生产者/消费者问题

4.2读者/写者问题

4.3哲学家进餐问题

3/9/202351第二章进程管理2.4.1生产者/消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。3/9/202352第二章进程管理问题描述通过一个有界缓冲区把一群生产者P1,P2…,Pm，和一群消费者Q1,Q2,…,Qn联系起来。只要缓冲区未满，生产者就可以把产品送入缓冲区;只要缓冲区未空，消费者就可以从缓冲区中取走物品。3/9/202353第二章进程管理图3/9/202354第二章进程管理问题分析设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值为０。M个生产者和N个消费者要对有界缓冲区进行操作。而有界缓冲区是一个临界资源，必须互斥使用，设置一个互斥信号量mutex，其初值为１。3/9/202355第二章进程管理用一个数组来表示具有n个(0，1，…，n-1)缓冲区的缓冲池，整型变量counter，其初始值为0。每当生产者进程向缓冲中投放一个消息后，使counter加1；每当消费者进程从中取走一个消息时，counter减1。3/9/202356第二章进程管理输入指针in：指示下一个可投放消息的缓冲区，初值为1，每当生产投放一个消息后，in指针加1，即in:=(in+1)modn，输出指针out指示下一个可获取消息的缓冲区，初值为1，每当取走一个消息后，out指针加1，即out：＝(out+1)modn。缓冲池满：(in+1)modn＝out缓冲池空：in=out3/9/202357第二章进程管理问题的解Q：j=0;while(1){

P(S2);P(mutex);从Buffer[j]取产品;j=(j+1)%n;

V(mutex);

V(S1);消费产品;};P：

i=0;

while(1){

生产产品;

P(S1);

P(mutex);往Buffer[i]放产品;i=(i+1)%n;

V(mutex);

V(S2);

};3/9/202358第二章进程管理【思考题】有一个仓库，可以存放A和B两种产品，但要求：（1）

每次只能存入一种产品（A或B）（2）

－N＜A产品数量－B产品数量＜M。其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。提示：设两个信号量Sa、SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量3/9/202359第二章进程管理解设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。3/9/202360第二章进程管理

B产品入库进程：j=0;while(1){

P(Sb);P(mutex);B产品入库

V(mutex);V(Sa);消费产品;};A产品入库进程：

i=0;

while(1){

生产产品;

P(Sa);

P(mutex);A产品入库

V(mutex);

V(Sb);

};3/9/202361第二章进程管理2.4.3读者/写者问题

有两组并发进程:读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作3/9/202362第二章进程管理第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待3/9/202363第二章进程管理第一类读者写者问题的解法设有两个信号量w=1，mutex=1另设一个全局变量readcount=0w用于读者和写者、写者和写者之间的互斥readcount表示正在读的读者数目mutex用于对readcount这个临界资源的互斥访问3/9/202364第二章进程管理读者：while(1){P(mutex);readcount++;if(readcount==1)P(w);V(mutex);读P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};写者：while(1){P(w);写V(w);};3/9/202365第二章进程管理【思考题】写优先修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。提示，增加一个信号量，用于在写者到达后封锁后续的读者3/9/202366第二章进程管理解

增加一个信号量s，初值为1读者：while(1){P(s);P(mutex);readcount++;if(readcount==1)P(w);V(mutex);

V(s);读P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};写者：while(1){

P(s);

P(w);写V(w);

V(s);};3/9/202367第二章进程管理2.4.2哲学家就餐问题有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子3/9/202368第二章进程管理设fork[5]为5个信号量，初值为均1Philosopheri：while(1){思考；P(fork[i]);P(fork[(i+1)%5])；进食；V(fork[i]);V(fork[(i+1)%5])；}解3/9/202369第二章进程管理以上解法会出现死锁为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之

分析3/9/202370第二章进程管理使用一个数组state来跟踪一个哲学家是在吃饭、思考还是正在试图拿筷子。一个哲学家只有在两个邻居都不在进餐时才允许转移到进餐状态。第i位哲学家的邻居由宏LEFT和RIGHT定义，换言之，若i为2，则LEFT为1，RIGHT为3。3/9/202371第二章进程管理信号量集——AND型信号量集AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作

AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal3/9/202372第二章进程管理

Swait(S1,S2,…,Sn) //P原语；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理；for(i=1;i<=n;++i)-–Si;//注：与P的处理不同，这里是在确信可满足//资源要求时，才进行减1操作；break;}else{ //某些资源不够时的处理；

调用进程进入第一个小于1信号量的等待队列Sj.queue;

阻塞调用进程;}3/9/202373第二章进程管理

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源；for(在Si.queue中等待的每一个进程P)//检查每种资源的等待队列的所有进程；{从等待队列Si.queue中取出进程P;

3/9/202374第二章进程管理

if(判断进程P是否通过Swait中的测试)//注：与signal不同，这里要进行重新判断；{//通过检查（资源够用）时的处理；

进程P进入就绪队列;}else{//未通过检查（资源不够用）时的处理；

进程P进入某等待队列；}}}}3/9/202375第二章进程管理一般“信号量集”一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理

一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。3/9/202376第二章进程管理进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si>=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);3/9/202377第二章进程管理一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1)表示互斥信号量Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）3/9/202378第二章进程管理2.5管程机制 Hoare（1974）和BrinchHansen（1975）提出了一种高级的同步原语，称为管程(monitor)。一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程外的过程中直接访问管程内的数据结构。3/9/202379第二章进程管理在OS中引入管程的目的是为了更简便、更可靠地解决进程之间的同步、互斥问题。在未引入管程之间，进程间的同步、互斥问题是由程序员处理的。例如，在临界区的前后插入P、V操作。但是，由程序员处理同步、互斥问题有可能引入种种人为的错误。管程主要是管理对共享数据的操作和使用，即把对共享数据互斥使用的控制这一任务从程序员身上，交由编译程序去处理，这样既方便了编程，又不会产生人为的同步、互斥上的错误。3/9/202380第二章进程管理管程机制 管程有一个很重要的特性，任一时刻管程中只能有一个活跃进程。 使管程能有效地完成互斥，只要把临界区代码放在管程中即可。 管程提供了一种实现互斥的简便途径，但这还不够，还需要一种办法以使得进程在无法继续运行时被阻塞。 例如，在生产者－消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放到管程的过程中，但是生产者在发现缓冲区满的时候如何阻塞?3/9/202381第二章进程管理 解决方法在于引入条件变量(conditionvariables)，及相关的两个操作：WAIT和SIGNAL。当一个管程过程发现它无法继续时（例如，生产者发现缓冲区满），它在某些条件变量上执行WAIT，如full。这个动作引起调用进程阻塞。它也允许另一个先前被挡在管程之外的进程现在进入管程。

3/9/202382第二章进程管理另一个进程，如消费者，可以通过对其伙伴正在其上等待的一个条件变量执行SIGNAL来唤醒正在睡眠的伙伴进程。为避免管程中同时有两个活跃进程，我们需要一条规则来通知在SIGNAL之后该怎么办。Hoare建议让新唤醒的进程运行，而挂起另一个进程。BrinchHansen则建议要求执行SIGNAL的进程必须立即退出管程。换言之，SIGNAL语句只可能作为一个管程过程的最后一条语句。我们将采纳BrinchHansen的建议，因为它在概念上更简单，并且更容易实现。如果在一个条件变量上正有若干进程等待，则对该条件变量执行SIGNAL操作，调度程序将在其中选择一个使其恢复运行。3/9/202383第二章进程管理使用管程解决生产者－消费者问题数据结构monitorProducerConsumerconditionfull，empty;integercount;procedureenter;beginifcount=Nthenwait（full）;enter_item;count：=count+1;ifcount=1thensignal（empty）end;3/9/202384第二章进程管理procedureremove;beginifcount=0thenwait（empty）;remove_item;count：=count-1;ifcount=N-1thensignal（full）;end;count：=0;endmonitor;3/9/202385第二章进程管理procedureproducer;begin whiletruedo begin produce-item; ProducerConsumer.enter endend3/9/202386第二章进程管理procedureconsumer;begin whiletruedo begin ProducerConsumer.remove; consume-item; endend3/9/202387第二章进程管理2.6进程通信所谓进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。如果要在进程间传递大量信息则要用Send/Receive原语（高级通讯原语）3/9/202388第二章进程管理2.6.1进程通信类型1、共享存储器系统

2、消息传递系统

3、管道通信(共享文件方式)3/9/202389第二章进程管理1、共享存储器系统基于共享数据结构的通信方式诸进程公用某些数据结构，进程通过它们交换信息。如生产者-消费者问题中的有界缓冲区3/9/202390第二章进程管理基于共享存储区的通信方式高级通信，在存储器中划出一块共享存储区，进程在通信前，向系统申请共享存储区中的一个分区，并指定该分区的关键字，若系统已经给其它进程分配了这样的分区，则将该分区的描述符返回给申请者。接着，申请者把获得的共享存储分区连接到本进程上，此后可读写该分区。

以上两种方式的同步互斥都要由进程自己负责。3/9/202391第二章进程管理2、消息传递系统 进程间的数据交换以消息为单位，程序员利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节，简化了通信程序编制的复杂性。因而得到广泛应用。3/9/202392第二章进程管理消息传递系统可分为：直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。 也称为消息缓冲通信3/9/202393第二章进程管理间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。 也称信箱通信。在网络中称为电子邮件系统。3/9/202394第二章进程管理3、管道通信所谓管道，是指用于连接一个读进程和一个写进程的文件，称pipe文件。向管道提供输入的进程（称写进程），以字符流的形式将大量数据送入管道，而接受管道输出的进程（读进程）可从管道中接收数据。该方式首创于UNIX，它能传送大量数据，被广泛采用。

发送进程接收进程字符流方式写入读出先进先出顺序3/9/202395第二章进程管理2.6.2消息缓冲通信的实现在操作系统空间设置一组缓冲区。当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系统。操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行。3/9/202396第二章进程管理在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管中断进入操作系统。由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行3/9/202397第二章进程管理PCB......Send(R,M)......SIZE:消息长度TEXT:消息正文......消息链指针............Receive(N)......SIZE:消息长度TEXT:消息正文......M:N:接收进程R发送进程S消息消息消息......图示3/9/202398第二章进程管理typemessageBuffer=recordsender;//发送者IDsize;//消息长度text;//消息正文next;//消息队列指针end消息缓冲区结构3/9/202399第二章进程管理PCB中有关通信的数据项typePCB=record…mq;//消息队列首指针mutex;//消息队列互斥信号量sm;//消息队列资源信号量end3/9/2023100第二章进程管理send（R,M）begin

在OS中分配M.size大小的缓冲区t;将M中的内容复制到t;得到进程R的PCB的指针q；P(q.mutex); 将t挂到队列q.mq队尾；

V(q.mutex);

V（q.sm);end用P、V操作来实现Send原语3/9/2023101第二章进程管理Receive(N）begin得到本进程PCB的指针q；P(q.sm);P(q.mutex);从q.mq队首取下一个缓冲区t；

V(q.mutex);将t的内容复制到N，并释放tend用P、V操作来实现Receive原语3/9/2023102第二章进程管理用消息传递解决生产者－消费者问题#defineN100 /*缓冲区中的槽数*/voidproducer(void){intitem;messagem; /*消息缓冲区*/while(TRUE){ produce-item(&item); /*产生数据*/ receive(consumer,&m); /*等待空消息*/ build-message(&m,item);/*构造消息供发送*/ send(consumer,&m); /*向消费者发送*/}}3/9/2023103第二章进程管理voidconsumer(void){intitem,i;messagem; /*消息缓冲区*/for(i=0;i<N;i++)send(producer,&m);/*发送N条空消息*/while(TRUE){ receive(producer,&m); /*收取一条消息*/ extract-item(&m,&item); /*从消息提取数据*/ send(producer,&m); /*回送空消息作为应答*/ consume-item(item); /*使用数据项*/}}3/9/2023104第二章进程管理信箱通信的实现信箱使用规则若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被唤醒若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被唤醒3/9/2023105第二章进程管理Send实现send（MailBox，M）：把信件M送到指定的信箱MailBox中步骤：查找指定信箱MailBox；若信箱未满，则把信件M送入信箱且唤醒“等信件”者；若信箱已满置发送信件进程为“等信箱”状态；3/9/2023106第二章进程管理Receive实现receive（MailBox，X）：从指定信箱MailBox中取出一封信，存放到指定的地址X中步骤：查找指定信箱MailBox；若信箱中有信，则取出一封信存于X中且唤醒“等信箱”者；若信箱中无信件则置接收信件进程“等信件”状态；3/9/2023107第二章进程管理把信箱分为以下三类： 私用信箱。 用户进程为自己建立的，并作为该进程的一部分。 信箱的拥有者有权从信箱中读取消息，其他用户则只能将消息发送到该信箱中。 私用信箱可采用单向通信链路实现。 当拥有该信箱的进程结束时，信箱也随之消失。

其

他

用

户

信箱

进程

3/9/2023108第二章进程管理公用信箱由操作系统创建，提供给系统中的所有核准进程使用。核准进程可使用该信箱收、发消息。公用信箱在系统运行期间始终存在。公用信箱应采用双向通信链路的信箱来实现。3/9/2023109第二章进程管理共享信箱 某进程在创建时或创建后，指明它是可供共享的，同时指出共享进程(用户)的名字。 拥有者和共享者，都有权从信箱中取走发送给自己的消息。

3/9/2023110第二章进程管理在利用信箱通信的发送进程和接收进程之间，存在下述的四种关系：一对一关系。发送进程和接收进程之间建立一条专用的通信链路进行通信，不受其它进程的影响。多对一关系。又称为客户／服务器交互，提供服务的进程与多个用户进程之间进行交互。一对多关系。一个发送进程与多个接收进程进行交互，发送进程可用广播形式，向接收者发送消息。多对多关系。建立一个公用信箱；让多个进程都能向信箱中投递消息，也可从信箱中取走属于自己的消息。3/9/2023111第二章进程管理2.6.3消息传递系统实现中的几个问题通信链路为了在发送进程和接收进程之间能进行通信，必须在它们之间建立一条通信链路。有两种方式建立通信链路：显式建立链路。由发送进程在通信之前，用“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也应用显式方式拆除链路。这种方式主要用于计算机网络中。隐式建立链路。利用系统提供的发送命令(原语)时，系统会自动地为之建立一条链路。主要用于单机系统中。3/9/2023112第二章进程管理根据通信链路的连接方法，又可把通信链路分为：点——点连接通信链路。一条链路只连接两个结点(进程)；多点连接链路。指用一条链路连接多个(M＞2)结点(进程)。根据通信方式的不同，又可把链路分为：单向通信链路。只允许发送进程向接收进程发送消息；双向链路。3/9/2023113第二章进程管理根据通信链路的容量的不同也可把链路分成：无容量通信链路。没有缓冲区，不能暂存任何消息；有容量通信链路。设置了暂存消息的缓冲区，缓冲区数目愈多，通信链路的容量愈大。3/9/2023114第二章进程管理进程同步方式（完成消息的发送或接收之后）发送进程阻塞、接收进程阻塞主要用于进程之间紧密同步、发送进程和接收进程之间无缓冲区时。两个进程平时都处于阻塞状态，直到有消息传递时。这种同步方式称为汇合。送进程不阻塞、接收进程阻塞平时发送进程不阻塞，而接收进程则处于阻塞状态，直到发送进程发来消息时被唤醒。应用得最广。例如：在服务器上的服务进程，平时都处于阻塞状态，直到有请求服务的消息到达时。3/9/2023115第二章进程管理发送进程与接收进程均不阻塞平时发送进程和接收进程都在忙于自己的事情，仅当发生某个事件，使它无法继续运行时，才把自己阻塞起来等待。例如，在发送进程和接收进程之间联系着一个最多可接纳N个消息的消息队列时。只有消息队列中的消息数目为N个时，发送进程才会阻塞；消息数为0时，接收进程才会阻塞。3/9/2023116第二章进程管理习题

进程A1、A2，。。。An1通过m个缓冲区向进程B1、B2、。。。Bn2不断发送消息。发送和接收工作遵循下列规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度（2）对每个消息，B1，B2，Bn2都须各接收一次，读入各自的数据区内（3）m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。试用P、V操作组织正确的发送和接收工作。3/9/2023117第二章进程管理提示：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。Sin[n2]=mSout[n2]=0;3/9/2023118第二章进程管理解先将问题简化：设缓冲区的大小为1有一个发送进程A1有二个接收进程B1、B2设有信号量Sin[1]、Sin[2]初值为1设有信号量Sout[1]、Sout[2]初值为03/9/2023119第二章进程管理Bi：while(1){

P(Sout[i]);

从缓冲区取数V(Sin[i]);}A1:

while(1){

P(Sin[1]);

P(Sin[2]);

将数据放入缓冲区 V(Sout[1]);V(Sout[2]);

}3/9/2023120第二章进程管理设缓冲区的大小为m有一个发送进程A1有二个接收进程B1、B2设有信号量Sin[1]、Sin[2]初值为m设有信号量Sout[1]、Sout[2]初值为03/9/2023121第二章进程管理Bi：while(1){

P(Sout[i]);

P(mutex); 从缓冲区取数

V(mutex);V(Sin[i]);};A1:

while(1){

P(Sin[1]);

P(Sin[2]);

P(mutex); 将数据放入缓冲区

V(mutex); V(Sout[1]);V(Sout[2]);

}3/9/2023122第二章进程管理设缓冲区的大小为m有n1个发送进程A1….An1有n2个接收进程B1…Bn2设有n2个信号量Sin[n2]初值均为m设有n2个信号量Sout[n2]初值均为03/9/2023123第二章进程管理Bi：while(1){

P(Sout[i]);

P(mutex);

从缓冲区取数

V(mutex);V(Sin[i]);};Aj:while(1){for(i=1;i<=n2;i++)

P(Sin[i]);

P(mutex); 将数据放入缓冲区

V(mutex); for(i=1;i<=n2;i++) V(Sout[2]);}3/9/2023124第二章进程管理oZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUm$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYpx-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A