3.1.1 临界区与临界资源
为更好地管理计算机系统的资源，引入了临界资源和临界区的概念。
一、临界资源
·任意时刻最多只允许一个进程使用的资源称为临界资源。
·如：打印机、键盘等。
二、临界区
·访问临界资源的程序（程序段），即不允许并发进程交叉执行的程序（程序段），称为临界区。
·如：写打印机缓冲区的程序，读键盘缓冲区的程序等。
现实生活中的临界资源很多。例如，一张小方凳，任意时刻最多仅能一个人坐在上面。这种情况下，小方凳就是临界资源，坐该小方凳的人就是临界区。又如，一台打印机，在任意时刻最多只允许打印一个文档（想想：否则会有什么结果？），该打印机就是临界资源；向该打印机缓冲区写入数据的程序就是临界区。
三、临界资源使用
假设进程 A 与进程 B 都需要访问相同的一台打印机。进程 A 与进程 B 怎样的执行方式才能既符合临界资源（打印机）的使用要求，又能有较高的执行效率呢？
方式一：进程 A 与进程 B 互斥地执行，即计算机系统中不允许同时执行这两个程序。这种方式的效果是：（1）满足了对临界资源的访问要求；（2）计算机系统的效率（利用率）低。原因在于：进程 A 和进程 B 的任务并不仅仅是访问打印机，它们还要完成其它功能。例如，从键盘或数据文件读数据、对数据进行计算与分析、将结果显示出来并写入到数据库等。这些任务中，有些是可以并发执行的。
方式二：进程 A 与进程 B 并发执行，但是限制它们不能同时执行相同的临界区。这种方式的效果是：（1）提高了计算机系统的效率（利用率）；（2）满足了对临界区的访问要求。例如，当进程 A 使用打印机临界区时，进程 B 可以使用键盘临界区；当进程 A 使用键盘临界区时，进程 B 可以使用打印机临界区。
由此，我们可以允许多个进程并发执行，只要能够控制好临界区的访问就能提高计算机系统的效率。
四、进程执行的约定
1．各并发进程享有平等的、独立的竞争和使用共享资源的权利。
２．并发执行的进程如果不在临界区，它不阻止其它进程进入临界区。
３．并发执行的进程都可以申请进入临界区时。
４．并发执行的某个进程从申请进入临界区开始，应在有限时间内进入临界区，也应在有限时间之内退出临界区
一、中断禁用
在使用硬件机制实现互斥的思路中，禁用中断是最简单直接的方法。在单处理器的机器中，并发进程轮流占用 CPU 执行，如果某个进程不被中断或执行系统调用的话，这个进程将会一直运行，因此如果需要实现互斥地访问共享资源，只需要保证一个进程不被中断就行了。
由此，可以使用启用和禁用中断的原语来实现对临界区的访问：
while (true)
{
/*进程其它代码*/
/*禁用中断*/；
临界区；
/*启用中断*/；
/*进程其它代码*/
}
以上代码保证了在临界区不会发生中断，所以可以保证进程在进入临界区后不会被打断执行，因此有效地实现了互斥。
这种方法由于禁止了中断，系统执行的效率会有明显地降低。并且该方法不能用于多处理器结构，当一个计算机系统包含多个处理器时，就有可能有一个或以上的进程同时执行，在这种情况下，禁止中断是不能保证互斥的。
二、专用机器指令
使用专用的机器指令可以实现程序对相同内存单元的互斥访问，例如 compare_and_swap 指令。该指令执行的过程中，任何其它指令访问内存将被阻止，而且这些动作在一个指令周期中完成。
int compare_and_swap(int *word, int testval, int newval)
{
int oldval;
oldval=*word;
if (oldval==testval) *word=newval;
return oldval;
}
在以上代码中，compare_and_swap 指令使用一个测试值 testval 检查一个*word。如果该内存单元的当前值是 testval，则就用 newval 取代该值，否则保持不变。该指令总是返回旧内存的值，因此，如果返回值与测试值相同，则表示该内存已经被更新。由此可见，这个原子指令由两个部分组成：比较内存单元值和测试值；如果值有差异，则产生交换。整个比较和交换功能按照原子操作执行，即它不接收中断。
以下这段代码是一个使用了 compare_and_swap 指令实现互斥的例程，变量 count 初始化为 0，只有检测到 count 为 0 的进程才能进入临界区。其它试图进入临界区的进程只能继续执行测试变量的指令来得到访问权。当一个进程离开临界区时，它把 count 重置为 0，此时下一个等待进入临界区的进程才能被允许进入临界区。
const int n=N; /*进程个数*/
int count;
void proc(int i)
{
while (true) {
while (compare_and_swap(count,0,1)==1) /*不做任何事*/;
/*临界区*/；
count=0;
}
}
void main()
{
count=0;
parbegin(P(1),P(2),…,P(n));
}
从以上的例子可以看出，使用专门的机器指令实施互斥可以很好地把修改和检查操作结合起来，因而具有明显的优点。具体地说，硬件方法具有如下的优点：
（1）适用范围广。适用于在单处理器或共享内存的多处理器上的任意数目进程。
（2） 使用简单。指令设置简单，容易验证其正确性。
（3） 可支持多个临界区。
当然机器指令也存在一些缺点，如：
（1）导致 CPU 空耗。当一个进程等待进入临界区时，会不断地持续检测，消耗处理器时间。
（2）导致饥饿进程。由于各种原因，当有多个进程都在等待进入临界区时，在某些极端情况下有可能某个进程永远无法进入临界区，发生饿死现象。
一、信号量的概念
1965 年，荷兰学者 Dijikstra 提出的信号量机制是一种有效的解决并发进程对共享资源管理的问题。
信号量机制的基本原理是：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到他接收到一个特定的信号。任何复杂的合作需求都可用适当的信号结构得到满足。
信号量是一种抽象的信号机制。例如，交通信号灯就是一种信号量：它表示当前道路是否允许通行。
信号量在操作系统中被用来表示资源的可使用状况，定义信号量 s 的结构为：
struct semaphore{
int value;
struct QUEUETYPE *queue;
}
资源的使用状况如下：
（1）s.value>0——信号量 s 对应的资源还有 s.value 个可供使用
（2）s.value =0——资源已用尽
（3）s.value <0——有|s.value|个进程等待使用资源
例如：设 s 表示系统中可使用的打印机，有
（1）s.value =1——表示还有一台打印机可供使用
（2）s.value =0——表示目前没有打印机可供使用
（3）s.value =-1——表示有一个进程等待使用打印机
二、信号量的操作
操作系统将对资源的控制转换为对信号量的操作。允许对信号量进行的操作称为 P 操作和 V 操作，分别对应于 P 原语 P(s)和 V 原语 V(s)。
1．P 操作
P 原语所执行的操作可使用下面的函数来表示：
void P(semaphore s)
{ s.value=s.value – 1;
If (s.value<0)
block(s.queue); /*将进程阻塞，并将其投入等待队列 s.queue*/
}
P 操作意味着进程请求一个资源，所以 s 的值减 1，当 s 的值为负数时，表示资源已经分配完毕，因而不能满足进程的需求，进程无法继续执行，故将会自我阻塞，放弃处理器，并插入到等待该信号量的等待队列中。
2．V 操作
V 原语所执行的操作可用下面的函数来表示：
void V(semaphore s)
{ s.value=s.value + 1;
if (s.value<=0)
wakeup(s.queue); /*唤醒被阻塞进程，将其从等待队列 s.queue 中取出，投入就绪队列*/
}
V 操作意味着进程释放一个资源，s 的值加 1，当 s 的值小于或等于 0 时，表示在该信号量的等待队列中有等待该资源的进程被阻塞，故应该将等待队列中的一个进程唤醒。
三、互斥的实现
使用信号量实现临界区的互斥访问时，将如果信号量的初始值为 1（表示仅允许一个进程访问临界区），此时的信号量转换成为互斥信号量。将 P 操作和 V 操作分别置于进入区和退出区，如定义 mutex 为互斥信号量，其初始值为 1，则应用模板为：
/* 其它操作 */
P(mutex)
临界区
V(mutex)
/* 其它操作 */
例 1：设 A，B 两站之间是单轨铁路，用 P、V 操作对通过该段铁路的列车设置安全保护。
设信号量 S 的初值为 1，AB 间列车安全运行进程：
……
P(S)
<列车在 AB 间运行>
V(S)
……
说明：
1．任一列车要经过 AB 间这段铁路，均需要执行从 P(S)到 V(S)这段程序。
2．通过 S 的值可以判断 AB 间铁路的状况：
S=1，AB 间无列车，任一列车可以驶入这段铁路。
S=0，AB 间有一列列车，其他列车不能驶入这段铁路。
S<0，AB 间有一列列车，且有|S|列列车等待驶入这段铁路。
例 2：设图书馆有某种图书 5 本供读者阅读。请编写控制图书借阅程序，保证同一时刻最多能有 5 个读者可以借到该书。
由于初始时有 5 个资源（5 本书），因此信号量 s 是初值设为 5。程序片段如下：
……
P(S)
<读者读书>
V(S)
……
请注意：
（1）P(s)用于控制读者借书。想一想：当借书的人超过 5 人时，会出现什么情况？
（2）V(s)表示还书。想一想：每执行一次 V(s)，会发生什么情况？
3.2.1 同步的概念
我们把一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程同步。
同步的进程之间需要交换一定的信息才能相互影响、互相协作，从而完成各自的功能。
例 1：计算进程 A 向缓冲区写计算结果，打印机进程 B 从缓冲区取出数据进行打印。约定：当缓冲区有空闲空间后，进程 A 才能将数据写入；当缓冲区有数据时，进程 B 才能取出数据。这样的两个进程 A 与进程 B 就是通过缓冲区关联的，通过缓冲区交换信息使两个进程完成各自的功能。
例 2：生产者 P 生产出商品后消费者 C 才能消费，消费者 C 消费商品后生成者才能进一步生产。生产者进程 P 和消费者进程 C 也需要相互协作才能完成各自的功能。
以上两列是两个进程之间的同步，多个进程间也可能需要同步。大家试试能不能举出例子来。
3.2.2 信号量实现同步
上节讲到了进程同步的概念，这节将如何通过信号量来实现进程同步。
一、进程同步的结构
1．原理
（1）为并发进程设置信号量 s,t；
（2）初始化它们的值；
（3）用 P、V 操作限定进程的执行顺序。
2．同步进程的模式
PA PB
…… ……
P(s) P(t)
<使用同步资源> <使用同步资源>
V(t) V(s)
…… ……
这里，s、t 及其初值根据具体问题确定。
二、例子
例 1：计算进程 A 向缓冲区写计算结果，打印机进程 B 从缓冲区取出数据进行打印。约定：当缓冲区有空闲空间后，进程 A 才能将数据写入；当缓冲区有数据时，进程 B 才能取出数据。进程 A、B 之间的同步关系可描述如下：
设置信号量：s=1, t=0；
进程片段：
PA
……
P(s)
计算结果写 Buf
V(t)
……
PB
……
P(t)
Buf 清空
V(s)
……
这里，Buf 为缓冲区。
分析：
（1）如果 PA 先执行，那么它可以通过操作 P(s)（想想为什么？），然后将结果写 Buf，然后执行操作 V(t)将信号量 t 的值修改为 1。接下来进程 PB 就可以顺执行完。
（2）如果 PB 先执行，那么它将由操作 P(t)阻塞：因为信号量 t 的初值为 0。根据 P 操作的对于，当前进程被阻塞。
例 2：生产者 P 生产出商品后消费者 C 才能消费，消费者 C 消费商品后生成者才能进一步生产。生产者进程 P 和消费者进程 C 也需要相互协作才能完成各自的功能。
设置信号量：s=1，t=0；
进程片段：
PP
……
P(s)
生产商品
V(t)
……
PC
……
P(t)
消费商品
V(s)
……
对这个例子的分析，大家参照例 1 自己做。
例 3：父亲不定时地向果盘中放入苹果和香蕉，儿子只取其中的苹果吃，女儿只取其中的香蕉吃。约定：（1）果盘中任何时刻最多只能放一个水果（苹果或香蕉）；（2）果盘中没有苹果（香蕉）时，才能向其中放入苹果（香蕉）；（3）果盘中有苹果（香蕉）时，才能取出苹果（香蕉）。要求：分别写出父亲进程 PF、儿子进程 PS、女儿进程 PD 使它们能够满足上述约定。
设置信号量：s=1；sa=0；sb=0；
进程片段：
PF /* 父亲进程 */
{
while(1)
{
P(s);
将水果放入盘中;
if（放入的是苹果）V(sa);
else V(sb);
}
}
PS /* 儿子进程 */
{
while(1)
{
P(sa);
从盘中取出苹果;
V(s);
吃苹果;
｝
}
PD /* 女儿进程 */
{
while(1)
{
P(sb);
从盘中取出香蕉;
V(s);
吃香蕉;
｝
｝
思考：信号量 s、sa、sb 分别的含义是什么
本节将通过两个例子来说明在进程控制中既有同步也有互斥。通过协作，进程才能顺利地进行。本小节先讲生产者/消费者问题。
1．问题描述
（1）当库房未满时，生产者生产出商品然后放入库房；
（2）当库房未空时，消费者从库房取出商品然后消费；
（3）一件商品不能既在生产又在消费
2．形式化描述
（1）有界缓冲区共 n 个单元——表示库房可以存放 n 件商品；
（2）生产者进程向缓冲区中写数据，每次写一个单元——生产者每次生产一件商品并放入库房；
（3）消费者进程读缓冲区中的数据，每次读一个单元——消费者每次从库房取一件商品并消费；
（4）缓冲区至少有一个单元有数据时，才能读——库房至少有一件商品时，才能取出消费；
（5）缓冲区至少有一个单元无数据时，才能写——库房至少有一个空位时，才能生产商品；
（6）生产者进程与消费者进程不能同时操作缓冲区——每个时刻最多只允许生产者和消费者的一方进入库房（放商品或取商品）。
3．假设：PA——生产者进程， PB——消费者进程
4．生产者与消费者的互斥
对于缓冲区来讲，由于生产者进程与消费者进程不能同时操作缓冲区，因此 PA、PB 对缓冲区的操作是互斥的。设公共信号量：mutex，初值为 1，有：
PA PB
…… ……
P（mutex） P（mutex）
生产者生产 数据 ¬ 缓冲区
缓冲区 ¬ 数据 消费者消费
V（mutex） V（mutex）
…… ……
5．生产者与消费者的同步
基于库存即缓冲区中的数据，生产者与消费者又是同步的。因此：
（1）设生产者进程与消费者进程的私有信号量：
avail——当前可用的缓冲区单元数，初值为 n
full——缓冲区中有数据的单元数，初值为 0
（2）生产者与消费者的同步为：
PA PB
…… ……
P（avail） P（full）
生产者生产 数据 ¬ 缓冲区
缓冲区 ¬ 数据 消费者消费
V（full） V（avail）
…… ……
6．生产者与消费者问题的解
综合上述互斥和同步两个方面，生产者/消费者进程问题的解为：
PA PB
…… ……
P（avail） P（full）
P（mutex） P（mutex）
生产者生产 数据 ¬ 缓冲区
缓冲区 ¬ 数据 消费者消费
V（full） V（avail）
V（mutex） V（mutex）
…… ……
7．思考题：
（1）k 个生产者之间的生产互斥吗？为什么？
（2）m 个消费者之间的消费互斥吗？为什么？
（3）如何才能使得多个生产者可以同时生产？多个消费者之间可以同时消费？
（4）可以将生产者进程与消费者进程间的私有信号量简化为一个吗？为什么？
3.3.2 死锁预防
如上节所述，当计算机系统中出现死锁时，系统的效率会下降：部分被死锁进程占据的资源将一直不能被其它进程使用，同时，死锁的多个进程也将占用部分内存空间。因此，不让系统中的进程出现死锁是操作系统设计要考虑的重要问题之一。
解决死锁的方法一般可分为预防、避免、检测与恢复。从本节开始依次讲解。
预防死锁是指在操作系统设计时防止死锁发生的条件被满足。只要造成死锁的四个必要条件中的任意一个不被满足，即可以预防死锁。
1．允许进程同时访问某些资源，使互斥条件不成立
例如，如采用 SPOOLING 技术。但是，这种方法不能解决访问那些固有不允许被同时访问的资源带来的死锁问题。
2．一次性分配全部资源，使资源的部分分配条件不成立
例如，每个进程一次申请它将使用的全部资源。分配资源时，如果进程申请的全部资源满足，就分配，否则拒绝分配。这种做法存在的问题是：
·多数情况下，一个进程在执行前不可能提出它所需要的全部资源；
·资源浪费太大；
·进程的并发性降低，系统性能降低。
3．适时释放资源，使不可剥夺条件不成立
例如，进程在申请新资源后的一段时间内，如果不能获得新资源就主动释放已经占有的资源。这种方法将降低系统的性能：进程除申请新的资源外，释放的资源也需要重新申请，系统可能出现多次分配相同资源的状况。
4．按资源类别序号申请资源，使环路条件不成立
例如，给每类资源一个类别序号，进程每次申请资源的类别序号必须比大于已占有资源的类别序号；进程释放资源时，每次释放资源的类别序号必须大于仍占有资源的类别序号。这种方法将使进程先获得一些短期内不使用的资源造成资源利用率下降，同时也增加系统开销。
一、静态预先分配所有资源
静态预先分配法又称为银行家算法：即事先静态说明而后静态分配，破坏部分分配条件。但这种方法的资源利用率低。
1．资源轨迹图
设系统有打印机一台，绘图机一台。
A 进程：I1 处申请一台打印机，I3 处释放；I2 处申请一台绘图机，I4 处释放。
B 进程：I5 处申请一台绘图机，I7 处释放；I6 处申请一台打印机，I8 处释放。
如下图为一个资源轨迹图。当进程沿 p→q→r→s 执行时，系统处于安全状态。一旦达到状态 t，系统是不安全的。
2．安全与不安全状态
安全状态：从该状态出发，系统能保证所有进程都能完成
不安全状态：从该状态出发，系统不能保证所有进程都能完成
例：假设系统共有 10 个资源，如图。其中 has 列表示相应进程已占有的资源数，max 列为计划分配给相应进程的最多资源数。
上排的五个状态为安全的，下排的四个状态中从第 2 个状态起便成为不安全的状态。
3．资源申请矩阵
例：如下图，初始资源申请矩阵(a)时，处于安全状态。进行资源分配后达到资源申请矩阵(b)时，处于安全状态。再进行资源分配后到达资源申请矩阵(c)时，处于不安全状态，因为此时 4 个进程均不能正常结束。
通过资源申请矩阵判定当前状态是否会发生死锁，可使用银行家算法。
4．银行家算法
算法：
（1）查找资源申请矩阵，是否存在申请资源数不超过剩余资源数的行。如果不存在这样的行，系统会死锁。
（2）如果存在，该进程能正常结束，标记该行为结束，将其所有资源撤消并归还。
（3）重复上述步骤，如果所有的进程都能标记为结束，那么系统安全，否则会产生死锁。
二、受控资源分配法
1969 年由 Haberman 提出，分配资源前先检查会不会发生死锁，要求各进程说明所需资源，将资源分类，按不同策略分配，又称为静态说明动态分配。
1．算法
假设每类资源仅有一个，根据进程数目和对每个资源的需求量，写出需求矩阵：B=（bij)mxn，其中 bij=(Pi,Rj)是进程 i 对资源 j 的需求量
以进程为顶点建立仅含顶点的图
当 Pi 有资源 Rj 请求时，向图中添加起点为 Pi 的有向边，边上标记为 Rj ，终点是除 Pi 外其它申请资源 Rj 的进程。检查图中是否包含回路，若是则可能出现死锁，拒绝资源 Rj 的分配，撤消具有标记 Rj 的边，并阻塞进程 Pi 。
当有进程完成时，从图中删除该进程顶点以及相关的边。
当图中的所有顶点及边被全部删除时，系统的全部进程结束，算法结束。
请大家自己完成余下部分。
3、思考题
当某些资源的数量大于 1 时，上述方法是否适用？如何改进？
3.3.4 死锁检测
死锁的预防和避免在某些时候可能花费较大的代价。另一种方法是检测到系统出现死锁时，通过采用一定的技术来恢复系统。因此，首先需要：（1）确定当前状态是否存在死锁？（2）存在死锁时包含哪些进程？
2．算法
用 L 记顶点集合。
（1）标记图中的所有顶点未作搜索；
（2）若图中存在顶点 N 的标记为未搜索，将 N 作为起点，标记为已搜索，执行下面（3）-（7），否则转（8）；
（3）将 L 初始化为空，并清除所有的有向边标记；
（4）将当前顶点添加到 L 的尾，检测该顶点在 L 中是否出现两次。若是，L 中包含了死锁环，算法结束；
（5）从当前顶点出发，检测是否存在以它为起始顶点且未标记的有向边，若是进行（5），否则转（6）；
（6）随机选取一条未标记的有向边，标记它，并以它的终止顶点为当前顶点，返回（3）；
（7）删除 L 中的最后一个顶点。若 L 为空，表明本次搜索中所经历的顶点不会出现在死锁环中。转（1）。若 L 不为空，以 L 的最后一个顶点为当前顶点，转（3）；
（8）当前状态不会出现死锁，算法结束。
3．算法
（1）设置每个进程的状态为未标记。
（2）寻找未标记且满足下述条件的进程 Pi。
C(i,j)+R(i,j) ≤Aj 1≤j ≤m
（3）若 Pi 不存在，转（4），否则修该 A 为：
Aj= Aj+ R(i,j) 1≤j ≤m
并标记 Pi。转（2）。
（4）若所有的进程都被标记，那么当前的状态不会造成死锁，否则当前饥饿状态将造成死锁。算法结束。
请大家根据算法判定当前状态是否会造成死锁？如果不会，请给出一种资源分配的方法。
对于已经检测的一组死锁进程，可以采取以下的策略进行恢复。每种策略都有相应的要求并存在一些问题或困难，这些都需要根据系统的总体目标进行平衡。没有哪一种策略是最优的。
一、剥夺法恢复
策略：将某些资源从其它进程抢占过来分配给另一些进程。
抢占的要求：强占不影响原进程恢复后的执行。
存在的问题：与资源的属性有关，难实现。
二、回退法恢复
策略：系统执行过程中设置若干断点并保存现场，采用回滚方式释放资源以解除死锁。
断点的要求：保护的现场不能频繁覆盖
存在的问题：断点的设置时机与多大的空间开销
三、杀死进程
策略：从系统中撤消（杀死）某些进程，释放资源以解除死锁。
杀死的要求：保证系统的数据等的一致性
存在的问题：难于判断是否能保证一致性
思考题
谁实施死锁的恢复？是死锁进程自己吗？为什么？
3.4.1 生产者/消费者问题
本节将通过两个例子来说明在进程控制中既有同步也有互斥。通过协作，进程才能顺利地进行。本小节先讲生产者/消费者问题。
1．问题描述
（1）当库房未满时，生产者生产出商品然后放入库房；
（2）当库房未空时，消费者从库房取出商品然后消费；
（3）一件商品不能既在生产又在消费
2．形式化描述
（1）有界缓冲区共 n 个单元——表示库房可以存放 n 件商品；
（2）生产者进程向缓冲区中写数据，每次写一个单元——生产者每次生产一件商品并放入库房；
（3）消费者进程读缓冲区中的数据，每次读一个单元——消费者每次从库房取一件商品并消费；
（4）缓冲区至少有一个单元有数据时，才能读——库房至少有一件商品时，才能取出消费；
（5）缓冲区至少有一个单元无数据时，才能写——库房至少有一个空位时，才能生产商品；
（6）生产者进程与消费者进程不能同时操作缓冲区——每个时刻最多只允许生产者和消费者的一方进入库房（放商品或取商品）。
3．假设：PA——生产者进程， PB——消费者进程
4．生产者与消费者的互斥
对于缓冲区来讲，由于生产者进程与消费者进程不能同时操作缓冲区，因此 PA、PB 对缓冲区的操作是互斥的。设公共信号量：mutex，初值为 1，有：
PA PB
…… ……
P（mutex） P（mutex）
生产者生产 数据 ¬ 缓冲区
缓冲区 ¬ 数据 消费者消费
V（mutex） V（mutex）
…… ……
5．生产者与消费者的同步
基于库存即缓冲区中的数据，生产者与消费者又是同步的。因此：
（1）设生产者进程与消费者进程的私有信号量：
avail——当前可用的缓冲区单元数，初值为 n
full——缓冲区中有数据的单元数，初值为 0
（2）生产者与消费者的同步为：
PA PB
…… ……
P（avail） P（full）
生产者生产 数据 ¬ 缓冲区
缓冲区 ¬ 数据 消费者消费
V（full） V（avail）
…… ……
6．生产者与消费者问题的解
综合上述互斥和同步两个方面，生产者/消费者进程问题的解为：
PA PB
…… ……
P（avail） P（full）
P（mutex） P（mutex）
生产者生产 数据 ¬ 缓冲区
缓冲区 ¬ 数据 消费者消费
V（full） V（avail）
V（mutex） V（mutex）
…… ……
7．思考题：
（1）k 个生产者之间的生产互斥吗？为什么？
（2）m 个消费者之间的消费互斥吗？为什么？
（3）如何才能使得多个生产者可以同时生产？多个消费者之间可以同时消费？
（4）可以将生产者进程与消费者进程间的私有信号量简化为一个吗？为什么？
3.4.2 读者-写者问题
本小节讨论另外一个经典的同步互斥问题：读者/写者问题。
1．问题描述
有一个文件，多个读者读这个文件和写者（作者）写（写作和修改统称为写）这个文件约定如下：
（1）多个读者可以同时读这个文件；
（2）一次只允许一个写者写这个文件；
（3）如果写者正在写这个文件时，禁止任何读者读这个文件；
（4）当有读者在读文件时不允许任何写者写文件。
2．形式化描述
有一个被许多进程共享的数据区称为文件。有一些只读取这个数据区的进程称为读进程和只往数据区中写数据的进程称为写进程。读进程和写进程对文件的操作满足要求：
（1）多个读进程可以同时读这个文件；
（2）一次只允许一个写进程写这个文件；
（3）如果一个写进程正在写文件，就禁止任何读进程和其它写进程访问该文件；
（4）当有读进程读文件时，禁止任何写进程写文件。
3．假设：PA——写进程， PB——读进程
4．读者优先
除了上述有关读、写进程的 4 个要求外，还规定读者优先：当有读进程在读文件时，对随后到达的读进程和写进程，要首先满足读进程，阻塞写进程。该要求即是：只要有一个读进程在读，那么随后而来的读进程都将被允许读文件，从而导致写进程长时间等待。
定义信号量：r_w=1; m_r=1;
整型量（计数器）：r_c=0;
PA：
……
While (1!=0) {
P(r_w);
写文件;
V(r_w);
}
……
PB：
……
While (1!=0) {
P(m_r);
If (r_c==0) P(r_w);
r_c++;
V(m_r);
读文件；
P(m_r);
r_c–;
If (r_c==0) V(r_w);
V(m_r);
}
……
5．写者优先
除了上述有关读、写进程的 4 个要求外，还增加写进程优先的规定，即当有读进程和写进程同时等待时，首先满足写进程。当一个写进程声明想写文件时，不允许新的读进程再访问文件。
定义信号量：r_w=1; r_wait=1; f_wait=1; m_r=1; m_w=1;
整型量（计数器）：r_c=0; w_c=0;
PA:
……
While (1!=0) {
P(m_w);
if (w_c==0) P(f_wait);
w_c++;
V(m_w);
P(r_w);
写文件;
V(r_w);
P(m_w);
w_c–;
if (w_c==0) V(f _wait);
V(m_w);
}
PB：
……
While (1!=0) {
P(r_wait);
P(f _wait);
P(m_r);
If (r_c==0) P(r_w);
r_c++;
V(m_r);
V(r_wait);
V(f _wait);
读文件;
P(m_r);
r_c–;
if (r_c==0) V(r_w);
V(m_r);
}
……
6．无优先
除了上述有关读、写进程的 4 个要求外，不再规定读写的优先权，谁先等待谁就先使用文件。
定义信号量：r_w=1; w=1; m_r=1;
整型量（计数器）：r_c=0;
PA:
……
While (1!=0) {
P(w);
P(r_w);
写文件;
V(r_w);
V(w);
}
PB：
……
While (1!=0) {
P(w);
P(m_r);
If (r_c==0) P(r_w);
r_c++;
V(m_r);
V(w);
读文件;
P(m_r);
r_c–;
if (r_c==0) V(r_w);
V(m_r);
}
7．思考题：
（1）上述描述进程 PA、PB 的描述中，哪个进程可能出现饥饿？
（2）上述描述进程 PA、PB 的描述中，尝试调整 P、V 操作的顺序，分析可能出现问题吗？是什么问题？
本章学习了通过对信号量的 P、V 操作实现进程互斥与同步控制的基本原理和方法。介绍了临界资源和临界区的概念、进程互斥与同步的概念。讨论了信号量的意义，以及对信号量操作的 P、V 原语。介绍了通过 P、V 操作对临界区实现互斥的原理与方法，通过 P、V 操作实现进程同步的原理与方法。对 P、V 操作可能出现的死锁和饥饿现象进行了介绍，讨论死锁预防、避免、检测与恢复的机制和方法。
