第四章 经典同步问题

 

4.3 无饿死的互斥

在上一节中，我们讨论了被称之为绝对饥饿的问题，其中一类线程（读者）允许另一类别（写者）挨饿。 在更基本的层面上，我们必须解决线程饿死的问题，即一个线程可能无限期地等待而其他线程继续进行。

对于大多数并发应用程序，饿死是不可接受的，因此我们强制执行有限等待的要求，这意味着线程等待信号量（或其他任何地方，就此而言）的时间必须可证明为是有限的。

在某种程度上，饿死是调度程序的责任。 每当准备好运行多个线程时，调度程序就会决定在哪个线程上运行哪个线程。 如果一个线程从未被调度过，那么无论我们使用信号量做什么，它都会饿死。

因此，为了说明关于饿死的事情，我们必须从对调度程序的一些假设开始。 如果我们愿意做出强有力的假设，我们可以假设调度程序使用了某种算法，它可以被证明会强制执行有限的等待。 如果我们不知道调度程序使用什么算法，那么我们可以通过一个较弱的假设：

• 属性1：如果只有一个线程可以运行，则调度程序必须让它运行。

如果我们可以假设属性1，那么我们可以建立一个可证明没有饥饿的系统。 例如，如果存在有限数量的线程，那么任何包含屏障的程序都不会饿死，因为最终除了一个线程以外的所有线程都将在屏障处等待，此时剩下的那个线程肯定会运行。

但总的来说，除非我们做出更强有力的假设，否则编写没有饥饿的程序是非常重要的：

• 属性2：如果线程已准备好运行，那么它等待运行的时间是有限的。

在我们迄今为止的讨论中，我们一直隐含地假设属性2，我们将继续如此。 另一方面，您应该知道许多现有系统使用的调度程序并不严格保证此属性。

即使有了属性2，当我们引入信号量时，饿死也会再次出现。 在信号量的定义中，我们说当一个线程执行signal函数发出信号时，其中一个等待线程被唤醒。 但我们从未说过哪一个。 为了阐述关于饿死的所有内容，我们必须对信号量的行为做出假设。

可以避免饿死的最弱假设是：

• 属性3：如果线程执行signal函数发送信号时有线程在等待信号量，则必须唤醒其中一个等待线程。

这个要求可能看起来很明显，但并非微不足道。 它具有的效果是禁止某种形式的有问题行为，在其他线程等待时，这是一个发出信号量信号的线程，然后它继续运行，等待同一个信号量，并获得自己的信号！ 如果可能的话，我们就无法做出任何事情来避免饿死。

有了属性3，避免饿死就就得可能了，但即使对于像互斥体这样简单的东西，也不容易。 例如，假设三个线程运行以下代码：

while语句是一个无限循环; 换句话说，一旦线程离开临界区，它就会循环到顶部并尝试再次获取互斥锁。

想象一下，线程A获取互斥锁，线程B和C等待。 当A离开时，B进入，但在B离开之前，A循环回来加入到队列中和C一起排队. B离开时，无法保证C接下来会执行。 实际上，如果接下来是A，并且B加入队列，那么我们将回到起始点，可以永远重复该循环。 C饿死。

这种模式的存在证明了互斥体容易受到饿死的影响。 这个问题的一个解决方案是改变信号量的实现，以便它保证更强的属性：

• 属性4：如果一个线程在信号量处等待，那么在它之前被唤醒的线程的数量是有限的。

例如，如果信号量维持先进先出队列，那么属性4成立，因为当一个线程加入队列时，它前面的线程数是有限的，后来到达的线程不能插队。

具有属性4的信号量有时被称为强信号量（strong semaphore）; 只有属性3的信号量被称为弱信号量（weak semaphore）。 我们已经证明，对于弱信号量，简单的互斥解决方案很容易受到饿死的影响。 事实上，Dijkstra推测，如果仅仅使用弱信号量，就不可能解决饿死的互斥问题。

1979年，J.M.Morris解决了这个问题，推翻了上述猜想。他假定线程的数量是有限的[6]。 如果您对此问题感兴趣，下一节将介绍他的解决方案。 如果这不是你的乐趣点，你可以假设信号量有属性4，并转到第4.4节。

思考：使用弱信号量编写互斥问题的解决方案。 您的解决方案应提供以下保证：一旦线程到达并尝试进入互斥锁，则在其之前继续执行的线程数量是有限的。 您可以假设线程总数是有限的。

 

4.3.1 无饿死互斥的提示

Morris的解决方案类似于3.7节中的可重用屏障。 它使用两个十字转门在临界区之前创建两个等候室。 该机制分两个阶段进行。 在第一阶段期间，第一个旋转门打开而第二个旋转门关闭，因此线程在第二个房间中积聚。 在第二阶段，第一个旋转门关闭，因此没有新线程可以进入，第二个旋转门打开，因此现有线程可以到达临界区。

虽然等候室中可能有任意数量的线程，但这里的每个线程都确保在未来的其他线程到达之前进入临界区。

以下是我在解决方案中使用的变量（我更改了Morris使用的名称，尝试使结构更清晰）。

room1和room2跟踪等候室中的线程数。 mutex有助于保护计数器。 t1和t2是十字转门。

 

4.3.2 无饿死互斥的方案

这是Morris的方案：

在进入临界区之前，线程必须通过两个十字转门。这些十字转门将代码划分为三个“房间”。 第2~8行是1号房间，第6~18行是2号线，其余的是3号房间。不严格地说，计数器room1和room2跟踪每个房间的线程数。

计数器room1以通常的方式受互斥锁mutex保护，但是room2的保护任务分配在t1和t2中。同样，对临界区进行独占访问的责任包括t1和t2这两个信号量。为了进入临界区，线程必须持有其中的一个，但不能同时持有两个。然后，在退出之前，它会放弃它所持有的任何一个。

要了解此解决方案的工作原理，请沿着单个线程的全程执行路线。当它到达第8行时，它持有信号量mutex和t1。如果它检查到room1的值是0，它就释放互斥锁mutex，然后打开第二个旋转门，t2。因此，它不会在第17行等待，它可以安全地递减room2并进入临界区，因为任何后续线程都必须在t1上排队。离开临界区后，它发现room2 = 0并释放t1，这使我们回到起始状态。

当然，如果有多个线程，情况会更有趣。 在这种情况下，当领头的线程到达第8行时，其他线程可能已进入等待室并在t1上排队。 由于room1> 0，领头线程并没有解锁t2以允许后续线程进入2号房间，而是发出t1信号。由于t2仍然被锁定，因此任何线程都不能进入3号房间。

最终（因为有一定数量的线程），在别的线程进入1号房间之前，有一个线程到达第8行，在这种情况下它将打开t2，允许那里的任何线程移动到3号房间。打开t2的线程继续保持t1，所以如果任何一个线程循环回去，它们将阻塞在第5行。

当每个线程离开3号房间时，它发出t2信号，允许另一个线程离开2号房间.当最后一个线程离开2号房间时，它将t2锁定并打开t1，这使我们回到起始状态。

要了解此解决方案如何避免饿死，分两个阶段考虑会有助于理解其运行原理。 在第一阶段，线程检查并进入1号房间，递增room1，然后一次一个地进入到房间2。 保持t2锁定的唯一方法是维持一系列线程通过1号房间。因为线程的数量有限，行进的队伍终究会结束，此时t1保持锁定状态，t2则是打开的。

在第二阶段，线程鱼贯进入到3号房间。因为房间2中有一定数量的线程，并且没有新线程可以进入，最终最后一个线程离开，此时t2锁定并且t1打开。

在第一阶段结束时，我们知道没有线程在t1等待，因为room1 = 0。并且在第二阶段结束时，我们知道没有线程在t2等待，因为room2 = 0。

对于有限数量的线程，只有当一个线程可以循环并超过另一个线程时，才可能导致饿死。 但是双旋转机制使得这不可能，所以不可能发生饿死。

这个故事的寓意是，即使对于最简单的同步问题，使用弱信号量也很难避免饿死。 在本书的其余部分，当我们讨论饿死时，我们将假设强信号量。