操作系统第三章

3.1进程间通信3.1.1并发进程的特点3.1.2进程间通信33.1.1并发进程的特点资源共享引起的互斥关系

并发进程互斥使用共享资源

Eg.两个进程均要独占使用打印机

间接制约关系

进程-资源-进程协作完成同一个任务引起的同步关系

同步点

直接制约关系

进程-进程

43.1.2进程间通信(1)进程之间既相互依赖又相互制约，既相

互合作又相互竞争允许进程相互交换数据与信息进程通信模式

共享内存

建立起一块供协作进程共享的内存区 域，进程通过向此共享区域读或写入 数据交换信息

消息传递

通过在协作进程间交换消息实现通信

53.1.2进程间通信(2)6进程间通信模型3.2进程同步3.2.1临界资源与临界区..5进程互斥进程同步信号量经典进程同步问题3.2.6管程

73.2.1临界资源与临界区(1)83.2.1临界资源与临界区(2)临界资源

一次仅允许一个进程使用的资源临界区

每个进程访问临界资源时必须互斥执行

的程序使用临界资源需遵循的原则

互斥使用：不能同时有两个进程在临界

区内执行

让权等待：等待进入临界区的进程应释 放处理机后阻塞等待

9103.2.1临界资源与临界区(3)

有空让进：临界资源空闲时，应允许一

个请求临界资源的进程进入临界区

有限等待：不能使进入临界区的进程无 限期地等待在临界区之外进程Pi的通用结构

do{ entrysection

criticalsection

exitsection remindersection}while(1);3.2.1临界资源与临界区(4)11进程A和进程B互斥使用临界区3.2.2进程互斥(1)解决进程互斥的硬件方法

关中断

进程刚进入临界区后立即禁止所有中 断；进程要离开之前打开所有中断

原理：CPU只有在发生时钟中断或其

它中断时才会进行进程切换实现12关中断(disable)criticalsection开中断(enable)3.2.2进程互斥(2)优点简单缺点将禁止中断的权力交给用户进程是不明智的在多处理机系统中，禁止中断仅对

执行本指令的CPU有效，其他CPU

仍将继续运行，并可访问共享资源133.2.2进程互斥(3)

测试和设臵指令

是一条不会被中断的机器指令

为临界资源设臵锁位变量W

W=0，资源空闲可用

W=1，资源已被占用

初始化时，W的初值为0退出临界区时，将W重臵为0实现14k:if(w==1)gotok;elsew=1;忙等待3.2.2进程互斥(4)

示例：多个进程利用TestSet实现互斥15constintn=3;voidP(inti){ while(1){

intw;TestSet(w);//加锁CriticalSectionw=0;//开锁

RemainderSection

}}

w=0;P(1);P(2);P(3);Parendvoidmain(){ Parbegin}3.2.2进程互斥(5)解决进程互斥的软件方法

方法1：为两个进程Pi和Pj分别设臵布尔

变量，即booleanflag[2]，若flag[i]为

true，则表示进程Pi正在临界区。

ProcessPi：do{while(flag[j]);

flag[i]=true;

CriticalSection flag[i]=false; RemainderSection}while(1);两个进程同时进入临界区

163.2.2进程互斥(6)

方法2：两个进程Pi和Pj共享整型变量

turn，turn指示哪个进程应进入临界区

，即turn==i时，允许进程Pi进入临界 区，反之允许进程Pj进入临界区。ProcessPi：do{while(turn!=i); CriticalSection turn=j; RemainderSection}while(1);强制两个进程交替进入临界区，临界资源利用率不高

17183.2.2进程互斥(7)

方法3：为两个进程Pi和Pj分别设臵布

尔变量，其初值为flag[i]=flag[j]=false

，若flag[i]==true，则表示进程Pi要求 进入临界区，或是已在临界区

ProcessPi：do{flag[i]=true;while(flag[j]);CriticalSectionflag[i]=false;RemainderSection}while(1);两个进程互相阻塞，均不能进入临界区3.2.2进程互斥(8)方法4（Dekker算法）为两个进程Pi和Pj分别设臵布尔变量，即booleanflag[2]，其初值为flag[i]=flag[j]=false，若flag[i]==true，则表示进程Pi要求进入临界区为两个进程Pi和Pj设臵共享整型变量turn指示应该由哪个进程进入临界区。turn==i时，表示允许进程Pi进入临界区，反之允许进程Pj进入临界区19203.2.2进程互斥(9)

ProcessPi：do{flag[i]=true;while(flag[j]) if(turn==j){ flag[i]=false; while(turn==j);

flag[i]=true;

}CriticalSectionturn=j;flag[i]=false;RemainderSection}while(1);3.2.3进程同步一组共行进程，各自以独立的、不可预

知的速度向前推进，在前进过程中彼此 之间需要相互协调步伐，才能正确地完

成同一项任务示例：计算进程与打印进程

213.2.4信号量(1)信号量

进程同步工具

1965年由Dijkstra（荷兰）提出 物理意义

表示资源的物理实体结构22typedefstruct{ intvalue; structprocess*L;}semaphore;3.2.4信号量(2)value：表示该类资源的当前可用数量L：等待使用该类资源的阻塞进程队列的队首指针操作初始化：将value初始化为该类资源的可用数量原子操作P：申请资源原子操作V：释放资源信号量value为负数时，其绝对值表示在该信号量上等待的进程数目233.2.4信号量(3)//wait(S);down(S)P(S)：

S.value--;if(S.value<0){

addthisprocesstoS.L; block;}V(S)://signal(S);up(S)S.value++;if(S.value<=0){

removeaprocessPfromS.L;

wakeup(P);}

243.2.4信号量(4)25利用信号量实现n个进程间的互斥

互斥信号量mutex，初值为1

第i个进程的执行代码

do{

P(mutex)

<criticalsection>

V(mutex)

<remindersection>

}while(1);3.2.4信号量(5)利用信号量实现进程间的同步

示例：利用信号量实现计算进程与打印

进程之间的同步过程。假定计算进程和 打印进程共同使用一个单缓冲

信号量

计算进程：信号量empty,表示缓冲区 是否空，初值为1;

打印进程：信号量full，表示缓冲区中

是否有可供打印的计算结果，初始值为026

3.2.4信号量(6)empty=1;full=0;parbeginbegin//计算进程

loop computenextnumber

P(empty)

addthenumbertobuf

V(full)

…… endloopendbegin//打印进程

loop

P(full)

printnextnumber

V(empty)

addtheemptytobuf …… endloopendparend

273.2.4信号量(7)信号量分类

公用信号量

互斥信号量，用于解决进程之间互斥 进入临界区

私用信号量

同步信号量，用于解决异步环境下进 程之间的同步

283.2.5经典进程同步问题(1)生产者—消费者问题

是相互合作进程关系的一种抽象

生产者：当进程释放一个资源时，可把它 看成是该资源的生产者

消费者：当进程申请使用一个资源时，可 把它看成该资源的消费者

计算进程：打印数据的生产者；空缓冲 的消费者

打印进程：打印数据的消费者；空缓冲 的生产者

293.2.5经典进程同步问题(2)问题描述：

假定有一组生产者(M个）和一组消费

者(N个）进程，通过一个有界环形缓 冲区（k个缓冲块）发生联系。生产 者将生产的产品放入缓冲区，消费者

从缓冲区取用产品。

当缓冲区满时，生产者要等消费者取 走产品后才能向缓冲区放下一个产品

；当缓冲区空时，消费者要等生产者

放一个产品入缓冲区后才能从缓冲区 取下一个产品。

303.2.5经典进程同步问题(3)信号量

empty：表示空缓冲

块的个数，初值为k full：有数据的缓冲

块个数，初值为0

mutex：互斥访问临 界区的信号量，初

值为1

313.2.5经典进程同步问题(4)323.2.5经典进程同步问题(5)读者—写者问题

有一个多进程共享的数据区（可以是一

个文件或者主存的一块空间），有一些 只读取这个数据区的进程（reader)和

一些只往数据区中写数据的进程（

writer)：

任意多的读进程可以同时读数据区

一次只有一个写进程可以写数据区

若有写进程正在写，禁止任何进程读

333.2.5经典进程同步问题(6)信号量

读写互斥信号量db：实现读写互斥和

写写互斥访问共享文件，初值为1

计数器变量rc：记录同时读的读者数，

初值为0

读计数互斥信号量mutex：使读者互斥 地访问共享变量rc，初值为1

343.2.5经典进程同步问题(7)353.2.5经典进程同步问题(8)哲学家就餐问题

假设有5个哲学家

，花费一生的时光 思考和吃饭。在桌 子上放着5把叉子

。一个哲学家要分

两次去取其左边和 右边的叉子。若得

到两把叉子，就开

始吃饭；吃完放下 两把叉子。363.2.5经典进程同步问题(9)fork:ARRAY[0-4]OFsemaphore;mutex:semaphore;fork[0]:=fork[l]:=fork[2]:=fork[3]:=fork[4]:=l;mutex:=1;parbeginPi:REPEAT/*第i个哲学家的活动情况*/ ThinkFORwhile;/*思考一会儿，想吃饭*/P(mutex);P(fork[i]);P(fork[(i+l)MOD5]);V(mutex);

/*申请拿叉子*//*释放申请权*/

EatFORWHILE;/*吃饭*/

V(fork[i]);

V(fork[(i+l)MOD5]);UNTILfalseparend

373.2.6管程(1)引入管程的原因

各个进程自备P(S)和V(S)操作，加重了

用户负担 大量同步操作分散在各个进程中，系统

管理复杂

易产生死锁提出

1974年由Hansen和Hoare提出管程的定义

383.2.6管程(2)

一个管程调用了一个数据结构和能为并

发进程所执行（在该数据结构上）的一

组操作，这组操作能同步进程和改变管 程中的数据 管程是关于共享资源的数据结构及一组 针对该资源的操作过程所构成的软件模块一次只有一个进程能在管程内活动。从而提供互斥机制，保证管程数据的一致性

39类3.2.6管程(3)管程的结构

管程名

局部于管程的共享 变量说明

对该数据结构进行

操作的一组过程 对局部于过程的数

据设臵初始值的语

句403.2.6管程(4)

monitormonitor-name{ sharedvariabledeclarations... ...procedurebodyP1(…){ ...}procedurebodyP2(…){}procedurebodyPn(…){}initializationcode{}}413.2.6管程(5)管程的特点

局部于管程的数据结构只能被局部于管

程的过程所访问，任何管程外部的过程 都不能访问它 局部于管程的过程只能服务管程内的数 据结构 管程每次只允许一个进程进入管程，从 而实现管程的互斥管程的同步机制

条件变量c

423.2.6管程(6)同步原语wait(c)：执行wait(c)的进程将自己阻塞在条件变量c的相应等待队列中。在阻塞前，释放管程的互斥使用权；同步原语signal(c)：执行signal(c)的进程检查条件变量c的相应等待队列。如果队列为空，则执行此操作的进程继续；否则，唤醒c队列中的第一个等待者，让被唤醒者进入该管程。433.2.6管程(7)利用管程实现临界资源的互斥使用monitormutexshow{

boolbusy;//临界资源状态

conditionnonbusy;//条件变量

definerequest,release;//进程可调用过程

usewait,signal;//同步操作

Procedurerequest{//申请资源

ifbusythenwait(nonbusy); busy=true; } Procedurerelease{//释放资源

busy=false;

signal(nonbusy);

}

{busy=false;}//初始：资源空闲}443.2.6管程(8)利用管程解决生产者—消费者问题453.3消息传递通信(1)共享内存通信（进程低级通信）

优点

速度快

缺点

传送信息量小且效率低，每次通信只

能传递一个单位的信息量

P、V操作使用不当时，易导致死锁消息传递通信（进程高级通信）

用户直接利用OS提供的通信命令，高 效地传递大量数据

463.3消息传递通信(2)消息传递通信

消息结构

消息缓冲

直接/间接通信

同步/异步通信直接通信

消息发送原语send(接收者，被发送信息始址，信息长度)

47structmessage_buffer{

sender:消息发送者

receiver:消息接收者size:消息长度text:消息正文next:指向下一消息 缓冲区指针};

主要工作请求分配一个消

息缓冲区；将消息正文传送

到该缓冲区中，

并填入有关发送

参数；将该消息缓冲区

挂到接收进程消

息链上send(receiver,a){ getbuf(a.size,i); i.sender=a.sender; i.size=a.size; i.text=a.text; i.next=0; getid(PCBset,receiver,j);P(j.mutex);Insert(j.mq,i);V(j.mutex);V(j.sm);}483.3消息传递通信(3)3.3消息传递通信(4)

接收消息原语

receive（发送者，信息始址，接收区

始址,信息长度)49

主要工作检查消息链上 是否有消息；有则将消息接 收到接收区；无则阻塞等待消息的到来receive(b){

j=getid; P(j.sm); P(j.mutex); Remove(j.mq,i);

V(j.mutex);

b.sender=i.sender; b.size=i.size;b.text=i.text;}发送进程P1send(p2,A,x)

发送区发送3.3消息传递通信(5)

接收进程PCB信息队列的头指针…第一个消息缓冲区

...第N个消息缓冲区

50接收进程P2接收receive(p1,A1,

B,x1)

接收区3.3消息传递通信(6)

消息队列通常放在进程控制块中

PCB的结构

structPCB{ …mq；//消息队列队首指针mutex；//消息队列互斥信号量sm；//消息队列同步信号量

…}

513.3消息传递通信(7)间接通信（信箱通信）

间接通信方式

发送原语

send(A,message)

接收原语

receive(A,message)

信箱属性

共享 专用523.3消息传递通信(8)消息同步

发送进程与接收进程状态

阻塞 非阻塞

消息同步方式

非阻塞发送，非阻塞接收 非阻塞发送，阻塞接收 阻塞发送，阻塞接收阻塞发送，非阻塞接收533.3消息传递通信(9)通信链路54

消息缓冲区发送进程发送信息接收进程接收信息消息发送发送信息接收进程接收回答接收信息缓冲区发送回答进程进程之间的双向通信进程之间的单向通信3.4客户-服务器系统通信(1)Socket通信RPC(RemoteProcedureCall)RMI(RemoteMethodInvocation)消息队列553.4客户-服务器系统通信(2)56Socket通信3.4客户-服务器系统通信(3)57RPC通信3.4客户-服务器系统通信(4)58消息队列3.5死锁3.5.1基本概念.3鸵鸟算法死锁预防3.5.4死锁避免3.5.5死锁检测3.5.6死锁恢复

593.5.1基本概念(1)死锁概念

多个进程在运行过程中因争夺资源而造

成的一种僵局，当进程处于这种僵持状 态时，若无外力作用，所有进程都将无 法向前推进产生死锁的原因

竞争资源（资源数量不足）

资源类型

可抢占资源：主存、CPU

不可抢占资源：慢速设备/共享变量

603.5.1基本概念(2)R1R2P1P2S2P1S3P3S1P2I/O设备共享时的死锁进程之间通信时的死锁

613.5.1基本概念(3)

进程推进顺序非法

请求和释放资源的顺序不当62

P2Rel(R1) P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D(1)(2)(3)(4)3.5.1基本概念(4)死锁产生的必要条件

同时具备下列四个条件

互斥条件

每个资源是不可共享的，它或者已经

分配给一个进程，或者空闲

保持和等待条件

进程因请求资源而被阻塞等待时，对

已经分配给它的资源保持不放

不可剥夺条件 循环等待条件

633.5.1基本概念(5)死锁产生的必要条件

同时具备下列四个条件

互斥条件 保持和等待条件 不可剥夺条件

进程所获得的资源在未使用完之前，不 能被其它进程强行剥夺，只能由获得资 源的进程自己释放

循环等待条件

存在进程循环链，链中有两(多)个进程 在等待链中下一个成员保持的资源643.5.1基本概念(6)资源分配图

由节点V和边E构成；

节点V分为两类：

进程节点：P={P1,P2,…,Pn},用圆圈

表示，构成了系统中的进程集合；

资源节点：R={R1,R2,…,Rm},用方 块表示，表示系统中的各种资源；

边E分为两类：

请求边–有向边P1→Rj

分配边–有向边Rj→Pi

65Pi拥有资源Rj的一个实例663.5.1基本概念(7)

示例

进程

具有4个实例的资源

Pi请求资源Rj的一个实例

PiPi

RjRj3.5.1基本概念(8)67资源分配图示例3.5.1基本概念(9)68资源分配图示例3.5.1基本概念(10)69带有死锁的资源分配图3.5.1基本概念(11)70有环路但未死锁的资源分配图3.5.1基本概念(12)结论资源分配图中无环路无死锁资源分配图中有环路每类资源只有一个实例则死锁；每类资源有多个实例，可能死锁；解决死锁的方法忽略死锁问题，假定系统永不死锁保证系统永远不进入死锁状态死锁预防死锁避免713.5.1基本概念(13)允许系统进入死锁状态，并可从死锁状态中恢复

死锁检测 死锁恢复723.5.2鸵鸟算法假定死锁从不发生原因

死锁在计算机中很少出现

预防死锁的代价太高UNIX和Windows采用此方法

733.5.3死锁预防(1)破坏死锁产生的必要条件破坏互斥条件

资源特性 将独享设备改造为共享设备破坏保持和请求条件

进程在开始运行前必须获得所需的全部 资源。若系统不能满足，则该进程等待

优点

简单，易于实现，安全

743.5.3死锁预防(2)

缺点

资源利用率低 饥饿问题破坏非剥夺条件

当一个已经占有了一些资源的进程提出新 的资源申请而不能立即得到满足时，必须 释放已经占有的全部资源，待以后需要时 再重新申请

缺点

保护进程放弃资源时的现场及之后的恢 复现场，系统要付出很高的代价

753.5.3死锁预防(3)

增加了进程周转时间破坏循环等待条件将系统全部资源按类进行全局编号排序，进程对资源的请求必须按照资源的递增或递减顺序序号申请缺点找到能满足所有进程要求的资源编号限制新类型设备的增加763.5.4死锁避免(1)死锁预防

静态分配资源死锁避免

动态分配资源

允许进程动态地申请资源，一次申请一

部分资源。系统在进行资源分配之前， 先计算资源分配的安全性。若此次分配

不会导致系统进入不安全状态，便将资

源分配给进程；否则，进程等待

773.5.4死锁避免(2)系统处于安全状态无死锁系统处于不安全状态可能死锁避免死锁保证系统永不进入不安全状态783.5.4死锁避免(3)安全状态

系统能按照某种进程顺序(P1,P2,…,Pn)

来为每个进程Pi分配其所需资源，直至 满足每个进程对资源的最大需求，使每

个进程都可顺利地完成安全序列

(P1,P2,…,Pn)不安全状态

不存在一个安全序列

793.5.4死锁避免(4)(a)(b)(c)(d)(e)安全状态——安全序列(B,C,A)

803.5.4死锁避免(5)不安全状态

81(a)(b)(c)(d)3.5.4死锁避免(6)银行家算法

1965年由Dijkstra提出

数据结构

n表示进程数目，m表示资源类型

可用资源向量Available：含有m个元

素的数组，每个元素代表一类可利用 的资源的数目，初始值为系统中所配

臵的该类资源的全部可用数目。如果

Available[j]=k，则表示系统中现有Rj

类资源k个。

823.5.4死锁避免(7)最大需求矩阵Max：n×m的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=k，则表示进程Pi需要Rj类资源的最大数目为k。分配矩阵Allocation：n×m的矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数目。如果Allocation[i,j]=k，则表示进程Pi当前已分配到Rj类资源的数目为k。833.5.4死锁避免(8)需求矩阵Need：n×m的矩阵，表示每一个进程还需要的各类资源的数目。如果Need[i,j]=k,则表示进程Pi还需要Rj类资源k个，才能完成其任务。各个矩阵之间的关系：Need[i,j]=Max[i,j]–Allocation[i,j]算法设Requesti是进程Pi的请求向量，如果Requesti[j]=k，表示进程Pi需要k个Rj类的资源843.5.4死锁避免(9)

1.如果Requesti[j]≤Need[i,j]，转向第

2步；否则出错；

2.如果Requesti[j]≤Available[j]，转 向第3步；否则表示尚无足够资源，

Pi须等待；

3.假定将资源分配给进程Pi，修改下 列数据结构：

Available[j]=Available[j]-Requesti[j]

Allocation[i,j]=Allocation[i,j]+Requesti[j]Need[i,j]=Need[i,j]-Requesti[j]853.5.4死锁避免(10)4.系统执行安全性算法，检查此次分配后，系统是否处于安全状态。安全资源分配给进程Pi不安全Pi等待，本次试探分配取消，恢复原来的资源分配状态安全性算法1.设臵工作向量Work，表示系统可提 供给进程继续运行所需要的各类资源

数目，它含有m个元素，初始值为

Work=Available；863.5.4死锁避免(11)2.设臵向量Finish，表示系统是否有足

够的资源分配给进程使之运行完成，

它含有n个元素，初始值为

Finish[i]=false；3.从进程集合中查找能满足下列条件的进程Finish[i]=falseNeed[i,j]Work[j]若存在该进程，则转4；否则，执行5；873.5.4死锁避免(12)4.进程Pi获得资源后可顺利执行至完成，并释放分配给它的资源，即执行

Work[j]=Work[j]+Allocation[i,j]

Finish[i]=true执行第3步；5.若所有进程均满足Finish[i]==true，则 系统处于安全状态；否则为不安全状态示例：假定有5个进程{P0,P1,P2,P3,P4}，3类资源{A,B,C}，各类资源的数目分别为10，5，7。88MaxAllocationNeedAvailableABCABCABCABCP

0753010743332P

1322200122P

2902302600P

3222211011P

44330024313.5.4死锁避免(13)T0时刻的资源分配情况如下：89WorkAllocationNeedWork+AllocationFinishABCABCABCABCP

1332200122532trueP

3532211011743trueP

4743002431745trueP

27453026001047trueP

010470107431057true3.5.4死锁避免(14)存在安全序列<P1,P3,P4,P2,P0>，系统处于安全状态

90MaxAllocationNeedAvailableABCABCABCABCP

0753010743230P

1322302020P

2902302600P

3222211011P

44330024313.5.4死锁避免(15)P1请求资源(1,0,2)

Request1(1,0,2)Need1(1,2,2)true Request1(1,0,2)Available1(3,3,2)true91WorkAllocationNeedWork+AllocationFinishABCABCABCABCP

1230302020532trueP

3532211011743trueP

4743002431745trueP

0745010743755trueP

27553026001057true3.5.4死锁避免(16)执行安全性算法可知，存在安全序列<P1,P3,P4,P0,P2>，系统处于安全状态，可将资源分配给P1923.5.4死锁避免(17)P4请求资源(3,3,0)

Request4(3,3,0)Need4(4,3,1)true Request4(3,3,0)Available4(2,3,0)false

P4等待P0请求资源(0,2,0)

Request0(0,2,0)Need0(7,4,3)true Request0(0,2,0)Available0(2,3,0)true

执行安全性算法可知，系统进入不安全 状态，不能够将资源分配给P0

93MaxAllocationNeedAvailableABCABCABCABCP

0753030723210P

1322302020P

2