复杂系统中的死锁预防

Question

假设我有一个有7个进程和3个资源A，B，C的系统，假设每个进程都需要读写{A，B，C}的一个不同的非空子集，我如何有效地防止死锁？也就是说，不能将三个资源作为一个整体放在一个互斥物上。

Answer 1

如果互斥锁支持非阻塞获取(通常称为trylock)，则可以实现避免死锁的解决方案，而不需要锁排序/层次结构。该算法如下：

1. 获取第一个资源的锁；这里允许等待。
2. 一旦获得第一个锁，试着用尝试锁获取另一个锁.
3. 如果尝试锁失败(指示资源正忙)，释放所有先前获得的锁，然后转到步骤1。
4. 如果“尝试锁定”成功，则从步骤2中对所有剩余资源重复执行.

避免死锁是通过非阻塞获取(如果你已经持有锁就不要等待锁)和合作(做一个好邻居，释放你已经获得的东西，如果你不能继续没有阻塞)。

这样的策略被用于例如Boost，用于同时获取多个锁。实际上，在Boost中，它甚至更高级:在步骤3释放锁之后，它们开始从上次尝试中繁忙的锁中等待。

另外，看一下这些主题：Acquire a lock on two mutexes and avoid deadlock，Multiple mutex locking strategies and why libraries don't use address comparison

Answer 2

当我们将资源组织成某种层次时，这类问题通常会得到解决。您有三个资源，{A, B, C}，我们可以确定A位于层次结构的顶部，C位于底层。现在有两种方法：

悲观:如果我需要资源X，那么我还必须获取X之上的所有资源，即使此时我不需要它们。原因是我可能在其他时间需要它们，同时仍然持有资源X。

乐观:如果我需要资源X，那么就获得它。如果以后我需要资源X-below，那么也可以获得它，没有问题。但是，如果在X之后我需要资源X-above，那么运气不好，我不能在持有资源X的时候拥有它，但是我可以释放资源X，然后首先获得X-above，然后再获得X。

如果所有进程都尊重资源的层次结构，那么就不会出现死锁。

Answer 3

您需要决定一个订单，资源将被获取，然后始终以相同的顺序获取它们。

使用您的示例，应该始终按A、B、C顺序获取资源，因此，例如：

P1 => A
P2 => A C
P3 => C
P4 => B C
P5 => B
P6 => A B
P7 => A B C

这样，就不会出现所有进程都持有一个资源而等待另一个进程拥有的资源的情况。

在一个更简单的场景中：

P1 => A B
P2 => B C

在这里，两个进程都将获得它们的第一个资源，但是process P1将被阻塞，因为P2有B，然而，P2将能够获得C并取得进展。在某个时候，它将发布C，这将允许P1继续进行。

如果您没有按固定顺序获取它们，那么您可以得到以下内容：

P1 => A B
P2 => B A

现在，每个进程都锁定了一个资源，并且正在等待另一个进程释放它所需的资源，从而导致死锁。