第三章进程同步、通信与死锁

第3章进程同步、通信与死锁3.1并发进程3.2临界区管理3.3经典的进程同步问题3.4管程和进程通信3.6死锁顺序程序执行、并发程序执行

输入：计算：输出：

t0t1t2t3t4t5t6ΔttI1三个程序并发执行的前驱图I2I3C1C2C3P1P2P3时间:5个Δt并行并行并行前驱关系执行顺序顺序程序设计(2)顺序程序设计具有如下的特点：程序执行的顺序性程序环境的封闭性程序执行结果的确定性计算过程的可再现性顺序程序设计(3)顺序程序设计的例

while(1){input，process，output}78输入机处理器磁带机130150228280300378430450时间处理器利用率：52/(78+52+20)≈35%

顺序程序设计(4)

顺序程序设计串行工作

i1p1o1i2p2o2．．．顺序程序设计(5)

顺序程序设计的优缺点顺序程序设计的顺序性、封闭性、确定性和再现性给程序的编制、调试带来很大方便，其缺点是计算机系统效率不高。进程的并发性(1)进程执行的并发性：一组进程的执行在时间上是重叠的并发性举例：例如：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行进程的并发性(2)从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态，从微观上看，任一时刻仅有一个进程在处理器上运行。进程的并发性(3)并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。无关的并发进程(1)并发进程分类：无关的，交往的。无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。无关的并发进程(2)

并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。

无关的并发进程(3)

Bernstein条件：

R(pi)={a1,a2,…an}，程序pi在执行期间引用的变量集

W(pi)={b1,b2,…bm}，程序pi在执行期间改变的变量集若两个程序的变量集交集之和为空集：

R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}

则并发进程的执行与时间无关。无关的并发进程(4)

例如，有如下四条语句：

S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1

于是有：R(S1)={x,y},R(S2)={z}，R(S3)={a,b}，R(S4)={c}；W(S1)={a},W(S2)={b}，W(S3)={c}，W(S4)={w}。

S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。无关的并发进程(5)

两个无关的进程并发执行的例处理器利用率：(52+42)/(78+52+20)≈63%78输入机处理器磁带机130150228280300378430450时间磁带机打印机2062170320交往的并发进程(1)交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。交往的并发进程(2)并发程序设计的例子

while(1){input，send}while(1){receive，process，send}while(1){receive，output}处理器利用率：（52*n）/（78*n+52+20）=67%78输入机处理器磁带机130150228306208286384364时间交往的并发进程(3)

并行工作

i1p1ipoo1i2p2o2i3p3o3t1t2t3进程时间交往的并发进程(4)

并发程序设计并发程序设计是：把一个程序设计成若干个可同时执行的程序模块的方法。并发程序设计的特征：并行性、共享性、制约性、交互性。

交往的并发进程(5)

并发程序设计的优点•对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。•对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。•简化了程序设计任务。

交往的并发进程(6)

采用并发程序设计的目的充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。交往的并发进程(7)

与时间有关的错误对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。与时间有关错误的表现形式：结果不唯一永远等待

（结果不唯一）机票问题processTi(i=1,2) varXi:integer;begin {按旅客定票要求找到Aj}；

Xi:=Aj; ifXi>=1thenbeginXi:=Xi-1;Aj:=Xi;{输出一张票}；end else{输出票已售完}；end;（永远等待）内存管理问题procedureborrow(varB:integer)beginifB>xthen{申请进程进入等待队列等主存资源}x:=x-B;{修改主存分配表，申请进程获得主存资源}

end;procedurereturn(varB:integer)beginx:=x+B;{修改主存分配表}{释放等主存资源的进程}

end;一.进程同步的基本概念1.两种形式的制约关系2.临界资源、临界区3.同步机制应遵循的规则二.信号量机制与P、V操作1.整型信号量2.记录型信号量返回目录3.2进程同步进程的交往：竞争与协作(1)

并发进程之间的竞争关系进程的互斥系统中的多个进程之间彼此无关并发进程之间的协作关系进程的同步系统中的多个进程之间彼此相关

资源竞争的两个控制问题：一个是死锁(Deadlock)问题，一个是饥饿(Starvation)问题，既要解决饥饿问题，又要解决死锁问题。

进程互斥(MutualExclusion)进程互斥：进程之间通过竞争系统某些资源产生的关系称为间接制约关系，它们之间是通过某种“媒介”而产生了“关系”。(间接制约关系)进程互斥指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他进程必须等待，直到占有资源的进程释放该资源。返回第二种是协作关系•

进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。进程同步：进程之间为了共同完成某项任务，或者协作完成，有意识彼此相互“交换信息”。如前分别将I、C和P都看成是进程。(直接制约关系)

返回同步互斥进程-进程进程-资源-进程时间次序上受到某种限制竞争到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间通讯制约例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间例：交通十字路口，单轨火车的拨道岔同步与互斥的比较返回2、临界资源、临界区临界资源

(criticalresource）

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。临界区（互斥区）：criticalsection

在进程中涉及到临界资源的程序段叫临界区简称CS多个进程的临界区称为相关临界区2、临界资源、临界区

进程的互斥（间接作用）…a:=a+1print(a)…P1互斥…a:=a-1print(a)…P2互斥…Ifa<0thena:=a+1elsea:=a-1…P3互斥2、临界资源、临界区程序段1共享变量程序段2程序段3例：有两个进程A和B，它们共享一个变量x，且两个进程按以下方式对变量X进行访问和修改:

其中R1和R2为处理机中的两个寄存器。A与B均对X+1，即X+2。若按另一顺序对变量进行修改：结果x只加了1。A:R1=X;B:R2=X;A:R1=R1+1;X=R1;B:R2=R2+1;X=R2;A:R1=X;R1=R1+1;X=R1;B:R2=X;R2=R2+1;X=R2;（1）变量X必需按临界资源处理。（2）每个进程中访问临界资源的那段代码称为临界区2、临界资源、临界区实现各进程互斥进入临界区进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entrysection)。在临界区后面加上一段称为退出区(exitsection)的代码While(1){

进入区代码;

临界区代码;

退出区代码;

其余代码;}进入区临界区退出区剩余区要进入临界区的若干进程必须满足如下三个条件：（1）一次只允许一个进程进入临界区（2）如果有进程在临界区,试图进入此临界区的其他进程等待（3）进入临界区的进程要在有限的时间内退出,以便让等待队列中的一个进程进入.解决临界区（互斥）问题的原则：

2、临界资源、临界区3、同步机制应遵循的规则有空让进(空闲让进）:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。互斥（忙则等待）:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。一、进程同步的基本概念算法可行:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态;当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。择一而入:一次只能进入一个一、进程同步的基本概念3、同步机制应遵循的规则返回解决临界区（互斥）问题的方法：

1.软件2．利用硬件方法解决进程互斥问题（1）禁止中断（2）专用机器指令3．信号量及原语是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomicaction），即一个操作中的所有动作要么全做，要么全不做。执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。临界区管理的尝试(1)inside1,inside2:Booleaninside1:=false;/*P1不在其临界区内*/inside2:=false;/*P2不在其临界区内*/cobeginprocessP1Begin whileinside2dobeginend;*** inside1:=true;

临界区; inside1:=false;end;processP2begin whileinside1dobeginend; inside2=true;

临界区; inside2:=false;end;coend临界区管理的尝试(2)inside1,inside2:boolean;inside1:=false;/*P1不在其临界区内*/inside2:=false;/*P2不在其临界区内*/cobeginprocessP1begin inside1:=true; whileinside2dobeginend;

临界区; inside1:=false;end;processP2begin inside2:=true; whileinside1dobeginend;

临界区; inside2:=false;end;coendPeterson算法(1)

varinside:array[1..2]ofboolean;turn:integer;turn:=1or2;inside[1]:=false;/*P1不在其临界区内*/inside[2]:=false;/*P2不在其临界区内*/Peterson算法(2)

cobeginprocessP1begin inside[1]:=true; turn:=2; while(inside[2]andturn=2)dobeginend;

临界区; inside[1]:=false;end;Peterson算法(3)

processP2begin inside[2]:=true; turn:=1; while(inside[1]andturn=1)dobeginend;

临界区; inside[2]:=false;end;coendPeterson算法(4)

用对turn的置值和while语句来限制每次只有一个进程进入临界区；进程执行完临界区程序后，修改inside[i]状态使等待进入临界区的进程可在有限时间内进入。算法满足临界区管理的三个条件。实现临界区管理的硬件设施

关中断测试并建立指令对换指令测试并建立指令(1)

TS指令的处理过程:

TS(x):若x=true，则x:=false；

returntrue；否则returnfalse；

TS指令管理临界区时，可把一个临界区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。测试并建立指令(2)s:boolean;s:=true;beginprocessPi(){/*i=1,2,…,n*/ while(!TS(S))；//上锁

{临界区}; s:=true；//开锁}coend;对换指令(1)

对换（Swap）指令的功能是交换两个字的内容：

Swap(a,b):

temp:=a;a:=b;b:=temp;对换指令(2)lock:boolean;lock:=false;processPi/*i=1,2,…,n*/pi:boolean;beginpi:=true;do{swap(lock,pi);}while(pi)；

{临界区}; swap(lock,pi);end;关中断实现互斥的最简单方法之一关中断方法的缺点返回三、信号量机制信号量机制是荷兰科学家E.W.Dijkstra在1965年提出的一种同步机制，也称为P、V操作。由最初的整型信号量发展为记录型信号量，进而发展为信号量集。整型信号量记录型信号量1、整型信号量整型信号量——非负整数，除了初始化外，只能通过两个原子操作wait和signal（P，V）来访问。wait和signal操作描述：

wait(S)：whileS0dono-op测试有无可用资源

S:=S-1;可用资源数减一个单位

signal(S):S:=S+1;主要问题：只要S0，wait操作就不断地测试（盲等），因而，未做到“让权等待”。

2、记录型信号量基本思想

1、设置一个代表资源数目的整型变量value（资源信号量）

2、设置一链表L用于链接所有等待的进程记录型信号量的数据结构

Typesemaphore=recordvalue:integer;L:listofprocess;end2、记录型信号量P、V操作

除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被称为P、V操作。

原子操作（atomicaction）或简称“原语”(primitive)：在执行上不可中断的操作。2、记录型信号量P、V操作定义P(s)/*=wait(s)）*/{s.value－－;if(s.value<0)block(s.queue)}该进程状态置为等待状态将该进程的PCB插入相的等待队列末尾s.queue;2、记录型信号量V(s)/*=signal(s)*/{s.value++;if(s.value<=0)wakeup(s.queue)}P、V操作定义唤醒相应等待队列s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列2、记录型信号量P、V操作含义信号量的物理含义：S>0表示有S个资源可用S=0表示无资源可用S<0则|S|表示S等待队列中的进程个数P、V操作的含义

P(S):表示申请一个资源

V(S)：表示释放一个资源。信号量的初值应≥0使用P,V操作实现互斥时应注意两点：①在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。②互斥信号量mutex的初值一般为1。三、信号量的应用利用信号量实现进程互斥Process1:while(true){

P(mutex);criticalsection;V(mutex);remaindersection;}while(true){

P(mutex);criticalsection;

V(mutex);remaindersection;}Process2:三、信号量的应用例:三个进程共用两个I/O缓冲区。解：设用信号量S表示共享资源，S初始值为2P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)三、信号量的应用利用信号量实现前驱关系P1P2三、信号量的应用设置一个信号量S，其初值为0,P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2三、信号量的应用Eg:设S1,S2,S3,S4为一组合作进程，其前趋图如图所示，用P、V操作实现其同步。

vara,b,c,d:semaphore:=0,0,0,0;/*表示进程是否执行完*/main(){cobegins1();s2();s3();s4();coend}s1s2s3s4abcdS1(){…v(a);}

S2(){…v(b);v(c);}

S3(){p(a);p(b);

…v(d);}

S4(){p(c);p(d);

...}

利用信号量实现前驱关系（同步例子）三、信号量的应用思考：已知一个求值公式（A2/3B）/（B+5A），若A、B已赋值，画出该公式求值过程的前趋图利用信号量实现前驱关系（同步例子）三、信号量的应用利用信号量实现同步有A、B两进程，A进程从卡片机读信息入缓冲区，B进程负责加工读进缓冲区的卡片解：设信号量S1：缓冲区中有否可供加工的信息，初始值为0；信号量S2：缓冲区是否为空，初始值为1。三、信号量的应用利用信号量实现同步举例返回3.3经典进程的同步问题

在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者—消费者问题哲学家进餐问题读者—写者问题返回目录1、“生产者—消费者”问题单缓冲区：生产者进程P和消费者进程C共用一个缓冲区，P生产产品放入缓冲区，C从缓冲区取产品来消费。消费者生产者1、“生产者—消费者”问题单缓冲区的同步问题P进程不能往“满”的缓冲区中放产品，设置信号量为emptyC进程不能从“空”的缓冲区中取产品，设置信号量full单缓冲区的互斥问题P、C进程不能同时使用缓冲区1、“生产者—消费者”问题单缓冲区的生产者─消费者问题解P：C：while(true){while(true){

生产一个产品;P(full);P(empty);从缓冲区取产品;

送产品到缓冲区;V(empty);V(full);消费产品;};};empty初值为1，full初值为01、“生产者—消费者”问题多个缓冲区：若干个生产者进程P1,P2,…,Pn，若干个消费者进程Cl，C2，…，Cm。它们通过一个有界缓冲池(k个)联系。....PC生产者消费者kk个Buffernm1、“生产者—消费者”问题多缓冲区的同步互斥问题

同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：所有进程应互斥使用缓冲池这一临界资源。多缓冲区的生产者─消费者问题解法1、“生产者—消费者”问题

设置两个同步信号量及一个互斥信号量empty：说明空缓冲单元的数目，其初值为有界缓冲区的大小n。full：说明满缓冲单元的数目（即产品数目），其初值为0。mutex:

说明该有界缓冲区是一临界资源，必须互斥使用，其初值为1。1、“生产者—消费者”问题多缓冲区的生产者─消费者问题解法思考：P操作的顺序可换吗？“生产者—消费者”问题的算法描述

semaphorefull=0;/*表示满缓冲区的数目*/semaphoreempty=n;/*表示空缓冲区的数目*/semaphoremutex=1;/*表示对缓冲区进程操作的互斥信号量*/Main(){cobeginproducer();consumer();coend}1、“生产者—消费者”问题{while(true){

生产一个产品;P(empty);P(mutex);

将一个产品送入缓冲区；

V(mutex);V(full);}}Producer(){while(true){p(full);P(mutex);

从缓冲区取走一个产品;V(mutex);V(empty);

消费一个产品；}}Consumer()1、“生产者—消费者”问题“生产者—消费者”问题的算法描述

“生产者-消费者”问题中应注意1.互斥信号量的P,V操作在每一程序中必须成对出现.1、“生产者—消费者”问题2.资源信号量(full,empty)也必须成对出现,但可分别处于不同的程序中.3.多个P操作顺序不能颠倒.4.先执行资源信号量的P操作,再执行互斥信号量的P操作,否则可能引起进程死锁.1、“生产者—消费者”问题5.它是一个同步问题：（1）消费者想要取产品，有界缓冲区中至少有一个单元是满的。（2）生产者想要放产品，有界缓冲区中至少有一个是空的。

“生产者-消费者”问题中应注意返回6.它是一互斥问题有界缓冲区是临界资源，因此，各生产者进程和各消费者进程必须互斥执行。2、“哲学家进餐”问题5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子，如图所示。为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。

问题描述semaphorestick[5]={1,1,1,1,1};/*分别表示5支筷子*/Main(){cobeginphilosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);coend

}哲学家进餐问题的解决2、“哲学家进餐”问题2、“哲学家进餐”问题哲学家i的活动为：

voidphilosopher(inti){while(true){

思考；

P(chopstick[i])；

//取左边筷子

P(chopstick[(i+1)%5])；

//取右边筷子进食；

V(chopstick[i])；//放左边筷子

V(chopstick[(i+1)%5])；//放右边筷子

}}哲学家进餐问题的解决2、“哲学家进餐”问题如果：5人同时拿起左边筷子，再企图拿起右边的筷子时，会如何？死锁！2、“哲学家进餐”问题

为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之返回3、“读者—写者”问题问题描述：多个进程访问一个共享数据对象（如数据文件或记录以及内存和寄存器）,为该类问题建立一个通用模型。其中，reader进程只能读，writer进程要求写或修改。允许多个读进程同时读数据，但绝不允许一个writer进程与其它的reader进程或writer进程同时访问，即writer进程必须与其它进程互斥访问共享对象。如一个联网售票系统:数据的查询和更新非常频繁,必然有多个进程试图查询或修改同一条记录的情况,多个进程同时查询(读)是允许的,但是不允许一个正在修改更新数据库(写)的进程工作的同时其他修改(写)或查询(读)发生,否则可能一票多售.3、“读者—写者”问题分析:有两组并发进程:

读者和写者，共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作如果用生产者消费者的方法来严格互斥任何读者写者进程,可以保证数据更新的正确性.但对查询不利.(与生产-消费的异同)3、“读者—写者”问题读者--写者问题有两种类型：解法1：读者优先

只要有一个读者存在，不管有否写者请求，后续读者都可以执行读过程。解法2：读写平等

即一旦有写者到达，后续的读者必须等待，无论是否有读者在读。写者优先。只要有一个写者请求，读者就要等待，直到所有写者退出。返回设置一个共享变量和两个信号量：共享变量Readcount：记录当前正在读数据集的读进程数目，初值为0。读互斥信号量Rmutex：表示读进程互斥地访问共享变量readcount，初值为1.写互斥信号量wmutex：表示写进程与其它进程（读、写）互斥地访问数据集，初值为1.3、“读者—写者”问题—读者优先semaphorermutex=1;semaphorewmutex=1;intreadcount=0;Main(){cobegin

reader();

writer();coend}3、“读者—写者”问题—读者优先{while(true){

p(rmutex);

if(readcount==1)p(wmutex);/*第一位读者阻止写者*/readcount++;

V(rmutex);

读数据集；

p(rmutex);

readcount--;if(readcount==0)v(wmutex);/*第末位读者允许写者进*/

V(rmutex);}}reader(){while(true){

p(wmutex);

/*阻止其它进程（读、写）进*/

写数据集；

V(wmutex);

/*允许其它进程（读、写）进*/}}writer()3、“读者—写者”问题—读写平等为了提高写者的优先级，我们增加一个信号量w，用以在写进程到达时封锁后续的读者进程。相应的控制算法如下：

BEGINintegermutex1,mutex2,rc,w;mutex1:=1;mutex2:=1;rc:=0;

w:=1;BEGIN

P(w);P(mutex1);rc:=rc+1;IFrc=1THENP(mutex2);V(mutex1);

V(w);ReadingtheFILE;P(mutex1);rc:=rc-1;IFrc=0THENV(mutex2);V(mutex1);END;readerBEGIN

P(w);P(mutex2);WriteingtheFILE;V(mutex2);

V(w);END;COENDWriter返回3、“读者—写者”问题—写者优先Constreadcount,writecount:integerVarx,y,z,rsem,wrem:=semaphoreReader:BeginRepeatP(z);

P(rsem);P(x);Readcount:=Readcount+1;IfReadcount=1thenP(wsem);V(x);

V(rsem);V(z);读数据;P(x);Readcount:=readcount-1;Ifreadcount=0thenV(wsem);V(x);Forever;End;Writer:BeginRepeatP(y);Writecount:=writecount+1;Ifwritecount=1thenP(rsem);V(y);

P(wsem);写数据;V(wsem);P(y);Writecount:=writecount-1;Ifwritecount=0thenV(rsem);V(y);Forever;End;【练习题】1.用P.V操作解决下图之同步问题:P1P2P3p1():p2():从磁盘读记录；p(full1);p(empty1);取记录；存入缓冲区1；v(empty1);V(full1);p(empty2);

存入区2；v(full2);P3():P(full2);从区2取记录；V(empty2);打印记录；2.桌上有一只盘子，每次只能放入一只水果，爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange),一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子中的苹果。只要盘子中空则爸爸或妈妈可向盘子中放一只水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出。把爸爸、妈妈、儿子、女儿看做四个进程，用PV操作进行管理，使这４个进程能正确地并发执行。

。【练习题】这个问题实际上可看作是两个生产者和两个消费者共享了一个仅能存放一件产品的缓冲区，生产者各自生产不同的产品，消费者各自取走自己需要的产品。beginS,SP,SO:semaphore；

S:=1；SP:=0；SO:=0；

Cobegin

Process爸爸

Begin

L1:准备一个苹果；

P(S)；

把苹果放入盘子中；

V(SP)；

GotoL1；

End；

Process妈妈

Begin

L2:准备一个桔子；

P(S)；

把桔子放入盘子中；

V(SO)；

GotoL2；

End；

Process儿子

Begin

L3:P(SO)；

从盘子中取一只桔子；

V(S)；

吃桔子；

GotoL3；

End；

Process女儿

Begin

L4:P(SP)；

从盘子中取一只苹果；

V(S)；

吃苹果；

gotoL4；

End；

Coend；

End；

【练习题】3.有一个仓库，可以存放A和B两种产品，但要求（1）每次只能存入一种产品（A或B）；（2）-N>A产品数量-B产品数量<M其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。intmutex=1,sa=M-1,sb=N-1;If(A):P(sa);P(mutex);产品入库；V(mutex);V(sb);Else(B):P(sb);P(mutex);产品入库；V(mutex);V(sa);司机售票员正常行驶到站停车开车售票开车门关车门【练习题】4：司机-售票员问题：4：司机-售票员问题解答：VARs1,s2:semaphore;司机活动：售票员活动：

RepeatRepeat

P(S1)

关车门启动车辆V(S1)

正常行驶售票到站停车P(S2)

V(S2)

开车门

UntilfalseUntilfalses1表示是否允许司机启动汽车，初值为0；s2表示是否允许售票员开门，初值为0.【练习题】*管程机制管程的提出

用信号量机制实现进程间的同步和互斥，即方便又有效。但存在以下两个问题：

每个访问临界资源的进程都必须自备同步操作（P、V操作），这使大量的同步操作分散在各个进程中，给系统的管理带来麻烦会因同步操作使用不当而导致系统死锁。

解决方法----管程（Monitors)Dijkstra于1971年提出，为每个共享资源设立一个“秘书”来管理对它的访问。一切来访者都要通过秘书，而秘书每次仅允许一个来访者（进程）来访问共享资源。这样既便于系统管理共享资源，又能保证进程的互斥访问和同步。1973年，Hanson和Hoare又把“秘书”概念发展为管程概念。3.4管程机制一、管程的基本概念

管程的定义一个数据结构和在该数据结构上能被并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。一、管程的基本概念(1)管程所管理的共享数据结构(变量)，这些数据结构是对相应临界资源的抽象；(2)建立在该数据结构上的一组操作(函数)；(3)对上述数据结构置初值的语句。一、管程的基本概念管程的几点说明：管程（相当于围墙）把共享变量和对它进行操作的若干过程围起来。管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量为了保证管程共享变量的数据完整性，规定管程互斥进入，由编译程序实现管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作一、管程的基本概念条件变量

在管程机制中，当某进程通过管程请求临界资源未能满足时，管程便调用wait原语使该进程等待，但等待的原因可能有多个，为了加以区别，引入条件变量加以说明。条件变量的定义格式

Varx,y:condition一、管程的基本概念

对条件变量执行的两种操作Wait操作如x.wait用来将执行进程挂到与条件变量x相应的等待队列上。Signal操作如x.signal用来唤醒与条件变量x相应的等待队列上的一个进程。但如果没有进程被阻塞，则不产生任何效果，这与信号量机制中的signal操作不同

条件变量一、管程的基本概念问题：管程中的多个进程进入当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程处理方法有三种：

Ｐ等待Ｑ继续，直到Ｑ退出或等待√（Hoare）Ｑ等待Ｐ继续，直到Ｐ等待或退出

唤醒是管程中可执行的最后一个操作（Hansen)

条件变量管程示意图urgentqueue入口等待队列：因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行时又唤醒进程Ｒ，则Ｑ等待Ｒ继续，...，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程（因唤醒其它进程而自己被阻塞的进程），因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。内部等待队列：varc:condition;可根据需要定义多个，用于设置等待条件。二、用管程机制解决生产者—消费者问题

建立Producer-consumer(PC)管程

Typeproducer-consumer=monitorvarin,out,count:integer;buffer:array[0,…,n-1]ofitem;

notfull,notempty:condition;

put(item);

get(item);beginin:=out:=0;/*初始化代码*/count:=0;end管程中的两个条件变量：

(1)notfull当缓冲区中不全满，该变量为真。

(2)notempty当缓冲区中不全空，该变量为真。二、用管程机制解决生产者—消费者问题

建立Producer-consumer(PC)管程

put(item)过程生产者利用此过程将自已的消息放到缓冲池中，若发现缓冲已满（countn)，则等待。Get(item)过程消费者利用此过程将缓冲池中的消息取走，若发现缓冲已空（count0)，则等待。

put(item)Procedureentryput(item)beginifcount≧nthenfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifempty.queuethenempty.signal;endget(item)Procedureentryget(item)beginifcount≦0thenempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;iffull.queuethenfull.signal;endProducer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalseendConsumer:begin repeat PC.get(item);consumetheiteminnextc;untilfalseend返回目录二、用管程机制解决生产者—消费者问题3.5进程通信—高级通信概念：进程间的信息交换。实例：信号量机制（一种低级通信） 缺点：（1）效率低 （2）通信对用户不透明高级通信特点：效率高，通信实现细节对用户透明3.5进程通信—高级通信高级进程通信机制可分为三大类：

1.共享存储器系统(Shared-MemorySystem)2.消息传递系统(Messagepassingsystem)（1）直接通信方式：消息缓冲通信（2）间接通信方式：又称为信箱通信方式

3.管道(Pipe)通信：又名共享文件通信3.5进程通信—高级通信1.共享存储器系统

基于共享数据结构的通信方式：produce-consume中的缓冲区，低效，不透明。系统只提供了一共享存贮器，适于少量通信。

基于共享存储区的通信方式：系统提供：共享存储区。通信过程：（1）向系统申请一个或多个分区（2）获得分区获后即可读/写.特点：高效，速度快。信息单位：消息（报文）实现：一组通信命令（原语）,具有透明性消息头消息正文注：消息格式：

msgsender 消息发送者

msgreceiver 消息接收者

msgnext 下一个消息的链指针

msgsize 整个消息的字节数

msgtext 消息正文3.5进程通信—高级通信2.消息缓冲通信（1）直接通信

send（Receiver，message

），如接收者因等消息而封锁，则唤醒。

receive(Sender，message)，无消息则阻塞。3.5进程通信—高级通信发送进程使用发送原语直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程使用接收原语从消息缓冲队列中取出消息。repeat...Receive(producer,nextc);...consumetheiteminnextc;untilfalserepeat….Produceaniteminnextp;….send(consumer,nextp)；untilfalse;生产者-消费者问题的解决3.5进程通信—高级通信（1）直接通信send和receive原语数据结构消息缓冲区

typemessagebuffer=recordsender:size:text:next:指向下一指针PCB中应增数据项：

typepcb=recordmq 消息队列指针

mutex消息队列互斥信息量

sm 消息队列资源信息量3.5进程通信—高级通信（1）直接通信3.5进程通信—高级通信发送原语

proceduresend(receiver,a)begin getbuf(a.size,i); i.sender:=a.sender; i.size:=a.size; i.text:=a.text; i.next:=0; getid(PCBset,receiver.j);

wait(j.mutex); insert(j.mq,i);

signal(j.mutex);

signal(j.sm);end（1）直接通信3.5进程通信—高级通信接收原语procedurereceive(b) begin j:=internalname;

wait(j.sm);

wait(j.mutex); remove(j.mq,i);

signal(j.mutex); b.sender:=i.sender; b.size:=i.size; b.text:=i.text; end3.5进程通信—高级通信（2）间接优点：在读/写时间上的随机性写进程――>信箱（中间实体）――>读进程原语

信息的创建与撤消：信箱名属性（公用、私用、共享）（共享者名字）

消息的发送和接收Send(mailbox,message)Receive(mailbox,message)3.5进程通信—高级通信（2）间接信箱类型私用：拥有者有读/写数，其它只有写权，（单向）存在期＝进程存在期。公用：系统创建，双向，存在期=系统存在期。共享信箱：一般进程创建，并指明其共享者，是双向。发送—接收进程之间的关系：一对一关系；多对一关系；一对多关系；多对多关系：公用信箱。3.5进程通信—高级通信3.5进程通信—高级通信semaphorefull=0; /*满格计数*/semaphoreempty=N; /*空格计数*/receive(mailbos,message){P(full);

选择满格F;

把满格F中的消息取出放msg中;

置F格标志为空E;V(empty);}send(mailbox,messsage){P(empty);

选择空格E;

将消息msg放入空格E中;

置格E的标志为满;V(full);}（2）间接