1
第 3章 并发控制 —— 互斥与同步
本章知识点：
? 3.1 并发原理
? 3.2 互斥 —— 软件解决方法
? 3.3 互斥 —— 硬件解决方法
? 3.4 信号量
? 3.5 管程
? 3.6 *消息传递
? 3.7 *读者 /写者问题
? 3.8 系统举例（略）
2
3.1 并发原理
在单处理机多道程序的系统中，进程的
并发执行方式是插入执行，表面看起来
进程如同是同时执行的。在多处理机系
统中并发执行方式有插入执行和重叠执
行。 并发的存在要求操作系统必须能跟
踪大量活跃进程,必须为每一活跃进程分
配资源，必须保护每一进程的数据和物
理资源不被其他进程侵犯，并且进程执
行的结果与其他并发进程执行时的相对
速度无关。
3
3.1.1 进程间的相互作用
进程之间常常相互作用，存在某种彼此
依赖或相互制约的关系, 同步和互斥关系。
根据进程意识到其他进程的存在程度不同,
可将进程间的相互作用划分为,进程互不
觉察, 进程间接觉察, 进程直接觉察 。
4
3.1.2 进程间的相互竞争
并发进程在竞争使用同一资源时将产生冲突。
进程间的竞争面临 3个控制问题：
? 互斥
? 死锁
? 饥饿
竞争的控制不可避免地涉及到操作系统，因为
是操作系统分配资源，另外，进程自身也必须
能以某种方式表达互斥的要求 。
5
3.1.2 进程间的相互竞争
? 临界资源,
? 在同一时刻只允许一个进程访问的资源
称为临界资源。
? 临界区 (段 ):访问临界资源的那一部分程
序称为临界区（段）。
6
3.1.3 进程间的相互合作
1.通过共享合作
这些进程并不是通过名字察觉到对方,
而是通过共享访问间接察觉 。 进程间通
过共享方式进行合作 。 除互斥, 死锁和
饥饿外, 保证数据的一致性也是一个潜
在的控制问题 。
7
3.1.3 进程间的相互合作
2.通过通信合作
进程通信是指进程之间可直接以较高的
效率传递较多数据的信息交换方式。这
种方式中采用的是通信机构，在进程通
信时往往以消息形式传递信息。 因为在
消息传递中不存在共享，所以这种形式
的合作不需要互斥，但是还存在死锁和
饥饿问题。
8
3.1.4 互斥的要求
并发进程的成功完成需要有定义临界段和
实现互斥的能力，这是任何并发进程方案
的基础。解决互斥问题必须满足以下要求：
? 互斥执行
? 执行非临界段的进程不能受到其他进程的
干扰
? 有限的等待
? 没有进程相对速度和数目的假设
? 进程进入到临界段中的时间有限
9
3.2 互斥 —— 软件解决方法
软件方法对并发进程不提供任何支持，
因此，无论是系统程序或应用程序，进
程都要同其他进程合作以解决互斥，它
们从程序设计语言和操作系统那里得不
到任何支持。软件方法易引起较高的进
程附和较多的错误，但有利于深刻理解
并发的复杂性。
10
3.2.1 Dekker算法
Dekker算法的优点在于它描述了并发进
程发展过程中遇到的大部分共同问题。
任何互斥都必须依赖于一些硬件上的基
本约束，其中最基本的约束是任一时刻
只能有一个进程访问内存中某一位置。
11
3.2.1 Dekker算法
1.第 1种途径
这种方法保证了互斥，但它只记住了允许哪个进
程进入其临界段，未记住每个进程的状态。
var turn,0..1; {turn为共享的全局变量 }
PROCESS 0 PROCESS 1
… …
while turn≠0 do {nothing}; while turn≠1 do {nothing}； 〈 critical
section〉 ; 〈 critical section〉 ;
turn,=1; turn,=0;
… …
12
3.2.1 Dekker算法
2.第 2种途径
这种解决方法依赖于进程执行的相对速度
共享的全局变量是,var flag,array[0..1]of boolean;
它被初始化为 false
PROCESS 0 PROCESS 1
… …
while flag[1]do {nothing}; while flag[0]do {nothing};
flag[0],=true; flag[1],=true;
〈 critical section〉 ; 〈 critical section〉 ;
flag[0],=false; flag[1],=false;
… …
13
3.2.1 Dekker算法
3.第 3种途径
这种方法保证了互斥但会导致死锁问题。
PROCESS 0 PROCESS 1
… …
flag[0],=true; flag[1],=true;
while flag[1] do {nothing}; while flag[0] do {nothing};
〈 critical section〉 ; 〈 critical section〉 ;
flag[0],=false; flag[1],=false;
… …
14
3.2.1 Dekker算法
4.第 4种途径
PROCESS 0 PROCESS 1
… …
flag[0],=true; flag[1],=true;
while flag[1] do {nothing}; while flag[0] do {nothing};
begin begin
flag[0],=false; flag[1],=false;
〈 delay for a short time〉 ; 〈 delay for a short time〉 ;
flag[0],=true; flag[1],=true;
end; end;
〈 critical section〉 ; 〈 critical section〉 ;
flag[0],=false； flag[1],=false;
… …
15
3.2.1 Dekker算法
5.一个正确的解决方法
设计一个“指示”小屋，小屋内的黑板标明
,turn”，当 P0想进入其临界段时，置自己的 flag
为,true”，这时它去查看 P1的 flag，如果是
,false”，则 P0就立即进入自己的临界段，反之 P0
去查看“指示”小屋，如果 turn=0，那么它知道
自己应该坚持并不时去查看 P1的小屋,P1将觉察
到它应该放弃并在自己的黑板上写上,false”，
以允许 P0继续执行。 P0执行完临界段后，它将
flag置为,false”以释放临界段，并且将 turn置为 1
，将进入权交给 P1 。
16
3.2.2 Peterson算法
Dekker算法可以解决互斥问题，但是，
其复杂的程序难于理解，其正确性难于
证明。 Peterson给出了一个简单的方法。
下面是一个两进程互斥的简单解决方法，
进一步可将 Peterson算法推广到多个进程
的情况。
17
3.2.2 Peterson算法
var flag,array[0..1] of boolean; flag[1],=true;
turn,0..1; turn,=0;
procedure P0; while flag[0] and turn=0 do {nothing};
begin 〈 critical section〉 ;
repeat flag[1],=false;
flag[0],=true; 〈 remainder〉
turn,=1; forever
while flag[1] and turn=1 do {nothing}; end;
〈 critical section〉 ; begin
flag[0],=false; flag[0],=false;
〈 remainder〉 flag[1],=false;
forever turn,=1;
end; parbegin
procedure P1; P0; P1
begin parend
repeat end.
18
3.3 互斥 —— 硬件解决方法
完全利用软件方法来解决进程互斥进入
临界区的问题有一定的难度，且有很大
局限性，现在有许多计算机提供了一些
可以解决临界区问题的特殊的硬件指令。
硬件方法通过特殊的机器指令实现互斥，
可以降低开销。
19
3.3.1 禁止中断
在单处理机中，禁止进程被中断即可保证互
斥，通过操作系统内核定义的禁止和允许中
断的原语就可获得这种能力。进程执行临界
段时不能被中断。
优点：
? 在单处理机中可保证互斥。
缺点：
? 代价较高，使执行效率显著降低
? 在多处理机系统中，禁止中断不能保证互斥
20
3.3.2 使用机器指令
1.特殊的机器指令
在多处理机系统中，多个处理机共享一
个共同的主存，这里并没有主 /从关系，
也没有实现互斥的中断机制。许多系统
都提供了一些特殊的硬件指令，允许我
们在一个存储周期内去测试和修改一个字的内容（ Test and Set指令），或者交
换两个字的内容（ Exchange指令）等等。
这些特殊指令可以用来解决临界段问题。
21
3.3.2 使用机器指令
2.机器指令方法的特性
优点：
? 可用于含有任意数量进程的单处理机或共享主存的多处
理机；
? 比较简单, 易于验证；
? 可支持多个临界段, 每个临界段用各自的变量加以定义 。
缺点：
? 采用 busy-waiting技术, 进程等待进入临界段时耗费处
理机时间；
? 可能产生饥饿；
? 可能产生死锁 。
22
3.4 信号量
信号量是一个整型变量，除对其初始化外，它
可由两个不可中断的 P,V操作存取。 不论是采
用一般信号量还是二元信号量，进程都将排队
等候信号量，但这并不意味着进程移出的顺序
与队列次序相同。
基本原则：两个或多个进程可通过单一的信号
量展开合作，即进程在某一特定的地方停止执
行，直到某个特定的信号量到来为止。通过信
号量，任何复杂的合作要求都可被满足 。
23
3.4 信号量
? P 操作
Wait(s):
s.count:=s.count-1
If s.count<0
Then begin
将该进程置入 s.queue,阻塞该进程
End ;
? V操作
s.count:=s.count+1
If s.count<=0
Then begin
将进程 从 s.queue 中移出，置入就绪队列
End ;
24
3.4.1 用信号量解决互斥问题
信号量的互斥算法可以用小屋模型来描述。除
了黑板外，小屋中还有一个大冰箱。某进程进
入小屋后执行 wait操作将黑板上的数减 1，这时，
如果黑板上的值非负，它就进入临界段，反之
它就进入冰箱内冬眠。这时，就允许另一进程
进入小屋。当一个进程完成其临界段后，它进
入小屋执行 signal，将黑板上的值加 1，这时如
果黑板上的值为非正数，它就从冰箱中唤醒一
个进程。
25
3.4.2 用信号量解决生产者 /消费者
问题
问题描述如下：一个或更多的生产者生
产出某种类型的数据 (记录、字符 )，并把
它们送入缓冲区，惟一的一个消费者一
次从缓冲区中取走一个数据，系统要保
证缓冲区操作不发生重叠，即在任一时
刻只能有一方 (生产者或消费者 )访问缓冲
区。
26
3.4.2 用信号量解决生产者 /消费者
问题
用二元信号量来解决此问题。在任何时候生
产者 (P)都可向缓冲区中添加数据，在添加数据前，
P执行 waitB(s)，然后执行 signalB(s)以防止在添加过
程中，别的消费者 (C)或 P访问缓冲区。在进入到临
界段时,P将增加 n的值，如果 n=1则在此次添加数
据前缓冲区为空，于是 P执行 signalB(delay)并将这
个情况通知 C。 C最初执行 waitB(delay)来等待 P生产
出第一个数据，然后取走数据并在临界段中减小 n
的值。如果 P总保持在 C前面，那么 C就不会因为信
号量 delay而阻塞，因为 n总是正数，这样 P和 C都能
顺利地工作。这个方法也存在缺陷有可能导致死锁。
27
3.4.2 用信号量解决生产者 /消费者
问题
解决这个问题的一个方法是引入一个附
加变量，它在消费者的临界段中设置。
这样，就不会出现死锁了。
使用一般信号量可以得到另一种解决方
法，变量 n是一个信号量，它的值等于缓
冲区中的数据项数。
28
3.4.3 信号量的实现
wait和 signal操作都必须作为原子操作实现。显
然，用硬件方法或固件方法都可解决这一问题，
而且还有其他解决方法。尽管 wait和 signal操作
执行的时间较短，但因包含了忙 --等，故忙 --等
占用的时间是主要的 。
对单处理机系统而言，可以在 wait和 signal操作
期间屏蔽中断, 而且这些操作的执行时间相对
较短。
29
3.4.4 用信号量解决理发店问题
理发店问题是使用信号量实现并发的另一个例
子，它同操作系统中的实际问题非常相似。如
图示 理发椅
沙发
收款台
出
口
入
口
顾客休息区
30
3.5 管程
信号量为实现互斥和进程间的协调提
供了一个功能强大而灵活的工具，然
而，使用信号量来编制正确的程序是
困难的。
作为程序设计语言中的一种结构，管
程 (Monitor)提供了与信号量相同的表
达能力，但它更容易控制。
31
3.5.1 带信号量的管程
管程是一种并发性的结构，它包括用于
分配一个特定的共享资源或一组共享资
源的数据和过程。管程由三部分组成：
? 局部于管程的共享变量说明。
? 对该数据结构进行操作的一组过程。
? 对局部于管程的数据设置初始值的语句。
此外，还需为该管程赋予一个名字。
32
3.5.1 带信号量的管程
管程最主要的特点如下：
? 只能通过管程中的过程而不能用其他外
部过程访问其局部数据变量。
? 进程通过调用管程的过程而进入管程。
? 每一时刻只能有一个进程在管程中执行，
任何其他调用管程的进程将被挂起直至
管程可用为止。
33
3.5.2 用管程解决生产者 /消费者
问题
管程模块控制着缓冲区。管程包括两个
条件变量：当缓冲区中还有空位置时，
变量 notfull为 true，如果缓冲区中至少有
一个字符存在，则变量 notempty为 true。
生产者只能通过管程中的过程 append向
缓冲区添加字符，生产者不能直接访问
缓冲区。这个例子比较了管程和信号量。
34
3.6 消息传递
进程间的相互作用必须满足两个条件：同
步和通信，进程需要同步来实现互斥，进
程间的协同需要交换信息，一个能解决上
述两个问题的方法是消息传递 (message
passing)。消息传递还有一个优点是，它
的适应性很强，能在分布式系统、共享存
储器的多处理机系统以及单处理机系统等
不同系统中实现。
35
3.6.1 消息传递原语
原语：
? ·send (destination,message)
? ·receive (source,message)
36
3.6.2 用消息传递实现同步
无论是发送方还是接收方都可能被阻塞。
下面有三种最一般的组合，任何特定系统
都实现了其中的一种或两种：
? 阻塞发送，阻塞接收。
? 无阻塞发送，阻塞接收。
? 无阻塞发送，无阻塞接收。
37
3.6.3 寻址方式
1,直接寻址
对直接寻址方式,send原语中明确标明
了目的进程。 receive原语有两种方式：
第一种方式接收进程预先知道发送消息
的源进程，另一种方式则不可能预先知
道源进程。
38
3.6.3 寻址方式
2,间接寻址
消息不直接由发送方传给接收方，而是
通过一个共享的数据结构，包括临时存
放消息的队列（邮箱式端口）。这种方
法有很大的灵活性。进程与邮箱的关系
可以是静态的或动态的，端口通常与一
个特定的进程相关联。端口通常由接收
进程产生并为其所有。
39
3.6.4 消息格式
消息格式依赖于消息系统的用途和消息
系统是在单个计算机上运行还是在分布
式系统中运行，一些操作系统选择了较
短的定长消息以减小处理和存储的开销，
如果有大量的数据需要传递，那么可以
将数据存入文件并把文件作为消息传递，一种更为灵活的方法是允许变长消息。
40
3.6.4 消息格式
支持变长消息的操作系统中的消息格式
消 息 源
目 的 地
消息长度
控制信息
消息类型
消
息
头
消
息
体
消息的内容
41
3.6.5 排队规则
最简单的排队规则是先进先出，但这远
远不够。一个改进的方法是由发送方或
接收方基于消息的类型标明消息的优先
权；另一个改进方法是允许接收方检查
消息队列并选择要接收的消息。
42
3.6.6 用消息传递实现互斥
假设使用阻塞 receive原语和无阻塞 send原
语，并发进程集共享一个邮箱 mutex，将
邮箱初始化为仅包含一个空消息，欲进
入临界段的进程首先要接收相应的消息，
如果邮箱为空则该进程被阻塞，一旦进
程得到消息它就执行其临界段，然后再
将消息放回邮箱，这样消息就如同令牌
一样在进程之间传递。
43
3.6.6 用消息传递实现互斥
这种解决方法是，假设有多于一个进程并
发执行 receive操作，则有：
? ·如果仅有一个消息，那么它只可传递给一
个进程，其他进程将被阻塞。
? ·如果邮箱为空，则所有的进程将被阻塞。
当消息可用时，仅有一个阻塞进程被激活
并得到消息。
44
3.6.6 用消息传递实现互斥
使用消息传递所支持的互斥和信号量不具
备传递数据的能力可以解决带有界缓冲区
的生产者 /消费者问题。
这个方法非常灵活，可以允许有多个生产
者和消费者，系统还可以是分布式的。
45
3.7 读者 /写者问题
Readers/writers问题的定义如下：一些进
程共享一个数据区。数据区可以是一个
文件、一块内存空间或一组寄存器。
readers进程只能读数据区中的数据，而
writers进程只能写。所谓读者 /写者问题
就是指保证一个 writer进程必须与其他进
程互斥地访问共享对象的同步问题。
46
3.7 读者 /写者问题
解决该问题必须满足的条件如下：
? 任意多个 readers可以同时读；
? 任一时刻只能有一个 writers可以写；
? 如果 writers正在写，那么 readers就不能读。
47
3.7.1 读者优先
信号量 wsem用来实现互斥，只要有 writer在访问
共享数据区，其他 writers或 readers就不能访问数
据区。 reader进程同样利用 wsem实现互斥。为了
适用于多个 reader，当没有 reader读时，第一个进
行读的 reader要测试 wsem，当已经有 reader在读
时，随后的 reader无须等待就可读取数据区。
一旦有一个 reader访问数据区，只要还有一个
reader在进行读操作,reader就可以保持对数据区
的控制，这就容易导致 writers饥饿。
48
3.7.2 写者优先
解决了读者优先中的饥饿问题。
? 只要有 writer申请写操作，就不允许新的 readers
访问数据区。
? 另一种解决方法是使用消息传递，有一个可访
问共享数据区的控制进程，其他欲访问数据区
的进程向控制进程发请求消息，收到,OK”应
答消息后就可访问，在访问完成后发出
,finished”消息，控制进程拥有 3个信箱，每个
信箱装一种类型的消息。
49
The end
Thanks!
第 3章 并发控制 —— 互斥与同步
本章知识点：
? 3.1 并发原理
? 3.2 互斥 —— 软件解决方法
? 3.3 互斥 —— 硬件解决方法
? 3.4 信号量
? 3.5 管程
? 3.6 *消息传递
? 3.7 *读者 /写者问题
? 3.8 系统举例（略）
2
3.1 并发原理
在单处理机多道程序的系统中，进程的
并发执行方式是插入执行，表面看起来
进程如同是同时执行的。在多处理机系
统中并发执行方式有插入执行和重叠执
行。 并发的存在要求操作系统必须能跟
踪大量活跃进程,必须为每一活跃进程分
配资源，必须保护每一进程的数据和物
理资源不被其他进程侵犯，并且进程执
行的结果与其他并发进程执行时的相对
速度无关。
3
3.1.1 进程间的相互作用
进程之间常常相互作用，存在某种彼此
依赖或相互制约的关系, 同步和互斥关系。
根据进程意识到其他进程的存在程度不同,
可将进程间的相互作用划分为,进程互不
觉察, 进程间接觉察, 进程直接觉察 。
4
3.1.2 进程间的相互竞争
并发进程在竞争使用同一资源时将产生冲突。
进程间的竞争面临 3个控制问题：
? 互斥
? 死锁
? 饥饿
竞争的控制不可避免地涉及到操作系统，因为
是操作系统分配资源，另外，进程自身也必须
能以某种方式表达互斥的要求 。
5
3.1.2 进程间的相互竞争
? 临界资源,
? 在同一时刻只允许一个进程访问的资源
称为临界资源。
? 临界区 (段 ):访问临界资源的那一部分程
序称为临界区（段）。
6
3.1.3 进程间的相互合作
1.通过共享合作
这些进程并不是通过名字察觉到对方,
而是通过共享访问间接察觉 。 进程间通
过共享方式进行合作 。 除互斥, 死锁和
饥饿外, 保证数据的一致性也是一个潜
在的控制问题 。
7
3.1.3 进程间的相互合作
2.通过通信合作
进程通信是指进程之间可直接以较高的
效率传递较多数据的信息交换方式。这
种方式中采用的是通信机构，在进程通
信时往往以消息形式传递信息。 因为在
消息传递中不存在共享，所以这种形式
的合作不需要互斥，但是还存在死锁和
饥饿问题。
8
3.1.4 互斥的要求
并发进程的成功完成需要有定义临界段和
实现互斥的能力，这是任何并发进程方案
的基础。解决互斥问题必须满足以下要求：
? 互斥执行
? 执行非临界段的进程不能受到其他进程的
干扰
? 有限的等待
? 没有进程相对速度和数目的假设
? 进程进入到临界段中的时间有限
9
3.2 互斥 —— 软件解决方法
软件方法对并发进程不提供任何支持，
因此，无论是系统程序或应用程序，进
程都要同其他进程合作以解决互斥，它
们从程序设计语言和操作系统那里得不
到任何支持。软件方法易引起较高的进
程附和较多的错误，但有利于深刻理解
并发的复杂性。
10
3.2.1 Dekker算法
Dekker算法的优点在于它描述了并发进
程发展过程中遇到的大部分共同问题。
任何互斥都必须依赖于一些硬件上的基
本约束，其中最基本的约束是任一时刻
只能有一个进程访问内存中某一位置。
11
3.2.1 Dekker算法
1.第 1种途径
这种方法保证了互斥，但它只记住了允许哪个进
程进入其临界段，未记住每个进程的状态。
var turn,0..1; {turn为共享的全局变量 }
PROCESS 0 PROCESS 1
… …
while turn≠0 do {nothing}; while turn≠1 do {nothing}； 〈 critical
section〉 ; 〈 critical section〉 ;
turn,=1; turn,=0;
… …
12
3.2.1 Dekker算法
2.第 2种途径
这种解决方法依赖于进程执行的相对速度
共享的全局变量是,var flag,array[0..1]of boolean;
它被初始化为 false
PROCESS 0 PROCESS 1
… …
while flag[1]do {nothing}; while flag[0]do {nothing};
flag[0],=true; flag[1],=true;
〈 critical section〉 ; 〈 critical section〉 ;
flag[0],=false; flag[1],=false;
… …
13
3.2.1 Dekker算法
3.第 3种途径
这种方法保证了互斥但会导致死锁问题。
PROCESS 0 PROCESS 1
… …
flag[0],=true; flag[1],=true;
while flag[1] do {nothing}; while flag[0] do {nothing};
〈 critical section〉 ; 〈 critical section〉 ;
flag[0],=false; flag[1],=false;
… …
14
3.2.1 Dekker算法
4.第 4种途径
PROCESS 0 PROCESS 1
… …
flag[0],=true; flag[1],=true;
while flag[1] do {nothing}; while flag[0] do {nothing};
begin begin
flag[0],=false; flag[1],=false;
〈 delay for a short time〉 ; 〈 delay for a short time〉 ;
flag[0],=true; flag[1],=true;
end; end;
〈 critical section〉 ; 〈 critical section〉 ;
flag[0],=false； flag[1],=false;
… …
15
3.2.1 Dekker算法
5.一个正确的解决方法
设计一个“指示”小屋，小屋内的黑板标明
,turn”，当 P0想进入其临界段时，置自己的 flag
为,true”，这时它去查看 P1的 flag，如果是
,false”，则 P0就立即进入自己的临界段，反之 P0
去查看“指示”小屋，如果 turn=0，那么它知道
自己应该坚持并不时去查看 P1的小屋,P1将觉察
到它应该放弃并在自己的黑板上写上,false”，
以允许 P0继续执行。 P0执行完临界段后，它将
flag置为,false”以释放临界段，并且将 turn置为 1
，将进入权交给 P1 。
16
3.2.2 Peterson算法
Dekker算法可以解决互斥问题，但是，
其复杂的程序难于理解，其正确性难于
证明。 Peterson给出了一个简单的方法。
下面是一个两进程互斥的简单解决方法，
进一步可将 Peterson算法推广到多个进程
的情况。
17
3.2.2 Peterson算法
var flag,array[0..1] of boolean; flag[1],=true;
turn,0..1; turn,=0;
procedure P0; while flag[0] and turn=0 do {nothing};
begin 〈 critical section〉 ;
repeat flag[1],=false;
flag[0],=true; 〈 remainder〉
turn,=1; forever
while flag[1] and turn=1 do {nothing}; end;
〈 critical section〉 ; begin
flag[0],=false; flag[0],=false;
〈 remainder〉 flag[1],=false;
forever turn,=1;
end; parbegin
procedure P1; P0; P1
begin parend
repeat end.
18
3.3 互斥 —— 硬件解决方法
完全利用软件方法来解决进程互斥进入
临界区的问题有一定的难度，且有很大
局限性，现在有许多计算机提供了一些
可以解决临界区问题的特殊的硬件指令。
硬件方法通过特殊的机器指令实现互斥，
可以降低开销。
19
3.3.1 禁止中断
在单处理机中，禁止进程被中断即可保证互
斥，通过操作系统内核定义的禁止和允许中
断的原语就可获得这种能力。进程执行临界
段时不能被中断。
优点：
? 在单处理机中可保证互斥。
缺点：
? 代价较高，使执行效率显著降低
? 在多处理机系统中，禁止中断不能保证互斥
20
3.3.2 使用机器指令
1.特殊的机器指令
在多处理机系统中，多个处理机共享一
个共同的主存，这里并没有主 /从关系，
也没有实现互斥的中断机制。许多系统
都提供了一些特殊的硬件指令，允许我
们在一个存储周期内去测试和修改一个字的内容（ Test and Set指令），或者交
换两个字的内容（ Exchange指令）等等。
这些特殊指令可以用来解决临界段问题。
21
3.3.2 使用机器指令
2.机器指令方法的特性
优点：
? 可用于含有任意数量进程的单处理机或共享主存的多处
理机；
? 比较简单, 易于验证；
? 可支持多个临界段, 每个临界段用各自的变量加以定义 。
缺点：
? 采用 busy-waiting技术, 进程等待进入临界段时耗费处
理机时间；
? 可能产生饥饿；
? 可能产生死锁 。
22
3.4 信号量
信号量是一个整型变量，除对其初始化外，它
可由两个不可中断的 P,V操作存取。 不论是采
用一般信号量还是二元信号量，进程都将排队
等候信号量，但这并不意味着进程移出的顺序
与队列次序相同。
基本原则：两个或多个进程可通过单一的信号
量展开合作，即进程在某一特定的地方停止执
行，直到某个特定的信号量到来为止。通过信
号量，任何复杂的合作要求都可被满足 。
23
3.4 信号量
? P 操作
Wait(s):
s.count:=s.count-1
If s.count<0
Then begin
将该进程置入 s.queue,阻塞该进程
End ;
? V操作
s.count:=s.count+1
If s.count<=0
Then begin
将进程 从 s.queue 中移出，置入就绪队列
End ;
24
3.4.1 用信号量解决互斥问题
信号量的互斥算法可以用小屋模型来描述。除
了黑板外，小屋中还有一个大冰箱。某进程进
入小屋后执行 wait操作将黑板上的数减 1，这时，
如果黑板上的值非负，它就进入临界段，反之
它就进入冰箱内冬眠。这时，就允许另一进程
进入小屋。当一个进程完成其临界段后，它进
入小屋执行 signal，将黑板上的值加 1，这时如
果黑板上的值为非正数，它就从冰箱中唤醒一
个进程。
25
3.4.2 用信号量解决生产者 /消费者
问题
问题描述如下：一个或更多的生产者生
产出某种类型的数据 (记录、字符 )，并把
它们送入缓冲区，惟一的一个消费者一
次从缓冲区中取走一个数据，系统要保
证缓冲区操作不发生重叠，即在任一时
刻只能有一方 (生产者或消费者 )访问缓冲
区。
26
3.4.2 用信号量解决生产者 /消费者
问题
用二元信号量来解决此问题。在任何时候生
产者 (P)都可向缓冲区中添加数据，在添加数据前，
P执行 waitB(s)，然后执行 signalB(s)以防止在添加过
程中，别的消费者 (C)或 P访问缓冲区。在进入到临
界段时,P将增加 n的值，如果 n=1则在此次添加数
据前缓冲区为空，于是 P执行 signalB(delay)并将这
个情况通知 C。 C最初执行 waitB(delay)来等待 P生产
出第一个数据，然后取走数据并在临界段中减小 n
的值。如果 P总保持在 C前面，那么 C就不会因为信
号量 delay而阻塞，因为 n总是正数，这样 P和 C都能
顺利地工作。这个方法也存在缺陷有可能导致死锁。
27
3.4.2 用信号量解决生产者 /消费者
问题
解决这个问题的一个方法是引入一个附
加变量，它在消费者的临界段中设置。
这样，就不会出现死锁了。
使用一般信号量可以得到另一种解决方
法，变量 n是一个信号量，它的值等于缓
冲区中的数据项数。
28
3.4.3 信号量的实现
wait和 signal操作都必须作为原子操作实现。显
然，用硬件方法或固件方法都可解决这一问题，
而且还有其他解决方法。尽管 wait和 signal操作
执行的时间较短，但因包含了忙 --等，故忙 --等
占用的时间是主要的 。
对单处理机系统而言，可以在 wait和 signal操作
期间屏蔽中断, 而且这些操作的执行时间相对
较短。
29
3.4.4 用信号量解决理发店问题
理发店问题是使用信号量实现并发的另一个例
子，它同操作系统中的实际问题非常相似。如
图示 理发椅
沙发
收款台
出
口
入
口
顾客休息区
30
3.5 管程
信号量为实现互斥和进程间的协调提
供了一个功能强大而灵活的工具，然
而，使用信号量来编制正确的程序是
困难的。
作为程序设计语言中的一种结构，管
程 (Monitor)提供了与信号量相同的表
达能力，但它更容易控制。
31
3.5.1 带信号量的管程
管程是一种并发性的结构，它包括用于
分配一个特定的共享资源或一组共享资
源的数据和过程。管程由三部分组成：
? 局部于管程的共享变量说明。
? 对该数据结构进行操作的一组过程。
? 对局部于管程的数据设置初始值的语句。
此外，还需为该管程赋予一个名字。
32
3.5.1 带信号量的管程
管程最主要的特点如下：
? 只能通过管程中的过程而不能用其他外
部过程访问其局部数据变量。
? 进程通过调用管程的过程而进入管程。
? 每一时刻只能有一个进程在管程中执行，
任何其他调用管程的进程将被挂起直至
管程可用为止。
33
3.5.2 用管程解决生产者 /消费者
问题
管程模块控制着缓冲区。管程包括两个
条件变量：当缓冲区中还有空位置时，
变量 notfull为 true，如果缓冲区中至少有
一个字符存在，则变量 notempty为 true。
生产者只能通过管程中的过程 append向
缓冲区添加字符，生产者不能直接访问
缓冲区。这个例子比较了管程和信号量。
34
3.6 消息传递
进程间的相互作用必须满足两个条件：同
步和通信，进程需要同步来实现互斥，进
程间的协同需要交换信息，一个能解决上
述两个问题的方法是消息传递 (message
passing)。消息传递还有一个优点是，它
的适应性很强，能在分布式系统、共享存
储器的多处理机系统以及单处理机系统等
不同系统中实现。
35
3.6.1 消息传递原语
原语：
? ·send (destination,message)
? ·receive (source,message)
36
3.6.2 用消息传递实现同步
无论是发送方还是接收方都可能被阻塞。
下面有三种最一般的组合，任何特定系统
都实现了其中的一种或两种：
? 阻塞发送，阻塞接收。
? 无阻塞发送，阻塞接收。
? 无阻塞发送，无阻塞接收。
37
3.6.3 寻址方式
1,直接寻址
对直接寻址方式,send原语中明确标明
了目的进程。 receive原语有两种方式：
第一种方式接收进程预先知道发送消息
的源进程，另一种方式则不可能预先知
道源进程。
38
3.6.3 寻址方式
2,间接寻址
消息不直接由发送方传给接收方，而是
通过一个共享的数据结构，包括临时存
放消息的队列（邮箱式端口）。这种方
法有很大的灵活性。进程与邮箱的关系
可以是静态的或动态的，端口通常与一
个特定的进程相关联。端口通常由接收
进程产生并为其所有。
39
3.6.4 消息格式
消息格式依赖于消息系统的用途和消息
系统是在单个计算机上运行还是在分布
式系统中运行，一些操作系统选择了较
短的定长消息以减小处理和存储的开销，
如果有大量的数据需要传递，那么可以
将数据存入文件并把文件作为消息传递，一种更为灵活的方法是允许变长消息。
40
3.6.4 消息格式
支持变长消息的操作系统中的消息格式
消 息 源
目 的 地
消息长度
控制信息
消息类型
消
息
头
消
息
体
消息的内容
41
3.6.5 排队规则
最简单的排队规则是先进先出，但这远
远不够。一个改进的方法是由发送方或
接收方基于消息的类型标明消息的优先
权；另一个改进方法是允许接收方检查
消息队列并选择要接收的消息。
42
3.6.6 用消息传递实现互斥
假设使用阻塞 receive原语和无阻塞 send原
语，并发进程集共享一个邮箱 mutex，将
邮箱初始化为仅包含一个空消息，欲进
入临界段的进程首先要接收相应的消息，
如果邮箱为空则该进程被阻塞，一旦进
程得到消息它就执行其临界段，然后再
将消息放回邮箱，这样消息就如同令牌
一样在进程之间传递。
43
3.6.6 用消息传递实现互斥
这种解决方法是，假设有多于一个进程并
发执行 receive操作，则有：
? ·如果仅有一个消息，那么它只可传递给一
个进程，其他进程将被阻塞。
? ·如果邮箱为空，则所有的进程将被阻塞。
当消息可用时，仅有一个阻塞进程被激活
并得到消息。
44
3.6.6 用消息传递实现互斥
使用消息传递所支持的互斥和信号量不具
备传递数据的能力可以解决带有界缓冲区
的生产者 /消费者问题。
这个方法非常灵活，可以允许有多个生产
者和消费者，系统还可以是分布式的。
45
3.7 读者 /写者问题
Readers/writers问题的定义如下：一些进
程共享一个数据区。数据区可以是一个
文件、一块内存空间或一组寄存器。
readers进程只能读数据区中的数据，而
writers进程只能写。所谓读者 /写者问题
就是指保证一个 writer进程必须与其他进
程互斥地访问共享对象的同步问题。
46
3.7 读者 /写者问题
解决该问题必须满足的条件如下：
? 任意多个 readers可以同时读；
? 任一时刻只能有一个 writers可以写；
? 如果 writers正在写，那么 readers就不能读。
47
3.7.1 读者优先
信号量 wsem用来实现互斥，只要有 writer在访问
共享数据区，其他 writers或 readers就不能访问数
据区。 reader进程同样利用 wsem实现互斥。为了
适用于多个 reader，当没有 reader读时，第一个进
行读的 reader要测试 wsem，当已经有 reader在读
时，随后的 reader无须等待就可读取数据区。
一旦有一个 reader访问数据区，只要还有一个
reader在进行读操作,reader就可以保持对数据区
的控制，这就容易导致 writers饥饿。
48
3.7.2 写者优先
解决了读者优先中的饥饿问题。
? 只要有 writer申请写操作，就不允许新的 readers
访问数据区。
? 另一种解决方法是使用消息传递，有一个可访
问共享数据区的控制进程，其他欲访问数据区
的进程向控制进程发请求消息，收到,OK”应
答消息后就可访问，在访问完成后发出
,finished”消息，控制进程拥有 3个信箱，每个
信箱装一种类型的消息。
49
The end
Thanks!
