下面介绍两个经典的同步互斥的例子。这两个例子及其解法都是很著名的，深人地分析 和透彻地理解这些例子，对于全面解决操作系统内的同步、互斥问题将有很大启发。

Dijksta 把同步问题抽象成一种“生产者和消费者关系”。生产者——消费者问题是计算机中各种实际的同步、互斥问题的一个抽象模型。计算机系统中的许多问题都可被归结为 生产者和消费者关系，例如，生产者是计算进程，消费者是打印进程；在输人时输入进程是 生产者，计算进程是消费者。

一、简单生产者——消费者问题

有关简单生产者——消费者问题的描述是这样的：设有一个生产者进程P，一个消费者进程Q，它们通过一个缓冲区联系起来。缓冲区只能容纳一个产品，生产者 不断地生产产品，然后往空缓冲区送产品; 而消费者则不断地从缓冲区中取出产品，并消费掉。

现在我们对生产者——消费者问题中的同 步互斥关系进行分析，并设置相应的信号量。显然，P进程不能往已经“满”的缓冲区中放 人产品，设置信号量empty,其初值为1，用于指示空缓冲区数量；同样，Q进程也不能从已经 full,初值为0,用于指示满缓冲区数量。

生产者——消费者同步问题的解决方案如下：

P:

while(true){

P(empty);

生成一个产品；

送产品到缓冲区；

V(full);

};

Q:

while(true){

p(full);

从缓冲区取产品；

V(empty);

消费产品；

}；

在这个方案中，产品生成出来之后立即往缓冲区中存放产品，因为刚开始时缓存区是空的，一定可以存放一个产品。

二、多个生产者——消费者问题

我们可以把上面介绍的简单生产者——消费者问题推广为多个生产者和多个消费者问题。

下面是有关多个生产者和多个消费者问题的描述：设有若干个生产者进程P1，P2，…， Pn，若干个消费者进程Q1, Q2，…，Qm，它们通过一个环形缓冲池联系起来，如图4-3所示。该环形缓冲池由&个大小相等的缓冲区组成，每个缓冲区能容纳一个产品，生产者每次 往空缓冲区送一个产品；消费者每次从满缓冲区取生产方向 出一个产品。生产者进程不断地生产产品并把它们 放人缓冲池内，消费者进程不断地从缓冲池内取产品并消费之。这里既存在同步问题，也存在互斥问题。

当整个缓冲池全满时，出现了供大于求的现 象。此时生产者必须暂缓生产，而消费者应该大力消费。当整个缓冲池全空时，出现了供不应求的现 象。此时消费者必须等待，而生产者必须努力生产。很明显，在上述生产者和消费者之间存在一定的合作关系。

在生产者向空的缓冲区里放入产品之后，或者消费者从满的缓冲区里取出产品之后，有关的缓冲区就改变了它的状态。

另外，环形缓冲池是临界资源，因为生产者和消费者都要使用它。在某个缓冲区为空 时，消费者不能从这个空的缓冲区里取出产品；同样，在某个缓冲区为满时，生产者不能向 这个满的缓冲区里放人产品。可见在生产者和消费者之间还存在着互斥关系。

(1)同步问题

生产者进程不能往“满”的缓冲区中放产品，设置信号量empty，初值为k，用于指示 缓冲池中空缓冲区数目。

消费者进程不能从“空”的缓冲区中取产品，设置信号量full,初值为0,用于指示缓 冲池中满缓冲区数目。

(2)互斥问题

设置信号量mutex，初值为1，用于实现临界区（环形缓冲池）的互斥。

另设整型量i和j，初值均为0。i用于指示空缓冲区的头指针；j用于指示有产品的满缓 冲区的头指针。

(3)算法

该同步互斥问题的解决方案如下：

// 生产者进程P1,P2,…,Pn:

i = 0；

while(true){

生产产品；

P(empty)；

P(mutex);

往Buffer[i]中存放产品；

i=(i+1) mod k;

V(mutex);

V(full);

}；

// 消费者进程Q1,Q2,...Qn:

j = 0;

while(true){

P(full);

P(mutex);

从Buffer[j]取产品；

j = (j+1) mod k;

V(mutex);

V(empty);

消费产品；

}；

读者可以自己分析该程序的执行过程。

三、读者--写者问题

在计算机系统中，一个数据对象（例如一个文件或记录）是可以供若干进程共享的。

(1)读者——写者问题的描述

假定有某个共享文件F，系统允许若干进程对文件F进行读或写。这里把要读文件的进程称为读者，把要写文件的进程称为写者。读者和写者必须遵守如下的规定。

(1)多个进程可以同时读文件F。

(2)任一个进程在对文件F进行写时，不允许其他进程对文件进行读或写。

(3)当有进程正在读文件时不允许任何进程去写文件。

当有多个读者和写者都要读写文件F时，按规定每次只允许一个进程执行写操作，且在有进程执行写时不允许进程读文件。显然，写者与写者之间要互斥，写者与读者之间也要互斥，但按规定多个读者可同时读文件，也就是说只要第一个读者取得了读文件的权利，则其他读者可以跟着读文件。所以，写者与读者之间的互斥就变成了写者与第一个读者之间的 互斥。

设read _ count记录当前正在读的读者进程个数，由于多个读者都对read _ count进行修 改，所以read_count是一个共享变量，需要互斥使用，故设置信号量mutex。再设置信号量 write，用于写者之间互斥，或第一个读者和最后一个读者与写者的互斥。

(2)读者——写者问题的解决方案

下面给出读者——写者问题的解决方案。

// 读者进程：

while(true){

P(mutex);

read_count = read_count + 1;

if(read_count = 1) P(write);

V(mutex);

读文件；

P(mutex);

read_count = read_count -1;

if(read_count = 0) V(write);

V(mutex);

}

// 写者进程：

while(true){

P(write);

写文件；

V(write);

}

这里对上面的解决方案做一些具体的说明:

read _ count是一个计数器，初值为0。而mutex和write都是信号量，它们的初值都 是1。

read _ count是一个共享变量，需要互斥使用，在每个读者进人时，对read _ count的计数不能出错。另外，如果第一个读者进人，就不能再允许写者进入，这就是if (read_Cmmt =1) P (write)语句的作用；第一个读者负责禁止任何写者进入。以上这两个操作都要放 在互斥区内。

而其他的读者可以随着第一个读者进人陆续进入。

当有读者完成读操作之后，相应地要对read _ count进行减一操作。而且如果read _ count =0,表明已经没有读者了，写者可以随时进人。

对于读者来说，只要有一个写者已经在临界区执行写操作，所有的读者就必须等待。

四、同步与互斥机制的综合应用

这里举一些运用经典的进程同步问题解决方案的例子，以帮助读者更好地掌握其解法的基本思想。

[例4.1] 路口单双号交通管制。

(1)问题

某个城市为了解决市内汽车太多、交通过于拥堵的问题，决定出台一项交通管制措施， 对进入市中心区的机动车辆实行单双日限制行驶的办法。具体要求是，逢单日，只允许车辆 牌号号码为单数的机动车进人市中心区；同样，逢双日，只允许车辆牌号号码为双数的机动 车进入市内中心区。有一个进人市中心区的交通路口，进人该路口的道路有一条，离开该路 口的道路有两条，其中一条是通往市中心区的道路，而另一条是绕过市中心区的环路，在通往路口上准备设置自动识别车辆牌号的识别设备与放行栅栏控制设备。请设计有关的单双号 交通管制控制程序，该程序能够完成如下工作。

在单日，遇有单号车辆进入路口车辆号码识别区，号码识别设备则打开通往市中心区道 路的放行栅栏；遇有双号车辆，则打开绕过市中心区环路的放行栅栏。在双日，有关的控制 类似，只允许双号车辆进人市区，单号车辆则只能通行绕过市中心区的环路。显然，只有在该路口车辆号码识别区中无车时，才允许一辆车进人车辆号码识别区。同时为了防止有车辆 混过路口，两个放行栅栏平时处于关闭状态，只有在车辆号码识别区中的车辆已被识别出单 双号之后，放行栅栏才会在识别设备的控制下，打开对应的放行栅栏，在车辆通过之后，该 放行栅栏自行关闭。

(2)分析

考虑单日允许进人市中心区的情况，如图44所示。上述问题可以被抽象为生产者-消费者问题：进人交通路口 “检查车辆牌号”被 看成生产者；进人“市区放行栅栏”被看成是一 种奇数消费者；而绕行“环路放行栅栏”被看成 是另一种偶数消费者。于是当生产者的产品“检查车辆牌号”为奇数时，则交给奇数消费者；当生产者的产品“检查车辆牌号”为偶数者时，则交给偶数消费。只有在奇数消费者和偶数消费者 得知识别区中“检查车辆牌号”是奇数或偶数的 消息之后，才能启动各自的放行栅栏，在放行之 后，应给“检查车辆牌号”发一个信号，告知车辆号码识别区中又可进人一辆汽车。这样，就有 三种信号通过P、V操作处理，分别定义如下。

Check:指示可否在车辆号码识别区中进人一辆汽车，由于只能进人一辆，其初值为1。

Odd:指示汽车号码是否为奇数，其初值为0,表示不是奇数。

Even:指示汽车号码是否为偶数，其初值为0,表示不是偶数。

(3)算法

这里列出"检测车辆牌号"、"市区放行栅栏"和"环路放行栅栏" 这三个进程有关的算法的关键部分如下：

vehicle_n: integer; // 车辆号码

// 检查车辆号进程：

while(true){

车辆到达识别区路口；

P(Check);

车辆进入号码识别区；

if(vehicle_n = 奇数) V(Odd);

else V(Event);

};

// 市区放行栅栏进程：

while(true){

P(Odd);

允许车辆进入市中心区；

V(Check);

};

// 环路放行栅栏进程：

while(true){

P(Event);

允许车辆绕行环路；

V(Check);

}

[例4. 2] 物流系统中的物品分检问题

(1)问题

在某个物流系统中，有一个位于上海的集装箱中转枢纽。从不同方向进入枢纽的集装箱 运输车，在这里卸下集装箱，然后依据其来自方向的不同，这些集装箱又被装上其他运输工具继续各自的行程。根据整体的物流规划，从沿长江一线进人枢纽的集装箱，要从这里直接 吊装到上海至旧金山的定期集装箱班轮上。而从沪杭高速公路上进入枢纽的集装箱，要从这 里换装到专门在京沪高速公路上行驶的集装箱运输车上。现在需要设计为该物流系统上海集 装箱中转枢纽使用的物流软件。为简化问题起见，假设该中转枢纽的场地每次只能接收一个 方向来的同一批次的集装箱。

(2)分析

这个物流问题可以看作一个有两个生产者和两个消费者的问题。长江一线进入的集装箱 卸货是一个生产者，从沪杭髙速公路上进人的集装箱卸货是第二个生产者。

这两个生产者都要使用中转枢纽的场地。由于该场地每次只能接收一个方向来的同一批次的集装箱，所以长江一线生产者和沪杭高速公路生产者必须互斥。

去旧金山的定期集装箱班轮和去北京高速公路上的集装箱运输车，分别是两个消费者， 他们分别消费长江一线生产者和沪杭高速公路生产者提供的产品——集装箱。这样，两个生 产者在把集装箱卸到枢纽的场地之后，应该分别通知去旧金山的班轮和去北京高速公路上的 集装箱运输车。另外，在班轮和北京运输车分别装完货物之后，还应该通知中转枢纽的场 地，又可以接收新的集装箱了。可见，长江一线卸货生产者和旧金山班轮装货消费者之间要 同步，沪杭卸货生产者和北京运输车装货消费者之间也要同步。

下面对有关的信号量进行定义。

首先,定义一个是否允许进入的信号量Site,其初值为1,表示允许存放一批集装箱。其次,长江一线卸货生产者和沪杭高速公路卸货生产者需要分别向旧金山的班轮和北京运输车消费者发送消息,分别用 Arrive_Y和 Arrive_H信号量表示,它们的初值为0,表示还没有到货。

在旧金山的班轮和北京运输车消费者分别装完货物之后,可以调用V(Site),于是发送中转枢纽的场地又可以接收新集装箱了。

至于是长江生产者还是沪杭生产者能够把集装箱卸到枢纽的场地上,则通过两个生产者调用P(Site)来竞争。如上所述,安排三个信号量如下。

Site,指示能否在中转枢纽的场地上卸下集装箱。

Arrive_Y,指示场地上的集装箱是否来自长江。

Arrive_H,指示场地上的集装箱是否来自沪杭。

(3)算法

在算法中，安排"长江集装箱卸货"、"沪杭集装箱卸货"、"旧金山班轮装货"、"北京运算车装货" 四个进程，通过对三个信号量的P、V操作，实现这四个进程的并发执行。

// 长江集装箱准备卸货进程：

while(true){

长江集装箱准备卸货；

P(site);

长江集装箱卸货；

V(Arrive_Y);

};

// 沪杭集装箱卸货进程

while(true){

沪杭集装箱准备卸货；

p(Site);

沪杭集装箱卸货；

V(Arrive_H);

};

// 旧金山班轮装货进程： (旧金山班轮检查场地上的集装箱是否来自长江)

while(true){

P(Arrive_Y);

旧金山班轮装货；

V(Site);

};

// 北京运输车装货进程： (北京运输车检查场地上的集装箱是否来自沪杭)

while(true){

P(Array_H);

北京运输车装货；

V(Site);

};

(4) 说明

在算法中可以看到,进程“长江集装箱卸货”和“沪杭集装箱卸货”在卸下集装箱之前,都分别调用了P(Site)。这个调用有以下两个作用。

首先,由于Site初值为1,P(Site)起到互斥作用,无论谁先卸下了集装箱,另一个物流方向上,不能再卸货,只能等待。

其次,在集装箱已经卸下,但是还没有被装运到对应的运输工具上时,Site的值为0。在集装箱被装运到对应的运输工具上之后,Site的值为恢复为1,又可以卸下新的货物。所以P(Site)起到了测试“又可以接收新集装箱的消息”是否到达的同步作用。

再者,进程“旧金山班轮装货”和“北京运输车装货”在装完集装箱之后,都调用Ⅴ(Site),发出可以接收新集装箱的消息。

可见,在本算法中Ste信号量既作为互斥的信号量,又起着同步信号量的作用。