第三课 进程的同步和通讯
(Synchronization and
Communication Among
Processes )
教学目的：
在进程的控制的基础上这课引入进程同步和进程同
步机制的概念, 它对并发执行进程的推进序列加以限
制以保证互斥使用临界资源或协同完成任务, 解决程
序并发执行时带来结果不可再现问题 。 这课介绍了用
软件, 硬件, 信号量机制, AND型信号量集, 一般信
号量集, 管程等各种解决进程互斥同步问题的方法,
重点介绍了信号量机制的概念和用信号量机制解决进
程互斥同步问题的方法 。
教学要求：
?熟悉 进程间制约关系，掌握临界资源和临界区概念，掌
握进程同步和进程同步机制,熟悉 利用 软件方法和硬件
技术解决进程同步机制。
?熟练掌握信号量和 P,V操作的概念、定义和实质，熟练
掌握 利用信号量实现进程互斥和同步,熟悉 用信号量 描
述前趋关系。
?掌握 利用信号量解 生产者 -消费者问题,熟悉 利用信号
量解 读者 -写者问题等经典同步问题，掌握进程同步分
析方法。
?了解 用 AND型 信号集机制、一般信号集机制和管程 解 经
典同步问题。
?熟悉 进程通讯的 概念和共享存储器系统、消息传送系统、
管道通信系统 三类高级 通讯 机制，掌握消息缓冲队列通
信机制。
（一） 进程同步
(Synchronization of multiple
processes)
（ 1）进程同步的概念
1。 进程间制约关系
? 在多道程序环境下，系统中各进程以不可预测的速度向
前推进，进程的异步性会造成了结果的不可再现性。为防止
这种现象，异步的进程间推进受到二种限制：
?资源共享关系（ Cooperation Among Processes by Sharing）
多进程共享资源，例如各进程争用一台打印机，这时各进
程使用这台打印机时有一定的限制。每次只允许一个进程使
用一段时间打印机，等该进程使用完毕后再将打印机分配给
其它进程。这种使用原则称为互斥使用。
进程同步的概念 -1
进程之间竞争资源面临三个控制问题：
互斥（ mutual exclusion )指多个进程不能同时使用同一个
资源；
死锁 （ deadlock )指多个进程互不相让，都得不到足够的资源；
饥饿（ starvation )指一个进程一直得不到资源（其他进程可
能轮流占用资源）
相互合作关系
（ Cooperation Among Processes by Communication）
在某些进程之间还存在合作关系，例如一个程序的输入、计
算、打印三个程序段作为三个进程并发执行，由于这三个进程
间存在着相互合作的关系，即先输入再计算、最后再打印的关
系，所以这三个进程在并发执行时推进序列受到限制，要保证
其合作关系正确，进程间这种关系称为同步关系。
2,临界资源和临界区
? 临界资源
象打印机这类资源一次只允许一个进程使用的资源称为临
界资源。属于临界资源有硬件打印机、磁带机等，软件在消
息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘
等资源，它允许进程间共享，即可交替使用，所以它称为共
享资源，而临界资源又称独享资源。
?临界区 (critical sections)
多个进程共享临界资源时必须互斥使用，例如 A和 B两个进程
都需要使用打印机，它们必须互斥使用。如果为了保证结果
的正确性限制 A,B二进程推进序列，规定进程 A执行好再执行
进程 B,这样的限制就显得过死，因为它已不能保证进程 A,B
能并发执行，所以必须把限制减少到最少，以尽可能支持并
发执行。为此把各进程分解，把访问临界资源的那段代码
（称为临界区）与其它段代码分割开来，只对各种进程进入
自己的临界区加以限制，即各进程互斥地进入自己的临界区。
临界资源和临界区
例如进程 A,B的程序如下：
A,begin
Input data 1 form I/O 1 ;
Computer…… ;
Print results 1 by printer ; A临界区
end
B,begin
Input data 1 form I/O 2 ;
Computer…… ;
Print results 2 by printer ; B临界区
end
3,进程同步机制
进程在并发执行时为了保证结果的可再现性，各进
程执行序列必须加以限制以保证互斥地使用临界资
源，相互合作完成任务。
多个相关进程在执行次序上的协调称为进程同步。
用于保证多个进程在执行次序上的协调关系的相应
机制称为进程同步机制。
所有的进程同步机制应遵循下述四条准则：
?空闲让进。
当无进程进入临界区时，相应的临界资源处于空
闲状态，因而允许一个请求进入临界区的进程立即
进入自己的临界区。
进程同步机制
?忙则等待。
当已有进程进入自己的临界区时，即相应的
临界资源正被访问，因而其它试图进入临界区的
进程必须等待，以保证进程互斥地访问临界资源。
?有限等待 。
对要求访问临界资源的进程，应保证进程能
在有限时间进入临界区，以免陷入, 饥饿, 状态。
?让权等待。
当进程不能进入自己的临界区时，应立即释
放处理机，以免进程陷入忙等。
进程同步机制
Mutual exclusion using critical regions
进程同步机制
? 一个由临界区和剩余区 1和剩余区 2程序段组成的进程采
用进程同步机制后的描述如下：
begin remainder section 1； 剩余区 1
进入区
critical section ； 临界区
退出区
remainder section 2 ； 剩余区 2
end
进程同步机制在临界区前加上进入区，它负责对欲访问
的临界资源状态进行检查，以决定是允许该进程进入临
界区还是等待。同时在临界区后加上退出区，它负责释
放临界资源以便其它等待该临界资源的进程使用。
?实现进程互斥和同步的信号量机制有软件方法、硬件指
令方法、信号量机制和管程等。
(2)利用 软件方法解决 进程互斥 (Mutual
Exclusion )问题
问题：有 二个进程 Pi和 Pj互斥共享 临界资源 R，
begin
parbegin
Pi,...…
Pj,.....
parend
end
下列 算法 只写出进程 Pi程序。
利用 软件方法解决 进程互斥问题 -1
算法 1
?该算法设置了一个公用整型变量 turn,用于指示被允许进
入临界区的进程编号，既若 ture=0,表示允许 Pi进程进入
临界区。该算法可确保每次只允许一个进入临界区。但采
用强制两个进程轮流进入临界区，很容易造成资源利用不
充分。
?P0进程, P1进程,
repeat repeat
while turn≠0 do no op while turn≠1 do no op
Critical section Critical section
turn=1 turn=0
Remain Section Remain Section
until false until false
利用 软件方法解决 进程互斥问题 -2
算法 2:
?算法基本思想：在每一个进程访问临界区资源之前，先动查
看一下临界资源是否正被访问，若正被访问，该进程需等待，
否则才进入自己的临界区。为此设置了一个数据 flag[0,1]，
如第 i个元素值为 false表示 Pi进程未进入临界区，值为 true表
示 Pi进程进入临界区。
?P0:repeat P1:repeat
① while flag[1] do no_op; ② while flag[0] do no_op;
③ flag[0]:=true; ④ flag[1]:=true;
⑤ critical_section; ⑥ critical_section;
flag[0]:=false; flag[1]:=false;
remainder section; remainder section;
until false until false
?按 ①②③④⑤ ⑥ 序列执行会出现 Pi和 Pj同时 进入临界区错误。
利用 软件方法解决 进程互斥问题 -3
算法 3:
?算法 2是先检测对方进程状态标志后再置自己标志，由于在检
测和放置中可插入另一个进程时检测操作，会造成二个进程
在分别检测后同时进入临界区。为此算法 3采用先设置自己标
志后再检测对方状态标志，它的程序如下，但也可能出现二
个进程先后同时设置后再分别检测对方状态标志，造成对方
都不能进入临界区，无限期等待。
P0:repeat P1:repeat
① flag[0]:=true; ② flag[1]:=true;
③⑤ while flag[1] do no_op;④ ⑥ while flag[0] do no_op
critical_section; critical_section;
flag[0]:=false; flag[1]:=false;
remainder section; remainder section;
until false until false
利用 软件方法解决 进程互斥问题 -4
算法 4(Peterson 1981)：
?该算法组合了算法 1和算法 4，为了防止二进程进入临界
区而无限期等待，又设置变量 turn,表示不允许进入临界
区的编号，每个进程在先设置自己标志后再设置 turn标志，
不允许另一个进程进入，这时再同时检测另一个进程状
态标志和不允许进入标志，这样可以保证当二个进程同
时要求进入临界区时，只允许一个进程进入临界区。
?Pi,repeat
flag[i]:=true; turn:=j;
while (flag[j] and turn=j) do no_op;
critical_section;
flag[i]:=false;
remainder section;
until false
(3)利用 硬件技术实现进程同步机制
1.提高临界区代码执行中断优先级
这种方法在 UNIX和 Windows NT中都使用，它是在单机系
统中有效地实现互斥的一种方法。
因为在传统操作系统中，打断进程对临界区代码的执
行只有中断请求、中断一旦被接受，系统就有可能调用
其它进程进入临界区，并修改此全局数据库。所以用提
高临界区中断优先级方法就可以屏蔽了其它中断，保证
了临界段的执行不被打断，从而实现了互斥。
在多处理机情况下，用提高临界段代码执行的中断优先
级方法是无法保证互斥的，因为在一个处理机上提高中
断优先级并不能阻止其它处理器上的中断，所以必须采
用其它方法。
2,检测和设置（ TS） 硬件指令
?许多大型机（如 IBM370等）和微型机（如 Intel × 86等）中
都提供了专用的硬件指令，这些指令全部允许对一个字中的
内容进行检测和修正，或交换两个字的内容。特别要指出的
是这些操作都是在一个存储周期中完成，或者说由一条指令
来完成，用这些指令就可以解决临界区问题了。
?在单机系统中，由于中断的原因，使得一个进程在对一个公
用变量先取来并检测其值，然后修改的这两个动作中，可以
插入其它进程对此公用变量的访问和修改，从而破坏了此公
用变量数据的完整性和正确性。在多机系统中，多处理机共
享主存，因而使得某处理机可插入另一处理机的两个存储访
问周期之间，访问并修改此共享变量。
检测和设置（ TS） 硬件指令 -1
对于同一主存块访问要求，即使两个处理机同时提出，存
储控制逻辑也只能让其中之一先访问，但在一个处理机
的两个存储周期间则可以插入另一个处理机的存储周期。
现在用一条指令来完成检测和修改两个功能，这样中断
和插入另一处理机的存储周期均不可能，所以不会影响
此公用变量数据的完整性。
?检测和设置（ TS） 的功能可用 PASCAL语言描述如下：
function TS (var flag,boolean):boolean
begin
TS = flag ；
flag,=true ；
end
这条指令在 Z-8000中称为 TEST指令，在 IBM370中称为 TS指令。
检测和设置（ TS） 硬件指令 -2
?用这些硬件指令可以简单有效地实现互斥。其方法是为每个
临界段或其它互斥资源设置一个布尔变量，例如称为 lock。
当其值为 false则临界区末被使用，反之则说明正有进程在
临界区中执行。于是某进程用 TS指令实现互斥的程序结构为
（设为无限循环进程）：
repeat
...
while TS(lock) do skip ；
进程临界区 CS ；
lock,=false ；
...
until false;
?WindowsNT 内核用来达到多处理器互斥的机制, 转锁,,它
类同于 TS指令机制。
(二 )信号量 (Semaphores)机制
?1965年，荷兰学者 Dijkstra提出的信号量机制是一种卓
有成效的进程同步工具，在长期广泛的应用中，信号量
机制又得到了很大的发展，它从整型信号量机制发展到
记录型信号量机制，进而发展为, 信号集, 机制。现在
信号量机制已广泛应用于 OS中。
（ 1） 记录型信号机制
?记录型信号量结构
在信号量机制中信号量是代表资源物理实体的数据结构，
记录型信号量的数据结构描述如下：
type semaphore=record
value,integer;
L,pointer of PCB;
end
? 信号量的值只能通过两个原子操作,P,V操作来改变，
它代表分配资源和释放资源。
信号量机制－ 1
? 信号量 S取值意义如下：
S,value ＞ 0 ； 表示可供使用资源数
＝ 0 ；表示资源已被占用，无其它进程等待。
＜ 0 （ -n） ； 表示资源已被占用，还有 n个进
程因等待资源而阻塞。
（ 2） 信号量的类型
信号量按联系进程的关系分成二类：
? 公用信号量（互斥信号量）：它为一组需互斥共享临界资源
的并发进程而设置，代表共享的临界资源，每个进程均可对
它施加 P,V操作，即都可申请和释放该临界资源，其初始值
置为 1。
? 专用信号量（同步信号量）：它为一组需同步协作完成任务
的并发进程而设置，只有拥有该资源的进程才能对它施加 P
操作（即可申请资源），而由其合作进程对它施加 V操作
（即释放资源）。
（ 3） P-V操作 (wait(s)和 signal(s) 操作 )
对信号量施加 P,V操作代表申请和释放资源。 P-V操作描述如下：
?proceduce P(S)
var S:semaphore ；
begin
S.value=S.value-1 ；
If S.value<0 then block(S.L) ；
end
?Procefuce V(S)
Var S:semaphore ； ;
begin
S.value=S.value+1 ；
If s.value≤0 then wakeup(S.L) ；
end (练习 )
（ 4） 利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只需
为该资源设置一个互斥信号量 mutex,并设其初值为 1，
然后将各进程的临界区 CS置于 P（ mutex） 和 V(mutex)
操作之间即可。利用信号量实现共享打印机的 A,B
两进程互斥的类并行 PASCAL程序描述如下：
利用信号量实现进程互斥 -1
var mutex:=semaphore:=1 ；
begin
parbegin
A:begin B:begin
Input data 1 from I/0 1 ； Input data 2 from I/O 2 ；
Compute…… ； Compute…… ；
P(mutex) ； P(mutex) ；
Print results1 by printer; Print results2 by printer;
V(mutex) ； V(mutex) ；
end end
parend
end (练习 )
(5)利用信号量实现进程同步
?利用信号量能解决进程间的同步问题，这里以下图所示
的计算进程 C和打印进程 P通过缓冲区 Buffer传送数据的
同步问题为例说明。
Buffer
C P
利用信号量实现进程同步 -1
C和 P两进程基本算法如下：
C,begin P,begin
repeat repeat
Compute next number ; remove from Buffer ;
add to Buffer ; print last number ;
until false until false
end end
?C和 P两进程并发执行，必须在执行序列上遵循以下规则，才
能避免错误。
只有当 C进程把数据送入 Buffer后,P进程才能从 Buffer中取
出数据来打印，否则 P进程只能等待。
只有当 P进程从 Buffer中取走数据后,C进程才能将新计算的
数据再存入 Buffer,否则 C进程也只能等待。
利用信号量实现进程同步 -2
?为了实现进程同步，需采用同步信号量。为了满足第一
条同步规则，设置一个同步信号量 full,它代表的资源
是缓冲器满，它的初值为 0。这个资源是 P进程所拥有,P
进程可以申请该资源，对它施加 P操作，如条件满足 P进
程可从 Buffer中取数。而 P进程的合作进程 C对 full信号
量施加 V操作，即它可释放该资源。当 C进程将数据存入
Buffer后，即可释放该资源供 P进程再使用。同样为了满
足第二条同步规则，设置另一个同步信号量 empty,它代
表的资源是缓冲器空，它的初值为 1 。缓冲器空这个资
源是进程 C所拥有，它可以申请该资源，对它施加 P操作。
而它的合作进程 P对 empty信号量施加 V操作。
?实现 C和 P两进程同步的类 PASCAL程序：
考虑第一个同步关系－ C加入话后 P再取var,full:semaphore:=0 ；
begin
parbegin
C,begin
repeat
Compute next number ；
Add to buffer ；
V(full) ；
until false
end
P,begin
repeat
P(full) ；
remove from Buffer ；
Print last number ；
until false
end
parend
end
考虑第二个同步关系－ P取走后 C再加入
var,empty:semaphore:=1 ；
begin
parbegin
C,begin
repeat
Compute next number ；
P(empty) ；
Add to buffer ；
until false
end
P,begin
repeat
remove from Buffer ；
V(empty) ；
Print last number ；
until false
end
parend
end
考虑二个同步关系
var,empty,full:semaphore:=1,0 ；
begin
parbegin
C,begin
repeat
Compute next number ；
P(empty) ；
Add to buffer ；
V(full) ；
until false
end
P,begin
repeat
P(full) ；
remove from Buffer ；
V(empty) ；
Print last number ；
until false
end
parend
end
同步物理意义
?首先由 C进程先将数据加入缓冲区, 再由 P进程从缓
冲区中取出数据 。 为此 设置一个同步信号量 full，
先 做动作的 进程 C在 动作 （ Add to buffer;） 完成后
对信号量 full施加 V操作, 代表释放该资源 。 后 做动
作的 进程 P在 动作 （ Remove from buffer;） 前对信
号量 full施加 P操作, 代表申请该资源 。 信号量 full
它代表的资源是缓冲器满 （ 装满输入数据 ）, 它的
初值为 0,它代表的资源是后 做动作的 进程 P所拥有 。
?也可以理解为：先 做动作的 进程 C在 动作 完成后对同
步信号量施加 V操作, 代表发送消息；后 做动作的 进
程 P在 动作 前对同步信号量施加 P操作, 代表测试消
息是否到达 。
(6)利用信号量描述前趋关系
进程间同步关系也可用前趋图表示。 C和 P两进程间先计
算好再打印同步关系用前趋图表示如下：
对应这个前趋关系可设置同步信号量 full,它为后继进
程 P拥有，初值为 0。它的并发执行程序如下：
var full, semaphore,=0;
begin
parbegin
C,begin Compute ； V(full) ； end
P,begin P(full) ； Print ； end
parend
end
C P
（三） 利用信号量解 经典进程同步问题
经典进程同步问题是从进程并发执行中归纳的典型例子，这
些问题常用来测试新的同步机制可行性。主要的经典同步问
题有生产者 -消费者问题、读者 -写者问题、哲学家进餐问题
等。
（ 1）生产者 -消费者问题
（ producer-consumer Problem ）
?生产者 -消费者问题是最著名的同步问题，它描述一组生产
者（ P1 …… Pm） 向一组消费者（ C1…… Cq） 提供消息。它们
共享一个有界缓冲池（ bounded buffer pool）,生产者向其
中投放消息，消费者从中取得消息，如下图所示。生产者 -
消费者问题是许多相互合作进程的一种抽象。
利用信号量解 经典进程同步问题 -1
假定缓冲池中有 n个缓冲区，每个缓冲区存放一个消息。由
于缓冲池是临界资源，它只允许一个生产者投入消息，或者
一个消费者从中取出消息。即生产者之间、生产者与消费者
之间、消费者之间都必须互斥使用缓冲池。所以必须设置互
斥信号量 mutex,它代表缓冲池资源，它的数值为 1。
P1 Pm C1 Cq
B0 B1 …, …,.,……… Bn-1
利用信号量解 经典进程同步问题 -2
与计算打印两进程同步关系相同，生产者和消费者二类进程 P
和 C之间应满足下列二个同步条件：
? 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才
能从中提取消息，否则消费者必须等待。
? 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息
放入缓冲区，否则生产者必须等待。
为了满足第一个同步条件，设置一个同步信号量 full,它代
表的资源是缓冲区满，它的初始值为 0，它的值为 n时整个缓
冲池满。这个资源是消费者类进程 C所拥有,C进程可以申请
该资源，对它施加 P操作，而 C进程的合作进程生产者进程 P对
它施加 V操作。同样为了满足第二个同步条件，设置另一个同
步信号量 empty,它代表的资源是缓冲区空，它的初始值为 n，
表示缓冲池中所有缓冲区空。
用类并行 PASCAL语言和信号量机制解生产者 -消费者问题程序：
利用信号量解生产者 -消费者互斥 问题 -1
var mutex,empty,full:semaphore:=1,n,o ；
Buffer, array [0…… n-1] of message ；
in,out, o…… n-1:=0,0 ；
begin
parbegin
P,begin
repeat
Produce a new message m ；
P (mutex) ；
Buffer[in]=m ；
in,=(in+1) mod n ；
V (mutex) ；
until false
end
利用信号量解生产者 -消费者互斥 问题 -2
C,begin
repeat
P (mutex) ；
m,= buffer[out] ；
out, = (out+1) mod n ；
V (mutex) ；
Consume message m ；
until false
end
parend
end
利用信号量解 经典进程同步问题 -3
var mutex,empty,full:semaphore:=1,n,o ；
Buffer, array [0…… n-1] of message ；
in,out, o…… n-1:=0,0 ；
begin
parbegin
P,begin
repeat
Produce a new message m ；
P (empty) ；
P (mutex) ；
Buffer[in]=m ；
in,=(in+1) mod n ；
V (mutex) ；
V (full) ；
until false
end
利用信号量解 经典进程同步问题 -4
C,begin
repeat
P (full) ；
P (mutex) ；
m,= buffer[out] ；
out, = (out+1) mod n ；
V (mutex) ；
V (empty) ；
Consume message m ；
until false
end
parend
end
（ 2） 读者 -写者问题
（ Readers/Writers Problem ）
? 一个数据集（如文件）如果被几个并行进程所共享，有
些进程只要求读数据集内容，它称读者，而另一些进程则
要求修改数据集内容，它称写者，几个读者可以同时读些
数据集，而不需要互斥，但一个写者不能和其它进程（不
管是写者或读者）同时访问些数据集，它们之间必须互斥。
? 设置互斥 信号量 wmutex 表示写者间、读者和写者间互斥，
读者和写者主要 程序如下：
reader,writer:
第一个读者到时 P（ wmutex） P（ wmutex）
Read Text Write Text
最后 一个读者离开时 V（ wmutex） V（ wmutex）
读者 -写者问题 -1
?用 readcount变量来记录读者数，读者 程序为：
if readcount=0 then P（ wmutex） ;
readcount= readcount+1;
Read Text
readcount= readcount-1;
if readcount=0 then V（ wmutex） ;
?由于 readcount是读者间共享变量，属于临界资源，它也需互
斥，为此又增设互斥信号量 rmutex.
用类并行 PASCAL语言和信号量机制解读者 -写者问题程序：
读者 -写者问题 -2
Var rmutex,wmutex,semaphore:=1,1 ;
readcount,integer,=0 ;
begin
parbegin
reader:begin writer:begin
repeat repeat
P(rmutex) P(wmutex);
if readcount=0 then P(wmutex); Write Text;
readcunt=readcount+1; V(wmutex);
V(rmutex) until false
Read Text end
P(rmutex)
readcount=readcount-1 ;
if readcount=0 then V(wmutex) ;
V(rmutex)
until false
end
parend
end
(3)Dining-Philosophers Problem哲学家就餐问题
?Shared data semaphore chopstick[5];
The structure of Philosophers i
?Philosopher i:
repeat
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
…
eat;
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think;
…
until false;
（ 3） 进程同步的分析
? 用信号量机制解决进程同步问题需在程序中正确设置信号
量和在适当位置安排 P,V操作。例如生产者 -消费者问题中，
用于互斥进入临界区的 P（ mutex）,V(mutex)语句需紧靠着
临界区前和后，而生产者用于同步的 P（ empty） 和 V（ full）
(消费者为 P（ full） 和 V(empty))语句相对临界区就在外面
一层，格式如上程序所述。如在以上问题中生产者的 P
（ empty） 和 P(mutex)先后位置对调，相应消费者的 P（ full）
和 P（ mutex） 先后位置也对调，则生产者和消费者在并发执
行时，在某个执行序列会出现问题。
? 下面介绍如何寻找会发生问题的那个执行序列，分析方法
用下表表示。表左边是生产者和消费者二进程推进序列，此
推进序列需用户寻找；表中间是该操作执行后信号量的变化
值，表中信号量有 mutex,empty和 full； 表的右边是该操作
执行后引起进程 PCB的队列变化。表中队列有就绪队列 RL，
因分别等待 mutex,empty,full信号量而阻塞的队列 QmL、
QeL,和 QfL。
进程同步的分析 -1
?在表中已找到一个推进序列。该序列先执行消费者进程，
由于消费者进程交换了 P操作，消费者进程在先后执行 P
（ muyex） 和 P（ full） 后阻塞在等待 full信号量的队列
中。这时只能执行生产者进程，由于生产者进程也交换
了 P操作，在生产者进程执行了 P（ mutex） 操作后，生产
者进程阻塞在等待 mutex信号量的队列中。这样生产者和
消费者两进程分别阻塞在等待 mutex和 full信号量的队列，
没有进程可以向前推进，系统进入死锁状态。这说明在
生产者 -消费者问题中对同步信号量和互斥信号量的二个
P操作的是不能颠倒，而对互斥信号量和同步信号量的二
个 V操作的顺序交换影响不大。
?生产者、消费者交换 P操作后发生问题的那个执行序列：
进程同步的分析 -2
操 作 操作引起 （信号量）
变化
操作引起 ( 队列 ) 变化事
件 生产者
(P)
消费者
(C)
m u t e x e m p t y full RL Q mL QeL QfL
0 / / 1 n 0 P, C / / /
C
1
/ P
( m u t e x )
0 n 0 P / / /
C
2
/ P ( f u l l ) 0 n -1 P / / C
P
1
P r a d u c e 0 n -1 / / / C
P
2
P
( m u t e x )
-1 n -1 / P / C
（四）经典进程同步问题的其它方法解
（ 1） AND型 /一般 信号集机制
1。定义：
为了解决一个进程一次同时能申请几类临界资源，引入
AND型信号量 集 机制；为了对每类资源又能同时申请几个，
又扩充 AND型信号量 集 机制，形成一般信号量 集 机制，它的
相应的 Swait,Ssignal操作如下：
Swait(S1,t 1,d 1,…,S n,t n,d n )
if S1 >= t 1 and …..and S n >=t n then
for i:=1 to n do Si = Si - d i ;
endfor
endif
AND型 /一般 信号集机制 -1
else
Place the executing process in the waiting queue of the first Si
with Si< t i and set its program counter to the beginning of
the the Swait operation.
Ssignal(S1,d 1,…,S n,d n )
for i:=1 to n do Si = Si + d i ;
Remove all the process waiting in the queue associated with Si
into the ready queue.
endfor
2,用 一般 信号集机制解读者 -写者问题
var RN integer ;
L,mx, semaphore,=RN,1 ;
begin
parbegin
reader, begin
repeat
Swait (L,1,1 ) ;
Swait (mx,1,0 ) ;
perform read operation
Ssignal (L,1) ;
until false ;
end
用 一般 信号集机制解读者 -写者问题 -1
writer,begin
repeat
Swait (mx,1,1,L,RN,0 );
perform write operation
Ssignal (mx,1 ) ;
until false ;
end
parend
end
(2)管程 (Monitors)
1,管程的引入
用信号量和 P,V操作来解决进程互斥同步问题, 需在程序
中适当位置安排 P,V操作, 否则会造成死锁错误, 为了解决
分散编程带来的困难, 采用资源集中管理的方法, 用某种数
据结构表示某类资源, 并将这种数据结构以及与资源有关操
作集中一起定义为类程或管程, 并用类程管理独立资源, 用
管程管理共享资源, 它两是能被进程调用的实体 。
2。 管程定义
管程是由一些共享数据、能为并发进程所执行的作用在共享
数据上的操作的集合、初始代码以及存取权组成。
管程提供了一种可以允许多进程安全有效地共享抽象数据
类型的机制，管程实现同步机制由“条件结构”（ condition
construct） 所提供。为实现进程互斥同步，必须定义一些条
件变量，（例如,var notempty,,notfull,condition）,这些
条件变是只能被 wait和 signal 操作所访问。
Structure of Monitor
Eotrance
Queue of
Entering
ProcessesMonitior Waiting Area
Condition c1
C1.wait
.
.
.
condition cn
.
.
.
Cn.wait
Next Queue
Next.signal Exit
M0NITOR
Local Data
Condition Variables
Procedure 1
Procedure k
Initialization Code
管程 -1
notfull, wait操作意味着调用该操作的进程将被挂起，另至直
一个进程执行；
而 notfull, signal操作仅仅是启动一个被挂起的进程，如无挂起
进程则 notfall, signal操作相当于空操作，不改变 notfull状态，
这不同于 v操作。
并发语言及其编译系统自动地处理多个进程互斥地和串行
地调用管程的过程和函数并加工管程的数据。
3。利用管程解决生产者 ―― 消费者问题
建立一个管程 PC,它包括两个过程 put（ item） 和 get
（ item）,它们分别执行将生产的消息放入缓冲池和从缓冲
池取出消息的操作，设置一变量 count表示缓冲池已存消息数
目。
管程 -2
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 ;
beffer ( in ), = nextp ;
in,= (in+1) mod n ;
count = count + 1 ;
if notempty.queue then notempty.signal ;
end
管程 -3
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
利用管程解决生产者 ―― 消费者问题，其中生产者和消费者
程序为
管程 -4
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
（五） 进程 通信
(Interprocess Communication)
高级通信机制可归结为三大类：共享存储器系统，消息传送
系统和管道通信系统。
（ 1）共享存储器系统
1,基于共享数据结构的通信方式
在这种通信方式中，要求诸进程公用某个数据结构，进程
通过它们交换信息。如在生产者 -消费者问题中，就是把缓
冲池（有界缓冲区）这种数据结构用来作通信的。这种通信
方式是低效的，只适用传送少量的数据。
2,基于共享存储区的通信方式
共享存储区是 UNIX系统 V中通信速度最高的一种通信机
制，它包含在进程通信软件包 IPC中。 该方法为了传送
大量数据，在存储区中划出一块存储区，供多个进程共
享，共享进程通过对这一共享存储区中的数据进行读或
写来实现通信。当进程 A要利用共享存储区进行通信时，
应先利用系统调用 shmget建立一个共享存储区。执行该
系统调用时，核心首先检查共享存储区表，该表是系统
范围的数据结构，每个共享存储区在该表中占一表项。
如末找到，则分配一系统空闲区作为共享区的页表区，
分配相应的内存块，有关参数填入页表中。返回共享存
储器的描述符 shmid。 进程 B要利用共享存储区与进程 A
通信时，也要先利用系统调用 shmget,此时核心检查共
享存储区表找到了指定的表项，则返回该表项的描述符
shmid。
基于共享存储区的通信方式 -1
进程 A和 B在建立了一个共享存储区并获得了其描
述符后，还需分别利用系统调用 shmat将共享存储区
附接到各自进程的虚地址空间上，如图 3-8所示。此
后共享存储区便成为进程虚地址空间的一部分，进
程可采取与其它虚地址空间一样的存取方法来存取
它。
进程 A和 B利用共享存储区进行通信时，需自己设
置进程同步机制，才能保证实现正确的通信。
进程 A和 B在利用共享存储区进行通信时，还可利
用系统调用 shmctl对共享存储区的状态信息（如长
度，当前连接的进程数等）进行读取，也可设置和
改变共享存储区的属性（如共享存储区的许可权
等）。最后仍可利用系统调用 shmctl断开进程与共
享存储区的连接。当所有进程都断开了与共享存储
区的连接时，便可取消共享存储区。
基于共享存储区的通信方式 -2
A正文
A数据
A栈
OS
A正文
B正文
:
:
共享
存储
器
.
B正文
B数据
B栈
进程 A 进程 B
虚地址空间 内存空间 虚地址空间
（ 2） 消息传递系统（ Message passing system）
消息传递系统分为直接通信方式和间接通信方式两种。
1,直接通信方式
这是指发送进程利用 OS提供的发送命令直接把消息发送给接
收进程，并将它挂在接收进程的消息缓冲队列上。接收进程
利用 OS提供的接收命令直接从消息缓冲队列中取得消息。此
时要求发送进程和接收进程都以显示的方式提供对方的标识
符，通常系统提供下述两条通信原语：
Send(Receiver,message) ；
Receive(Sender,message) ； 或 (Receive (message)) ；
直接通信的实例 -消息缓冲队列通信机制。
消息传递系统 -1
?消息缓冲队列通信原理
消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，
其中每个缓冲区可以存放一个消息。当发送进程要发送消息
时先要向系统申请一个缓冲区，然后把消息写进去，接着把
该缓冲区连接到接收进程的消息缓冲队列中。接收进程可以
在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，
并释放该缓冲区。
?消息缓冲队列通信的数据结构有消息缓冲区和进程 PCB中有关
通信的扩充数据项，消息缓冲区描述如下：
?type message buffer=record
sender ； 发送进程的标识符
size ； 消息长度
text ； 消息正文
next ； 指向下一个消息缓冲区的指针
end
图,消息缓冲队列通信的发送和接收过程
.
mutex
sm
mq
………,
.
.
send(B,a);
sender,A
size, 13
text,
How are
you?
Next
send,A
size,13
text:
How are
you?
Next:
sender,A
size,5
text,Hello
Next,
sender,A
size:13
text:
How are
you?
Next:0
sender,A
size,5
text,Hello
Next:
.
.
receive(b);
sender,A
size,5
text,Hello
系统管理的－组缓冲区
进程 A 进程 B
进程 B PCB
消息传递系统 -2
? PCB 有关通信的扩充数据项
type PCB = record
.
mutex ； 消息缓冲队列互斥信息量 ；
Sm ； 消息缓冲队列资源信息量 ；
mq ； 消息缓冲队列首指针 ；
,
End
(练习 )
消息传递系统 -3
?发送原语
Proceduce send (receiver,a)
begin
getbuf(a.size,i) ；
i.sender = a.sender i.size = a.size ；
i.text = a.text ； i.next = 0 ；
getid (PCB set,receiver, j) ；
P(j.mutex) ；
insert(j.mq,i) ；
V(j.mutex) ；
V(j.Sm) ；
end
消息传递系统 -4
?接收原语
proceduce receive(b)
begin
j,= internal name ；
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 ；
Releasebuf(i) ；
end
2.间接通信方式
? 在间接通信情况，消息不直接从发送者发送到接收者，而
是发送到暂存消息的共享数据结构组成的队列，这个实体称
为信箱（ mailbox）,因此二个进程通信情况，一个进程发送
一个消息到某个信箱，而另一个进程从信箱中摘取消息。
? 间接通信的使用好处是增加了使用消息的灵活性。发送者
和接收者的关系可能是一对一、多对一，一对多或多对多。
一对一的关系允许一个专用通信链路用于二个进程间的交互，
它能使俩进程间交互不受其它进程错误干予的影响，多对一
的关系对客户／服务器交互特别有用，一个进程对多个其它
进程（用户）提供服务。在这种情况信箱经常称作为端口
(port)。 一对多关系允许一个发送进程和多个接收进程交互，
这可用来将消息广播 (broadcast)给一组进程。
消息传递系统 -5
?进程与信箱的联系有二种：静态和动态。端口经常与特定的
进程保持静态的联系，即端口创建后永久地分配给某个进程。
同样一对一关系是典型地规定为静态的和永久的。当有许多
发送者时，一个发送者与信箱的联系可以动态发生，例如联
接（ conect） 和去联接原语可以应用于此用途。
?对于端口它是接收进程拥有和创建的。当进程撤消时相应端
口也撤消。对于一般信箱，操作系统可以提供创建和撤消信
箱的服务。
3,UNIX系统消息机制
UNIX系统 V的进程通信软件包 IPC提供了消息机制。
消息机制的数据结构
UNIX系统将消息分为消息首部和消息数据两部分。消息首
部和消息头表的关系、消息首部和消息数据的关系见 下图 。
消息首部：在消息首部中记录有消息的类型、大小、指向消
息数据区的指针、消息队列的链接指针等。
消息传递系统 -6
消息队列头表：消息队列头表的每一表项是作为一个消息
队列的消息头。在消息头中包含了指向消息队列中第一个消
息的指针和指向最后一个消息指针，队列中消息的数目、队
列中消息数据的总字节数等。
队列 0
.
.
队列 i
消 息 首 部
msgh 0
消息缓冲
区 0
消息首部
msgh 8
消 息 缓 冲
区 8
消息首部
msgh 3
消息缓冲
区 3
消 息 首 部
msgh 2
消息缓冲
区 2
消息传递系统 -7
?消息队列的建立和消息队列描述符的获取
msgget(key,msgflg); key_t key ; int msgflg ;
?消息的发送
msgsnd(msgid,msgp,msgsz,msgflg);
int msgid,msgsz,msgflg ; struct msgbuf *msgp ;
?消息的接收
msgrcv(msgid,msgp,msgsz,msgtpy,msgflg);long
msgtpy;
int msgid,msgsz,msgflg ; struct msgbuf *msgp ;
?消息队列的操纵
msgctl(msgid,cmd,buf); int msgid,cmd;
struct msgid_ds *buf;
(3)管道通信
UNIX系统在 OS的发展上最重要的贡献之一便是该系统首创了
管道（ pipes） 。
? 管道是指用于连接一个读进程和一个写进程，以实现它们
之间通信的共享文件，又称为 pipe文件。向管道（共享文件）
提供输入的发送进程（即写进程），以字符形式将大量的数
据送入管道，而接收管道输出的接收进程（即读进程）可从
管道中接收数据。管道通信是基于文件系统形式的一种通信
方式。
? 管道分为无名管道和有名管道两种类型。无名管道是早期
UNIX版本已提供的，它是一个只存在于打开文件机构中的一
个临时文件，从结构上没有文件路径名，不占用文件目录项。
无名管道利用系统调用 pipe(filedes)创建，只用该系统调用
所返回的文件描述符 filedes[2]来标识该文件。只有调用
pipe的进程及调用后该进程创建的子孙进程，才能识别此文
件描述符，从而才能利用该文件（管道）进行父子或子、子
之间通信。
管道通信方式 Pipe
也称共享文件方式，基于文件系统，
利用一个打开的共享文件连接两个相互
通信的进程，文件作为缓冲传输介质
字符流方式写入读出
先进先出顺序
发送进程 接收进程
管道通信 -1
?UNIX系统 V的管道文件最大长度为 10个盘块，核心为它设置了
一个读指针和一个写指针。为了确保利用管道使进程间传送
数据的正确性。系统在管道读写时设置互斥和同步机制，它
首先保证写进程和读进程互斥地进行写和读，同时又要保证
写和读的同步。即写进程将数据写入管道后，读进程才能来
读取数据，如写进程未将数据写入管道，则读进程必须阻塞
等待。如写进程将数据写满管道后读进程未来读，则发出写
溢出，此时写进程必须阻塞等待。与一般文件不同是管道数
据的先进先出（ FIFO） 处理方式和管道文件数据不可再现性。
即被读取的数据在管道中不能再利用，无名管道在关机后自
动消失。
?在 UNIX,MS-DOS系统中，用户可以在命令级使用管道，这时
管道是一个程序的标准输出和另一个程序的标准输入之间的
连接，管道命令用符号, |” 表示。
管道通信 -2
?pipe使用
pipe系统调用的语法格式是,int pipe (filedes)
int filedes [2]；
核心创建一条管道完成下述工作：
a.分配一个隶属于 root文件系统的磁盘和内存索引结点 inode.
b.在系统打开文件表中分别分配一读管道文件表项和一写管道
文件表项。
c.在创建管道的进程控制块的文件描述表（进程打开文件表 u-
ofile） 中分配二表项，表项中的偏移量 filedes[o]和 ditedes[1]
分别指向系统打开文件表的读和写管道文件表项。
系统调用所涉及的数据结构如下图所示。
例：
父进程
管道 CHAN1
子进程管道 CHAN2
管道通信 -3
PCB 系统打开文件表 活动索引结点表 磁盘
进程打开文件表
Filedes[0]
Filedes[1]
.
.
.
.
f-flag FREAD |
FDIPE
f-count 1
f-inode
f-offset[0]
f-offset[1]
f-flag FWRITE |
FPIPE
f-count 1
f-inode
f-offset[0]
f-offset[1]
.
.
.
.
.
i-count 2
i-size
i-addr[0]
.,
.
i-addr[9]
.
.
.
管道通信数据结构
父进程打开文件表 系统打开文件表 活动索引结点表
子进程打开文件表
chan1[0]
chan1[1]
chan2[0]
chan2[1]
Chan1[0]
chan1[1]
chan2[0]
chan2[1]
f-flag FREAD | FPIPE
f-inode
f-count 1
f-flag FWRITE | FPIPE
f-inode
f-count 1
f-flag FREAD | FPIPE
f-inode
f-count 1
f-flag FWRITE | FPIPE
f-inode
f-count 1
i-addr[0]
.
i-addr[9]
i-addr[0]
.
i-addr[9]
管道通信 程序
#include <stdio.h>
#include <fcntl.h>
char parent[]={“A message from parent,”};
char child[]={“A message from child,”};
main()
{int chan1[2],chan2[2];
char buf[100];
if (pipe(chan1)==-1 || pipe(chan2)==-1) errexit(“pipe”);
if (fork())
{close(chan1[0]); close(chan2[1]);
write(chan1[1],parent,sizeof parent);
close(chan1[1]);
read(chan2[0],buf,100);
管道通信 程序 -1
printf(“parent process, %s \n”,buf);
close(chan2[0]);
}
else
{close(chan1[1]); close(chan2[0]);
read(chan1[0],buf,100);
printf(“child process, %s \n”,buf);
write(chan2[1],child,sizeof child);
close(chan2[1]); close(chan1[0]);
}
}
(4)WindowsNT进程通信－本地过程调用 LPC
?LPC是一个同一机上用于高速信息传输的进程间的通
信机构。 LPC是一个灵活的、经过优化的“远程 过程
调用, (RPC)版本,RPC是一种通过网络在客户与
服务器进程之间传递信息的工业标准通信机制。 LPC
被使用在同一机上一个服务器进程与该服务器的一
个或多个客户进程之间，在 Win32 API下它是不可用
的，它是一个只对 WindowNT操作系统组件有效的内
部机制。 LPC提供了三种不同的消息传送方法：
?第一种方法适用于传送小于 256B的消息。它将消息
传给与服务器进程相连的端口对象，系统为每个端
口对象设置有一个固定大小的消息队列，作为通信
之用，此方法用于发送少于 256字节的信息。这个方
法类同于消息缓冲队列通信机制。
本地过程调用 LPC-1
?第二种方法适用于传送大于 256B的消息。它将消息指针
传给与服务器进程相连的端口对象，并把消息存放在共
享的主存区域中，消息大小受进程所分得的主存配额限
制。消息传送的过程如下：当客户要传送大消息时，就
由它自己创建一个称为主存区域的对象 -主存共享的对
象,LPC机制使得该地址空间为客户进程和服务器均可
见，然后客户进程把大消息存放在该主存区域对象中；
再向服务的的端口对象的消息队列中传送一个小消息指
出所传送消息的大小和消息所在的地址指针。
?第三种方法适用于服务器想读或写大量数据而共享区又
太小情况。数据可以直接从客户地址空间读出或向客户
地址间写入。 LPC组件提供了两个函数，服务器可以用
它们来完成这些操作，以第一种方法发送的消息被用于
同步正在传送的信息。
例题
?有一阅览室, 读者进入时必须先在一张登记表上进行登记,
该表为每一座位列一表目, 包括座号和读者姓名 。 读者离开
时要消掉登记信息, 阅览室中共有 100个座位, 请问：
为描述读者的动作, 应编写几个程序？ 设置几个进程？ 进程与
程序间的对应关系如何？
解 1：二个程序 。 管理员 1和管理员 2:管理员 1负责在读者进入时
在一张登记表上进行登记, 管理员 2负责读者离开时要消掉登
记信息 。 二个进程, 进程与程序间的对应关系一对一 。
var mutex,empty,full,Semaphore,=﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎, ﹎﹎ C﹎﹎ 。
begin
parbegin
Manager1：
begin
repeat
Wait a reader in；
﹎﹎﹎ D﹎﹎﹎ ；
例题 -1
﹎﹎﹎ E﹎﹎﹎ ；
Login a name in the register；
﹎﹎﹎ F﹎﹎﹎ ；
﹎﹎﹎ G﹎﹎﹎ ；
forever
end
Manager2：
begin
repeat
Wait a reader out；
﹎﹎﹎ H﹎﹎﹎ ；
﹎﹎﹎ I﹎﹎﹎ ；
Logout a name in the register；
﹎﹎﹎ J﹎﹎﹎ ；
﹎﹎﹎ K﹎﹎﹎ ；
forever
end
coend
end
例题 -2
解 2：一个读者程序, 每一个读者一个进程, 进程与程序间的对
应关系一对多 。
var empty, Semaphore,=﹎﹎ L﹎﹎；
begin
parbegin
Reader i：
Begin
﹎﹎﹎ M﹎﹎﹎；
Login a name in the register；
Read …,
Logout name in a register；
﹎﹎﹎ N﹎﹎﹎；
end
parend
end
A,B,C,L,(1)0; (2)1; (3)2; (4)100; (5)n;
D---K,M,N,(1)P(mutex); (2)V(mutex); (3)P(empty);(4)V(empty); (5)P(full); (6)V(full); (练习 )
习题
1,对于记录型信号量, 在执行一次 P操作时, 信号量的值应当
为﹎﹎ A﹎﹎； 当其值为﹎﹎ B﹎﹎ 时, 进程应阻塞 。 在执行 V
操作时, 信号量的值应当﹎﹎ C﹎﹎； 当其值为﹎﹎ D﹎﹎ 时,
应唤醒阻塞队列中的进程 。
A,C,(1)不变； (2)加 1； (3)减 1； (4)加指定数值； (5)减指
定数值 。
B,D,(1)大于 0； (2)小于 0； (3)大于等于 0； (4)小于等于 0。
(解 )
习题 -1
2.在操作系统中，解决进程间的﹎﹎ A﹎﹎ 两种基本关系，往往
运用对信号量进行﹎﹎ B﹎﹎ 的﹎﹎ C﹎﹎,例如，为保证系
统数据库的完整性，可以把信号量定义为某个库文件（或记
录）的锁，初值为 1，任何进程存取该库文件（或记录）之前
先对它作一个﹎﹎ D﹎﹎,存取之后对它作一个﹎﹎ E﹎﹎，
从而做到对该文件（或记录）任一时刻只有一个进程可存取，
但要注意使用不当引起的死锁。
A,(1)同步与异步； (2)串行与并行； (3)调度与控制； (4)同步
与互斥。
B,(1)消息操作； (2)P-V操作； (3)开关操作； (4)读写操作。
C,(1)通信原语； (2)调度算法； (3)分配策略； (4)进程控制。
D,E,(1)联机操作； (2)V操作； (3)输出操作； (4)读操作；
(5)写操作； (6)P操作； (7)输入操作。
(解 )
习题 -2
3。 有一阅览室，读者进入时必须先在一张登记表上进行登记，
该表为每一座位列一表目，包括座号和读者姓名。读者离开
时要消掉登记信息，阅览室中共有 100个座位，请问：
a.为描述读者的动作, 应编写几个程序？ 设置几个进程？ 进程
与程序间的对应关系如何？
b.用类 Pascal语言和 P,V操作写出这些进程间的同步算法 。
(解 )
4.试述 消息缓冲队列通信机制通信原理 。 (解 )
5.今有三个并发进程 R, M,P,它们共享一个缓冲区, R负责从
输入设备读信息, 每读一个记录后, 把它存放在缓冲区, M在
缓冲区加工读入的记录, P把加工后的记录打印输出, 读入的
记录经加工输出后, 缓冲区中又可存放下一个记录 。 请用 P、
V操作为同步机制写出它们并发执行时能正确工作的程序
习题 5图
R
Buf
M P
习题 -3
var s1,s2,s3,semaphore:=﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎, ﹎﹎ C﹎
﹎ ;
begin
parbegin
R,begin
repeat
Read from i/o
﹎﹎﹎ D﹎﹎﹎ ;
Add to buffer;
﹎﹎﹎ E﹎﹎﹎ ;
until
end
习题 -4
M,begin
repeat
﹎﹎﹎ F﹎﹎﹎ ;
Remove from buffer;
Process …
Add to buffer;
﹎﹎﹎ G﹎﹎﹎ ;
until
end
P,begin
repeat
习题 -3
﹎﹎﹎ H﹎﹎﹎ ;
Remove from buffer;
﹎﹎﹎ I﹎﹎﹎ ;
Print a message;
until
end
parend
end
A,B,C,(1)0; (2)1; (3)2; (4)100; (5)n;
D---I,(1)P(s1); (2)V(s1); (3)P(s2); (4)V(s2);
(5)P(s3); (6)V(s3);
习题 -4
6,进程之间有哪几种高级通信方式?各种通信方式的特点如何?
分别运用哪些场合?
7,试述 UNIX S Ⅴ 通信软件包 IPC提供的消息机制 。
(Synchronization and
Communication Among
Processes )
教学目的：
在进程的控制的基础上这课引入进程同步和进程同
步机制的概念, 它对并发执行进程的推进序列加以限
制以保证互斥使用临界资源或协同完成任务, 解决程
序并发执行时带来结果不可再现问题 。 这课介绍了用
软件, 硬件, 信号量机制, AND型信号量集, 一般信
号量集, 管程等各种解决进程互斥同步问题的方法,
重点介绍了信号量机制的概念和用信号量机制解决进
程互斥同步问题的方法 。
教学要求：
?熟悉 进程间制约关系，掌握临界资源和临界区概念，掌
握进程同步和进程同步机制,熟悉 利用 软件方法和硬件
技术解决进程同步机制。
?熟练掌握信号量和 P,V操作的概念、定义和实质，熟练
掌握 利用信号量实现进程互斥和同步,熟悉 用信号量 描
述前趋关系。
?掌握 利用信号量解 生产者 -消费者问题,熟悉 利用信号
量解 读者 -写者问题等经典同步问题，掌握进程同步分
析方法。
?了解 用 AND型 信号集机制、一般信号集机制和管程 解 经
典同步问题。
?熟悉 进程通讯的 概念和共享存储器系统、消息传送系统、
管道通信系统 三类高级 通讯 机制，掌握消息缓冲队列通
信机制。
（一） 进程同步
(Synchronization of multiple
processes)
（ 1）进程同步的概念
1。 进程间制约关系
? 在多道程序环境下，系统中各进程以不可预测的速度向
前推进，进程的异步性会造成了结果的不可再现性。为防止
这种现象，异步的进程间推进受到二种限制：
?资源共享关系（ Cooperation Among Processes by Sharing）
多进程共享资源，例如各进程争用一台打印机，这时各进
程使用这台打印机时有一定的限制。每次只允许一个进程使
用一段时间打印机，等该进程使用完毕后再将打印机分配给
其它进程。这种使用原则称为互斥使用。
进程同步的概念 -1
进程之间竞争资源面临三个控制问题：
互斥（ mutual exclusion )指多个进程不能同时使用同一个
资源；
死锁 （ deadlock )指多个进程互不相让，都得不到足够的资源；
饥饿（ starvation )指一个进程一直得不到资源（其他进程可
能轮流占用资源）
相互合作关系
（ Cooperation Among Processes by Communication）
在某些进程之间还存在合作关系，例如一个程序的输入、计
算、打印三个程序段作为三个进程并发执行，由于这三个进程
间存在着相互合作的关系，即先输入再计算、最后再打印的关
系，所以这三个进程在并发执行时推进序列受到限制，要保证
其合作关系正确，进程间这种关系称为同步关系。
2,临界资源和临界区
? 临界资源
象打印机这类资源一次只允许一个进程使用的资源称为临
界资源。属于临界资源有硬件打印机、磁带机等，软件在消
息缓冲队列、变量、数组、缓冲区等。当然还有一类象磁盘
等资源，它允许进程间共享，即可交替使用，所以它称为共
享资源，而临界资源又称独享资源。
?临界区 (critical sections)
多个进程共享临界资源时必须互斥使用，例如 A和 B两个进程
都需要使用打印机，它们必须互斥使用。如果为了保证结果
的正确性限制 A,B二进程推进序列，规定进程 A执行好再执行
进程 B,这样的限制就显得过死，因为它已不能保证进程 A,B
能并发执行，所以必须把限制减少到最少，以尽可能支持并
发执行。为此把各进程分解，把访问临界资源的那段代码
（称为临界区）与其它段代码分割开来，只对各种进程进入
自己的临界区加以限制，即各进程互斥地进入自己的临界区。
临界资源和临界区
例如进程 A,B的程序如下：
A,begin
Input data 1 form I/O 1 ;
Computer…… ;
Print results 1 by printer ; A临界区
end
B,begin
Input data 1 form I/O 2 ;
Computer…… ;
Print results 2 by printer ; B临界区
end
3,进程同步机制
进程在并发执行时为了保证结果的可再现性，各进
程执行序列必须加以限制以保证互斥地使用临界资
源，相互合作完成任务。
多个相关进程在执行次序上的协调称为进程同步。
用于保证多个进程在执行次序上的协调关系的相应
机制称为进程同步机制。
所有的进程同步机制应遵循下述四条准则：
?空闲让进。
当无进程进入临界区时，相应的临界资源处于空
闲状态，因而允许一个请求进入临界区的进程立即
进入自己的临界区。
进程同步机制
?忙则等待。
当已有进程进入自己的临界区时，即相应的
临界资源正被访问，因而其它试图进入临界区的
进程必须等待，以保证进程互斥地访问临界资源。
?有限等待 。
对要求访问临界资源的进程，应保证进程能
在有限时间进入临界区，以免陷入, 饥饿, 状态。
?让权等待。
当进程不能进入自己的临界区时，应立即释
放处理机，以免进程陷入忙等。
进程同步机制
Mutual exclusion using critical regions
进程同步机制
? 一个由临界区和剩余区 1和剩余区 2程序段组成的进程采
用进程同步机制后的描述如下：
begin remainder section 1； 剩余区 1
进入区
critical section ； 临界区
退出区
remainder section 2 ； 剩余区 2
end
进程同步机制在临界区前加上进入区，它负责对欲访问
的临界资源状态进行检查，以决定是允许该进程进入临
界区还是等待。同时在临界区后加上退出区，它负责释
放临界资源以便其它等待该临界资源的进程使用。
?实现进程互斥和同步的信号量机制有软件方法、硬件指
令方法、信号量机制和管程等。
(2)利用 软件方法解决 进程互斥 (Mutual
Exclusion )问题
问题：有 二个进程 Pi和 Pj互斥共享 临界资源 R，
begin
parbegin
Pi,...…
Pj,.....
parend
end
下列 算法 只写出进程 Pi程序。
利用 软件方法解决 进程互斥问题 -1
算法 1
?该算法设置了一个公用整型变量 turn,用于指示被允许进
入临界区的进程编号，既若 ture=0,表示允许 Pi进程进入
临界区。该算法可确保每次只允许一个进入临界区。但采
用强制两个进程轮流进入临界区，很容易造成资源利用不
充分。
?P0进程, P1进程,
repeat repeat
while turn≠0 do no op while turn≠1 do no op
Critical section Critical section
turn=1 turn=0
Remain Section Remain Section
until false until false
利用 软件方法解决 进程互斥问题 -2
算法 2:
?算法基本思想：在每一个进程访问临界区资源之前，先动查
看一下临界资源是否正被访问，若正被访问，该进程需等待，
否则才进入自己的临界区。为此设置了一个数据 flag[0,1]，
如第 i个元素值为 false表示 Pi进程未进入临界区，值为 true表
示 Pi进程进入临界区。
?P0:repeat P1:repeat
① while flag[1] do no_op; ② while flag[0] do no_op;
③ flag[0]:=true; ④ flag[1]:=true;
⑤ critical_section; ⑥ critical_section;
flag[0]:=false; flag[1]:=false;
remainder section; remainder section;
until false until false
?按 ①②③④⑤ ⑥ 序列执行会出现 Pi和 Pj同时 进入临界区错误。
利用 软件方法解决 进程互斥问题 -3
算法 3:
?算法 2是先检测对方进程状态标志后再置自己标志，由于在检
测和放置中可插入另一个进程时检测操作，会造成二个进程
在分别检测后同时进入临界区。为此算法 3采用先设置自己标
志后再检测对方状态标志，它的程序如下，但也可能出现二
个进程先后同时设置后再分别检测对方状态标志，造成对方
都不能进入临界区，无限期等待。
P0:repeat P1:repeat
① flag[0]:=true; ② flag[1]:=true;
③⑤ while flag[1] do no_op;④ ⑥ while flag[0] do no_op
critical_section; critical_section;
flag[0]:=false; flag[1]:=false;
remainder section; remainder section;
until false until false
利用 软件方法解决 进程互斥问题 -4
算法 4(Peterson 1981)：
?该算法组合了算法 1和算法 4，为了防止二进程进入临界
区而无限期等待，又设置变量 turn,表示不允许进入临界
区的编号，每个进程在先设置自己标志后再设置 turn标志，
不允许另一个进程进入，这时再同时检测另一个进程状
态标志和不允许进入标志，这样可以保证当二个进程同
时要求进入临界区时，只允许一个进程进入临界区。
?Pi,repeat
flag[i]:=true; turn:=j;
while (flag[j] and turn=j) do no_op;
critical_section;
flag[i]:=false;
remainder section;
until false
(3)利用 硬件技术实现进程同步机制
1.提高临界区代码执行中断优先级
这种方法在 UNIX和 Windows NT中都使用，它是在单机系
统中有效地实现互斥的一种方法。
因为在传统操作系统中，打断进程对临界区代码的执
行只有中断请求、中断一旦被接受，系统就有可能调用
其它进程进入临界区，并修改此全局数据库。所以用提
高临界区中断优先级方法就可以屏蔽了其它中断，保证
了临界段的执行不被打断，从而实现了互斥。
在多处理机情况下，用提高临界段代码执行的中断优先
级方法是无法保证互斥的，因为在一个处理机上提高中
断优先级并不能阻止其它处理器上的中断，所以必须采
用其它方法。
2,检测和设置（ TS） 硬件指令
?许多大型机（如 IBM370等）和微型机（如 Intel × 86等）中
都提供了专用的硬件指令，这些指令全部允许对一个字中的
内容进行检测和修正，或交换两个字的内容。特别要指出的
是这些操作都是在一个存储周期中完成，或者说由一条指令
来完成，用这些指令就可以解决临界区问题了。
?在单机系统中，由于中断的原因，使得一个进程在对一个公
用变量先取来并检测其值，然后修改的这两个动作中，可以
插入其它进程对此公用变量的访问和修改，从而破坏了此公
用变量数据的完整性和正确性。在多机系统中，多处理机共
享主存，因而使得某处理机可插入另一处理机的两个存储访
问周期之间，访问并修改此共享变量。
检测和设置（ TS） 硬件指令 -1
对于同一主存块访问要求，即使两个处理机同时提出，存
储控制逻辑也只能让其中之一先访问，但在一个处理机
的两个存储周期间则可以插入另一个处理机的存储周期。
现在用一条指令来完成检测和修改两个功能，这样中断
和插入另一处理机的存储周期均不可能，所以不会影响
此公用变量数据的完整性。
?检测和设置（ TS） 的功能可用 PASCAL语言描述如下：
function TS (var flag,boolean):boolean
begin
TS = flag ；
flag,=true ；
end
这条指令在 Z-8000中称为 TEST指令，在 IBM370中称为 TS指令。
检测和设置（ TS） 硬件指令 -2
?用这些硬件指令可以简单有效地实现互斥。其方法是为每个
临界段或其它互斥资源设置一个布尔变量，例如称为 lock。
当其值为 false则临界区末被使用，反之则说明正有进程在
临界区中执行。于是某进程用 TS指令实现互斥的程序结构为
（设为无限循环进程）：
repeat
...
while TS(lock) do skip ；
进程临界区 CS ；
lock,=false ；
...
until false;
?WindowsNT 内核用来达到多处理器互斥的机制, 转锁,,它
类同于 TS指令机制。
(二 )信号量 (Semaphores)机制
?1965年，荷兰学者 Dijkstra提出的信号量机制是一种卓
有成效的进程同步工具，在长期广泛的应用中，信号量
机制又得到了很大的发展，它从整型信号量机制发展到
记录型信号量机制，进而发展为, 信号集, 机制。现在
信号量机制已广泛应用于 OS中。
（ 1） 记录型信号机制
?记录型信号量结构
在信号量机制中信号量是代表资源物理实体的数据结构，
记录型信号量的数据结构描述如下：
type semaphore=record
value,integer;
L,pointer of PCB;
end
? 信号量的值只能通过两个原子操作,P,V操作来改变，
它代表分配资源和释放资源。
信号量机制－ 1
? 信号量 S取值意义如下：
S,value ＞ 0 ； 表示可供使用资源数
＝ 0 ；表示资源已被占用，无其它进程等待。
＜ 0 （ -n） ； 表示资源已被占用，还有 n个进
程因等待资源而阻塞。
（ 2） 信号量的类型
信号量按联系进程的关系分成二类：
? 公用信号量（互斥信号量）：它为一组需互斥共享临界资源
的并发进程而设置，代表共享的临界资源，每个进程均可对
它施加 P,V操作，即都可申请和释放该临界资源，其初始值
置为 1。
? 专用信号量（同步信号量）：它为一组需同步协作完成任务
的并发进程而设置，只有拥有该资源的进程才能对它施加 P
操作（即可申请资源），而由其合作进程对它施加 V操作
（即释放资源）。
（ 3） P-V操作 (wait(s)和 signal(s) 操作 )
对信号量施加 P,V操作代表申请和释放资源。 P-V操作描述如下：
?proceduce P(S)
var S:semaphore ；
begin
S.value=S.value-1 ；
If S.value<0 then block(S.L) ；
end
?Procefuce V(S)
Var S:semaphore ； ;
begin
S.value=S.value+1 ；
If s.value≤0 then wakeup(S.L) ；
end (练习 )
（ 4） 利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只需
为该资源设置一个互斥信号量 mutex,并设其初值为 1，
然后将各进程的临界区 CS置于 P（ mutex） 和 V(mutex)
操作之间即可。利用信号量实现共享打印机的 A,B
两进程互斥的类并行 PASCAL程序描述如下：
利用信号量实现进程互斥 -1
var mutex:=semaphore:=1 ；
begin
parbegin
A:begin B:begin
Input data 1 from I/0 1 ； Input data 2 from I/O 2 ；
Compute…… ； Compute…… ；
P(mutex) ； P(mutex) ；
Print results1 by printer; Print results2 by printer;
V(mutex) ； V(mutex) ；
end end
parend
end (练习 )
(5)利用信号量实现进程同步
?利用信号量能解决进程间的同步问题，这里以下图所示
的计算进程 C和打印进程 P通过缓冲区 Buffer传送数据的
同步问题为例说明。
Buffer
C P
利用信号量实现进程同步 -1
C和 P两进程基本算法如下：
C,begin P,begin
repeat repeat
Compute next number ; remove from Buffer ;
add to Buffer ; print last number ;
until false until false
end end
?C和 P两进程并发执行，必须在执行序列上遵循以下规则，才
能避免错误。
只有当 C进程把数据送入 Buffer后,P进程才能从 Buffer中取
出数据来打印，否则 P进程只能等待。
只有当 P进程从 Buffer中取走数据后,C进程才能将新计算的
数据再存入 Buffer,否则 C进程也只能等待。
利用信号量实现进程同步 -2
?为了实现进程同步，需采用同步信号量。为了满足第一
条同步规则，设置一个同步信号量 full,它代表的资源
是缓冲器满，它的初值为 0。这个资源是 P进程所拥有,P
进程可以申请该资源，对它施加 P操作，如条件满足 P进
程可从 Buffer中取数。而 P进程的合作进程 C对 full信号
量施加 V操作，即它可释放该资源。当 C进程将数据存入
Buffer后，即可释放该资源供 P进程再使用。同样为了满
足第二条同步规则，设置另一个同步信号量 empty,它代
表的资源是缓冲器空，它的初值为 1 。缓冲器空这个资
源是进程 C所拥有，它可以申请该资源，对它施加 P操作。
而它的合作进程 P对 empty信号量施加 V操作。
?实现 C和 P两进程同步的类 PASCAL程序：
考虑第一个同步关系－ C加入话后 P再取var,full:semaphore:=0 ；
begin
parbegin
C,begin
repeat
Compute next number ；
Add to buffer ；
V(full) ；
until false
end
P,begin
repeat
P(full) ；
remove from Buffer ；
Print last number ；
until false
end
parend
end
考虑第二个同步关系－ P取走后 C再加入
var,empty:semaphore:=1 ；
begin
parbegin
C,begin
repeat
Compute next number ；
P(empty) ；
Add to buffer ；
until false
end
P,begin
repeat
remove from Buffer ；
V(empty) ；
Print last number ；
until false
end
parend
end
考虑二个同步关系
var,empty,full:semaphore:=1,0 ；
begin
parbegin
C,begin
repeat
Compute next number ；
P(empty) ；
Add to buffer ；
V(full) ；
until false
end
P,begin
repeat
P(full) ；
remove from Buffer ；
V(empty) ；
Print last number ；
until false
end
parend
end
同步物理意义
?首先由 C进程先将数据加入缓冲区, 再由 P进程从缓
冲区中取出数据 。 为此 设置一个同步信号量 full，
先 做动作的 进程 C在 动作 （ Add to buffer;） 完成后
对信号量 full施加 V操作, 代表释放该资源 。 后 做动
作的 进程 P在 动作 （ Remove from buffer;） 前对信
号量 full施加 P操作, 代表申请该资源 。 信号量 full
它代表的资源是缓冲器满 （ 装满输入数据 ）, 它的
初值为 0,它代表的资源是后 做动作的 进程 P所拥有 。
?也可以理解为：先 做动作的 进程 C在 动作 完成后对同
步信号量施加 V操作, 代表发送消息；后 做动作的 进
程 P在 动作 前对同步信号量施加 P操作, 代表测试消
息是否到达 。
(6)利用信号量描述前趋关系
进程间同步关系也可用前趋图表示。 C和 P两进程间先计
算好再打印同步关系用前趋图表示如下：
对应这个前趋关系可设置同步信号量 full,它为后继进
程 P拥有，初值为 0。它的并发执行程序如下：
var full, semaphore,=0;
begin
parbegin
C,begin Compute ； V(full) ； end
P,begin P(full) ； Print ； end
parend
end
C P
（三） 利用信号量解 经典进程同步问题
经典进程同步问题是从进程并发执行中归纳的典型例子，这
些问题常用来测试新的同步机制可行性。主要的经典同步问
题有生产者 -消费者问题、读者 -写者问题、哲学家进餐问题
等。
（ 1）生产者 -消费者问题
（ producer-consumer Problem ）
?生产者 -消费者问题是最著名的同步问题，它描述一组生产
者（ P1 …… Pm） 向一组消费者（ C1…… Cq） 提供消息。它们
共享一个有界缓冲池（ bounded buffer pool）,生产者向其
中投放消息，消费者从中取得消息，如下图所示。生产者 -
消费者问题是许多相互合作进程的一种抽象。
利用信号量解 经典进程同步问题 -1
假定缓冲池中有 n个缓冲区，每个缓冲区存放一个消息。由
于缓冲池是临界资源，它只允许一个生产者投入消息，或者
一个消费者从中取出消息。即生产者之间、生产者与消费者
之间、消费者之间都必须互斥使用缓冲池。所以必须设置互
斥信号量 mutex,它代表缓冲池资源，它的数值为 1。
P1 Pm C1 Cq
B0 B1 …, …,.,……… Bn-1
利用信号量解 经典进程同步问题 -2
与计算打印两进程同步关系相同，生产者和消费者二类进程 P
和 C之间应满足下列二个同步条件：
? 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才
能从中提取消息，否则消费者必须等待。
? 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息
放入缓冲区，否则生产者必须等待。
为了满足第一个同步条件，设置一个同步信号量 full,它代
表的资源是缓冲区满，它的初始值为 0，它的值为 n时整个缓
冲池满。这个资源是消费者类进程 C所拥有,C进程可以申请
该资源，对它施加 P操作，而 C进程的合作进程生产者进程 P对
它施加 V操作。同样为了满足第二个同步条件，设置另一个同
步信号量 empty,它代表的资源是缓冲区空，它的初始值为 n，
表示缓冲池中所有缓冲区空。
用类并行 PASCAL语言和信号量机制解生产者 -消费者问题程序：
利用信号量解生产者 -消费者互斥 问题 -1
var mutex,empty,full:semaphore:=1,n,o ；
Buffer, array [0…… n-1] of message ；
in,out, o…… n-1:=0,0 ；
begin
parbegin
P,begin
repeat
Produce a new message m ；
P (mutex) ；
Buffer[in]=m ；
in,=(in+1) mod n ；
V (mutex) ；
until false
end
利用信号量解生产者 -消费者互斥 问题 -2
C,begin
repeat
P (mutex) ；
m,= buffer[out] ；
out, = (out+1) mod n ；
V (mutex) ；
Consume message m ；
until false
end
parend
end
利用信号量解 经典进程同步问题 -3
var mutex,empty,full:semaphore:=1,n,o ；
Buffer, array [0…… n-1] of message ；
in,out, o…… n-1:=0,0 ；
begin
parbegin
P,begin
repeat
Produce a new message m ；
P (empty) ；
P (mutex) ；
Buffer[in]=m ；
in,=(in+1) mod n ；
V (mutex) ；
V (full) ；
until false
end
利用信号量解 经典进程同步问题 -4
C,begin
repeat
P (full) ；
P (mutex) ；
m,= buffer[out] ；
out, = (out+1) mod n ；
V (mutex) ；
V (empty) ；
Consume message m ；
until false
end
parend
end
（ 2） 读者 -写者问题
（ Readers/Writers Problem ）
? 一个数据集（如文件）如果被几个并行进程所共享，有
些进程只要求读数据集内容，它称读者，而另一些进程则
要求修改数据集内容，它称写者，几个读者可以同时读些
数据集，而不需要互斥，但一个写者不能和其它进程（不
管是写者或读者）同时访问些数据集，它们之间必须互斥。
? 设置互斥 信号量 wmutex 表示写者间、读者和写者间互斥，
读者和写者主要 程序如下：
reader,writer:
第一个读者到时 P（ wmutex） P（ wmutex）
Read Text Write Text
最后 一个读者离开时 V（ wmutex） V（ wmutex）
读者 -写者问题 -1
?用 readcount变量来记录读者数，读者 程序为：
if readcount=0 then P（ wmutex） ;
readcount= readcount+1;
Read Text
readcount= readcount-1;
if readcount=0 then V（ wmutex） ;
?由于 readcount是读者间共享变量，属于临界资源，它也需互
斥，为此又增设互斥信号量 rmutex.
用类并行 PASCAL语言和信号量机制解读者 -写者问题程序：
读者 -写者问题 -2
Var rmutex,wmutex,semaphore:=1,1 ;
readcount,integer,=0 ;
begin
parbegin
reader:begin writer:begin
repeat repeat
P(rmutex) P(wmutex);
if readcount=0 then P(wmutex); Write Text;
readcunt=readcount+1; V(wmutex);
V(rmutex) until false
Read Text end
P(rmutex)
readcount=readcount-1 ;
if readcount=0 then V(wmutex) ;
V(rmutex)
until false
end
parend
end
(3)Dining-Philosophers Problem哲学家就餐问题
?Shared data semaphore chopstick[5];
The structure of Philosophers i
?Philosopher i:
repeat
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
…
eat;
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think;
…
until false;
（ 3） 进程同步的分析
? 用信号量机制解决进程同步问题需在程序中正确设置信号
量和在适当位置安排 P,V操作。例如生产者 -消费者问题中，
用于互斥进入临界区的 P（ mutex）,V(mutex)语句需紧靠着
临界区前和后，而生产者用于同步的 P（ empty） 和 V（ full）
(消费者为 P（ full） 和 V(empty))语句相对临界区就在外面
一层，格式如上程序所述。如在以上问题中生产者的 P
（ empty） 和 P(mutex)先后位置对调，相应消费者的 P（ full）
和 P（ mutex） 先后位置也对调，则生产者和消费者在并发执
行时，在某个执行序列会出现问题。
? 下面介绍如何寻找会发生问题的那个执行序列，分析方法
用下表表示。表左边是生产者和消费者二进程推进序列，此
推进序列需用户寻找；表中间是该操作执行后信号量的变化
值，表中信号量有 mutex,empty和 full； 表的右边是该操作
执行后引起进程 PCB的队列变化。表中队列有就绪队列 RL，
因分别等待 mutex,empty,full信号量而阻塞的队列 QmL、
QeL,和 QfL。
进程同步的分析 -1
?在表中已找到一个推进序列。该序列先执行消费者进程，
由于消费者进程交换了 P操作，消费者进程在先后执行 P
（ muyex） 和 P（ full） 后阻塞在等待 full信号量的队列
中。这时只能执行生产者进程，由于生产者进程也交换
了 P操作，在生产者进程执行了 P（ mutex） 操作后，生产
者进程阻塞在等待 mutex信号量的队列中。这样生产者和
消费者两进程分别阻塞在等待 mutex和 full信号量的队列，
没有进程可以向前推进，系统进入死锁状态。这说明在
生产者 -消费者问题中对同步信号量和互斥信号量的二个
P操作的是不能颠倒，而对互斥信号量和同步信号量的二
个 V操作的顺序交换影响不大。
?生产者、消费者交换 P操作后发生问题的那个执行序列：
进程同步的分析 -2
操 作 操作引起 （信号量）
变化
操作引起 ( 队列 ) 变化事
件 生产者
(P)
消费者
(C)
m u t e x e m p t y full RL Q mL QeL QfL
0 / / 1 n 0 P, C / / /
C
1
/ P
( m u t e x )
0 n 0 P / / /
C
2
/ P ( f u l l ) 0 n -1 P / / C
P
1
P r a d u c e 0 n -1 / / / C
P
2
P
( m u t e x )
-1 n -1 / P / C
（四）经典进程同步问题的其它方法解
（ 1） AND型 /一般 信号集机制
1。定义：
为了解决一个进程一次同时能申请几类临界资源，引入
AND型信号量 集 机制；为了对每类资源又能同时申请几个，
又扩充 AND型信号量 集 机制，形成一般信号量 集 机制，它的
相应的 Swait,Ssignal操作如下：
Swait(S1,t 1,d 1,…,S n,t n,d n )
if S1 >= t 1 and …..and S n >=t n then
for i:=1 to n do Si = Si - d i ;
endfor
endif
AND型 /一般 信号集机制 -1
else
Place the executing process in the waiting queue of the first Si
with Si< t i and set its program counter to the beginning of
the the Swait operation.
Ssignal(S1,d 1,…,S n,d n )
for i:=1 to n do Si = Si + d i ;
Remove all the process waiting in the queue associated with Si
into the ready queue.
endfor
2,用 一般 信号集机制解读者 -写者问题
var RN integer ;
L,mx, semaphore,=RN,1 ;
begin
parbegin
reader, begin
repeat
Swait (L,1,1 ) ;
Swait (mx,1,0 ) ;
perform read operation
Ssignal (L,1) ;
until false ;
end
用 一般 信号集机制解读者 -写者问题 -1
writer,begin
repeat
Swait (mx,1,1,L,RN,0 );
perform write operation
Ssignal (mx,1 ) ;
until false ;
end
parend
end
(2)管程 (Monitors)
1,管程的引入
用信号量和 P,V操作来解决进程互斥同步问题, 需在程序
中适当位置安排 P,V操作, 否则会造成死锁错误, 为了解决
分散编程带来的困难, 采用资源集中管理的方法, 用某种数
据结构表示某类资源, 并将这种数据结构以及与资源有关操
作集中一起定义为类程或管程, 并用类程管理独立资源, 用
管程管理共享资源, 它两是能被进程调用的实体 。
2。 管程定义
管程是由一些共享数据、能为并发进程所执行的作用在共享
数据上的操作的集合、初始代码以及存取权组成。
管程提供了一种可以允许多进程安全有效地共享抽象数据
类型的机制，管程实现同步机制由“条件结构”（ condition
construct） 所提供。为实现进程互斥同步，必须定义一些条
件变量，（例如,var notempty,,notfull,condition）,这些
条件变是只能被 wait和 signal 操作所访问。
Structure of Monitor
Eotrance
Queue of
Entering
ProcessesMonitior Waiting Area
Condition c1
C1.wait
.
.
.
condition cn
.
.
.
Cn.wait
Next Queue
Next.signal Exit
M0NITOR
Local Data
Condition Variables
Procedure 1
Procedure k
Initialization Code
管程 -1
notfull, wait操作意味着调用该操作的进程将被挂起，另至直
一个进程执行；
而 notfull, signal操作仅仅是启动一个被挂起的进程，如无挂起
进程则 notfall, signal操作相当于空操作，不改变 notfull状态，
这不同于 v操作。
并发语言及其编译系统自动地处理多个进程互斥地和串行
地调用管程的过程和函数并加工管程的数据。
3。利用管程解决生产者 ―― 消费者问题
建立一个管程 PC,它包括两个过程 put（ item） 和 get
（ item）,它们分别执行将生产的消息放入缓冲池和从缓冲
池取出消息的操作，设置一变量 count表示缓冲池已存消息数
目。
管程 -2
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 ;
beffer ( in ), = nextp ;
in,= (in+1) mod n ;
count = count + 1 ;
if notempty.queue then notempty.signal ;
end
管程 -3
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
利用管程解决生产者 ―― 消费者问题，其中生产者和消费者
程序为
管程 -4
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
（五） 进程 通信
(Interprocess Communication)
高级通信机制可归结为三大类：共享存储器系统，消息传送
系统和管道通信系统。
（ 1）共享存储器系统
1,基于共享数据结构的通信方式
在这种通信方式中，要求诸进程公用某个数据结构，进程
通过它们交换信息。如在生产者 -消费者问题中，就是把缓
冲池（有界缓冲区）这种数据结构用来作通信的。这种通信
方式是低效的，只适用传送少量的数据。
2,基于共享存储区的通信方式
共享存储区是 UNIX系统 V中通信速度最高的一种通信机
制，它包含在进程通信软件包 IPC中。 该方法为了传送
大量数据，在存储区中划出一块存储区，供多个进程共
享，共享进程通过对这一共享存储区中的数据进行读或
写来实现通信。当进程 A要利用共享存储区进行通信时，
应先利用系统调用 shmget建立一个共享存储区。执行该
系统调用时，核心首先检查共享存储区表，该表是系统
范围的数据结构，每个共享存储区在该表中占一表项。
如末找到，则分配一系统空闲区作为共享区的页表区，
分配相应的内存块，有关参数填入页表中。返回共享存
储器的描述符 shmid。 进程 B要利用共享存储区与进程 A
通信时，也要先利用系统调用 shmget,此时核心检查共
享存储区表找到了指定的表项，则返回该表项的描述符
shmid。
基于共享存储区的通信方式 -1
进程 A和 B在建立了一个共享存储区并获得了其描
述符后，还需分别利用系统调用 shmat将共享存储区
附接到各自进程的虚地址空间上，如图 3-8所示。此
后共享存储区便成为进程虚地址空间的一部分，进
程可采取与其它虚地址空间一样的存取方法来存取
它。
进程 A和 B利用共享存储区进行通信时，需自己设
置进程同步机制，才能保证实现正确的通信。
进程 A和 B在利用共享存储区进行通信时，还可利
用系统调用 shmctl对共享存储区的状态信息（如长
度，当前连接的进程数等）进行读取，也可设置和
改变共享存储区的属性（如共享存储区的许可权
等）。最后仍可利用系统调用 shmctl断开进程与共
享存储区的连接。当所有进程都断开了与共享存储
区的连接时，便可取消共享存储区。
基于共享存储区的通信方式 -2
A正文
A数据
A栈
OS
A正文
B正文
:
:
共享
存储
器
.
B正文
B数据
B栈
进程 A 进程 B
虚地址空间 内存空间 虚地址空间
（ 2） 消息传递系统（ Message passing system）
消息传递系统分为直接通信方式和间接通信方式两种。
1,直接通信方式
这是指发送进程利用 OS提供的发送命令直接把消息发送给接
收进程，并将它挂在接收进程的消息缓冲队列上。接收进程
利用 OS提供的接收命令直接从消息缓冲队列中取得消息。此
时要求发送进程和接收进程都以显示的方式提供对方的标识
符，通常系统提供下述两条通信原语：
Send(Receiver,message) ；
Receive(Sender,message) ； 或 (Receive (message)) ；
直接通信的实例 -消息缓冲队列通信机制。
消息传递系统 -1
?消息缓冲队列通信原理
消息缓冲队列通信机制的原理是：由系统管理一组缓冲区，
其中每个缓冲区可以存放一个消息。当发送进程要发送消息
时先要向系统申请一个缓冲区，然后把消息写进去，接着把
该缓冲区连接到接收进程的消息缓冲队列中。接收进程可以
在适当的时候从消息缓冲队列中摘下消息缓冲区，读取消息，
并释放该缓冲区。
?消息缓冲队列通信的数据结构有消息缓冲区和进程 PCB中有关
通信的扩充数据项，消息缓冲区描述如下：
?type message buffer=record
sender ； 发送进程的标识符
size ； 消息长度
text ； 消息正文
next ； 指向下一个消息缓冲区的指针
end
图,消息缓冲队列通信的发送和接收过程
.
mutex
sm
mq
………,
.
.
send(B,a);
sender,A
size, 13
text,
How are
you?
Next
send,A
size,13
text:
How are
you?
Next:
sender,A
size,5
text,Hello
Next,
sender,A
size:13
text:
How are
you?
Next:0
sender,A
size,5
text,Hello
Next:
.
.
receive(b);
sender,A
size,5
text,Hello
系统管理的－组缓冲区
进程 A 进程 B
进程 B PCB
消息传递系统 -2
? PCB 有关通信的扩充数据项
type PCB = record
.
mutex ； 消息缓冲队列互斥信息量 ；
Sm ； 消息缓冲队列资源信息量 ；
mq ； 消息缓冲队列首指针 ；
,
End
(练习 )
消息传递系统 -3
?发送原语
Proceduce send (receiver,a)
begin
getbuf(a.size,i) ；
i.sender = a.sender i.size = a.size ；
i.text = a.text ； i.next = 0 ；
getid (PCB set,receiver, j) ；
P(j.mutex) ；
insert(j.mq,i) ；
V(j.mutex) ；
V(j.Sm) ；
end
消息传递系统 -4
?接收原语
proceduce receive(b)
begin
j,= internal name ；
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 ；
Releasebuf(i) ；
end
2.间接通信方式
? 在间接通信情况，消息不直接从发送者发送到接收者，而
是发送到暂存消息的共享数据结构组成的队列，这个实体称
为信箱（ mailbox）,因此二个进程通信情况，一个进程发送
一个消息到某个信箱，而另一个进程从信箱中摘取消息。
? 间接通信的使用好处是增加了使用消息的灵活性。发送者
和接收者的关系可能是一对一、多对一，一对多或多对多。
一对一的关系允许一个专用通信链路用于二个进程间的交互，
它能使俩进程间交互不受其它进程错误干予的影响，多对一
的关系对客户／服务器交互特别有用，一个进程对多个其它
进程（用户）提供服务。在这种情况信箱经常称作为端口
(port)。 一对多关系允许一个发送进程和多个接收进程交互，
这可用来将消息广播 (broadcast)给一组进程。
消息传递系统 -5
?进程与信箱的联系有二种：静态和动态。端口经常与特定的
进程保持静态的联系，即端口创建后永久地分配给某个进程。
同样一对一关系是典型地规定为静态的和永久的。当有许多
发送者时，一个发送者与信箱的联系可以动态发生，例如联
接（ conect） 和去联接原语可以应用于此用途。
?对于端口它是接收进程拥有和创建的。当进程撤消时相应端
口也撤消。对于一般信箱，操作系统可以提供创建和撤消信
箱的服务。
3,UNIX系统消息机制
UNIX系统 V的进程通信软件包 IPC提供了消息机制。
消息机制的数据结构
UNIX系统将消息分为消息首部和消息数据两部分。消息首
部和消息头表的关系、消息首部和消息数据的关系见 下图 。
消息首部：在消息首部中记录有消息的类型、大小、指向消
息数据区的指针、消息队列的链接指针等。
消息传递系统 -6
消息队列头表：消息队列头表的每一表项是作为一个消息
队列的消息头。在消息头中包含了指向消息队列中第一个消
息的指针和指向最后一个消息指针，队列中消息的数目、队
列中消息数据的总字节数等。
队列 0
.
.
队列 i
消 息 首 部
msgh 0
消息缓冲
区 0
消息首部
msgh 8
消 息 缓 冲
区 8
消息首部
msgh 3
消息缓冲
区 3
消 息 首 部
msgh 2
消息缓冲
区 2
消息传递系统 -7
?消息队列的建立和消息队列描述符的获取
msgget(key,msgflg); key_t key ; int msgflg ;
?消息的发送
msgsnd(msgid,msgp,msgsz,msgflg);
int msgid,msgsz,msgflg ; struct msgbuf *msgp ;
?消息的接收
msgrcv(msgid,msgp,msgsz,msgtpy,msgflg);long
msgtpy;
int msgid,msgsz,msgflg ; struct msgbuf *msgp ;
?消息队列的操纵
msgctl(msgid,cmd,buf); int msgid,cmd;
struct msgid_ds *buf;
(3)管道通信
UNIX系统在 OS的发展上最重要的贡献之一便是该系统首创了
管道（ pipes） 。
? 管道是指用于连接一个读进程和一个写进程，以实现它们
之间通信的共享文件，又称为 pipe文件。向管道（共享文件）
提供输入的发送进程（即写进程），以字符形式将大量的数
据送入管道，而接收管道输出的接收进程（即读进程）可从
管道中接收数据。管道通信是基于文件系统形式的一种通信
方式。
? 管道分为无名管道和有名管道两种类型。无名管道是早期
UNIX版本已提供的，它是一个只存在于打开文件机构中的一
个临时文件，从结构上没有文件路径名，不占用文件目录项。
无名管道利用系统调用 pipe(filedes)创建，只用该系统调用
所返回的文件描述符 filedes[2]来标识该文件。只有调用
pipe的进程及调用后该进程创建的子孙进程，才能识别此文
件描述符，从而才能利用该文件（管道）进行父子或子、子
之间通信。
管道通信方式 Pipe
也称共享文件方式，基于文件系统，
利用一个打开的共享文件连接两个相互
通信的进程，文件作为缓冲传输介质
字符流方式写入读出
先进先出顺序
发送进程 接收进程
管道通信 -1
?UNIX系统 V的管道文件最大长度为 10个盘块，核心为它设置了
一个读指针和一个写指针。为了确保利用管道使进程间传送
数据的正确性。系统在管道读写时设置互斥和同步机制，它
首先保证写进程和读进程互斥地进行写和读，同时又要保证
写和读的同步。即写进程将数据写入管道后，读进程才能来
读取数据，如写进程未将数据写入管道，则读进程必须阻塞
等待。如写进程将数据写满管道后读进程未来读，则发出写
溢出，此时写进程必须阻塞等待。与一般文件不同是管道数
据的先进先出（ FIFO） 处理方式和管道文件数据不可再现性。
即被读取的数据在管道中不能再利用，无名管道在关机后自
动消失。
?在 UNIX,MS-DOS系统中，用户可以在命令级使用管道，这时
管道是一个程序的标准输出和另一个程序的标准输入之间的
连接，管道命令用符号, |” 表示。
管道通信 -2
?pipe使用
pipe系统调用的语法格式是,int pipe (filedes)
int filedes [2]；
核心创建一条管道完成下述工作：
a.分配一个隶属于 root文件系统的磁盘和内存索引结点 inode.
b.在系统打开文件表中分别分配一读管道文件表项和一写管道
文件表项。
c.在创建管道的进程控制块的文件描述表（进程打开文件表 u-
ofile） 中分配二表项，表项中的偏移量 filedes[o]和 ditedes[1]
分别指向系统打开文件表的读和写管道文件表项。
系统调用所涉及的数据结构如下图所示。
例：
父进程
管道 CHAN1
子进程管道 CHAN2
管道通信 -3
PCB 系统打开文件表 活动索引结点表 磁盘
进程打开文件表
Filedes[0]
Filedes[1]
.
.
.
.
f-flag FREAD |
FDIPE
f-count 1
f-inode
f-offset[0]
f-offset[1]
f-flag FWRITE |
FPIPE
f-count 1
f-inode
f-offset[0]
f-offset[1]
.
.
.
.
.
i-count 2
i-size
i-addr[0]
.,
.
i-addr[9]
.
.
.
管道通信数据结构
父进程打开文件表 系统打开文件表 活动索引结点表
子进程打开文件表
chan1[0]
chan1[1]
chan2[0]
chan2[1]
Chan1[0]
chan1[1]
chan2[0]
chan2[1]
f-flag FREAD | FPIPE
f-inode
f-count 1
f-flag FWRITE | FPIPE
f-inode
f-count 1
f-flag FREAD | FPIPE
f-inode
f-count 1
f-flag FWRITE | FPIPE
f-inode
f-count 1
i-addr[0]
.
i-addr[9]
i-addr[0]
.
i-addr[9]
管道通信 程序
#include <stdio.h>
#include <fcntl.h>
char parent[]={“A message from parent,”};
char child[]={“A message from child,”};
main()
{int chan1[2],chan2[2];
char buf[100];
if (pipe(chan1)==-1 || pipe(chan2)==-1) errexit(“pipe”);
if (fork())
{close(chan1[0]); close(chan2[1]);
write(chan1[1],parent,sizeof parent);
close(chan1[1]);
read(chan2[0],buf,100);
管道通信 程序 -1
printf(“parent process, %s \n”,buf);
close(chan2[0]);
}
else
{close(chan1[1]); close(chan2[0]);
read(chan1[0],buf,100);
printf(“child process, %s \n”,buf);
write(chan2[1],child,sizeof child);
close(chan2[1]); close(chan1[0]);
}
}
(4)WindowsNT进程通信－本地过程调用 LPC
?LPC是一个同一机上用于高速信息传输的进程间的通
信机构。 LPC是一个灵活的、经过优化的“远程 过程
调用, (RPC)版本,RPC是一种通过网络在客户与
服务器进程之间传递信息的工业标准通信机制。 LPC
被使用在同一机上一个服务器进程与该服务器的一
个或多个客户进程之间，在 Win32 API下它是不可用
的，它是一个只对 WindowNT操作系统组件有效的内
部机制。 LPC提供了三种不同的消息传送方法：
?第一种方法适用于传送小于 256B的消息。它将消息
传给与服务器进程相连的端口对象，系统为每个端
口对象设置有一个固定大小的消息队列，作为通信
之用，此方法用于发送少于 256字节的信息。这个方
法类同于消息缓冲队列通信机制。
本地过程调用 LPC-1
?第二种方法适用于传送大于 256B的消息。它将消息指针
传给与服务器进程相连的端口对象，并把消息存放在共
享的主存区域中，消息大小受进程所分得的主存配额限
制。消息传送的过程如下：当客户要传送大消息时，就
由它自己创建一个称为主存区域的对象 -主存共享的对
象,LPC机制使得该地址空间为客户进程和服务器均可
见，然后客户进程把大消息存放在该主存区域对象中；
再向服务的的端口对象的消息队列中传送一个小消息指
出所传送消息的大小和消息所在的地址指针。
?第三种方法适用于服务器想读或写大量数据而共享区又
太小情况。数据可以直接从客户地址空间读出或向客户
地址间写入。 LPC组件提供了两个函数，服务器可以用
它们来完成这些操作，以第一种方法发送的消息被用于
同步正在传送的信息。
例题
?有一阅览室, 读者进入时必须先在一张登记表上进行登记,
该表为每一座位列一表目, 包括座号和读者姓名 。 读者离开
时要消掉登记信息, 阅览室中共有 100个座位, 请问：
为描述读者的动作, 应编写几个程序？ 设置几个进程？ 进程与
程序间的对应关系如何？
解 1：二个程序 。 管理员 1和管理员 2:管理员 1负责在读者进入时
在一张登记表上进行登记, 管理员 2负责读者离开时要消掉登
记信息 。 二个进程, 进程与程序间的对应关系一对一 。
var mutex,empty,full,Semaphore,=﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎, ﹎﹎ C﹎﹎ 。
begin
parbegin
Manager1：
begin
repeat
Wait a reader in；
﹎﹎﹎ D﹎﹎﹎ ；
例题 -1
﹎﹎﹎ E﹎﹎﹎ ；
Login a name in the register；
﹎﹎﹎ F﹎﹎﹎ ；
﹎﹎﹎ G﹎﹎﹎ ；
forever
end
Manager2：
begin
repeat
Wait a reader out；
﹎﹎﹎ H﹎﹎﹎ ；
﹎﹎﹎ I﹎﹎﹎ ；
Logout a name in the register；
﹎﹎﹎ J﹎﹎﹎ ；
﹎﹎﹎ K﹎﹎﹎ ；
forever
end
coend
end
例题 -2
解 2：一个读者程序, 每一个读者一个进程, 进程与程序间的对
应关系一对多 。
var empty, Semaphore,=﹎﹎ L﹎﹎；
begin
parbegin
Reader i：
Begin
﹎﹎﹎ M﹎﹎﹎；
Login a name in the register；
Read …,
Logout name in a register；
﹎﹎﹎ N﹎﹎﹎；
end
parend
end
A,B,C,L,(1)0; (2)1; (3)2; (4)100; (5)n;
D---K,M,N,(1)P(mutex); (2)V(mutex); (3)P(empty);(4)V(empty); (5)P(full); (6)V(full); (练习 )
习题
1,对于记录型信号量, 在执行一次 P操作时, 信号量的值应当
为﹎﹎ A﹎﹎； 当其值为﹎﹎ B﹎﹎ 时, 进程应阻塞 。 在执行 V
操作时, 信号量的值应当﹎﹎ C﹎﹎； 当其值为﹎﹎ D﹎﹎ 时,
应唤醒阻塞队列中的进程 。
A,C,(1)不变； (2)加 1； (3)减 1； (4)加指定数值； (5)减指
定数值 。
B,D,(1)大于 0； (2)小于 0； (3)大于等于 0； (4)小于等于 0。
(解 )
习题 -1
2.在操作系统中，解决进程间的﹎﹎ A﹎﹎ 两种基本关系，往往
运用对信号量进行﹎﹎ B﹎﹎ 的﹎﹎ C﹎﹎,例如，为保证系
统数据库的完整性，可以把信号量定义为某个库文件（或记
录）的锁，初值为 1，任何进程存取该库文件（或记录）之前
先对它作一个﹎﹎ D﹎﹎,存取之后对它作一个﹎﹎ E﹎﹎，
从而做到对该文件（或记录）任一时刻只有一个进程可存取，
但要注意使用不当引起的死锁。
A,(1)同步与异步； (2)串行与并行； (3)调度与控制； (4)同步
与互斥。
B,(1)消息操作； (2)P-V操作； (3)开关操作； (4)读写操作。
C,(1)通信原语； (2)调度算法； (3)分配策略； (4)进程控制。
D,E,(1)联机操作； (2)V操作； (3)输出操作； (4)读操作；
(5)写操作； (6)P操作； (7)输入操作。
(解 )
习题 -2
3。 有一阅览室，读者进入时必须先在一张登记表上进行登记，
该表为每一座位列一表目，包括座号和读者姓名。读者离开
时要消掉登记信息，阅览室中共有 100个座位，请问：
a.为描述读者的动作, 应编写几个程序？ 设置几个进程？ 进程
与程序间的对应关系如何？
b.用类 Pascal语言和 P,V操作写出这些进程间的同步算法 。
(解 )
4.试述 消息缓冲队列通信机制通信原理 。 (解 )
5.今有三个并发进程 R, M,P,它们共享一个缓冲区, R负责从
输入设备读信息, 每读一个记录后, 把它存放在缓冲区, M在
缓冲区加工读入的记录, P把加工后的记录打印输出, 读入的
记录经加工输出后, 缓冲区中又可存放下一个记录 。 请用 P、
V操作为同步机制写出它们并发执行时能正确工作的程序
习题 5图
R
Buf
M P
习题 -3
var s1,s2,s3,semaphore:=﹎﹎ A﹎﹎, ﹎﹎ B﹎﹎, ﹎﹎ C﹎
﹎ ;
begin
parbegin
R,begin
repeat
Read from i/o
﹎﹎﹎ D﹎﹎﹎ ;
Add to buffer;
﹎﹎﹎ E﹎﹎﹎ ;
until
end
习题 -4
M,begin
repeat
﹎﹎﹎ F﹎﹎﹎ ;
Remove from buffer;
Process …
Add to buffer;
﹎﹎﹎ G﹎﹎﹎ ;
until
end
P,begin
repeat
习题 -3
﹎﹎﹎ H﹎﹎﹎ ;
Remove from buffer;
﹎﹎﹎ I﹎﹎﹎ ;
Print a message;
until
end
parend
end
A,B,C,(1)0; (2)1; (3)2; (4)100; (5)n;
D---I,(1)P(s1); (2)V(s1); (3)P(s2); (4)V(s2);
(5)P(s3); (6)V(s3);
习题 -4
6,进程之间有哪几种高级通信方式?各种通信方式的特点如何?
分别运用哪些场合?
7,试述 UNIX S Ⅴ 通信软件包 IPC提供的消息机制 。
