第 5章 并行性：同步和互斥
? 概述
? 临界段
? 互斥
? 信号量
? 管程
? 进程间的通信
5.1 概 述
? 并行技术的发展
? 并发环境中进程间的关系
? 进程同步
? 进程互斥
一、并行技术的发展
? 多道程序设计
? 多处理器系统
? 分布式处理系统
二、并发环境中进程间的关系
间接制约关系,
源于资源共享
直接制约关系,
源于进程合作
三、进程同步
同步关系,
指散布在不同进程中的若干程序片段，它
们的运行必须严格按照规定的某种先后次
序来进行，这种先后次序依赖于要完成的
任务。
同步机制,
保证这种同步关系相应机制为同步机制。
例：一个用户作业：两个矩阵求逆后相加
加法进程
求逆进程
求逆进程
进程之间有一定的先后执行次序
例,
司机 P1 售票员 P2
while (true) while (true)
{ {
启动车辆； 关门；
正常运行； 售票；
到站停车； 开门；
} }
四,进程互斥
互斥关系,（间接制约）
指散布在不同进程中的若干程序片段，当
某个进程运行其中一个程序片段时，其它
进程就不能运行它们中的任一程序片段,
只能等到该进程运行完这个程序片段后才
可运行。
互斥可看成是一种特殊的同步关系。
5.2 临界段
? 临界段的提出
? 临界段的互斥要求
一、临界段的提出
? 两个例子（进程的输出结果取决于进程
运行的精确时序）
? 临界资源：一次仅能为一个进程使用的
资源。
硬件资源：输入机，打印机。
软件资源：变量，队列，表格。
? 临界段：进程中访问共享变量的代码段。
二、使用临界段的原则,
有空让进,当无进程在临界段时，任何有权使用
临界段的进程可进入
无空等待,不允许两个以上的进程同时进入临界
段
多中择一,当无进程在临界段，而同时有多个进
程要求进入临界段，只能让其中之一
进入临界段，其他进程须等待
有限等待,任何进入临界段的要求应在有限的时
间内得到满足
让权等待,处于等待状态的进程应放弃占用 CPU,
以使其他进程有机会使用 CPU
5.3 互斥
进程互斥的解决方法,
1、互斥的软件方法
2、互斥的硬件方法
硬件方法
允许在一个存储周期内测试和修改一个字的
内容，或者交换两个字的内容,指令的执行
不可中断。
? TS指令
? SWAP指令
? 开关中断指令
硬件解法 (1)
,测试并设置” TS指令
function TS (var flag,
boolean):boolean
begin
TS:= flag;
flag:= true;
end;
while TS(lock) do skip;
临界段
lock, = false;
硬件解法 (2)
,交换” SWAP指令
procedure SWAP ( var
a,b:boolean)
begin
temp:=a;
a,= b;
b,= temp;
end
key,= true;
repeat
SWAP(lock,key);
until key = false;
临界区
lock:=false;
硬件解法 (3)
,开关中断”指令
进入临界区前执行,
执行“关中断”指令
离开临界区后执行,
执行“开中断”指令
5.4 信号量
信号量概念
信号量及同步原语
信号量的应用
一、信号量的概念
1、概念：信号量表示 资源 的物理实体，是
一个 与队列有关的整体变量,除对其初始
化外，其值仅能由 wait和 signal两种不可中
断的操作 来改变。
2、对信号量 S的操作有两个,wait 与 signal。
(又称同步原语）表示为 wait(s),signal(s),
二、信号量及同步原语
1、信号量分类
? 二元信号量：它允许取值仅为 0,1，其
初始值为 1，主要用于解决进程互斥问题。
? 一般信号量：取值不限于 0和 1，其初值
为 0或为某个正整数 n,主要用于进程间
的同步。
2、同步原语的实现
同步原语的描述有两种不同的形式,
阻塞等待方式，忙等待方式。
（ 1）阻塞等待方式
WAIT（ S）
判断 S
进程继续 阻塞该进程
将进程插入 S的等待队
列 L中, 重新调度
SIGNAL（ S）
S=S+1
判断 S
进程
继续
唤醒等待队列中
的一个进程，重
新调度
S>0 S<0 S<=0
S=S-1
S>=0
?信号量的数据结构
(将信号量定义进一步扩充）
type s = record
value, integer ;
L, pointer to PCB; 指向等待队列的指针
end
?一般信号量上的同步原语
wait(s),
s.value,= s.value -1;
if s.value < 0
then begin
Insert ( CALLER,s.L);
Block (CALLER ) ;
end
?一般信号量上的同步原语
signal(s),
if s.value =1
then begin
remove (s.L,id) ;
wakeup (id) ;
end
?二元信号量上的同步原语
waitB(s),
if s.value =1
then
s.value = 0
else begin
Insert ( CALLER,s.L) ;
Block ( CALLER );
end
?二元信号量上的同步原语
signalB(s),
if L.queue is empty
then
s.value = 1
else begin
Remove ( s.L,id) ;
wakeup ( id );
end
(2)忙等待方式
一般信号量的同步原语 二元信号量的同步原语
WAIT（ S） WAITB（ S）
S?0
S?S-1
N
S=0
S?S-1
N
SIGNAL（ S） SIGNALB（ S）
S ?S-1 S ?S-1
Y Y
信号量定义为整型变量
Wait(s),
while s <= 0 do skip;
s:= s-1;
signal(s),
s,= s+1;
? 忙等待方式和阻塞方式的差别在于不会 出现
负值。
? 阻塞等待方式适用于单处理机方式。
? 忙等待方式适用于多处理机方式。
(3)关于同步原语的 讨论
1) 信号量的物理含义,
S>0表示有 S个资源可用
S=0表示无资源可用
S<0则 | S | 表示 S等待队列中的进程个数
wait(S):表示申请一个资源
signal(S)表示释放一个资源。
信号量的初值应该大于等于 0
2)wait,signal操作必须成对出现，有一个
wait操作就一定有一个 signal操作
当为互斥操作时，它们同处于同一进程
当为同步操作时，则不在同一进程中出现
如果 wait(S1)和 wait(S2)两个操作在一起,
那么 wait操作的顺序至关重要,而两个 signal
操作无关紧要
3）同步原语的优缺点
优点,
简单，而且表达能力强
缺点,
不够安全； 同步原语 使用不当会出现死锁；
遇到复杂同步互斥问题时实现复杂
例：同步原语使用不当会造成死锁
A进程 B进程
WAIT(S1) WAIT(S2)
WAIT(S2) WAIT(S1)
SIGNAL(S2) SIGNAL(S1)
SIGNAL(S1) SIGNAL(S2)
3、同步原语的不可分割性
信号量上的同步原语应该是原子的操作
? 保证进程间互斥地使用同步原语
? 整体操作、不可分割、也就是不可打断
其执行或者说不可中断
三、信号量应用
1、用信号量实现进程间的互斥
2、用信号量实现进程间的同步
1、用信号量实现进程间的互斥
? 设置互斥信号量，赋初值 1，表示临界资
源未被使用。
? 进程描述
例 1 设进程 P,Q共享一台打印机，打印机任何时
刻只能被一个进程使用，而不能同时使用。试用
同步原语描述进程，保证两个进程不同时使用打
印机。
定义信号量 S, 表示打印机数目，初值为 1；
进程 P,·
·
·
wait(s);
使用打印机
signal(s);
例 2 设 n个 进程 P1,P2,...,Pn共享 m台打印机，
试用同步原语描述进程。
定义信号量 S
进程描述
2、用信号量实现进程间的同步
例 1,
同步关系,P1-P2
定义信号量
进程描述
例 2 用同步原语解决司机与售票员的
问题
司机进程,
while
(true){
启动车辆
正常驾驶
到站停车
}…
售票员进程
,
while
(true){
关门
售票
开门
}…
有父母子女四人围坐一起吃水果，父亲不
断削苹果往盆中放，母亲不断削梨往盆中
放，女儿则从盆中取苹果吃，儿子则从盆
中取梨吃，假如盆中最多只能放 N只水果,
试用同步原语协调他们的关系。
四、经典的进程同步问题
1、生产者和消费者问题
2、阅读者和写入者问题
3、哲学家就餐问题
1、生产者和消费者问题
消费者 生产者
缓冲区
1、生产者和消费者问题
由 n个缓冲区构成的一个缓冲存储器，每
个缓冲区可存放一个数据项。
? 生产者：生产数据并将其放入缓冲区中
的进程。
? 消费者：消耗并处理缓冲区中数据的进
程。
（ 1）设置信号量
? mutex, 保证对该缓冲存储器的互斥
执行。其初值为 1。
? E,表示空缓冲区数目，其初值为 n
? F,表示满缓冲区数目，其初值为 0。
(2) 进程同步关系描述
? 生产者进程
? 消费者进程
注意：两个 wait操作顺序不能互换。例如：
当 mutex=1,E=0,F=n时，则对生产者进程：
wait(mutex)成功,wait(E)失败；对消费者
进程,wait(F)成功,wait(mutex)失败，形
成互锁。
(2) 进程同步关系描述
? 生产者进程
? 消费者进程
注意,wait两个操作不能互换。例如：当
mutex=1,E=0,F=n时，则对生产者进程：
wait(mutex)成功,wait(E)失败；对消费者
进程,wait(F)成功,wait(mutex)失败，形
成互锁。
注意,wait两个操作不能互换。
例如：当 mutex=1,E=0,F=n时,
则对生产者进程,wait(mutex)成功，
wait(E)失败；
对消费者进程,wait(F)成功，
wait(mutex)失败，形成互锁。
2、阅读者和写入者问题
一个数据集为若干并发进程共享。
阅读者：要求读取数据
写入者：要求修改数据
要求,
允许多个阅读者同时执行读操作
不允许阅读者、写入者同时操作
不允许多个写入者同时操作
如果阅读者来,
1）无阅读者、写入者，新读者可以读
2）有写入者等，但有其它阅读者正在读，
则新阅读者也可以读
3）有写入者写，新阅读者等
如果写入者来,
1）无阅读者、写入者，新写入者可以写
2）有阅读者，新写入者等待
3）有其它写入者，新写入者等待
（ 1）信号量设置,
? mutex,用于阅读者互斥地访问共享变量
? wrt,用于写入者和其它进程互斥地访问共享变
量，初值为 1。
? readcount 普通整形变量，表示正在读数据的
阅读者个数, 初值为 0。
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）
（ 2）进程 同步关系描述
阅读者进程
写入者进程
wait（ mutex）
写数据
signal（ wrt）
3、哲学家就餐问题
有五个哲学家，他们的生活方式是交替地进行思考
和进餐，哲学家们共用一张圆桌，周围放有五张椅
子，每人坐一张，在圆桌上有五碗面和五个叉子。
当哲学家思考时，他不与同事交谈。饥饿时，便试
图取用左边和右边的叉子，他可能一个也拿不到,
只有在他拿到两个叉子时，方能就餐，吃完后，放
下叉子又继续思考。
（ 1）信号量设置
为每个叉子设置信号量,
VAR fork, array[0..4] of semaphore
信号量的初值均为 1。
(2)进程描述（第 I个哲学家的活动 ）
WAIT( fork[I]) 取左边的叉子
WAIT(fork[(I+1) mod 5]) 取右边的叉子
就餐
SIGNAL(fork[I]) 放下左边的叉子
SIGNAL(fork[(I+1) mod 5]) 放下右边的叉子
思考
五、管程
1、管程的提出
2、管程的定义
3、用管程实现同步
1、管程的提出
采用信号量来编写并发程序，对于共享
变量及信号量的操作将被分散于各个进
程中
缺点,
（１）易读性差，因为要了解对于一组共享变量及信
号量的操作是否正确，则必须通读整个系统或者并
发程序
（ 2）不利于修改和维护，因为程序的局部性很差，所
以任一组变量或一段代码的修改都可能影响全局
（３）正确性难以保证，因为操作系统或并发程序通
常很大，要保证这样一个复杂的系统没有逻辑错误
是很难的
2、管程的定义
指关于共享资源的数据及在其上操作的一组
过程或共享数据结构及其规定的所有操作
管程是管理进程间同步的机制，它保证进
程互斥地访问共享变量，并且提供了一个
方便的阻塞和唤醒进程的机构。
管程的基本特性,
? 局部于管程的数据只能被局部于管程内
的过程所访问
? 一个进程只有通过调用管程内的过程才
能进入管程访问共享数据
? 每次只允许一个进程在管程内执行某个
内部过程
管程的四个组成部分,
管程的四个组成部分,
? 名称
? 数据结构说明
? 对该数据结构进行操作的一组过程 /函数
? 初始化语句
3、用管程实现同步
管程中支持同步的组成部分,
? 局限于管程并仅能从管程内进行访问的
若干条件变量（ Condition）
? 在条件变量上进行操作的两个函数过程
WaitC ( C ) 和 SignalC ( C )
WaitC(C):将调用此函数的进程挂起阻塞在与
该条件变量 C相关的队列中，并使
管程成为可用
SignalC(C),唤醒 条件变量 C的等待队列中
的某个进程；若等待队列为空,
则为空操作
5.6 进程间的通信
一、进程通信的概念
二、进程通信的实现
三、间接通信模式
四、其他通信模式
一、进程通信的概念
指在进程间交换一定数量的信息。
信号量实现的是进程之间的低级通讯，只能传
递简单的信号，不能传递大量信息。如果要在
进程间传递大量信息则要使用通信原语（ Send
/ Receive原语）
二、直接通信模式
1、数据结构
消息、消息缓冲、消息队列
2、通信原语
发送原语,send
接收原语,receive
PCB
.....,
Send(R,M)
.....,
SIZE:消息长度
TEXT:消息正文
.....,
消息链指针
.....,
.....,
Receive(pid,N)
.....,
SIZE:消息长度
TEXT:消息正文
.....,
M,N,
接受进程 R 发送进程 S
消息
消息
消息
.....,
三、间接通信模式
发送进程发消息时不指定接收进程的名
字，而是指定一个中间媒介，即信箱。进
程间通过信箱实现通信
发送原语,send(MB,Message)
接收原语,receive(MB,Message)
四、其他通信模式
? 概述
? 临界段
? 互斥
? 信号量
? 管程
? 进程间的通信
5.1 概 述
? 并行技术的发展
? 并发环境中进程间的关系
? 进程同步
? 进程互斥
一、并行技术的发展
? 多道程序设计
? 多处理器系统
? 分布式处理系统
二、并发环境中进程间的关系
间接制约关系,
源于资源共享
直接制约关系,
源于进程合作
三、进程同步
同步关系,
指散布在不同进程中的若干程序片段，它
们的运行必须严格按照规定的某种先后次
序来进行，这种先后次序依赖于要完成的
任务。
同步机制,
保证这种同步关系相应机制为同步机制。
例：一个用户作业：两个矩阵求逆后相加
加法进程
求逆进程
求逆进程
进程之间有一定的先后执行次序
例,
司机 P1 售票员 P2
while (true) while (true)
{ {
启动车辆； 关门；
正常运行； 售票；
到站停车； 开门；
} }
四,进程互斥
互斥关系,（间接制约）
指散布在不同进程中的若干程序片段，当
某个进程运行其中一个程序片段时，其它
进程就不能运行它们中的任一程序片段,
只能等到该进程运行完这个程序片段后才
可运行。
互斥可看成是一种特殊的同步关系。
5.2 临界段
? 临界段的提出
? 临界段的互斥要求
一、临界段的提出
? 两个例子（进程的输出结果取决于进程
运行的精确时序）
? 临界资源：一次仅能为一个进程使用的
资源。
硬件资源：输入机，打印机。
软件资源：变量，队列，表格。
? 临界段：进程中访问共享变量的代码段。
二、使用临界段的原则,
有空让进,当无进程在临界段时，任何有权使用
临界段的进程可进入
无空等待,不允许两个以上的进程同时进入临界
段
多中择一,当无进程在临界段，而同时有多个进
程要求进入临界段，只能让其中之一
进入临界段，其他进程须等待
有限等待,任何进入临界段的要求应在有限的时
间内得到满足
让权等待,处于等待状态的进程应放弃占用 CPU,
以使其他进程有机会使用 CPU
5.3 互斥
进程互斥的解决方法,
1、互斥的软件方法
2、互斥的硬件方法
硬件方法
允许在一个存储周期内测试和修改一个字的
内容，或者交换两个字的内容,指令的执行
不可中断。
? TS指令
? SWAP指令
? 开关中断指令
硬件解法 (1)
,测试并设置” TS指令
function TS (var flag,
boolean):boolean
begin
TS:= flag;
flag:= true;
end;
while TS(lock) do skip;
临界段
lock, = false;
硬件解法 (2)
,交换” SWAP指令
procedure SWAP ( var
a,b:boolean)
begin
temp:=a;
a,= b;
b,= temp;
end
key,= true;
repeat
SWAP(lock,key);
until key = false;
临界区
lock:=false;
硬件解法 (3)
,开关中断”指令
进入临界区前执行,
执行“关中断”指令
离开临界区后执行,
执行“开中断”指令
5.4 信号量
信号量概念
信号量及同步原语
信号量的应用
一、信号量的概念
1、概念：信号量表示 资源 的物理实体，是
一个 与队列有关的整体变量,除对其初始
化外，其值仅能由 wait和 signal两种不可中
断的操作 来改变。
2、对信号量 S的操作有两个,wait 与 signal。
(又称同步原语）表示为 wait(s),signal(s),
二、信号量及同步原语
1、信号量分类
? 二元信号量：它允许取值仅为 0,1，其
初始值为 1，主要用于解决进程互斥问题。
? 一般信号量：取值不限于 0和 1，其初值
为 0或为某个正整数 n,主要用于进程间
的同步。
2、同步原语的实现
同步原语的描述有两种不同的形式,
阻塞等待方式，忙等待方式。
（ 1）阻塞等待方式
WAIT（ S）
判断 S
进程继续 阻塞该进程
将进程插入 S的等待队
列 L中, 重新调度
SIGNAL（ S）
S=S+1
判断 S
进程
继续
唤醒等待队列中
的一个进程，重
新调度
S>0 S<0 S<=0
S=S-1
S>=0
?信号量的数据结构
(将信号量定义进一步扩充）
type s = record
value, integer ;
L, pointer to PCB; 指向等待队列的指针
end
?一般信号量上的同步原语
wait(s),
s.value,= s.value -1;
if s.value < 0
then begin
Insert ( CALLER,s.L);
Block (CALLER ) ;
end
?一般信号量上的同步原语
signal(s),
if s.value =1
then begin
remove (s.L,id) ;
wakeup (id) ;
end
?二元信号量上的同步原语
waitB(s),
if s.value =1
then
s.value = 0
else begin
Insert ( CALLER,s.L) ;
Block ( CALLER );
end
?二元信号量上的同步原语
signalB(s),
if L.queue is empty
then
s.value = 1
else begin
Remove ( s.L,id) ;
wakeup ( id );
end
(2)忙等待方式
一般信号量的同步原语 二元信号量的同步原语
WAIT（ S） WAITB（ S）
S?0
S?S-1
N
S=0
S?S-1
N
SIGNAL（ S） SIGNALB（ S）
S ?S-1 S ?S-1
Y Y
信号量定义为整型变量
Wait(s),
while s <= 0 do skip;
s:= s-1;
signal(s),
s,= s+1;
? 忙等待方式和阻塞方式的差别在于不会 出现
负值。
? 阻塞等待方式适用于单处理机方式。
? 忙等待方式适用于多处理机方式。
(3)关于同步原语的 讨论
1) 信号量的物理含义,
S>0表示有 S个资源可用
S=0表示无资源可用
S<0则 | S | 表示 S等待队列中的进程个数
wait(S):表示申请一个资源
signal(S)表示释放一个资源。
信号量的初值应该大于等于 0
2)wait,signal操作必须成对出现，有一个
wait操作就一定有一个 signal操作
当为互斥操作时，它们同处于同一进程
当为同步操作时，则不在同一进程中出现
如果 wait(S1)和 wait(S2)两个操作在一起,
那么 wait操作的顺序至关重要,而两个 signal
操作无关紧要
3）同步原语的优缺点
优点,
简单，而且表达能力强
缺点,
不够安全； 同步原语 使用不当会出现死锁；
遇到复杂同步互斥问题时实现复杂
例：同步原语使用不当会造成死锁
A进程 B进程
WAIT(S1) WAIT(S2)
WAIT(S2) WAIT(S1)
SIGNAL(S2) SIGNAL(S1)
SIGNAL(S1) SIGNAL(S2)
3、同步原语的不可分割性
信号量上的同步原语应该是原子的操作
? 保证进程间互斥地使用同步原语
? 整体操作、不可分割、也就是不可打断
其执行或者说不可中断
三、信号量应用
1、用信号量实现进程间的互斥
2、用信号量实现进程间的同步
1、用信号量实现进程间的互斥
? 设置互斥信号量，赋初值 1，表示临界资
源未被使用。
? 进程描述
例 1 设进程 P,Q共享一台打印机，打印机任何时
刻只能被一个进程使用，而不能同时使用。试用
同步原语描述进程，保证两个进程不同时使用打
印机。
定义信号量 S, 表示打印机数目，初值为 1；
进程 P,·
·
·
wait(s);
使用打印机
signal(s);
例 2 设 n个 进程 P1,P2,...,Pn共享 m台打印机，
试用同步原语描述进程。
定义信号量 S
进程描述
2、用信号量实现进程间的同步
例 1,
同步关系,P1-P2
定义信号量
进程描述
例 2 用同步原语解决司机与售票员的
问题
司机进程,
while
(true){
启动车辆
正常驾驶
到站停车
}…
售票员进程
,
while
(true){
关门
售票
开门
}…
有父母子女四人围坐一起吃水果，父亲不
断削苹果往盆中放，母亲不断削梨往盆中
放，女儿则从盆中取苹果吃，儿子则从盆
中取梨吃，假如盆中最多只能放 N只水果,
试用同步原语协调他们的关系。
四、经典的进程同步问题
1、生产者和消费者问题
2、阅读者和写入者问题
3、哲学家就餐问题
1、生产者和消费者问题
消费者 生产者
缓冲区
1、生产者和消费者问题
由 n个缓冲区构成的一个缓冲存储器，每
个缓冲区可存放一个数据项。
? 生产者：生产数据并将其放入缓冲区中
的进程。
? 消费者：消耗并处理缓冲区中数据的进
程。
（ 1）设置信号量
? mutex, 保证对该缓冲存储器的互斥
执行。其初值为 1。
? E,表示空缓冲区数目，其初值为 n
? F,表示满缓冲区数目，其初值为 0。
(2) 进程同步关系描述
? 生产者进程
? 消费者进程
注意：两个 wait操作顺序不能互换。例如：
当 mutex=1,E=0,F=n时，则对生产者进程：
wait(mutex)成功,wait(E)失败；对消费者
进程,wait(F)成功,wait(mutex)失败，形
成互锁。
(2) 进程同步关系描述
? 生产者进程
? 消费者进程
注意,wait两个操作不能互换。例如：当
mutex=1,E=0,F=n时，则对生产者进程：
wait(mutex)成功,wait(E)失败；对消费者
进程,wait(F)成功,wait(mutex)失败，形
成互锁。
注意,wait两个操作不能互换。
例如：当 mutex=1,E=0,F=n时,
则对生产者进程,wait(mutex)成功，
wait(E)失败；
对消费者进程,wait(F)成功，
wait(mutex)失败，形成互锁。
2、阅读者和写入者问题
一个数据集为若干并发进程共享。
阅读者：要求读取数据
写入者：要求修改数据
要求,
允许多个阅读者同时执行读操作
不允许阅读者、写入者同时操作
不允许多个写入者同时操作
如果阅读者来,
1）无阅读者、写入者，新读者可以读
2）有写入者等，但有其它阅读者正在读，
则新阅读者也可以读
3）有写入者写，新阅读者等
如果写入者来,
1）无阅读者、写入者，新写入者可以写
2）有阅读者，新写入者等待
3）有其它写入者，新写入者等待
（ 1）信号量设置,
? mutex,用于阅读者互斥地访问共享变量
? wrt,用于写入者和其它进程互斥地访问共享变
量，初值为 1。
? readcount 普通整形变量，表示正在读数据的
阅读者个数, 初值为 0。
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）
（ 2）进程 同步关系描述
阅读者进程
写入者进程
wait（ mutex）
写数据
signal（ wrt）
3、哲学家就餐问题
有五个哲学家，他们的生活方式是交替地进行思考
和进餐，哲学家们共用一张圆桌，周围放有五张椅
子，每人坐一张，在圆桌上有五碗面和五个叉子。
当哲学家思考时，他不与同事交谈。饥饿时，便试
图取用左边和右边的叉子，他可能一个也拿不到,
只有在他拿到两个叉子时，方能就餐，吃完后，放
下叉子又继续思考。
（ 1）信号量设置
为每个叉子设置信号量,
VAR fork, array[0..4] of semaphore
信号量的初值均为 1。
(2)进程描述（第 I个哲学家的活动 ）
WAIT( fork[I]) 取左边的叉子
WAIT(fork[(I+1) mod 5]) 取右边的叉子
就餐
SIGNAL(fork[I]) 放下左边的叉子
SIGNAL(fork[(I+1) mod 5]) 放下右边的叉子
思考
五、管程
1、管程的提出
2、管程的定义
3、用管程实现同步
1、管程的提出
采用信号量来编写并发程序，对于共享
变量及信号量的操作将被分散于各个进
程中
缺点,
（１）易读性差，因为要了解对于一组共享变量及信
号量的操作是否正确，则必须通读整个系统或者并
发程序
（ 2）不利于修改和维护，因为程序的局部性很差，所
以任一组变量或一段代码的修改都可能影响全局
（３）正确性难以保证，因为操作系统或并发程序通
常很大，要保证这样一个复杂的系统没有逻辑错误
是很难的
2、管程的定义
指关于共享资源的数据及在其上操作的一组
过程或共享数据结构及其规定的所有操作
管程是管理进程间同步的机制，它保证进
程互斥地访问共享变量，并且提供了一个
方便的阻塞和唤醒进程的机构。
管程的基本特性,
? 局部于管程的数据只能被局部于管程内
的过程所访问
? 一个进程只有通过调用管程内的过程才
能进入管程访问共享数据
? 每次只允许一个进程在管程内执行某个
内部过程
管程的四个组成部分,
管程的四个组成部分,
? 名称
? 数据结构说明
? 对该数据结构进行操作的一组过程 /函数
? 初始化语句
3、用管程实现同步
管程中支持同步的组成部分,
? 局限于管程并仅能从管程内进行访问的
若干条件变量（ Condition）
? 在条件变量上进行操作的两个函数过程
WaitC ( C ) 和 SignalC ( C )
WaitC(C):将调用此函数的进程挂起阻塞在与
该条件变量 C相关的队列中，并使
管程成为可用
SignalC(C),唤醒 条件变量 C的等待队列中
的某个进程；若等待队列为空,
则为空操作
5.6 进程间的通信
一、进程通信的概念
二、进程通信的实现
三、间接通信模式
四、其他通信模式
一、进程通信的概念
指在进程间交换一定数量的信息。
信号量实现的是进程之间的低级通讯，只能传
递简单的信号，不能传递大量信息。如果要在
进程间传递大量信息则要使用通信原语（ Send
/ Receive原语）
二、直接通信模式
1、数据结构
消息、消息缓冲、消息队列
2、通信原语
发送原语,send
接收原语,receive
PCB
.....,
Send(R,M)
.....,
SIZE:消息长度
TEXT:消息正文
.....,
消息链指针
.....,
.....,
Receive(pid,N)
.....,
SIZE:消息长度
TEXT:消息正文
.....,
M,N,
接受进程 R 发送进程 S
消息
消息
消息
.....,
三、间接通信模式
发送进程发消息时不指定接收进程的名
字，而是指定一个中间媒介，即信箱。进
程间通过信箱实现通信
发送原语,send(MB,Message)
接收原语,receive(MB,Message)
四、其他通信模式
