1.3   生产者-消费者问题

互斥并不是唯一需要关注的问题。故事的后来，Alice和Bob相爱并且结了婚。最终，他们又离了婚。（他们在想些什么？）法官将宠物的监管权判给了Alice，而让Bob负责喂养它们。现在两只小宠物相处得十分融洽，但它们只和Alice亲近，每当看到Bob就会上前攻击他。于是，Alice和Bob需要设计另外一个协议，允许Bob在他和宠物不同时在院子里的情况下给它们喂食物。更进一步，该协议还要能保证不浪费双方的时间：在院子里没有食物的情况下，Alice不会将宠物放出去；而在食物未被吃完前，Bob也不愿再次进入院子放置食物。这种问题称为生产者-消费者问题。

有趣的是，解决互斥问题时被放弃的啤酒罐-绳子协议在解决生产者-消费者问题时却非常有用。Bob在Alice的窗台上竖直摆放了一个啤酒罐，并用绳子的一端将其绑住，而把绳子的另一端牵进自己的房间。接着，他把食物放到院子里，拉动绳子将啤酒罐打翻。此后，当Alice要把宠物放入院子时，她按照以下步骤进行：

1. 等待直到啤酒罐被打翻。

2. 将宠物放出去。

3. 当宠物返回屋子以后，检查它们是否吃完了院子里的食物。如果吃完了，则重新将翻倒的啤酒罐摆正。

Bob的步骤如下：

1. 等待直到发现啤酒罐被重新摆正。

2. 将食物放到院子里。

3. 拉拽绳子，使啤酒罐再次翻倒。

啤酒罐的状态实质上反映了院子里的状态。如果啤酒罐是翻倒的，则意味着院子里有食物且宠物可以进去吃，如果啤酒罐是竖直放好的，则表示食物已经被吃完且Bob可以再放些食物。现在，考察下面三种特性：

互斥：Bob和宠物决不会同时出现在院子里。

无饥饿：如果Bob始终愿意投放食物，而两只小宠物总是很饿，那么两只小宠物将能够永远不停地吃到食物。

生产者-消费者：除非院子里有食物，否则宠物不会进入院子；除非院子里的食物已被吃完，否则Bob不会继续投放更多的食物。

此处的生产者-消费者协议以及上一节的互斥协议都能够保证Alice和Bob决不会同时出现在院子里。然而，不能使用这个生产者-消费者协议来保证Alice和Bob的互斥，理解这一点非常重要。互斥要求无死锁：任何一方就其自身而言，都能够无限次地进入院子，即使另一方不在场的情形下也是如此。与此相反，生产者-消费者协议的无饥饿特性却假设双方保持连续的协同操作。

下面对该协议进行分析：

互斥：这里采用一种与前面的互斥证明稍有区别的证明方法：基于“状态机”而不是反证法来证明。我们将系着绳子的啤酒罐视为一个状态机。啤酒罐具有两个状态：竖直和翻倒，并且在这两个状态之间反复地转换。现在需要证明，因为自动机的初始状态满足互斥特性，并且从任意一个状态向另一个状态的转换也保持着互斥特性，所以该协议满足互斥特性。

初始状态下啤酒罐只能是竖直或者翻倒的。现假设它为翻倒的，则只有宠物能够进入院子，故此时满足互斥特性。若Alice要摆正啤酒罐，宠物首先必须离开院子，因此，当啤酒罐被摆正的时候宠物不在院子里，又因为在啤酒罐再次被打翻之前宠物不会进入院子，所以自动机从翻倒状态转换为竖直状态时保持互斥特性。若要打翻啤酒罐，Bob必定已经离开了院子，并且在啤酒罐再次被摆正之前不会进入院子，因此从竖直状态转换为翻倒状态自动机也保持着互斥特性。此外，不再存在其他可能的转换过程了，因此断言成立。

无饥饿：假设此断言不成立，那么必然存在以下情形：Alice的宠物由于没有食物而一直处于饥饿状态，Bob试图投放食物但不能获得成功。此时，啤酒罐不可能是竖直的，因为这时Bob想给宠物提供食物并打翻了啤酒罐。那么，啤酒罐必定是翻倒的，又因为宠物是饥饿的，Alice最终必会摆正啤酒罐，与前述矛盾。

生产者-消费者：互斥特性意味着宠物和Bob不会同时在院子里出现。在Alice没有摆正啤酒罐之前Bob不会进入院子，而只有在院子里没有食物时Alice才会去摆正啤酒罐。同样，在Bob没有打翻啤酒罐之前宠物不会进入院子，而只有在Bob放置了食物以后他才会打翻啤酒罐。

与前面已经讲过的互斥协议一样，该协议存在着等待。若Bob在院子里放置食物后忘记了打翻啤酒罐并马上度假去了，那么此时院子里虽然有食物，但宠物却是饥饿的。

现在把注意力转回到计算机科学上来，几乎所有的并行分布式系统都会出现生产者-消费者问题。它是各个处理器向通信缓冲区中放置数据，由其他处理器读取或者通过互联网络或共享总线进行传递的方式。