第五章 稍欠经典的同步问题

 

5.6 生产水（Building H2O）

这个问题至少十年来一直是加州大学伯克利分校操作系统类课程的主要内容。这似乎是基于安德鲁斯并行编程[1]中的一个练习。

有两种线程，氧气和氢气。 为了将这些线程组装成水分子，我们必须创建一个屏障(barrier)，使每个线程都等到一个完整的分子准备好后再继续。

当每个线程通过屏障时，它应该调用bond。 您必须保证来自一个分子的所有线程在下一个分子的任何线程之前调用bond。

换句话说：

•如果在没有氢线程存在时氧线程到达屏障，则必须等待两个氢线程。
•如果在没有其他线程存在时氢线程到达屏障，则必须等待氧线程和另一个氢线程。

 

我们不必考虑明确的线程匹配; 也就是说，线程不一定知道它们与哪些其他线程配对。 关键是线程以完整的集合通过屏障; 因此，如果我们检查调用bond的线程序列并将它们分成每三个一组，每组应包含一个氧线程和两个氢线程。

思考：编写氧和氢原子的同步代码，强制执行这些约束。

 

5.6.1 水的提示

以下是我在解决方案中使用的变量：

oxygen和hydrogen是计数器，由互斥锁保护。 barrier是每组三个线程在调用bond之后并允许下一组线程继续之前相遇的地方。

oxyQueue是氧线程等待的信号量; hydroQueue是氢线程等待的信号量。我正在使用队列的命名约定，因此oxyQueue.wait（）表示“加入氧气队列”，而oxyQueue.signal（）表示“从队列中释放氧气线程”。

 

5.6.1 水的方案

最初，hydroQueue和oxyQueue被锁定。 当氧线程到达时，它向hydroQueue发出两次信号，允许两个氢线程执行。 然后氧线程等待氢线程到达。

当每个氧线程进入时，它会获得互斥锁并检查记分板。 如果至少有两个氢线程在等待，它会发送信号给其中的两个氢线程和它自己，然后调用bond。 如果没有，它会释放互斥锁并等待。

绑定后，氧线程在屏障处等待，直到所有三个线程都完成绑定，然后氧线程释放互斥锁。 由于每组三个中只有一个氧线程，我们可确保只发出一次互斥信号。

氢的代码类似：

此解决方案的一个不寻常的特征是互斥体的出口点是模糊的。 在某些情况下，线程进入互斥锁，更新计数器，然后退出互斥锁。 但是当一个线程到达形成一个完整的集合时，它必须保留互斥锁以便阻止后续线程，直到当前集合调用了bond。

在调用bond之后，三个线程在屏障处等待。 当屏障打开时，我们知道所有三个线程都调用了bond，并且其中一个线程持有互斥锁。 我们不知道哪个线程拥有互斥锁，但只要其中只有一个线程释放它就没关系。 因为我们知道只有一个氧线程，所以我们让它完成这个工作。

这似乎是错误的，因为到目前为止，线程必须持有锁才能释放它。但是没有规则说必须要这样。 这是其中的一个例子，如果将互斥看作是线程获取和释放的令牌，可能会产生误导。