王道考研操作系统同步与互斥（王道大题详解）（二）

五、经典同步问题

1.生产者-消费者问题

问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

问题分析

生产者消费者互斥访问缓冲区

生产者消费者是相互协作关系（个人理解：前文所说的同步问题是单方向的，即先。。。再。。。，而这里的互相协作代表了同步是双向的，即有时要先等生产者生产后消费者才能消费，有时要等消费者消费后生产者才能生产。而这里的有时就由信号量决定。因为有两个同步关系，所以在解决同步问题时需要有两个信号量。）

信号量 m u t e x mutexmutex 作为互斥信号量，初值为一

信号量 f u l l fullfull 表示缓冲区有物品（满）的数量，初值为零，用来解决 生 产 者 → 消 费 者 生产者 \to 消费者生产者→消费者 的同步问题。信号量为零时，必须生产者先生产商品，消费者才能消费。

信号量 e m p t y emptyempty 表示缓冲区没有物品（空）的数量，初值为 n nn，用来解决 消 费 者 → 生 产 者 消费者 \to 生产者消费者→生产者 的同步问题，信号量为零时，必须消费者先消费商品，生产者才能生产

代码展示

semaphore mutex = 1;
semaphore full = 0;
semaphore empty = n;
producer()
{
    while (1)
    {
        produce an item in nextp;
        P(empty);
        P(mutex);
        add nextp to buffer;
        V(mutex);
        V(full);
    }
}
consumer()
{
    while (1)
    {
        P(full);
        P(mutex);
        remove an item from buffer;
        V(mutex);
        V(empty);
        consume the item;
    }
}

若生产者进程先 P ( m u t e x ) P(mutex)P(mutex)，然后执行 P ( e m p t y ) P(empty)P(empty)，消费者先执行 P ( m u t e x ) P(mutex)P(mutex)，然后执行 P ( f u l l ) P(full)P(full)，可不可以？

不行，假设缓冲区已满，先运行生产者进程，它先互斥加锁，然后执行 P ( e m p t y ) P(empty)P(empty) 被阻塞，这是去运行消费者进程，执行 P ( m u t e x ) P(mutex)P(mutex)，但此时锁在生产者进程，因此消费者进程也被阻塞，导致无休止的等待。

再看一个较为复杂的生产者消费者问题

问题描述

桌子上有一个盘子，每次只能向其中放入ー个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果：仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

问题分析

信号量 p l a t e plateplate 作为同步信号量，初值为一，用来解决 盘 子 变 空 事 件 → 放 水 果 事 件 盘子变空事件 \to 放水果事件盘子变空事件→放水果事件，也就是先盘子为空，才能放水果。但其实盘子为空事件可以由女儿或者儿子引起，所以进程同步不能从单一进程角度考虑，而是由系列事件的先后顺序角度出发，加以分析！

信号量 a p p l e appleapple 表示缓冲区苹果的数量，初值为零，用来解决 爸 爸 → 女 儿 爸爸 \to 女儿爸爸→女儿 的同步问题，信号量为零时，必须爸爸先放苹果，女儿才能消费

信号量 o r a n g e orangeorange 表示缓冲区橘子的数量，初值为零，用来解决 妈 妈 → 儿 子 妈妈 \to 儿子妈妈→儿子 的同步问题，信号量为零时，必须妈妈先放橘子，儿子才能消费

🚫 王道书里plate是互斥信号量，但其实完全不是这样的！按照我之前的推论和在王道代码中的实际位置和效果，也可以看出它实际上是一个同步信号量。**先盘子为空，才能放水果。**王道书中我觉得有点误人子弟了。

后来看了咸鱼学长的视频，发现他讲的是正确的，也介绍了为什么可以不写互斥。可能写书的不是他吧。还是建议2倍速把咸鱼视频过一遍再看书，效率奇高。

上图是加了互斥信号量的情况。那么为什么可以去掉？

原因在于本题缓冲区大小为1，在任何时刻，三个同步信号量最多只有一个值为一。因此在任何时刻，最多只有一个进程的 P PP 操作不会被阻塞，并顺利进入临界区。

问：那缓冲区大小为1，一定不用设置互斥信号量？

答：只是有可能不需要设置，还是要具体问题具体分析。

代码展示

semaphore plate = 1;
semaphore apple = 0;
semaphore orange = 0;
dad()
{
    while (1)
    {
        prepare an apple;
        P(plate);
        put the apple on the plate;
        V(apple);
    }
}
mom()
{
    while (1)
    {
        prepare an orange;
        P(plate);
        put the orange on the plate;
        V(orange);
    }
}
son()
{
    while (1)
    {
        P(orange);
        take an orange from the plate;
        V(plate);
        eat the orange;
    }
}
daughter()
{
    while (1)
    {
        P(apple);
        take an apple from the plate;
        V(plate);
        eat the apple;
    }
}

这里的互斥锁夹的实际上是两个进程，因为爸爸和女儿，妈妈和儿子必须连续的执行。所以个人理解（不一定对）为爸爸和女儿，妈妈和儿子这两个流程互斥

2.读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

问题分析

题意：任一写者在完成写操作之前不允许其他读者或写者工作

写者要与读者互斥，但同时也要与其他写者互斥

题意：允许多个读者可以同时对文件执行读操作

这说明仅有一个互斥信号量不能解决问题，因为一个互斥信号量只能让每次只有一个进程访问临界资源。这导致多个读者之间也互斥，不符合题意。造成这的原因是每次读者进程都会进行一次 P PP 操作，那么为了使多个读者可以同时对文件执行读操作，我只有在第一个读者进程访问时上锁，在最后一个读者进程离开时解锁。所以需要一个计数器判断当前在读文件的读者数量。

信号量设置

信号量 r w rwrw 为互斥信号量，初值为一，保证读者和写者的互斥访问

信号量 m u t e x mutexmutex 为互斥信号量，初值为一，保证计数器在更新时的互斥访问

代码展示

int count = 0;
semaphore rw = 1;
semaphore mutex = 1;
writer()
{
    while (1)
    {
        P(rw);
        writing;
        V(rw);
    }
}
reader()
{
    while (1)
    {
        P(mutex);
        if (count == 0)
        {
            P(rw);
        }
        count++;
        V(mutex);
        reading;
        P(mutex);
        count--;
        if (count == 0)
        {
            V(rw);
        }
        V(mutex);
    }
}

上面算法种，读者进程是优先的，也就是说只要有一个读者进程活跃，随后而来的读者进程都可以访问文件，而写者进程却被长时间阻塞，存在长时间饿死的情况。

代码优化

如果希望写优先，当读进程正在读文件时，有一个写进程请求，就应该阻止后续的读进程请求，等到当前访问文件的读进程们执行完毕，立刻让等待的写进程执行。在无写进程执行的情况下，才放先前排队的读进程们执行。

增加一个互斥信号量 w ww，初值为一，用于保证“写优先”

int count = 0;
semaphore rw = 1;
semaphore mutex = 1;
semaphore w = 1;
writer()
{
    while (1)
    {
        P(w);
        P(rw);
        writing;
        V(rw);
        V(w);
    }
}
reader()
{
    while (1)
    {
        P(w);
        P(mutex);
        if (count == 0)
        {
            P(rw);
        }
        count++;
        V(mutex);
        V(w);
        reading;
        P(mutex);
        count--;
        if (count == 0)
        {
            V(rw);
        }
        V(mutex);
    }
}

注意 w 信号量的位置。为什么怎么加？我们可以推一下看看

问：读 者 1 → 写 者 1 → 读 者 2

答：读者1正在读文件时，写者1来了，会被 r w  信号量阻塞，读者2来了，会被 w 信号量阻塞。在读者1读完撤离后，$ V(rw)$ 保证了写者1紧随其后运行，写者1撤离后，V ( w )保证读者2紧随其后运行

问：写 者 1 → 读 者 1 → 写 者 2

答：写者1正在写文件，读者1来了，会被 w ww 信号量阻塞，读者2来了，也会被 w 信号量阻塞。信号量的阻塞队列保证了先来先服务，所以读者1会先执行。这就导致并不是“写进程优先”，实际上是读写公平

注意：写进程优先是相对而言，实际上可以叫做读写公平法。

3.哲学家进餐问题

问题描述

一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

问题分析

每名哲学家与左右邻居对在其中间的筷子是互斥访问

问题的关键就在于如何拿到左右筷子而不造成死锁

方法一：同时拿左右两根筷子

方法二：对每个哲学家的动作制定规则，避免死锁现象的发生

信号量设置：

信号量数组 c h o p s t i c k [ 5 ] = { 1 , 1 , 1 , 1 , 1 } ，用于对五个筷子互斥访问。哲学家按顺序编号为 0 ∼ 4，哲学家 i ii 左边筷子的编号为 i ii，哲学家右边筷子的编号为 ( i + 1 ) % 5

代码展示

有问题的代码

semaphore chopstick[5] = {1, 1, 1, 1, 1};
Pi()
{
    do
    {
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5]);
        eat;
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        think;
    } while (1);
}

存在问题：5名哲学家同时想吃饭并都拿起左边的筷子。筷子都被拿完，这时他们想拿右边的筷子，就全被阻塞，产生死锁。

问：如何防止死锁的发生？

答：施加一些限制条件

方法一：最多允许四位哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右筷子的

方法二：要求奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子。这样可以保证相邻的奇偶号哲学家都想吃饭时，只会有其中一个可以拿起第一只筷子，另一个直接阻塞。这样避免了占有一只后再等待另一只的情况。

方法三：仅当一名哲学家左右两边筷子都可用时，才允许哲学家拿起筷子（王道书上原话，但其实并不准确）。准确说法为：各个哲学家拿筷子这件事是互斥的，这样就保证一个哲学家拿筷子拿到一半时被阻塞，也不会有别的哲学家继续尝试拿筷子。这样的话，当正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

采用方法三，代码如下：

semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi()
{
    do
    {
        P(mutex);
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5]);
        V(mutex);
        eat;
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5]);
        think;
    } while (1);
}

大部分练习题和真题用消费者-生产者模型或读者-写者问题就能解决，但对于哲学家进餐问题和吸烟者问题仍然要熟悉。考研复习的关键在于反复多次和全面，“偷工减料”是要吃亏的。

4.吸烟者问题

问题描述

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。

问题分析

信号量设置

信号量 o f f e r 1 表示烟草和纸组合的资源数，初值为0，用来描述 供 应 者 提 供 烟 草 和 纸 组 合 → 一 号 吸 烟 者 卷 烟 供应者提供烟草和纸组合 \to 一号吸烟者卷烟供应者提供烟草和纸组合→一号吸烟者卷烟 的同步问题

信号量 o f f e r 2 表示烟草和胶水组合的资源数，初值为0，用来描述 供 应 者 提 供 烟 草 和 胶 水 组 合 → 二 号 吸 烟 者 卷 烟 供应者提供烟草和胶水组合 \to 二号吸烟者卷烟供应者提供烟草和胶水组合→二号吸烟者卷烟 的同步问题

信号量 o f f e r 3 表示纸和胶水组合的资源数，初值为0，用来描述 供 应 者 提 供 纸 和 胶 水 组 合 → 三 号 吸 烟 者 卷 烟 供应者提供纸和胶水组合 \to 三号吸烟者卷烟供应者提供纸和胶水组合→三号吸烟者卷烟 的同步问题

信号量 f i n i s h  作为同步信号量，初值为0，用来描述 抽 掉 烟 事 件 → 放 材 料 事 件 抽掉烟事件 \to 放材料事件抽掉烟事件→放材料事件，我这里说事件，就是为了强调引起抽掉烟这一事件的主体不是一个进程，而是吸烟者1，2，3都有可能引发这一事件。

代码展示

int num = 0;
semaphore offer1 = 0;
semaphore offer2 = 0;
semaphore offer3 = 0;
semaphore finish = 0;
process P1()
{
    while (1)
    {
        num++;
        num = num % 3;
        任意两种材料放在桌上;
        if (num == 0)
        {
            V(offer1);
        }
        else if (num == 1)
        {
            V(offer2);
        }
        else
        {
            V(offer3);
        }
        P(finish);
    }
}
process P2()
{
    while (1)
    {
        P(offer1);
        卷烟抽;
        V(finish);
    }
}
process P3()
{
    while (1)
    {
        P(offer2);
        卷烟抽;
        V(finish);
    }
}
process P4()
{
    while (1)
    {
        P(offer3);
        卷烟抽;
        V(finish);
    }
}

下图是王道书中供应者的相关代码

我觉得是有问题的。我的改动地方就是“任意两种材料放在桌子上”这句话的位置。按照王道的逻辑，我 V完后被切到对应的那个吸烟者进程，那个进程就可以进行卷烟吸烟的操作。但按照逻辑来说，你材料实际上并没有放到缓冲区，这是于事实相矛盾的！

还有要强调的是这里供应者的 P V  顺序可不可以换。我认为是可以的，当然前提是改 f i n i s h 初值为1。

六、王道习题详解

大题1

题目

答案

当共享资源用共享数据结构表示时，资源管理程序可用对该数据结构进行操作的一组过程来表示，如资源的请求和释放过程request和release。。把这样一组相关的数据结构和过程一并归为管程。Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。”由定义可知，管程由三部分组成：

1)局部于管程的共享变量说明。

2)该数据结构进行操作的一组过程。

3)对局部于管程的数据设置初始值的语句；此外，还需为该管程赋予一个名字。

管程的引入是为了解决临界区分散所带来的管理和控制问题。在没有管程之前，对临界区的访问分散在各个进程之中，不易发现和纠正分散在用户程序中的不正确使用，V操作等问题。管程将这些分散在各进程中的临界区集中起来，并加以控制和管理，管程一次只允许一个进程进入管程内，从而既便于系统管理共享资源，又能保证互斥。

大题2

题目

答案

1)是互斥关系，同一本书只能被一名学生借阅，或任何时刻只能有一名学生借阅一本书。

2)是互斥关系，篮球是互斥资源，只可被一个队伍获得。

3)是同步关系，一个工序完成后开始下一个工序。

4)是同步关系，生产商品后才能消费。

大题3

题目

答案

信号量设置

互斥信号量 m u t e x ，初值为1

同步信号量 o d d，初值为0，表示奇数的个数。生产者先放一个奇数，P 2  才能取

同步信号量 e v e n，初值为0，表示偶数的个数。生产者先放一个偶数，P 3才能取

同步信号量 e m p t y ，初值为 n，表示缓冲区没有物品（空）的数量。先消费者取出东西，生产者才能再放东西

semaphore mutex = 1;
semaphore odd = 0;
semaphore even = 0;
semaphore empty = n;
P1()
{
    while (1)
    {
        x = produce();
        P(empty);
        P(mutex);
        put(x);
        V(mutex);
        if (x % 2)
        {
            V(odd);
        }
        else
        {
            V(even);
        }
    }
}
P2()
{
    while (1)
    {
        P(odd);
        P(mutex);
        getodd();
        V(mutex);
        V(empty);
        countodd();
    }
}
P3()
{
    while (1)
    {
        P(even);
        P(mutex);
        geteven();
        V(mutex);
        V(empty);
        counteven();
    }
}

大题4

题目

答案

不能，x xx 作为临界资源没有被互斥访问

直接上答案

大题5

题目

答案

这题还是挺坑的，没考虑全，因为甚至在if语句里x都有切换进程，x值改变的可能性！

z的值：− 2 , 1 , 2 , 3 , 5 , 7

c的值：9 , 25 , 81

大题6

题目

答案

对于条件二显然需要同步信号量。这个要求如何转化？假设信号量 S a

，实际上就是要把这个不等式的临界值转化成信号量 S a

 为零时的含义。题目中，A产品和B产品数量差为 M MM 时，我的信号量 S a

 应该值为零。当我的 S a

 表示什么的时候，满足条件？自然而然推出 S a

 表示A产品还可以放的产品数量（按理来说A和B的数量差应该由A和B一起控制，这里我只用A表示的原因是只有在A产品生产时才有可能会到达临界情况）。

信号量设置

互斥信号量 m u t e x，初值为1

同步信号量 S a

，初值为 M − 1  ，表示产品A还可以放的数量

同步信号量 S b  

，初值为 N − 1  ，表示产品B还可以放的数量

semaphore mutex = 1;
semaphore Sa = M - 1;
semaphore Sb = N - 1;
process_A()
{
    while (1)
    {
        P(Sa);
        P(mutex);
        A产品入库;
        V(mutex);
        V(Sb);
    }
}
process_B()
{
    while (1)
    {
        P(Sb);
        P(mutex);
        B产品入库;
        V(mutex);
        V(Sa);
    }
}

大题7

题目

答案

信号量设置

同步信号量 t a k e n u m takenumtakenum，初值为 0 00，表示已经取号的顾客数量

同步信号量 c a l l n u m callnumcallnum，初值为 0 00，表示空闲可以叫号的销售员数量

semaphore takenum = 0;
semaphore callnum = 0;
salesman()
{
    while (1)
    {      
        P(takemun);
      叫号;
      推销面包;
      V(callnum); 
    }
}
consumer()
{
    进店;
    取号;
    V(takenum);
    P(callnum);
    被服务;
}

大题8

题目

答案

信号量设置

同步信号量 e m p t y ，初值为 500，表示还可以容纳多少人

互斥信号量 m u t e x ，初值为1，可使出入口一次仅一人通过

semaphore empty = 500;
semaphore mutex = 1;
cobegin
参观者进程i:
{
    ... 
    P(empty);
    P(mutex);
    进门;
    V(mutex);
    参观;
    P(mutex);
    出门;
    V(mutex);
    V(empty);
    ...
}
coend

大题9

题目

答案

信号量设置

互斥信号量 m u t e x 1，初值为一，表示互斥访问 F 1

互斥信号量 m u t e x 2 ，初值为一，表示互斥访问 F 2

同步信号量 e m p t y 1，初值为10，表示 F 1

 空闲的容量

同步信号量 e m p t y 2 ，初值为10，表示 F 2

 空闲的容量

同步信号量 f u l l 1 ，初值为0，表示 F 1

 已用的容量

同步信号量 f u l l 2 ，初值为0，表示 F 2

 已用的容量

semaphore mutex1 = 1;
semaphore mutex2 = 1;
semaphore empty1 = 10;
semaphore empty2 = 10;
semaphore full1 = 0;
semaphore full2 = 0;
producer_A()
{
    while (1)
    {
        生产零件A;
        P(empty1);
        P(mutex1);
        放到货架F1;
        V(mutex1);
        V(full1);
    }
}
producer_B()
{
    while (1)
    {
        生产零件B;
        P(empty2);
        P(mutex2);
        放到货架F2;
        V(mutex2);
        V(full2);
    }
}
consumer()
{
    while (1)
    {
        P(full1);
        P(mutex1);
        取零件A;
        V(mutex1);
        V(empty1);
        P(full2);
        P(mutex2);
        取零件B;
        V(mutex2);
        V(empty2);
        组装产品;
    }
}

大题10

题目

答案

信号量设置

互斥信号量 v a t ，互斥访问水缸

互斥信号量 w e l l ，互斥访问水井

互斥信号量 p a i l ，初值为3，互斥的访问水桶

同步信号量 e m p t y ，初值为10，表示缸剩余可以容纳的水的桶数

同步信号量 f u l l ，初值为0，表示缸中已有的水的桶数

semaphore vat = 1;
semaphore well = 1;
semaphore pail = 3;
semaphore empty = 10;
semaphore full = 0;
old()
{
    while (1)
    {
        P(full);
        P(pail);
        P(vat);
        打水;
        V(vat);
        V(empty);
        喝水;
        V(pail);
    }
}
young()
{
    while (1)
    {
        P(empty);
        P(pail);
        P(well);
        从井里打水;
        V(well);
        P(vat);
        倒水;
        V(vat);
        V(full);
        V(pail);
    }
}

易错点

要先看水缸容量后再决定是否拿起水桶，如果顺序颠倒，会引发死锁。

大题11

题目

答案

理一下关系，数据abc依次输入，所以要保证先p1再p2最后p3的顺序。

同步信号量 S 2 ，初值为零，用来维护先p1后p2的顺序

同步信号量 S 3 ，初值为零，用来维护先p2后p3的顺序

王道答案的 S 1  其实是没有必要的，因为3个进程中后2个进程都会被阻塞，只有P1可以运行。互斥信号量也不需要，因为在同一时刻只会有一个设备正常运行未被阻塞。

p1需要p2中的数据b

同步信号量 S b SbSb，初值为零，用来维护先b被p2取出后 x = a + b x=a+bx=a+b 才能执行这一顺序

p1需要等y和z都计算出后才能通过打印机打印

同步信号量 S y ，初值为零，用来维护先y计算出后p1通过打印机打印的先后顺序

同步信号量 S z ，初值为零，用来维护先z计算出后p1通过打印机打印的先后顺序

semaphore S2 = 0;
semaphore S3 = 0;
semaphore Sb = 0;
semaphore Sy = 0;
semaphore Sz = 0;
p1()
{
    读取数据a;
    V(S2);
    P(Sb);
    x = a + b;
    P(Sy);
    P(Sz);
    打印机打印;
}
p2()
{
    P(S2);
    读取数据b;
    V(Sb);
    y = a * b;
    V(S3);
    V(Sy);
}
p3()
{
    P(S3);
    读取数据c;
    z = y + c - a;
    V(Sz);
}

发现写出来和王道答案不一样，我又推了一下，感觉自己的也没问题

我是在 y = a ∗ b 这一计算结束后才允许p3唤醒，这就保证了p3运行时y的值已有。而王道是先允许p3允许读取数据c，后等待 S y同步信号量。区别就在是否可以先读取数据c上，但题目中并未对数据c不是临界资源，所以何使读取无所谓。然后衍生一下，发现其实 S y  可以不需要，王道是让p1等待 S y 和 S z  两个信号量，但按照我的逻辑，已经保证了y和z的先后顺序，所以不需要 S y 。当然王道的逻辑肯定更加严谨，我也不保证我的理解对，纯粹突发奇想。