第五章 并行性：互斥和同步
第 5章 并行性：互斥和同步
? 5.1 引论
? 5.2 临界段
? 5.3 互斥
? 5.4 信号量
? 5.5 管程
? 5.6 进程间的通信
第五章 并行性：互斥和同步
5.1 引论
? 多道程序设计的出现对计算机系统产生
了极大的影响，推动了操作系统技术的
发展
? 并行的进程之间由于争用资源、互相通
信、互相制约而产生了 互斥, 同步 和 通
信 问题是本章解决的重点内容，也是本
课程的重点内容。
第五章 并行性：互斥和同步
5.1 引论
? 多道程序系统中存在的进程之间有三种典型的
关系,
? 进程之间相互协作，直接知道对方的存在，直到对
方的名字（如进程之间的调用）
? 进程之间通过共享间接知道对方的存在，但并不知
道对方的名字（如共享同一变量或文件）
? 进程之间晚全部知道对方的存在，但因为竞争资源
而形成制约关系（如争用 CPU、内存或硬盘等）
第五章 并行性：互斥和同步
进程的交互关系：可以按照相互感知的程度来分类
相互感知的程度 交互关系 一个进程对其他进程
的影响
潜在的控制问题
相互不感知 ( 完全不了
解其它进程的存在 )
竞争 ( c o m p e tition ) 一个进程的操作对其他
进程的结果无影响
互斥，死锁 （可释放的资
源），饥饿
间接感知 ( 双方都与第
三方交互，如共享资
源 )
通过共享进行协作 一个进程的结果依赖于
从其他进程获得的信息
互斥，死锁 （可释放的资
源），饥饿，数据一致性
直接感知 ( 双方直接交
互，如通信 )
通过通信进行协作 一个进程的结果依赖于
从其他进程获得的信息
死锁，饥饿
互斥，指多个进程不能同时使用同一个资源；
死锁，指多个进程互不相让，都得不到足够的资源；
饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）
第五章 并行性：互斥和同步
一个飞机订票系统，两个终端，运 行 T1, T2 进
程
T 1, T 2,
...,..
R e a d ( x ) ; R e a d ( x ) ;
i f x > = 1 t h e n i f x > = 1 t h e n
x, = x - 1 ; x, = x - 1 ;
w r i t e ( x ) ; w r i t e ( x ) ;
...,..
共享变量的修改冲突
第五章 并行性：互斥和同步
5.2 临界段
设 X初始值为 10
T1.Read(X)
T1.if x>=1 then
//x=10
T1.x=x-1
T1.write(X) // X=9
T2.Read(X)
T2.if x>=1 then
T2.x=x-1
T2.write(X) // X=8
设 X初始值为 10
T1.Read(X)
T2.Read(X)
T1.if x>=1 then //x=10
T1.x=x-1
T1.write(X) // X=9
T2.if x>=1 then //x=10
T2.x=x-1
T2.write(X) // X=9
第五章 并行性：互斥和同步
get copy put
f s t g
有 3个进程,get,copy和 put，它们对 4个存储区域 f,s,t和 g进
行操作。
操作顺序冲突
第五章 并行性：互斥和同步
get copy put
f s t g
f s t g 结果
初始状态 3,4,...,m 2 2 ( 1,2 )
g,c,p 4,5,...,m 3 3 ( 1,2,3) 正确
g,p,c 4,5,...,m 3 3 ( 1,2,2) 错误
c,g,p 4,5,...,m 3 2 ( 1,2,2) 错误
c,p,g 4,5,...,m 3 2 ( 1,2,2) 错误
p,c,g 4,5,...,m 3 2 ( 1,2,2) 错误
p,g,c 4,5,...,m 3 3 ( 1,2,2) 错误
第五章 并行性：互斥和同步
5.2 临界段
? 临界资源 (Critical Resource),在系统中每次
只能一个（有限个）进程访问的资源，
如打印机、磁带机等。临界资源访问控
制是进程同步的基本问题。
? 临界段 (Critical section):每个进程中访问
临界资源的那段代码叫临界段。
第五章 并行性：互斥和同步
5.2 临界段
? 进程使用临界段的原则
? 如果临界资源空闲，在共享同一个临界资源的进程中，
每次只允许一个进程进入自己的临界段；
? 如有多个进程同时要求进入临界段，应在有限时间内
允许其中一个进程进入临界段，不能互相阻塞；
? 进程在临界段内只能停留有限的时间；
? 应保证进程能够在有限时间内进入临界段；
? 处于临界段之外的进程不能阻止其它进程进入临界段；
? 如果进程不能进入临界段，应立即释放 CPU，进入阻
塞状态。
第五章 并行性：互斥和同步
5.3 互斥
? 5.3.1 互斥的软件方法
? 5.3.2 互斥的硬件方法
第五章 并行性：互斥和同步
5.3 互斥
? 例：有两个并行进程 P0和 P1，互斥的共
享某一个资源。 P0和 P1都是无限循环
进程，每次使用资源有限的时间。
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 1：单标志）
? 设立一个公用整型变量 turn：描述允许进入临界
区的进程标识
? 在进入区循环检查是否允许本进程进入,turn为 i时，
进程 Pi可进入；
? 在退出区修改允许进入进程标识：进程 Pi退出时，改
turn为进程 Pj的标识 j；
while (turn != i);
critical section
turn = j;
remainder section
两个进程 Pi,Pj，其中的 Pi
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 1：单标志）
? 缺点：强制轮流进入临界区，没有考虑
进程的实际需要。容易造成资源利用不
充分：在 Pi出让临界区之后,Pj使用临
界区之前,Pi不可能再次使用临界区；
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 2：双标
志，先检查）
? 设立一个标志数组 flag[]：描述进程是否在临
界区，初值均为 FALSE。
? 先检查，后修改：在进入区检查另一个进程是否在
临界区，不在时修改本进程在临界区的标志；
? 在退出区修改本进程在临界区的标志；
while (flag[j]); <a>
flag[i] = TRUE; <b>
critical section
flag[i] = FALSE;
remainder section
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 2：双标
志，先检查）
? 优点：不用交替进入，可连续使用；
? 缺点,Pi和 Pj可能同时进入临界区。
? 按下面序列执行时，会同时进入,"Pi<a>
Pj<a> Pi<b> Pj<b>"。即在检查对方 flag
之后和切换自己 flag之前有一段时间，结
果都检查通过。这里的问题出在检查和修
改操作不能连续进行。
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 3：双
标志，后检查）
? 类似于算法 2，与互斥算法 2的区别在于
先修改后检查。可防止两个进程同时进
入临界区。
flag[i] = TRUE; <b>
while (flag[j]); <a>
critical section
flag[i] = FALSE;
remainder section
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 3：双标
志，后检查）
? 缺点,Pi和 Pj可能都进入不了临界区。
? 按下面序列执行时，会都进不了临界区：
"Pi<a> Pj<a> Pi<b> Pj<b>"。即在切换自
己 flag之后和检查对方 flag之前有一段时间，
结果都切换 flag，都检查不通过。
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（ 算法 4：
先修改，后检查，后修改者等待 ）
? 结合算法 1和算法 3，
是正确的算法
? turn=j;描述可进入的
进程（同时修改标志
时）
flag[i] = TRUE; turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
在进入区先修改后检查，并检查并发修改的先后,
检查对方 flag，如果不在临界区则自己进入－－空闲则入
否则再检查 turn：保存的是较晚的一次赋值，则较晚的进
程等待，较早的进程进入－－先到先入，后到等待
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? 完全利用软件方法，有很大局限性（如不适于
多进程等），现在已很少采用。
? 可以采用中断屏蔽方法（只能适用于单处理器
系统）
? 也可以利用某些硬件指令－－其读写操作由一
条指令完成，因而保证读操作与写操作不被打
断；
? TS(Test and Set)指令
? Swap指令
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? TS(Test and Set)指令
while TS(&lock);
lock = FALSE;
critical section
remainder section
TS(var flag:boolean),
boolean
Begin
TS:=flag;
flag:=true;
end
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? 利用 TS实现进程互斥：每个临界资源设
置一个公共布尔变量 lock，初值为
FALSE
? 在进入区利用 TS进行检查：有进程在临
界区时，重复检查；直到其它进程退出
时，检查通过；
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? Swap指令：交换两个字（字节）的内容
Swap(var a,b:boolean)
Var temo:boolean;
Begin
Temp:=a;
A:=b;
B:=temp;
end
key = TRUE;
do
{
SWAP(&lock,&key);
} while (key);
lock = FALSE;
critical section
remainder section
利用 Swap实现进程互斥：每个临界资源设
置一个公共布尔变量 lock，初值为 FALSE。
每个进程设置一个私有布尔变量 key
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? 硬件方法的优缺点
? 优点
? 适用于任意数目的进程，在单处理器或多处理器上；
? 简单，容易验证其正确性；
? 可以支持进程内存在多个临界区，只需为每个临界
区设立一个布尔变量；
? 缺点
? 等待要耗费 CPU时间，不能实现 "让权等待 "
? 可能 "饥饿 "：从等待进程中随机选择一个进入临界
区，有的进程可能一直选不上
? 可能死锁
第五章 并行性：互斥和同步
5.4 信号量 (semaphore)
? 前面的互斥算法都存在问题，它们是平
等进程间的一种协商机制，需要一个地
位高于进程的管理者来解决公有资源的
使用问题。
? OS可从进程管理者的角度来处理互斥的
问题，信号量就是 OS提供的管理公有资
源的有效手段。
? 信号量代表可用资源实体的数量。
第五章 并行性：互斥和同步
5.4 信号量 (semaphore)
? 5.4.1 信号量
? 5.4.2 信号量及其同步原语
? 5.4.3 同步原语的不可分割性
? 5.4.4 用信号量实现进程的互斥
第五章 并行性：互斥和同步
5.4.1 信号量 (semaphore)
? 1965年，由荷兰学者 Dijkstra提出（ P,V分别是荷
兰语的 test(proberen)和 increment(verhogen)），
是一种卓有成效的进程同步机制。
? 每个信号量 s除一个整数值 s.count（计数）外，还
有一个进程等待队列 s.queue，其中是阻塞在该信号
量的各个进程的标识
? 信号量只能通过初始化和两个标准的原语来访问－－作
为 OS核心代码执行，不受进程调度的打断
? 初始化指定一个非负整数值，表示空闲资源总数（又称
为 "资源信号量 "）－－若为非负值表示当前的空闲资源数，
若为负值其绝对值表示当前等待临界区的进程数
第五章 并行性：互斥和同步
5.4.1 信号量 (semaphore)
? 一个信号量被定义为一个整型变量，其
上定义了 3个操作,
? 初始化
? Wait操作,如果信号量 s≤0,则等待。
如果信号量 s>0，则 s:=s-1。
? Signal操作,s:=s+1;
第五章 并行性：互斥和同步
5.4.1 信号量 (semaphore)
? 信号量 S的物理意义
? 信号量 S用于表示系统中某种资源的数量；
? 当 S>=0时，表示系统中剩余的该资源数量；
? 当 S<0时，表示等待使用该资源的进程数量。
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 二元信号量和一般信号量,
? 二元信号量：仅允许取值为 0和 1，主要用作
互斥变量
? 一般信号量：允许取值为非负整数，主要用
于进程间的一般同步问题
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式和忙等待方式,
? 忙等待方式：进程不阻塞，如果没有资源可用，
进程一直检测信号量值，直到有可用的资源。
? 阻塞等待方式：把等待进程放入与此信号量有关
的阻塞队列，每当由资源可用时，让队列头的进
程占用资源。这种方式下，需要对信号量进程扩
充
? 信号量的数据结构形式由整型变为记录类型
? 信号量的取值允许为负数
? 忙等待多用于多处理器系统；而阻塞等待多用于
单处理器系统。为什么？
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 忙等待方式,
一般信号量同步原语
Wait(S),
while s<=0 do skip
s:=s-1;
Signal(S)
s:=s+1;
二元信号量同步原语
Wait(S),
while s=0 do skip
s:=s-1;
Signal(S)
s:=s+1;
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（一般信号量）,
信号量的定义
type Semaphore=record
value:integer;
L:pointre to PCB
end
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（一般信号量同步原语）,
Wait(S),
s.value:=s.value-1;
if s.value<0 then
begin
Insert(CALLER,s.L);
Block(CALLER);
end
Signal(S),
s.value:=s.value+1;
if s.value<=0 then
begin
Remove(s.L,id);
Wakeup(id);
end
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（二元信号量）,
信号量的定义
type BinarySemaphore=record
value,(0,1);
L:pointre to PCB
end
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（二元信号量同步原语）,
Wait(S),
if s.value=1 then
s.value=0
else begin
Insert(CALLER,s.L);
Block(CALLER);
end
Signal(S),
if s.L Queue is empty then
s.value=1
else begin
Remove(s.L,id);
Wakeup(id);
end
第五章 并行性：互斥和同步
5.4.3 同步原语的不可分割性
? 信号量也是临界资源，对信号量的操作也必
须是互斥的，即同步原语是临界段。
? 解决：规定同步原语具有原子性
? 同步原语的执行不可中断
? 保持进程只见互斥的使用同步原语
? 实现方法：现代操作系统中使用硬件和固件
直接实现同步原语并保证互斥使用和整体性。
第五章 并行性：互斥和同步
5.4.4 用信号量实现进程之间的互斥
? 经典进程同步问题
? 5.4.4.1 生产者 ——消费者问题
? 5.4.4.2阅读者 ——写入者问题
? 5.4.4.3哲学家就餐问题
第五章 并行性：互斥和同步
5.4.4.1 生产者 ——消费者问题
? 问题描述
? 系统中存在一些生产者和消费者进程，他们
共享同一个缓冲池（设缓冲池由 n个缓冲区构
成），生产者进程生产信息并把它们放入缓
冲池中，消费者从缓冲池中取走信息，每个
进程一次只能使用一个缓冲区。
? 互斥关系,
? 当 n个单元装满时，生产者进程必须等待。
? 当缓冲池空时，消费者进程必须等待。
? 生产者进程之间、消费者进程之间互斥
第五章 并行性：互斥和同步
消费者C
生产者P
满
空
消费者C 生产者P
满
空
消费者C
生产者P
满
空
第五章 并行性：互斥和同步
5.4.4.1 生产者 ——消费者问题
? 采用信号量机制,
? full是 "满 "数目，初值为 0,empty是 "空 "数目，
初值为 N。实际上,full和 empty是同一个含
义,full + empty == N
? mutex用于访问缓冲区时的互斥，初值是 1
第五章 并行性：互斥和同步
5.4.4.1 生产者 ——消费者问题
Producer:
begin
repeat
生产数据;
Wait(E);
Wait(mutex);
分配缓冲区并调整指针P;
Signal(Mutex);
装入数据;
Signal(F);
forever
end
Consumer:
begin
repeat
Wait(F);
Wait(mutex);
分配缓冲区并调整指针C;
Signal(Mutex);
取出数据;
Signal(E);
使 用数据；
forever
end
注意每个进程中 Wait操作的顺序，否则可能会死锁，为什么？
什么情况下，信号量 Mutex可以不用？
第五章 并行性：互斥和同步
5.4.4.2 阅读者 ——写入者问题
? 问题描述
? 一个数据集被一些并行进程共享，其中一些进程
要求读数据级的内容，称为阅读者；而另一些进
程要求项数据集写入内容，称为写入者。
? 互斥关系,
? 多个阅读者进程可以同时使用数据集
? 如果有阅读者进程，则写入者进程不能使用数据
集
? 如果有写入者进程，则其它所有进程不能使用数
据集
第五章 并行性：互斥和同步
5.4.4.2 阅读者 ——写入者问题
? 采用信号量机制
? Readcount记录阅读者进程的数目，初值为 0
? Mutex作为访问 Readcount时的互斥信号量
? Wrt作为对写入者进程的互斥信号量
第五章 并行性：互斥和同步
5.4.4.2 阅读者 ——写入者问题
Reader:
begin
Wait(Mutex);
Readcount:=Readcount+1;
if Readcount=1 then
Wait(Wrt);
Signal(Mutex);
读 数据;
Wait(Mutex);
Readcount:=Readcount-1;
if Readcount=0 then
Signal(Wrt);
Signal(Mutex);
end
Writer:
begin
Wait(Wrt);
写数据;
Signal(Wrt);
end
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 问题描述,(the dining philosophers
problem：由 Dijkstra首先提出并解决） 有五
个哲学家围在一张圆桌，桌上放五个碗
和五支筷子。哲学家的动作包括 思考 和
进餐,进餐时需要同时拿起他左边和右
边的两支筷子，思考时则同时将两支筷
子放回原处。如何保证哲学家们的动作
有序进行？如：不出现相邻者同时要求
进餐；不出现有人永远拿不到筷子。
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 分析,
? 筷子为临界资源，五支筷子用五个信号量表示。
? 每个哲学家只与和它相邻的两支筷子有关，让
哲学家们饥饿时总是先拿左边的筷子，然后再
拿右边的筷子。 p1
p2
p3
p4
p5
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 信号量机制
? Chopstick:array[0...4] of Semaphore，每
个数组元素表示一支筷子，取值为 0和 1，
当为 0时表示筷子没有空闲，为 1时表示筷
子闲着。
第五章 并行性：互斥和同步
Var chopstick:array[0,…,4] of semaphore;
Repeat
wait(chopstick[I]);
wait(chopstick[(I+1) mod 5]);
……
eat;
……
signal(chopstick[I]);
signal(chopstick[(I+1) mod 5]);
……
think;
Until false;
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 死锁问题,
? 所有哲学家同时拿着左边的筷子等待右边的
筷子。
? 解决办法,
? 限制同时只允许 4个哲学家进餐。
? 当哲学家左右筷子均可用时，才能拿起筷子
进餐。
? 限制拿起筷子的方法：一部分（偶数）先拿
左边、一部分（奇数）先拿右边。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 管程机制的提出（信号量同步存在缺点）
? 同步操作分散：信号量机制中，同步操作分散在各个
进程中，系统无法有效的控制和管理这些同步原语；
? 用户对同步原语使用不当就可能导致各进程死锁（如
Wait操作的次序错误、重复或遗漏）
? 易读性差：要了解对于一组共享变量及信号量的操作
是否正确，必须通读整个系统或者并发程序；
? 不利于修改和维护：各模块的独立性差，任一组变量
或一段代码的修改都可能影响全局；
? 正确性难以保证：操作系统或并发程序通常很大，很
难保证这样一个复杂的系统没有逻辑错误；
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 管程机制的提出（解决思路）
? 把所有进程对某一临界资源的同步操作集中起来，构
成一个统一管理进程 —“秘书, 进程。凡要访问该临
界资源的进程，都报告该, 秘书, 进程，由该秘书进
程实现进程的同步。该, 秘书, 进程 叫管程 (Monitor)。
? 定义,管程是管理进程间同步的机制，它保证进程互
斥的访问共享变量，并且提供了一个方便的阻塞和唤
醒进程的机构。它定义一个数据结构和能为并发进程
所执行 的一组操作，这组操作能同步进程和改变管
程中的数据。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 管程的特性
? 局部于管程的数据只能被局部于管程的过程
所访问
? 一个进程只有通过调用管程内的过程才能进
入管程访问管程内的数据
? 每次只允许一个进程在管程内执行某个内部
过程
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
管程由三部分
组成,
(1)局部于管程
的共享变量
说明。
(2)对数据进行
操作的一组
过程。
(3)对局部于管
程的数据设
置初始化的
语句。
Waiting Area
Queue of
Entering
processes
Local data
Condition variables
Produre1
Procedure n
Init Code
Exit
Wait(c1)
Wait(cn)
Signal
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 入口等待队列：因为管程是互斥进入的，所以当一个进
程试图进入一个巳被占用的管程时它应当在管程的入口
处等待，因而在管程的入口处应当有一个进程等待队列，
称作入口等待队列。
? 紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继
续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ等待Ｒ继
续,...，如此，在管程内部，由于执行唤醒操作，可能
会出现多个等待进程（已被唤醒，但由于管程的互斥进
入而等待），因而还需要有一个进程等待队列，这个等
待队列被称为紧急等待队列。它的优先级应当高于入口
等待队列的优先级。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 由于管程通常是用于管理资源的，因而在
管程内部，应当存在某种等待机制。当进
入管程的进程因资源被占用等原因不能继
续运行时使其等待。为此在管程内部可以
说明和使用一种特殊类型的变量 ----条件
变量。每个表示一种等待原因，并不取具
体数值－－相当于每个原因对应一个队列。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 同步操作原语 waitc和 signalc：针对条件变量 c，
waitc (c)将自己阻塞在 c队列中,signalc (c)将 c
队列中的一个进程唤醒。
? waitc（ c）：如果紧急等待队列非空，则唤醒第一个
等待者；否则释放管程的互斥权，执行此操作的进程
排入 c队列尾部（紧急等待队列与 c队列的关系：紧急
等待队列是由于管程的互斥进入而等待的队列，而 c
队列是因资源被占用而等待的队列）
? signalc（ c）：如果 c队列为空，则相当于空操作，执
行此操作的进程继续；否则唤醒第一个等待者，执行
此操作的进程排入紧急等待队列的尾部
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 若进程 P唤醒进程 Q，则随后可有两种执行
方式（进程 P,Q都是管程中的进程）
? P等待，直到执行 Q离开管程或下一次等待。
? Q送入 Ready队列，直到执行 P离开管程或下
一次等待。 1980年,Lampson和 Redell采用。
原语由 signalc (x)改为 notifyc (x)。
第五章 并行性：互斥和同步
用管程实现 Producer-Consumer问题
PC问题用 Monitor，定义,
(1)put(item)过程,
生产者利用该过程把生产的信息放入缓冲
池中。
(2)get(item)过程,
消费者利用该过程从缓冲池中获取信息。
(3)条件变量,
notfull—表示缓冲池尚未装满。
notempty—表示缓冲池非空。
第五章 并行性：互斥和同步
PC管程描述 Type PC=monitor
var in,out,count:integer; {缓冲池中投入位置、取出位置、信息量 }
buffer:array[0,…,n -1] of item;{定义缓冲池 }
notfull,notempty:condition;{定义条件变量 }
procedure entry put(item) {定义生产者投入函数 }
begin
if count>=n then notfull.wait;{如果缓冲池满，等待 }
buffer[in]:=nextp;
in:=(in+1) mod n;
count:=count+1;
if notempty.queue then notempty.signal;{如果非空队列
end; 有，则唤醒 }
第五章 并行性：互斥和同步
PC管程描述
procedure entry get(item)
begin
if count<=0 then notempty.wait;
nextc:=buffer[out];
out:=(out+1) mod n;
count:=count-1;
if notfull.queue then notfull.signal;
end
begin in:=out:=0;count:=0;end
第五章 并行性：互斥和同步
PC管程实现
Producer,
begin
repeat
produce an item in nextp;
PC.put(item);
until false;
end
Consumer,
begin
repeat
PC.get(item);
consume the item in nextc;
until false
end
第五章 并行性：互斥和同步
用管程哲学家进餐问题
? 分析,
? 每个哲学家处于三种状态：进餐、饥饿、思考。
var state:array[0,..,4] of
(thinking,hungry,eating);
? 每个哲学家应该有一个条件变量 self[i],
var self:array[0,..,4] of condition;
? 果哲学家饥饿时想进餐，不能获得所需的筷子，则：
self[i].wait,
? 操作过程,
pickup(i):第 i个哲学家拿起筷子；
putdown(i):第 i个哲学家用餐完毕放下筷子。
test(i):测试第 i个哲学家是否具备用餐条件。
第五章 并行性：互斥和同步
测试进餐条件 test()
? 设现在第 i个哲学家想进餐，则应满足,
State[i]=hungry and state[(i+1) mod 5]!=eating
and
State[(i+4) mod 5]!=eating
执行操作,
state[i]:=eating;self[i].signal;
? 说明,
当第 i个哲学家饥饿、且相临的两个哲学家都不在进餐，
则他可以进餐。
第五章 并行性：互斥和同步
拿起筷子 pickup()过程
procedure entry pickup(i:0… 4)
begin
state[i]:=hungry;
test(i);
if state[i]<>eating then self[i].wait;
end
第五章 并行性：互斥和同步
放下筷子过程 putdown()
Procedure entry putdown(i:0..4)
begin
state[i]:=thinking;
test((i+4) mod 5);
test((i+1) mod 5);
end
begin
for I:=0 to 4
do state[I]:=thinking;
end
第五章 并行性：互斥和同步
5.6 进程通信
? 进程通信：进程间的信息传递。
? 进程通信常见的类型,
? 共享内存（ shared Memory system）
? 消息传递（ Message Passing system）
? 管道通信 (Pipe communication)
第五章 并行性：互斥和同步
5.6 进程通信（ 共享内存通信 ）
? 基于共享数据结构的通信方式,
? 进程间共用某些数据结果，通过这些数据结构实现
进程间的通信。这种方式系统仅提供存储区，进程
间的通信、数据结构设置全部由程序员负责。
? 存在问题,效率低下。
? 基于共享存储区的通信方式
? 在系统中划出一块存储区作为共享存储区，进程可
以对共享存储区的数据进行读 /写，以实现进程间的
通信。
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 在进程间的数据交换以消息（ message)为单位 (在
计算机网络中叫报文 )。
? 消息传递系统按实现方式分为,
? 直接通信方式,
? 发送进程直接将消息发送给接收进程，并将接收进程
挂在消息队列上，接收进程从消息缓冲队列中接收消
息。
? 间接通信方式,
? 发送进程把消息发送到某中介上（邮箱），接收进程
从中介中获取消息 —邮箱通信方式。
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 直接通信,发送进程把消息直接发送给目标进程,
send(receiver,message);
receive(sender,message); or
receive(id,message)
?例如,
Repeat
……
produce an item in nextp;
……
send(consumer,nextp);
Until fasle;
Repeat
receive(producer,nextc)
……
consume the item in nextc;
Until false;
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 直接通信（阻塞与不阻塞模式）
? 发送者进程
? 阻塞发送：发送消息后等待接收者的应答信息后才
继续向前执行
? 非阻塞发送：发送消息后不等待接收者的应答信息，
继续向前执行
? 接收者进程
? 有消息等待接收，则接收消息
? 阻塞接收：没有消息到来，阻塞自己等待消息
? 非阻塞接收：没有消息到来，则继续执行
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 直接通信（ 阻塞与不阻塞模式：操作系统实现
方式）
? 非阻塞发送，阻塞接收
? 非阻塞发送，非阻塞接收
? 阻塞发送，阻塞接收
? 请讨论它们的利弊
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 间接通信方式：进程间的通信是通过共享
数据结构的实体 (信箱 )来实现的。
Sender 1
Sender n
…… 信箱
Receiver 1
Receiver n
……
信箱的类型,
?私有信箱
?公共信箱
?共享信箱
发送者和
接收者：
1…n 个
通信需要 创建、
发送与接收、撤
消三个过程
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 间接通信也叫信箱通信。信箱大体可以分成,
? 私有信箱：进程为自己创建一个信箱，其他进程只
能发送信息到信箱中，供该进程读取。单向信箱。
? 公共信箱：由系统创建，供系统所有进程使用。
? 共享信箱：由进程创建并指明是共享。
邮箱
进程 i
进程 j
进程 p
进程 q
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 管道：用于连接一个读进程和一个写进程、实现
两个进程间通信的共享文件 —pipe文件。
? 管道通信：利用管道进行通信。
? 管道通信提供给进程间三种协调能力,
? 互斥
? 同步
? 检测对方是否存在
写进程 Pipe文件 读进程
第五章 并行性：互斥和同步
课后作业
? 书面作业（上交时间：下周）
? 5.17
? 5.18
? 5.19
? 思考（讨论时间：下周）
? 5.1~5.7
? 5.20
第 5章 并行性：互斥和同步
? 5.1 引论
? 5.2 临界段
? 5.3 互斥
? 5.4 信号量
? 5.5 管程
? 5.6 进程间的通信
第五章 并行性：互斥和同步
5.1 引论
? 多道程序设计的出现对计算机系统产生
了极大的影响，推动了操作系统技术的
发展
? 并行的进程之间由于争用资源、互相通
信、互相制约而产生了 互斥, 同步 和 通
信 问题是本章解决的重点内容，也是本
课程的重点内容。
第五章 并行性：互斥和同步
5.1 引论
? 多道程序系统中存在的进程之间有三种典型的
关系,
? 进程之间相互协作，直接知道对方的存在，直到对
方的名字（如进程之间的调用）
? 进程之间通过共享间接知道对方的存在，但并不知
道对方的名字（如共享同一变量或文件）
? 进程之间晚全部知道对方的存在，但因为竞争资源
而形成制约关系（如争用 CPU、内存或硬盘等）
第五章 并行性：互斥和同步
进程的交互关系：可以按照相互感知的程度来分类
相互感知的程度 交互关系 一个进程对其他进程
的影响
潜在的控制问题
相互不感知 ( 完全不了
解其它进程的存在 )
竞争 ( c o m p e tition ) 一个进程的操作对其他
进程的结果无影响
互斥，死锁 （可释放的资
源），饥饿
间接感知 ( 双方都与第
三方交互，如共享资
源 )
通过共享进行协作 一个进程的结果依赖于
从其他进程获得的信息
互斥，死锁 （可释放的资
源），饥饿，数据一致性
直接感知 ( 双方直接交
互，如通信 )
通过通信进行协作 一个进程的结果依赖于
从其他进程获得的信息
死锁，饥饿
互斥，指多个进程不能同时使用同一个资源；
死锁，指多个进程互不相让，都得不到足够的资源；
饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）
第五章 并行性：互斥和同步
一个飞机订票系统，两个终端，运 行 T1, T2 进
程
T 1, T 2,
...,..
R e a d ( x ) ; R e a d ( x ) ;
i f x > = 1 t h e n i f x > = 1 t h e n
x, = x - 1 ; x, = x - 1 ;
w r i t e ( x ) ; w r i t e ( x ) ;
...,..
共享变量的修改冲突
第五章 并行性：互斥和同步
5.2 临界段
设 X初始值为 10
T1.Read(X)
T1.if x>=1 then
//x=10
T1.x=x-1
T1.write(X) // X=9
T2.Read(X)
T2.if x>=1 then
T2.x=x-1
T2.write(X) // X=8
设 X初始值为 10
T1.Read(X)
T2.Read(X)
T1.if x>=1 then //x=10
T1.x=x-1
T1.write(X) // X=9
T2.if x>=1 then //x=10
T2.x=x-1
T2.write(X) // X=9
第五章 并行性：互斥和同步
get copy put
f s t g
有 3个进程,get,copy和 put，它们对 4个存储区域 f,s,t和 g进
行操作。
操作顺序冲突
第五章 并行性：互斥和同步
get copy put
f s t g
f s t g 结果
初始状态 3,4,...,m 2 2 ( 1,2 )
g,c,p 4,5,...,m 3 3 ( 1,2,3) 正确
g,p,c 4,5,...,m 3 3 ( 1,2,2) 错误
c,g,p 4,5,...,m 3 2 ( 1,2,2) 错误
c,p,g 4,5,...,m 3 2 ( 1,2,2) 错误
p,c,g 4,5,...,m 3 2 ( 1,2,2) 错误
p,g,c 4,5,...,m 3 3 ( 1,2,2) 错误
第五章 并行性：互斥和同步
5.2 临界段
? 临界资源 (Critical Resource),在系统中每次
只能一个（有限个）进程访问的资源，
如打印机、磁带机等。临界资源访问控
制是进程同步的基本问题。
? 临界段 (Critical section):每个进程中访问
临界资源的那段代码叫临界段。
第五章 并行性：互斥和同步
5.2 临界段
? 进程使用临界段的原则
? 如果临界资源空闲，在共享同一个临界资源的进程中，
每次只允许一个进程进入自己的临界段；
? 如有多个进程同时要求进入临界段，应在有限时间内
允许其中一个进程进入临界段，不能互相阻塞；
? 进程在临界段内只能停留有限的时间；
? 应保证进程能够在有限时间内进入临界段；
? 处于临界段之外的进程不能阻止其它进程进入临界段；
? 如果进程不能进入临界段，应立即释放 CPU，进入阻
塞状态。
第五章 并行性：互斥和同步
5.3 互斥
? 5.3.1 互斥的软件方法
? 5.3.2 互斥的硬件方法
第五章 并行性：互斥和同步
5.3 互斥
? 例：有两个并行进程 P0和 P1，互斥的共
享某一个资源。 P0和 P1都是无限循环
进程，每次使用资源有限的时间。
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 1：单标志）
? 设立一个公用整型变量 turn：描述允许进入临界
区的进程标识
? 在进入区循环检查是否允许本进程进入,turn为 i时，
进程 Pi可进入；
? 在退出区修改允许进入进程标识：进程 Pi退出时，改
turn为进程 Pj的标识 j；
while (turn != i);
critical section
turn = j;
remainder section
两个进程 Pi,Pj，其中的 Pi
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 1：单标志）
? 缺点：强制轮流进入临界区，没有考虑
进程的实际需要。容易造成资源利用不
充分：在 Pi出让临界区之后,Pj使用临
界区之前,Pi不可能再次使用临界区；
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 2：双标
志，先检查）
? 设立一个标志数组 flag[]：描述进程是否在临
界区，初值均为 FALSE。
? 先检查，后修改：在进入区检查另一个进程是否在
临界区，不在时修改本进程在临界区的标志；
? 在退出区修改本进程在临界区的标志；
while (flag[j]); <a>
flag[i] = TRUE; <b>
critical section
flag[i] = FALSE;
remainder section
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 2：双标
志，先检查）
? 优点：不用交替进入，可连续使用；
? 缺点,Pi和 Pj可能同时进入临界区。
? 按下面序列执行时，会同时进入,"Pi<a>
Pj<a> Pi<b> Pj<b>"。即在检查对方 flag
之后和切换自己 flag之前有一段时间，结
果都检查通过。这里的问题出在检查和修
改操作不能连续进行。
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 3：双
标志，后检查）
? 类似于算法 2，与互斥算法 2的区别在于
先修改后检查。可防止两个进程同时进
入临界区。
flag[i] = TRUE; <b>
while (flag[j]); <a>
critical section
flag[i] = FALSE;
remainder section
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（算法 3：双标
志，后检查）
? 缺点,Pi和 Pj可能都进入不了临界区。
? 按下面序列执行时，会都进不了临界区：
"Pi<a> Pj<a> Pi<b> Pj<b>"。即在切换自
己 flag之后和检查对方 flag之前有一段时间，
结果都切换 flag，都检查不通过。
第五章 并行性：互斥和同步
5.3.1 互斥的软件方法（ 算法 4：
先修改，后检查，后修改者等待 ）
? 结合算法 1和算法 3，
是正确的算法
? turn=j;描述可进入的
进程（同时修改标志
时）
flag[i] = TRUE; turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
在进入区先修改后检查，并检查并发修改的先后,
检查对方 flag，如果不在临界区则自己进入－－空闲则入
否则再检查 turn：保存的是较晚的一次赋值，则较晚的进
程等待，较早的进程进入－－先到先入，后到等待
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? 完全利用软件方法，有很大局限性（如不适于
多进程等），现在已很少采用。
? 可以采用中断屏蔽方法（只能适用于单处理器
系统）
? 也可以利用某些硬件指令－－其读写操作由一
条指令完成，因而保证读操作与写操作不被打
断；
? TS(Test and Set)指令
? Swap指令
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? TS(Test and Set)指令
while TS(&lock);
lock = FALSE;
critical section
remainder section
TS(var flag:boolean),
boolean
Begin
TS:=flag;
flag:=true;
end
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? 利用 TS实现进程互斥：每个临界资源设
置一个公共布尔变量 lock，初值为
FALSE
? 在进入区利用 TS进行检查：有进程在临
界区时，重复检查；直到其它进程退出
时，检查通过；
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? Swap指令：交换两个字（字节）的内容
Swap(var a,b:boolean)
Var temo:boolean;
Begin
Temp:=a;
A:=b;
B:=temp;
end
key = TRUE;
do
{
SWAP(&lock,&key);
} while (key);
lock = FALSE;
critical section
remainder section
利用 Swap实现进程互斥：每个临界资源设
置一个公共布尔变量 lock，初值为 FALSE。
每个进程设置一个私有布尔变量 key
第五章 并行性：互斥和同步
5.3.2 互斥的硬件方法
? 硬件方法的优缺点
? 优点
? 适用于任意数目的进程，在单处理器或多处理器上；
? 简单，容易验证其正确性；
? 可以支持进程内存在多个临界区，只需为每个临界
区设立一个布尔变量；
? 缺点
? 等待要耗费 CPU时间，不能实现 "让权等待 "
? 可能 "饥饿 "：从等待进程中随机选择一个进入临界
区，有的进程可能一直选不上
? 可能死锁
第五章 并行性：互斥和同步
5.4 信号量 (semaphore)
? 前面的互斥算法都存在问题，它们是平
等进程间的一种协商机制，需要一个地
位高于进程的管理者来解决公有资源的
使用问题。
? OS可从进程管理者的角度来处理互斥的
问题，信号量就是 OS提供的管理公有资
源的有效手段。
? 信号量代表可用资源实体的数量。
第五章 并行性：互斥和同步
5.4 信号量 (semaphore)
? 5.4.1 信号量
? 5.4.2 信号量及其同步原语
? 5.4.3 同步原语的不可分割性
? 5.4.4 用信号量实现进程的互斥
第五章 并行性：互斥和同步
5.4.1 信号量 (semaphore)
? 1965年，由荷兰学者 Dijkstra提出（ P,V分别是荷
兰语的 test(proberen)和 increment(verhogen)），
是一种卓有成效的进程同步机制。
? 每个信号量 s除一个整数值 s.count（计数）外，还
有一个进程等待队列 s.queue，其中是阻塞在该信号
量的各个进程的标识
? 信号量只能通过初始化和两个标准的原语来访问－－作
为 OS核心代码执行，不受进程调度的打断
? 初始化指定一个非负整数值，表示空闲资源总数（又称
为 "资源信号量 "）－－若为非负值表示当前的空闲资源数，
若为负值其绝对值表示当前等待临界区的进程数
第五章 并行性：互斥和同步
5.4.1 信号量 (semaphore)
? 一个信号量被定义为一个整型变量，其
上定义了 3个操作,
? 初始化
? Wait操作,如果信号量 s≤0,则等待。
如果信号量 s>0，则 s:=s-1。
? Signal操作,s:=s+1;
第五章 并行性：互斥和同步
5.4.1 信号量 (semaphore)
? 信号量 S的物理意义
? 信号量 S用于表示系统中某种资源的数量；
? 当 S>=0时，表示系统中剩余的该资源数量；
? 当 S<0时，表示等待使用该资源的进程数量。
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 二元信号量和一般信号量,
? 二元信号量：仅允许取值为 0和 1，主要用作
互斥变量
? 一般信号量：允许取值为非负整数，主要用
于进程间的一般同步问题
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式和忙等待方式,
? 忙等待方式：进程不阻塞，如果没有资源可用，
进程一直检测信号量值，直到有可用的资源。
? 阻塞等待方式：把等待进程放入与此信号量有关
的阻塞队列，每当由资源可用时，让队列头的进
程占用资源。这种方式下，需要对信号量进程扩
充
? 信号量的数据结构形式由整型变为记录类型
? 信号量的取值允许为负数
? 忙等待多用于多处理器系统；而阻塞等待多用于
单处理器系统。为什么？
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 忙等待方式,
一般信号量同步原语
Wait(S),
while s<=0 do skip
s:=s-1;
Signal(S)
s:=s+1;
二元信号量同步原语
Wait(S),
while s=0 do skip
s:=s-1;
Signal(S)
s:=s+1;
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（一般信号量）,
信号量的定义
type Semaphore=record
value:integer;
L:pointre to PCB
end
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（一般信号量同步原语）,
Wait(S),
s.value:=s.value-1;
if s.value<0 then
begin
Insert(CALLER,s.L);
Block(CALLER);
end
Signal(S),
s.value:=s.value+1;
if s.value<=0 then
begin
Remove(s.L,id);
Wakeup(id);
end
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（二元信号量）,
信号量的定义
type BinarySemaphore=record
value,(0,1);
L:pointre to PCB
end
第五章 并行性：互斥和同步
5.4.2 信号量及其同步原语
? 阻塞等待方式（二元信号量同步原语）,
Wait(S),
if s.value=1 then
s.value=0
else begin
Insert(CALLER,s.L);
Block(CALLER);
end
Signal(S),
if s.L Queue is empty then
s.value=1
else begin
Remove(s.L,id);
Wakeup(id);
end
第五章 并行性：互斥和同步
5.4.3 同步原语的不可分割性
? 信号量也是临界资源，对信号量的操作也必
须是互斥的，即同步原语是临界段。
? 解决：规定同步原语具有原子性
? 同步原语的执行不可中断
? 保持进程只见互斥的使用同步原语
? 实现方法：现代操作系统中使用硬件和固件
直接实现同步原语并保证互斥使用和整体性。
第五章 并行性：互斥和同步
5.4.4 用信号量实现进程之间的互斥
? 经典进程同步问题
? 5.4.4.1 生产者 ——消费者问题
? 5.4.4.2阅读者 ——写入者问题
? 5.4.4.3哲学家就餐问题
第五章 并行性：互斥和同步
5.4.4.1 生产者 ——消费者问题
? 问题描述
? 系统中存在一些生产者和消费者进程，他们
共享同一个缓冲池（设缓冲池由 n个缓冲区构
成），生产者进程生产信息并把它们放入缓
冲池中，消费者从缓冲池中取走信息，每个
进程一次只能使用一个缓冲区。
? 互斥关系,
? 当 n个单元装满时，生产者进程必须等待。
? 当缓冲池空时，消费者进程必须等待。
? 生产者进程之间、消费者进程之间互斥
第五章 并行性：互斥和同步
消费者C
生产者P
满
空
消费者C 生产者P
满
空
消费者C
生产者P
满
空
第五章 并行性：互斥和同步
5.4.4.1 生产者 ——消费者问题
? 采用信号量机制,
? full是 "满 "数目，初值为 0,empty是 "空 "数目，
初值为 N。实际上,full和 empty是同一个含
义,full + empty == N
? mutex用于访问缓冲区时的互斥，初值是 1
第五章 并行性：互斥和同步
5.4.4.1 生产者 ——消费者问题
Producer:
begin
repeat
生产数据;
Wait(E);
Wait(mutex);
分配缓冲区并调整指针P;
Signal(Mutex);
装入数据;
Signal(F);
forever
end
Consumer:
begin
repeat
Wait(F);
Wait(mutex);
分配缓冲区并调整指针C;
Signal(Mutex);
取出数据;
Signal(E);
使 用数据；
forever
end
注意每个进程中 Wait操作的顺序，否则可能会死锁，为什么？
什么情况下，信号量 Mutex可以不用？
第五章 并行性：互斥和同步
5.4.4.2 阅读者 ——写入者问题
? 问题描述
? 一个数据集被一些并行进程共享，其中一些进程
要求读数据级的内容，称为阅读者；而另一些进
程要求项数据集写入内容，称为写入者。
? 互斥关系,
? 多个阅读者进程可以同时使用数据集
? 如果有阅读者进程，则写入者进程不能使用数据
集
? 如果有写入者进程，则其它所有进程不能使用数
据集
第五章 并行性：互斥和同步
5.4.4.2 阅读者 ——写入者问题
? 采用信号量机制
? Readcount记录阅读者进程的数目，初值为 0
? Mutex作为访问 Readcount时的互斥信号量
? Wrt作为对写入者进程的互斥信号量
第五章 并行性：互斥和同步
5.4.4.2 阅读者 ——写入者问题
Reader:
begin
Wait(Mutex);
Readcount:=Readcount+1;
if Readcount=1 then
Wait(Wrt);
Signal(Mutex);
读 数据;
Wait(Mutex);
Readcount:=Readcount-1;
if Readcount=0 then
Signal(Wrt);
Signal(Mutex);
end
Writer:
begin
Wait(Wrt);
写数据;
Signal(Wrt);
end
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 问题描述,(the dining philosophers
problem：由 Dijkstra首先提出并解决） 有五
个哲学家围在一张圆桌，桌上放五个碗
和五支筷子。哲学家的动作包括 思考 和
进餐,进餐时需要同时拿起他左边和右
边的两支筷子，思考时则同时将两支筷
子放回原处。如何保证哲学家们的动作
有序进行？如：不出现相邻者同时要求
进餐；不出现有人永远拿不到筷子。
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 分析,
? 筷子为临界资源，五支筷子用五个信号量表示。
? 每个哲学家只与和它相邻的两支筷子有关，让
哲学家们饥饿时总是先拿左边的筷子，然后再
拿右边的筷子。 p1
p2
p3
p4
p5
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 信号量机制
? Chopstick:array[0...4] of Semaphore，每
个数组元素表示一支筷子，取值为 0和 1，
当为 0时表示筷子没有空闲，为 1时表示筷
子闲着。
第五章 并行性：互斥和同步
Var chopstick:array[0,…,4] of semaphore;
Repeat
wait(chopstick[I]);
wait(chopstick[(I+1) mod 5]);
……
eat;
……
signal(chopstick[I]);
signal(chopstick[(I+1) mod 5]);
……
think;
Until false;
第五章 并行性：互斥和同步
5.4.4.3 哲学家就餐问题
? 死锁问题,
? 所有哲学家同时拿着左边的筷子等待右边的
筷子。
? 解决办法,
? 限制同时只允许 4个哲学家进餐。
? 当哲学家左右筷子均可用时，才能拿起筷子
进餐。
? 限制拿起筷子的方法：一部分（偶数）先拿
左边、一部分（奇数）先拿右边。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 管程机制的提出（信号量同步存在缺点）
? 同步操作分散：信号量机制中，同步操作分散在各个
进程中，系统无法有效的控制和管理这些同步原语；
? 用户对同步原语使用不当就可能导致各进程死锁（如
Wait操作的次序错误、重复或遗漏）
? 易读性差：要了解对于一组共享变量及信号量的操作
是否正确，必须通读整个系统或者并发程序；
? 不利于修改和维护：各模块的独立性差，任一组变量
或一段代码的修改都可能影响全局；
? 正确性难以保证：操作系统或并发程序通常很大，很
难保证这样一个复杂的系统没有逻辑错误；
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 管程机制的提出（解决思路）
? 把所有进程对某一临界资源的同步操作集中起来，构
成一个统一管理进程 —“秘书, 进程。凡要访问该临
界资源的进程，都报告该, 秘书, 进程，由该秘书进
程实现进程的同步。该, 秘书, 进程 叫管程 (Monitor)。
? 定义,管程是管理进程间同步的机制，它保证进程互
斥的访问共享变量，并且提供了一个方便的阻塞和唤
醒进程的机构。它定义一个数据结构和能为并发进程
所执行 的一组操作，这组操作能同步进程和改变管
程中的数据。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 管程的特性
? 局部于管程的数据只能被局部于管程的过程
所访问
? 一个进程只有通过调用管程内的过程才能进
入管程访问管程内的数据
? 每次只允许一个进程在管程内执行某个内部
过程
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
管程由三部分
组成,
(1)局部于管程
的共享变量
说明。
(2)对数据进行
操作的一组
过程。
(3)对局部于管
程的数据设
置初始化的
语句。
Waiting Area
Queue of
Entering
processes
Local data
Condition variables
Produre1
Procedure n
Init Code
Exit
Wait(c1)
Wait(cn)
Signal
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 入口等待队列：因为管程是互斥进入的，所以当一个进
程试图进入一个巳被占用的管程时它应当在管程的入口
处等待，因而在管程的入口处应当有一个进程等待队列，
称作入口等待队列。
? 紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继
续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ等待Ｒ继
续,...，如此，在管程内部，由于执行唤醒操作，可能
会出现多个等待进程（已被唤醒，但由于管程的互斥进
入而等待），因而还需要有一个进程等待队列，这个等
待队列被称为紧急等待队列。它的优先级应当高于入口
等待队列的优先级。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 由于管程通常是用于管理资源的，因而在
管程内部，应当存在某种等待机制。当进
入管程的进程因资源被占用等原因不能继
续运行时使其等待。为此在管程内部可以
说明和使用一种特殊类型的变量 ----条件
变量。每个表示一种等待原因，并不取具
体数值－－相当于每个原因对应一个队列。
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 同步操作原语 waitc和 signalc：针对条件变量 c，
waitc (c)将自己阻塞在 c队列中,signalc (c)将 c
队列中的一个进程唤醒。
? waitc（ c）：如果紧急等待队列非空，则唤醒第一个
等待者；否则释放管程的互斥权，执行此操作的进程
排入 c队列尾部（紧急等待队列与 c队列的关系：紧急
等待队列是由于管程的互斥进入而等待的队列，而 c
队列是因资源被占用而等待的队列）
? signalc（ c）：如果 c队列为空，则相当于空操作，执
行此操作的进程继续；否则唤醒第一个等待者，执行
此操作的进程排入紧急等待队列的尾部
第五章 并行性：互斥和同步
5.5 管程 (Monitor)
? 若进程 P唤醒进程 Q，则随后可有两种执行
方式（进程 P,Q都是管程中的进程）
? P等待，直到执行 Q离开管程或下一次等待。
? Q送入 Ready队列，直到执行 P离开管程或下
一次等待。 1980年,Lampson和 Redell采用。
原语由 signalc (x)改为 notifyc (x)。
第五章 并行性：互斥和同步
用管程实现 Producer-Consumer问题
PC问题用 Monitor，定义,
(1)put(item)过程,
生产者利用该过程把生产的信息放入缓冲
池中。
(2)get(item)过程,
消费者利用该过程从缓冲池中获取信息。
(3)条件变量,
notfull—表示缓冲池尚未装满。
notempty—表示缓冲池非空。
第五章 并行性：互斥和同步
PC管程描述 Type PC=monitor
var in,out,count:integer; {缓冲池中投入位置、取出位置、信息量 }
buffer:array[0,…,n -1] of item;{定义缓冲池 }
notfull,notempty:condition;{定义条件变量 }
procedure entry put(item) {定义生产者投入函数 }
begin
if count>=n then notfull.wait;{如果缓冲池满，等待 }
buffer[in]:=nextp;
in:=(in+1) mod n;
count:=count+1;
if notempty.queue then notempty.signal;{如果非空队列
end; 有，则唤醒 }
第五章 并行性：互斥和同步
PC管程描述
procedure entry get(item)
begin
if count<=0 then notempty.wait;
nextc:=buffer[out];
out:=(out+1) mod n;
count:=count-1;
if notfull.queue then notfull.signal;
end
begin in:=out:=0;count:=0;end
第五章 并行性：互斥和同步
PC管程实现
Producer,
begin
repeat
produce an item in nextp;
PC.put(item);
until false;
end
Consumer,
begin
repeat
PC.get(item);
consume the item in nextc;
until false
end
第五章 并行性：互斥和同步
用管程哲学家进餐问题
? 分析,
? 每个哲学家处于三种状态：进餐、饥饿、思考。
var state:array[0,..,4] of
(thinking,hungry,eating);
? 每个哲学家应该有一个条件变量 self[i],
var self:array[0,..,4] of condition;
? 果哲学家饥饿时想进餐，不能获得所需的筷子，则：
self[i].wait,
? 操作过程,
pickup(i):第 i个哲学家拿起筷子；
putdown(i):第 i个哲学家用餐完毕放下筷子。
test(i):测试第 i个哲学家是否具备用餐条件。
第五章 并行性：互斥和同步
测试进餐条件 test()
? 设现在第 i个哲学家想进餐，则应满足,
State[i]=hungry and state[(i+1) mod 5]!=eating
and
State[(i+4) mod 5]!=eating
执行操作,
state[i]:=eating;self[i].signal;
? 说明,
当第 i个哲学家饥饿、且相临的两个哲学家都不在进餐，
则他可以进餐。
第五章 并行性：互斥和同步
拿起筷子 pickup()过程
procedure entry pickup(i:0… 4)
begin
state[i]:=hungry;
test(i);
if state[i]<>eating then self[i].wait;
end
第五章 并行性：互斥和同步
放下筷子过程 putdown()
Procedure entry putdown(i:0..4)
begin
state[i]:=thinking;
test((i+4) mod 5);
test((i+1) mod 5);
end
begin
for I:=0 to 4
do state[I]:=thinking;
end
第五章 并行性：互斥和同步
5.6 进程通信
? 进程通信：进程间的信息传递。
? 进程通信常见的类型,
? 共享内存（ shared Memory system）
? 消息传递（ Message Passing system）
? 管道通信 (Pipe communication)
第五章 并行性：互斥和同步
5.6 进程通信（ 共享内存通信 ）
? 基于共享数据结构的通信方式,
? 进程间共用某些数据结果，通过这些数据结构实现
进程间的通信。这种方式系统仅提供存储区，进程
间的通信、数据结构设置全部由程序员负责。
? 存在问题,效率低下。
? 基于共享存储区的通信方式
? 在系统中划出一块存储区作为共享存储区，进程可
以对共享存储区的数据进行读 /写，以实现进程间的
通信。
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 在进程间的数据交换以消息（ message)为单位 (在
计算机网络中叫报文 )。
? 消息传递系统按实现方式分为,
? 直接通信方式,
? 发送进程直接将消息发送给接收进程，并将接收进程
挂在消息队列上，接收进程从消息缓冲队列中接收消
息。
? 间接通信方式,
? 发送进程把消息发送到某中介上（邮箱），接收进程
从中介中获取消息 —邮箱通信方式。
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 直接通信,发送进程把消息直接发送给目标进程,
send(receiver,message);
receive(sender,message); or
receive(id,message)
?例如,
Repeat
……
produce an item in nextp;
……
send(consumer,nextp);
Until fasle;
Repeat
receive(producer,nextc)
……
consume the item in nextc;
Until false;
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 直接通信（阻塞与不阻塞模式）
? 发送者进程
? 阻塞发送：发送消息后等待接收者的应答信息后才
继续向前执行
? 非阻塞发送：发送消息后不等待接收者的应答信息，
继续向前执行
? 接收者进程
? 有消息等待接收，则接收消息
? 阻塞接收：没有消息到来，阻塞自己等待消息
? 非阻塞接收：没有消息到来，则继续执行
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 直接通信（ 阻塞与不阻塞模式：操作系统实现
方式）
? 非阻塞发送，阻塞接收
? 非阻塞发送，非阻塞接收
? 阻塞发送，阻塞接收
? 请讨论它们的利弊
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 间接通信方式：进程间的通信是通过共享
数据结构的实体 (信箱 )来实现的。
Sender 1
Sender n
…… 信箱
Receiver 1
Receiver n
……
信箱的类型,
?私有信箱
?公共信箱
?共享信箱
发送者和
接收者：
1…n 个
通信需要 创建、
发送与接收、撤
消三个过程
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 间接通信也叫信箱通信。信箱大体可以分成,
? 私有信箱：进程为自己创建一个信箱，其他进程只
能发送信息到信箱中，供该进程读取。单向信箱。
? 公共信箱：由系统创建，供系统所有进程使用。
? 共享信箱：由进程创建并指明是共享。
邮箱
进程 i
进程 j
进程 p
进程 q
第五章 并行性：互斥和同步
5.6 进程通信（ 消息传递通信 ）
? 管道：用于连接一个读进程和一个写进程、实现
两个进程间通信的共享文件 —pipe文件。
? 管道通信：利用管道进行通信。
? 管道通信提供给进程间三种协调能力,
? 互斥
? 同步
? 检测对方是否存在
写进程 Pipe文件 读进程
第五章 并行性：互斥和同步
课后作业
? 书面作业（上交时间：下周）
? 5.17
? 5.18
? 5.19
? 思考（讨论时间：下周）
? 5.1~5.7
? 5.20
