操作系统中的死锁检测算法

---

引言

死锁是指在计算机系统中，两个或多个进程阻塞并等待彼此释放资源，从而导致僵局的一种情况。

这是操作系统中一个严重的问题，因为它可能导致整个系统冻结或崩溃。因此，检测和解决死锁对于任何计算机系统的平稳运行至关重要。

死锁检测算法用于识别计算机系统中死锁的存在。这些算法检查系统的进程和资源，以确定是否存在可能导致死锁的循环等待情况。如果检测到死锁，该算法可以采取措施来解决它并防止它在将来再次发生。有几种流行的死锁检测算法。在这里，我们将探讨死锁的必要条件、死锁检测算法的目的，以及详细介绍这些算法中的每一个以及它们最有效的应用场景。

死锁检测算法的目的

• 死锁检测算法的目的是识别和解决计算机系统中的死锁。

• 它通过识别死锁的发生、确定涉及的进程和资源、采取纠正措施来打破死锁以及恢复正常的系统操作来实现这一点。

• 该算法通过防止死锁导致系统冻结或崩溃，在确保系统稳定性和可靠性方面发挥着至关重要的作用。

死锁检测算法

1. 资源分配图 (RAG) 算法

• 构建RAG − 第一步是构建一个资源分配图 (RAG)，该图显示系统中资源的分配和请求。每种资源类型都由一个矩形表示，每个进程都由一个圆圈表示。

• 检查循环 − 在RAG中查找循环。如果存在循环，则表示系统处于死锁状态。

• 识别死锁进程 − 识别参与循环的进程。这些进程处于死锁状态，并等待其他进程持有的资源。

• 确定资源类型 − 确定死锁中涉及的资源类型，以及每个进程持有的和请求的资源。

• 采取纠正措施 − 通过释放资源、中止进程或抢占资源来采取纠正措施以打破死锁。一旦死锁被打破，系统就可以继续进行正常操作。

• 重新检查循环 − 采取纠正措施后，重新检查RAG是否存在循环。如果没有更多循环，则系统不再处于死锁状态，可以恢复正常操作。

优点

• 易于理解和实现

• 可以处理多种类型的资源

• 有助于识别参与死锁的进程

缺点

• 对于大型系统来说可能很耗时

• 如果对同一资源有多个请求，则可能出现误报。

• 假设所有资源都是预先分配的，这在某些系统中可能并非如此。

示例

考虑一个具有两个进程 P1 和 P2 以及两个资源 R1 和 R2 的系统。

进程	R1	R2
P1	1	0
P2	0	1

此系统的RAG可以表示如下：------

P1 -> R1

P2 -> R2

R1 -> P2

R2 -> P1

P1 和 P2 之间存在循环，表明潜在的死锁。为了确认是否存在死锁，我们可以对RAG使用循环检测算法。该算法将检测循环并识别P1和P2之间潜在的死锁。然后，我们可以采取适当的措施来解决死锁并防止其在将来再次发生。

2. 等待图 (WFG) 算法

• 构建WFG − 第一步是构建一个等待图 (WFG)，该图显示进程之间的等待关系。每个进程都由一个圆圈表示，如果前一个进程正在等待后一个进程持有的资源，则在两个进程之间画一条箭头。

• 检查循环 − 在WFG中查找循环。如果存在循环，则表示系统处于死锁状态。

• 识别死锁进程 − 识别参与循环的进程。这些进程处于死锁状态，并等待其他进程持有的资源。

• 确定资源类型 − 确定死锁中涉及的资源类型，以及每个进程持有的和请求的资源。

• 采取纠正措施 − 通过释放资源、中止进程或抢占资源来采取纠正措施以打破死锁。一旦死锁被打破，系统就可以继续进行正常操作。

• 重新检查循环 − 采取纠正措施后，重新检查WFG是否存在循环。如果没有更多循环，则系统不再处于死锁状态，可以恢复正常操作。

优点

• 可以处理多种类型的资源

• 适用于具有大量进程的系统

• 提供死锁的清晰可视化

缺点

• 对于大型系统来说可能很耗时

• 如果对同一资源有多个请求，则可能出现误报。

• 假设所有资源都是预先分配的，这在某些系统中可能并非如此。

示例

三个进程 P1、P2 和 P3 以及两个资源 R1 和 R2。

进程	R1	R2
P1	1	0
P2	0	1
P3	1	1

此系统的等待图 (WFG) 可以表示如下：

P1 -> P3

P3 -> P2

P2 -> P3

P2 和 P3 之间存在循环，表明潜在的死锁。为了确认是否存在死锁，我们可以对WFG使用循环检测算法。该算法将检测循环并识别P2和P3之间潜在的死锁。然后，我们可以采取适当的措施来解决死锁并防止其在将来再次发生。

3. 银行家算法

它可以用作死锁检测算法。事实上，它是操作系统中最著名的死锁检测算法之一。

它使用3个数据结构：

• Available −

• 长度为m的向量

• 它指示每种类型的可用资源有多少。

• Allocation −

• 大小为n*m的矩阵

• A[i,j]指示分配给第i个进程的第j种资源类型的数量。

• Request −

• 大小为n*m的矩阵

• 指示每个进程的请求。

• Request[i,j]表示Pi进程请求的第j种资源类型的实例数量。

算法

• 步骤1 −

• 令Work（向量）长度 = m

• Finish（向量）长度 = n

• 初始化 Work = Available。

• 对于 i = 0, 1, …., n-1，如果 Allocation_i = 0，则 Finish[i] = true；否则，Finish[i] = false。

• 步骤2 −

• 找到一个索引 i，使得：

• Finish[i] == false

• Request_i <= Work

• 如果没有这样的i存在，则转到步骤4。

• 步骤3 −

• Work = Work + Allocation_i

• Finish[i] = true

  转到步骤2。

• 步骤4 −

• 如果对于某些 i，0 <= i < n，Finish[i] == false，则系统处于死锁状态。此外，如果 Finish[i] == false，则进程 Pi 处于死锁状态。

• 否则，没有死锁。

示例

进程	Allocation (ABC)	Request (ABC)	Available (ABC)
P0	010	000	000
P1	200	202
P3	303	000
P4	211	100
P5	002	002

解决方案

• 步骤1 −

  Work = [0,0,0] &

  Finish = [false, false, false, false, false]。

• 步骤2 −

  选择 i=0，因为 Finish[0]=false 且 [0,0,0] <= [0,0,0]。

• 步骤3 −

  Work = [0,0,0] + [0,1,0] => [0,1,0] &

  Finish = [true, false, false, false, false]。

• 步骤4 −

  选择 i=2，因为 Finish[2] = false 且 [0,0,0] <= [0,1,0]。

• 步骤5 −

  Work = [0,1,0] + [3,0,3] => [3,1,3] &

  Finish = [true, false, false, false, false]。

• 步骤6 −

  选择 i=1，因为 Finish[1] = false 且 [2,0,2] <= [3,1,3]。

• 步骤7 −

  Work = [3,1,3] + [2,0,0] => [5,1,3] &

  Finish = [true, true, true, false, false]。

• 步骤8 −

  选择 i=3，因为 Finish[3] = false 且 [1,0,0] <= [5,1,3]。

• 步骤9 −

  Work = [5,1,3] + [2,1,1] => [7,2,4] &

  Finish = [true, true, true, true, false]。

• 步骤10 −

  选择 i=4，因为 Finish[4] = false 且 [0,0,2] <= [7,2,4]。

• 步骤11 −

  Work = [7,2,4] + [0,0,2] => [7,2,6] &

  Finish = [true, true, true, true, true]。

现在我们可以看到 Finish（一个向量）包含所有真值，这意味着在这个例子中没有死锁。

优点

• 通过确保进程在执行前获取所有必需的资源来防止死锁

• 可以处理多种资源类型

• 提供安全有效的资源分配方法

缺点

• 对于具有大量进程和资源的系统可能不可行

• 假设资源需求是预先知道的，这在某些系统中可能并非如此

• 如果资源被保留但未使用，则可能导致资源利用率低。

结论

死锁检测算法是维护计算机系统稳定性和可靠性的重要工具。可以使用不同的实现策略。每种算法都有其自身的优缺点，选择使用哪种算法将取决于被检查系统的特定需求。总的来说，死锁检测算法在确保复杂计算环境中操作系统的可靠性和性能方面发挥着至关重要的作用。