五、经典同步问题
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 。当然王道的逻辑肯定更加严谨，我也不保证我的理解对，纯粹突发奇想。
