优秀课件笔记之进程管理(中)

1、本文所以内容来自 著名高校课件和学生笔记（校园里面经常见到有人高价买笔记）
2、任课教师不会提供参考文献，所以只能对作者表示感谢，如果引用了您的作品，可以用回复方式补充参考文献。
3、我不对文章无关问题进行解答，文章内容也比较难，我也很难解答您遇到的问题，如果发现BUG可以用回复方式帮我修正。
4、本课 计算机操作系统
，适用于计算机操作系统课、考研

本课其他部分的导航条见页面底部

§3.5 进程互斥
§3.6 进程同步
§3.7 进程通信

§3.5
进
程
互
斥
3.5.1
资源共享所引起的制约
进程的并发执行不仅仅是用户程序的执行开始
时间的随机性和提高资源利用率的结果，也是资源
有限性导致资源的竞争与共享对进程的执行过程进
行制约所造成的。
1.
临界区
在描述一个程序或算法时，总是认为存在一个
伪处理机，可以按程序或算法所规定的步骤来执行
该程序或算法的。但是，事实上，在实际的系统中
则往往不是这样。一般说来，即使在程序中所描述
的一条语句，也是由多条执行指令构成的。例如，
各种程序中经常出现的赋值语句： X=X+1
；
52
u在用汇编语言书写时，就变成：
LOAD A
，X
ADDI A
，1
STORE A
，X
等三条语句，这里
A
代表累加器。根据系统的设计
和要求，在这三条语句的执行期间，也有可能发生
中断或调度，从而使得与当前进程无关的程序得以
执行。为了保证程序执行最终结果的正确性，必须
对并发执行的各进程进行制约，以控制它们的执行
速度和对资源的竞争。在进程的概念一节中已经介
绍了进程中两相邻语句可并发执行的三个条件。是
否有一种更为简单的办法来检查出需要对程序的哪
些部分进行制约才能保证其执行结果的正确性呢？
这里来看下面的例子。53
• 设有两个计算进程ＰA
，ＰB
共享内存ＭS
。其中
ＭS
分为三
个领域，即系统区、进程工作区和数据区。这里数据区被
划分大小相等的块，每个块中既可能放有数据，也有可能
未放有数据。系统区主要是堆栈Ｓ，其中存放那些空数据
块的地址（如图3.10
）。
图3.10
多进程共享内存栈区示例
54
• 当进程ＰA
或ＰB
要求空数据块时，从堆栈最顶部
（top
指针所指的位置）取出所需数据块。当进程
ＰA
或ＰB
释放数据块时，则把所释放数据块的地址
放入堆栈顶部。令getspace
为取空数据块过程，
release(ad)
为释放数据块过程。这里，ad
为待释放
数据块的地址。如果堆栈Ｓ非空的话，进程ＰA
或
ＰB
是可以用任意的顺序释放和获取数据块的。执
行getspace
tsegpeac
就是获取一个空数据块，而执行
release(ad)
就是释放一个地址为ad
的数据块。然
而，由下面的描述可以看到，在进程并发执行时，
getspace
tsegpeac
或
release(ad)
将有可能完不成所要求的功
能。
• getspace
tsegpeac
和
release(ad)
可进一步描述为：
55
getspace:
begin
local g
g
←stack[top
]
top
←top-1
end
release(ad): begin
top
←top+1
stack[top]
←ad
end
• 设时刻t
0
时，top=h
tohp=
0
，则getspace
tsegpeac
和
release(ad)
可能
按以下顺序执行：
• 首先
release(ad)
的第一句执行，
t
0
：top
← top+1
→ top=h
tohp=
0
+1
；
• 接着getspace
执行，得：
56
t
1
：g
←
stack[top
]
→ g=stack[ h
tsagkhc=[
0
+1]
；
t
2
：top
← top-1
→ top=h
tohp=
0
；
• 再是
release(ad)
的第二句执行，得：
t
3
：stack[top
]
← ad
→ stack[ h
0
]
← ad
；
• 其结果是调用getspace
tsegpeac
的进程取到的是h
0
+1
中的一
个未定义值，而调用release(ad)
的进程把所释放的
空块地址ad
重复放入了h
0
中。
• 怎样保证上述执行结果的正确性呢？
一个较为明
显的答案是，如果把getspace
tsegpeac
和release(ad)
抽象为
两个各以一个动作完成的顺序执行单位，那么执行
结果的正确性是可以保证的。
57
• 把不允许多个并发进程交叉执行的一段程序称为临
界部分（critical section
）或临界区（critical
region
）。
• 临界区是由属于不同并发进程的程序段共享公用数
据或公用数据变量而引起的，例如上例中就是因为
过程
getspace
和
release(ad)
共同访问栈Ｓ中的数据
而引起的。临界区不可能用增加硬件的方法来解决。
因此，临界区也可以被称为访问公用数据的那段程
序。
58
2.
间接制约
l 一般来说，可以把那些不允许交叉执行的临界区按不同的
公用数据划分为不同的集合。上例中，以公用数据栈Ｓ划
分的临界区集合是{getspace, release}
。把这些集合称为类
（class
）。显然，对类给定一个唯一的标识名，系统就会
容易地区分它们。在程序的描述中，可用下列标准形式来
描述临界区：
when
〈类名〉do
〈临界区〉od
l 设类
{getspace
，release}
的类名为sp
，则getspace
和
release(ad)
可重新描述为：
getspace:
when
sp
do
getspce
←stack[top
]
top
←top-1
od
release(ad): when
sp
do
top
← top+1
stack[top
]
← ad
od
59
l把这种由于共享某一公有资源而引起的在临界区内
不允许并发进程交叉执行的现象，称为由共享公有
资源而造成的对并发进程执行速度的间接制约，简
称间接制约。这里，“
间接”
二字主要是指各并发进
程的速度受公有资源制约，而不是进程间直接制约
的意思。
l这里，受间接制约的类中各程序段在执行顺序上是
任意的。
l显然，对于每一类，系统应有相应的分配和释放相
应公有资源的管理办法，以制约并发进程。这就是
互斥。
60
3.
什么是互斥
l可以把互斥定义为：一组并发进程中的一个或多个
程序段，因共享某一公有资源而导致它们必须以一
个不允许交叉执行的单位执行。也就是说，不允许
两个以上的共享该资源的并发进程同时进入临界区
称为互斥。
l这里，考虑类中只有一个元素，也就是只有一个程
序段的情况是很有意思的。这时程序段本身为公有
资源被并发进程共享。一般情况下，作为程序段的
一个过程不允许多个进程共同访问它。但如果该过
程是纯过程，则各并发进程可以同时访问它。纯过
程是指在执行过程中不改变过程自身代码的一类过
程。
61
l 通常，在计算机系统中，有许多过程是被多个并发进程同
时访问共享，例如编辑程序、编译程序等。把一个过程作
成纯过程可便于多个进程共享，但由于编制纯过程必须对
有关变量和工作区作相应的处理，从而其执行效率往往会
受到一定的影响。
l 一组并发进程互斥执行时必须满足如下准则：
(1)
不能假设各并发进程的相对执行速度。即各并发进程享有
平等的、独立的竞争共有资源的权利，且在不采取任何措
施的条件下，在临界区内任一指令结束时，其他并发进程
可以进入临界区。
(2)
并发进程中的某个进程不在临界区时，它不阻止其他进程
进入临界区。
(3)
并发进程中的若干个进程申请进入临界区时，只能允许一
个进程进入。
62
(4)
并发进程中的某个进程申请进入临界区时开始，应在有限
时间内得以进入临界区。
l 这里，准则(1)
，(2)
，(3)
是保证各并发进程享有平等的、独
立的竞争和使用公有资源的权利，且保证每一时刻至多只
有一个进程在临界区。而准则(4)
则是并发进程不发生死锁
（将在后面讲述）的重要保证。否则，由于某个并发进程
长期占有临界区，其他进程则因为不能进入临界区而进入
互相等待状态。
l 在一组并发执行进程中，除了因为竞争公有资源而引起的
间接制约带来进程之间互斥之外，还存在有因为并发进程
互相共享对方的私有资源所引起的直接制约。直接制约将
使得各并发进程同步执行。下面，将讨论互斥的实现方法。
63
3.5.2
互斥的加锁实现
l上节中，给出了临界区的描述方法和并发进程互斥执
行时所必要遵守的准则。但是，并没有给出怎样实现
并发进程的互斥。人们可能认为只需把临界区中的各
个过程按不同的时间排列调用就行了。但事实上这是
不可能的。因为这要求该组并发进程中的每个进程事
先知道其他并发进程与系统的动作，由用户程序执行
开始的随机性可知，这是不可能的。
l一种可能的办法是对临界区加锁以实现互斥。当某个
进程进入临界区之后，它将锁上临界区，直到它退出
临界区时为止。并发进程在申请进入临界区时，首先
测试该临界区是否是上锁的。如果该临界区已被锁
住，则该进程要等到该临界区开锁之后才有可能获得
临界区。
64
l 设临界区的类名为Ｓ。为了保证每一次临界区中只能有一个
程序段被执行，又设锁定位
key[
Ｓ]
。Key[
Ｓ]
表示该锁定位
属于类名为Ｓ的临界区。加锁后的临界区程序描述如下：
lock(key[
Ｓ])
〈临界区〉
unlock(key[
Ｓ])
l 设key [
Ｓ]=1
时表示类名为Ｓ的临界区可用，key[
Ｓ]=0
时表
示类名为Ｓ的临界区不可用。则，unlock(key[
Ｓ])
只用一条
语句即可实现。即：
key[
Ｓ]
←1
l 不过，由于lock(key[
Ｓ])
必须满足key[
Ｓ]=0
时，不允许任何
进程进入临界区，而key[
Ｓ]=1
时仅允许一个进程进入临界区
的准则，因而实现起来较为困难。
65
l一种简便的实现方法是：
lock(x
)=begin local v
repeat
v
←x
until v=1
x
←0
end
l 这种实现方法是不能保证并发进程互斥执行所要求的准则(3)
的。因为当同时有几个进程调用lock(key[
Ｓ])
时，在x
←0
语
句执行之前，可能已有两个以上的多个进程由于key[
Ｓ]=1
而
进入临界区。为解决这个问题有些机器在硬件中设置了“
测
试与设置”
指令，保证第一步和第二步执行不可分离。
注意：在系统实现时锁定位key[
Ｓ]
总是设置在公有资源所
对应的数据结构中的。
66
3.5.3
信号量和Ｐ，Ｖ原语
1.
信号量（semaphore
seamphor
）
l 尽管用加锁的方法可以实现进程之间的互斥，但这种方法仍然存在一些
影响系统可靠性和执行效率的问题。例如，循环测试锁定位将损耗较多
的
CPU
计算时间。如果一组并发进程的进程数较多，且由于每个进程在
申请进入临界区时都得对锁定位进行测试，这种开销是很大的。
l 另外，使用加锁法实现进程间互斥时，还将导致在某些情况下出现不公
平现象。试考虑以下进程P
A
和P
B
反复使用临界区的情况：
P
A
P
B
A
：lock(key
［Ｓ］) B
：lock(key
［Ｓ］)
〈Ｓ〉
＜Ｓ＞
unlock(key
［Ｓ］)
unlock(key
［Ｓ］)
Goto
A
Goto
B
设进程ＰA
已通过lock(key
[
Ｓ])
过程而进入临界区。显然，在进程P
A
执行unlock(key
[
Ｓ])
过程之前，key [
Ｓ]=0
且进程P
B
没有进入临界区的机
会。然而，当进程P
A
执行完unlock(key
[
Ｓ])
过程之后，由于紧接着是一
转向语句，进程P
A
将又立即去执行lock(key
[
Ｓ])
过程。
67
l 此时，由于unlock(key
[
Ｓ])
过程已将key[
Ｓ]
的值置为1
，也就
是开锁状态，从而进程P
A
又可进入临界区Ｓ。只有在进程P
A
执行完unlock(key
[
Ｓ])
过程之后、执行Goto
A
语句之前的瞬
间发生进程调度，使进程P
A
把处理机转让给进程P
B
，进程P
B
才有可能得到执行。然而遗憾的是，这种可能性是非常小的。
因此，进程P
B
将处于永久饥饿状态（starvation
）。
l 解决上述问题首先必须找到产生问题的原因。显然，在用加
锁法解决进程互斥的问题时，一个进程能否进入临界区是依
靠进程自己调用lock
过程去测试相应的锁定位。每个进程能
否进入临界区是依靠自己的测试判断。这样没有获得执行机
会的进程当然无法判断，从而出现不公平现象。而获得了测
试机会的进程又因需要测试而损失一定的CPU
时间。
68
l 这正如某个学生想使用某个人人都可借用、且不规定
使用时间的教室时一样，他必须首先申请获得使用该
教室的权利，然后再到教室看看该教室是不是被锁上
了。如果该教室被锁上了，他只好下次再来观察，看
该教室的门是否已被打开。这种反复将持续到他进门
后为止。从这个例子中，可以得到解决加锁法所带来
的问题的方法。一种最直观的办法是，设置一个教室
管理员。从而，如果有学生申请使用教室而未能如愿
时，教室管理员记下他的名字，并等到教室门一打开
则通知该学生进入。这样，既减少了学生多次来去教
室检查门是否被打开的时间，又减少了因为学生自发
地检查造成的不公平现象。在操作系统中，这个管理
员就是信号量。信号量管理相应临界区的公有资源，
它代表可用资源实体。
69
l信号量的概念和下面所述的Ｐ、Ｖ原语是荷兰科学
家E.W.Dijkstra
ijtrakEWs 提出来的。信号是铁路交通管理中
的一种常用设备，交通管理人员利用信号颜色的变
化来实现交通管理。在操作系统中，信号量sem
是
一整数。在sem
大于等于零时代表可供并发进程使
用的资源实体数，但sem
小于零时则表示正在等待
使用临界区的进程数。显然，用于互斥的信号量
sem
的初值应该大于零，而建立一个信号量必须经
过说明所建信号量所代表的意义，和赋初值以及建
立相应的数据结构以便指向那些等待使用该临界区
的进程。
70
2.
Ｐ，Ｖ原语
l 信号量的数值仅能由Ｐ，Ｖ原语操作改变(
Ｐ和Ｖ分别是荷
兰语
Passeren
和Verhoog
的头一个字母，相当于英文的
pass
和increment
的意思)
。采用Ｐ，Ｖ原语，可以把类名为
Ｓ的临界区描述为When
Ｓ
do
Ｐ(
sem
)
临界区Ｖ(
sem
)
od
。
l 这里，sem
是与临界区内所使用的公用资源有关的信号量。
一次Ｐ原语操作使得信号量sem
减1
，而一次Ｖ原语操作将
使得信号量sem
加1
。必须强调的一点是，当某个进程正在
临界区内执行时，其他进程如果执行了Ｐ原语操作，则该
进程并不像调用lock
时那样因进不了临界区而返回到lock
的
起点，等以后重新执行测试，而是在等待队列中等待有其
他进程做Ｖ原语操作释放资源后，进入临界区，这时，Ｐ
原语的执行才算真正结束。
71
l 另外，当有好几个进程执行Ｐ原语未通过而进入等待状态
之后，如有某进程作了Ｖ原语操作，则等待进程中的一个
可以进入临界区，但其他进程必须等待。
l Ｐ原语操作的主要动作是：
(1)
sem
减
1
；
(2)
若sem
减1
后仍大于或等于零，则进程继续执行；
(3)
若sem
减1
后小于零，则该进程被阻塞后进入与该信
号相对应的队列中，然后转进程调度。
l Ｐ原语操作的功能框图如图3.11
。
72
图3.11
Ｐ原语操作功能图
3.12
Ｖ原语操作功能
73
l Ｖ原语的操作主要动作是：
(1)
sem
加1
；
(2)
若相加结果大于零，进程继续执行；
(3)
若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进
程，然后再返回原进程继续执行或转进程调度。
l Ｖ原语操作的功能框图如图3.12
。
l 有了加锁法的基础，大家应该明白为什么Ｐ，Ｖ过程要以
原语实现的原因。否则，如果多个进程同时调用Ｐ操作或
Ｖ操作的话，则有可能在Ｐ操作刚把sem-1
而未把对应进程
送入等待队列时，Ｖ操作开始执行。从而，Ｖ操作将无法
发现等待进程而返回。因此，Ｐ，Ｖ操作都必须以原语实
现，且在Ｐ，Ｖ原语执行期间不允许中断发生。
74
l 关于Ｐ，Ｖ原语的实现，有许多方法。这里介绍一种使用
加锁法的软件实现方法，实现过程描述如下：
Ｐ(
sem
)
：
begin
封锁中断；
lock(lockbit
)
val[sem
]=val[sem]-1
if
val[sem
]<0
保护当前进程CPU
现场
当前进程状态置为″
等待″
将当前进程插入信号sem
等待队列
转进程调度
fi
unlock(lockbit
)
；开放中断
end
75
Ｖ(
sem
)
：
begin
封锁中断；
lock(lockbit
)
va[sem
]=val[sem]+1
if val[sem]
≤0
local k
从sem
等待队列中选取一等待进程，将其指针置入k
中
将k
插入就绪队列
进程状态置“
就绪”
fi
unlock(lockbit
)
；开放中断
end
76
3.5.4
用Ｐ，Ｖ原语实现进程互斥
l 利用Ｐ，Ｖ原语和信号量，可以方便地解决并发进程的互
斥问题，而且不会产生使用加锁法解决互斥问题时所出现
的问题。
l 设信号量sem
是用于互斥的信号量，且其初值为1
表示没有
并发进程使用该临界区。显然，由上面几节的讨论可知，
只要把临界区置于Ｐ(
sem
)
和Ｖ(
sem
)
之间，即可实现进程间
的互斥。当一个进程想要进入临界区时，它必须先执行Ｐ
原语操作以将信号量sem
减1
。在一个进程完成对临界区的
操作之后，它必须执行Ｖ原语操作以释放它所占用的临界
区。由于信号量初始值为
1
，所以，任一进程在执行Ｐ原语
操作之后将sem
的值变为0
，表示该进程可以进入临界区。
77
l 在该进程未执行Ｖ原语操作之前如有另一进程想进入临界
区的话，它也应先执行
Ｐ
原语操作，从而使sem
的值变为
-1
，因此，第二个进程将被阻塞。直到第一个进程执行Ｖ
原语操作之后，sem
的值变为0
，从而可唤醒第二个进程进
入就绪队列，经调度后再进入临界区。在第二个进程执行
完Ｖ原语操作之后，如果没有其他进程申请进入临界区的
话，则sem
又恢复到初始值。
l 用信号量实现两并发进程P
A
，P
B
互斥的描述如下：
1)
设
sem
为互斥信号量，其取值范围为(1,0,-1)
。
其中sem
=1
表示进程P
A
和P
B
都未进入类名为Ｓ的临界
区，sem
=0
表示进程P
A
或P
B
已进入类名为Ｓ的临界区，
sem
=-1
表示进程P
A
和P
B
中，一个进程已进入临界区，而另
一个进程等待进入临界区。
78
2)
描述：
P
A
：
Ｐ(
sem
)
〈Ｓ〉
Ｖ(
sem
)
：
：
：
P
B
：
Ｐ(
sem
)
〈Ｓ〉
Ｖ(
sem
)
∷
：
：
79
§3.6
进
程
同
步
3.6.1
同步的概念
l除了对公有资源的竞争而引起的间接制约之外，并
发进程之间是否还存在着其他制约关系影响执行速
度呢？来看下面的例子。
l计算进程和打印进程共同使用同一缓冲区Buf
。计
算进程反复地把每次计算结果放入
Buf
中，而打印
进程则把计算进程每次放入
Buf
中的数据通过打印
机打印输出。如果不采取任何制约措施，这两个进
程的执行起始时间和执行速度都是彼此独立的，其
相应的控制段可以描述为：
80
P
C
：
:
A:
local
Buf
Repeat
Buf
←
Buf
Until
Buf
=
空
计算
得到计算结果
Buf
←
计算结果
Goto
A
P
P
:
：
:
B:
local
Pri
Repeat
Pri
←
Buf
Until
Pri
≠
空
打印
Buf
中的数据
清除
Buf
中的数据
Goto
B
81
l 这里，如果假定进程P
C
和P
P
对公用缓冲区Buf
已采取了互
斥措施。
l 显然，如果按上面的描述并发执行进程P
C
和P
P
的话，则会
造成CPU
时间的极大浪费（因为其中包含有二处反复测试
语句）。这是操作系统设计要求不允许的。CPU
时间的浪
费主要是由于进程P
C
和P
P
的执行互相制约所引起的。P
C
的
输出结果是P
P
的执行条件，反过来，P
P
的执行结果也是P
C
的执行条件。这种现象在操作系统和用户进程中大量存在。
这与上节中讲述的进程互斥是不同的，进程互斥时它们的
执行顺序可以是任意的。一组在异步环境下的并发进程，
各自的执行结果互为对方的执行条件，从而限制各进程的
执行速度的过程称为并发进程间的直接制约。
82
l这里异步环境主要指各并发进程的执行起始时间的
随机性和执行速度的独立性。正如在上面例子中所
看到的那样，如果没有相应的解决方法，进程的直
接制约将会造成大量的CPU
时间浪费。一种最为简
单和直观的方法是直接制约的进程互相给对方进程
发送执行条件已经具备的信号。这样，被制约进程
即可省去对执行条件的测试，只要收到了制约进程
发来的信号便开始执行，而在未收到制约进程发来
的信号时便进入等待状态。
83
l把异步环境下的一组并发进程，因直接制约而互相
发送消息而进行互相合作、互相等待，使得各进程
按一定的速度执行的过程称为进程间的同步。具有
同步关系的一组并发进程称为合作进程，合作进程
间互相发送的信号称为消息或事件。如果对一个消
息或事件赋以唯一的消息名，则可用过程
wait(
消息名）
l表示进程等待合作进程发来的消息，而用过程
signal
（消息名）
l表示向合作进程发送消息。利用过程wait
tawi
和
signal
，可以简单地描述上面例子中的计算进程P
C
和打印进程P
P
的同步关系如下：
84
(1)
设消息名Bufempty
表示Buf
空，消息名Buffull
表示Buf
中装满了数据。
(2)
初始化Bufempty
=true
，Buffull
=false
。
l (3)
描述：
P
C
：
ggg P
P
：
A:
wait(Bufempty
) B:
wait(Buffull
)
计算
打印Buf
中的数据
Buf
←
计算结果
清除Buf
中的数据
Bufempty
← false
Buffull
← false
signal(Buffull
)
signal(Bufempty
)
Goto
A
Goto
B
过程wait
的功能是等待到消息名为true
的进程继续执
行，而signal
的功能则是向合作进程发送合作进程所需要的消
息名，并将其值置为true
。
85
3.6.2
私用信号量
l 上面用wait
（消息名）与signal
（消息名）的方式，描述了
进程同步的一种实现方法。事实上，使用
3.5
节介绍的信号
量的方法也可实现进程间的同步。
l 一般来说，也可以把各进程之间发送的消息作为信号量看
待。与进程互斥时不同的是，这里的信号量只与制约进程
及被制约进程有关而不是与整组并发进程有关。因此，称
该信号量为私用信号量（Private
Semaphvre
）。一个进程
Pi
的私用信号量Semi
是从制约进程发送来的进程Pi
的执行条
件所需要的消息。与私用信号量相对应，称互斥时使用的
信号量为公用信号量。
86
3.6.3
用Ｐ，Ｖ原语操作实现同步
l有了私用信号量的概念，可以使用Ｐ，Ｖ原语操作
实现进程间的同步。利用Ｐ，Ｖ原语实现进程同步
的方法与利用wait
tawi
和signal
过程时相同，也是分为
三步。首先为各并发进程设置私用信号量，然后为
私用信号量赋初值，最后利用Ｐ，Ｖ原语和私用信
号量规定各进程的执行顺序。
图3.13
缓冲区队列
87
l 例：设进程P
A
和P
B
通过缓冲区队列传递数据（如图3.13
）。
P
A
为发送进程，P
B
为接收进程。P
A
发送数据时调用发送过程
deposit(data)
，P
B
接收数据时调用过程remove(data)
。且数据
的发送和接收过程满足如下条件：
(1)
在P
A
至少送一块数据入一个缓冲区之前，P
B
不可能从缓冲
区中取出数据（假定数据块长等于缓冲区长度）；
（2) P
A
往缓冲队列发送数据时，至少有一个缓冲区是空的；
（3)
由P
A
发送的数据块在缓冲队列中按先进先出（FIFO
）方
式排列。
?
如何描述发送过程deposit(data)
和接收过程remove(data)
。
88
解：由题意可知，进程P
A
调用的过程deposit(data)
和进程P
B
调
用的过程remove(data)
必须同步执行，因为过程
deposit(data)
的执行结果是过程remove(data)
的执行条件，而当缓冲队列全
部装满数据时，remove(data)
的执行结果又是deposit(data)
的
执行条件，满足同步定义。从而，按以下三步描述过程
deposit(data)
和remove(data)
：
（1)
设Bufempty
为进程P
A
的私用信号量，Buffull
为进程P
B
的私
用信号量；
（2)
令Bufempty
的初始值为n
（n
为缓冲队列的缓冲区个数），
Buffull
的初始值为0
；
（3)
描述(
见下页)
89
P
A
: deposit(data):
begin local x
P(
Bufempty
)
；
按FIFO
方式选择一个空缓冲区Buf(x
)
；
Buf(x
)
← data
Buf(x
)
置满标记
V(
Buffull
)
end
P
B
: remove(data):
Begin local x
P(
Buffull
)
；
按FIFO
方式选择一个装满数据的缓冲区Buf(x
)
data
←
Buf(x
)
Buf(x
)
置空标记
V(
Bufempty
)
end
90
u（思考：在该题中需要考虑互斥吗？为什么？如果每次只允许一个
进程对缓冲队列进行操作时怎么办？）
这里，局部变量x
用来
指明缓冲区的区号，
给Buf(x
)
置标志位是
为了便于区别和搜索
空缓冲区及非空缓冲
区。
3.6.4
生产者-
消费者问题（producer-consumer problems
）
l把并发进程的同步和互斥问题一般化，可以得到一
个抽象的一般模型，即生产者-
消费者问题。计算
机系统中，每个进程都申请使用和释放各种不同类
型的资源，这些资源既可以是像外设、内存及缓冲
区等硬件资源，也包括临界区、数据、例程等软件
资源。把系统中使用某一类资源的进程称为该资源
的消费者，而把释放同类资源的进程称为该资源的
生产者。例如在上面的计算进程P
C
与打印进程P
P
公
用一个缓冲区的例子中，计算进程P
C
把数据送入缓
冲区，打印进程P
P
从缓冲区中取数据打印输出，因
此，P
C
进程相当于数据资源的生产者，而P
P
进程相
当于消费者。
91
l 把一个长度为ｎ的有界缓冲区（n>0)
与一群生产者进程Ｐ1
，Ｐ2
，…
，
Ｐm
和一群消费者进程Ｃ1
，Ｃ2
，…
，Ｃk
联系起来（如图3.14
所示）。
l 设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的
过程deposit(data)
和各消费者使用的过程remove(data)
可描述如下：
Ø 首先，可以看到，上述生产者-
消费者问题是一个同步问题。即生产者
和消费者之间满足如下条件：
(1)
消费者想接收数据时，有界缓冲区中至少有一个单元是满的；
(2)
生产者想发送数据时，有界缓冲区中至少有一个单元是空的。
Ø 另外，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进
程之间必须互斥执行。
92
图3.14
生产者-
消费者问题
l 由以上分析，设公用信号量mutex
保证生产者进程和消费者进程之间的
互斥，设信号量avail
为生产者进程的私用信号量，信号量full
为消费者
进程的私用信号量。信号量avail
表示有界缓冲区中的空单元数，初值为
n
；信号量full
表示有界缓冲区中非空单元数，初值为0
。信号量mutex
表示可用有界缓冲区的个数，初值为
1
。从而有：
deposit(data
):
remove(data
):
begin
begin
Ｐ（avail
）
Ｐ（full
）
Ｐ（mutex
）
Ｐ（mutex
）
送数据入缓冲区某单元
取缓冲区中某单元数据
Ｖ（full
）
Ｖ（avail
）
Ｖ（mutex
）
Ｖ（mutex
）
end
end
在上例中，由于一个过程中包含有几个公用、私用信号量，因此，
Ｐ、Ｖ原语的操作次序要非常小心。一般说来，由于Ｖ原语是释放资源
的，所以可以以任意次序出现。但Ｐ原语则不然，如果次序混乱，将会
造成进程之间的死锁。关于死锁，将在3.8
中介绍。
93
§3.7
进
程
通
信
本节介绍进程间互相传递信息的方法和原理。通信
（communication
）意味着在进程间传送数据。操作系统可
以被看作是各种进程组成的。这些进程都具有各自的独立
功能，且大多数被外部需要而启动执行。一般来说，进程
间的通信根据通信内容可以划分为二种：即控制信息的传
送与大批量数据传送。有时，也把进程间控制信息的交换
称为低级通信，而把进程间大批量数据的交换称为高级通
信。上面几节中所介绍的进程间同步或互斥，也是使用锁
或信号量进行通信来实现的。低级通信一般只传送一个或
几个字节的信息，以达到控制进程执行速度的作用。高级
通信要传送大量数据。高级通信的目的不是为了控制进程
的执行速度，而是为了交换信息。
94
3.7.1
进程的通信方式
n 在单机系统中，进程间通信可分为4
种形式：
(1)
主从式；
(2)
会话式；
(3)
消息或邮箱机制；
(4)
共享存储区方式。
u主从式通信系统的主要特点是：
①
主进程可自由地使用从进程的资源或数据；
②
从进程的动作受主进程的控制；
③
主进程和从进程的关系是固定的。
Ø 主从式通信系统的典型例子是终端控制进程和终端进程。
95
u会话方式中，通信进程双方可分别称为使用进程和服务
进程。其中，使用进程调用服务进程提供的服务。它们
具有如下特点：
①
使用进程在使用服务进程所提供的服务之前，必须得到服务进
程的许可；
②
服务进程根据使用进程的要求提供服务，但对所提供服务的控
制由服务进程自身完成。
③
使用进程和服务进程在通信时有固定连接关系。
Ø 用户进程与磁盘管理进程之间的通信是会话系统的一个
例子。各用户进程向磁盘管理进程提出使用要求并得到
许可之后，才可以使用相应的存储区。而且，由磁盘管
理进程自身完成对磁盘存储区的管理和控制。另外，用
户进程与磁盘管理进程之间，只有在用户进程要求使用
磁盘存储区时才有通信关系。
96
u消息或邮箱机制则无论接收进程是否已准备好接收消息，
发送进程都将把所要发送的消息送入缓冲区或邮箱。消息
的一般形式为４个部分组成。即：发送进程名、接收进程
名、数据和有关数据的操作（图3.15
）。
u消息或邮箱机制的特点是：
①
只要存在空缓冲区或邮箱，发送进程就可以发送消息。
②
与会话系统不同，发送进程和接收进程之间无直接连接关系，接收进
程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进
程发来的消息。
③
发送进程和接收进程之间存在缓冲区或邮箱（图3.16
）用来存放被传
送消息。
97
图3.15
消息的组成图3.16
缓冲区或邮箱通信结构
u与前面三种方式不同，共享存储区方式不要求数据移动。
两个需要互相交换信息的进程通过对同一共享数据区
（shared memory
）的操作来达到互相通信的目的。这个
共享数据区是每个互相通信进程的一个组成部分。
u以上几种通信方式都可用于大量数据传送，而且，由于
其通信方式不同，需要使用不同的控制方式来达到通信
进程之间同步或互斥的目的。
下面，首先介绍进程通信中较为常用的消息与邮箱
机制，然后再介绍几个实际例子。
98
3.7.2
消息缓冲机制
u 发送进程和接收进程采用消息缓冲机制进行数据传送时，发送进程在
发送消息前，先在自己的内存空间设置一个发送区，把欲发送的消息
填入其中，然后再用发送过程将其发送出去。接收进程则在接收消息
之前，在自己的内存空间内设置相应的接收区，然后用接收过程接收
消息。由于消息缓冲机制中所使用的缓冲区为公用缓冲区，使用消息
缓冲机制传送数据时，两通信进程必须满足如下条件：
①
在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止
其他进程对该缓冲区消息队列的访问。否则，将引起消息队列的混乱。
同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其他进程
对该队列的访问。
②
当缓冲区中无消息存在时，接收进程不能接收到任何消息。
Ø 至于发送进程是否可以发送消息，则由发送进程是否申请
到缓冲区决定。
99
u 设公用信号量mutex
为控制对缓冲区访问的互斥信号量，其初值为1
。设SM
为
接收进程的私用信号量，表示等待接收的消息个数，其初值为0
。设发送进程
调用过程send(m)
将消息m
送往缓冲区，接收进程调用过程Receive(m)
将消息m
从缓冲区读往自己的数据区，则Send(m)
和Receive(n)
可分别描述为：
Send(m
):
begin
向系统申请一个消息缓冲区
Ｐ（mutex
）
将发送区消息m
送入新申请的消息缓冲区
把消息缓冲区挂入接收进程的消息队列
Ｖ（mutex
）
Ｖ（SM
）
end
Receive(n
):
begin
Ｐ（SM
）
Ｐ（mutex
）
摘下消息队列中的消息n
将消息n
从缓冲区复制到接收区
释放缓冲区
Ｖ（mutex
）
end