处理机死锁：操作系统中的棘手问题-EW帮帮网

可剥夺资源（Preemptible Resources）：
- 定义：可以被抢占或中断的资源。
- 例子：CPU时间、内存。
- 特点：资源可以在不影响进程状态的情况下被重新分配。
不可剥夺资源（Non-preemptible Resources）：
- 定义：一旦被分配，在使用完毕之前无法被强行抢占的资源。
- 例子：打印机、硬盘。
- 特点：资源必须在进程使用完毕后才能被释放，不能中途被抢占。

资源冲突与死锁

当多个进程同时请求不可剥夺资源时，可能会出现资源冲突，进而导致死锁。死锁是一种特殊的资源冲突状态，具体表现为：

互斥条件：每个资源要么被一个进程独占，要么可供分配。
占有并等待条件：一个进程已经持有至少一个资源，并且在等待获取其他被占有的资源。
不可剥夺条件：资源不能被强行从占有它的进程中抢走，只能由进程自行释放。
循环等待条件：存在一个进程链，使得每个进程都在等待链中下一个进程所占有的资源。

解决资源冲突的方法

预防死锁：
- 破坏互斥条件：尽量减少资源的独占使用。
- 破坏占有并等待条件：在进程开始时一次性申请所有需要的资源。
- 破坏不可剥夺条件：允许资源被强行抢占。
- 破坏循环等待条件：为资源分配一个全局顺序，进程按顺序请求资源。
避免死锁：
- 银行家算法：通过模拟资源分配，确保系统始终处于安全状态。
- 资源分配图：使用图论方法检测和避免循环等待。
检测与恢复：
- 死锁检测：定期检查系统状态，检测是否存在死锁。
- 死锁恢复：通过终止进程或强制释放资源来打破死锁。

资源分配策略

静态分配：
- 在进程开始时一次性分配所有需要的资源。
- 优点：简单，避免占有并等待条件。
- 缺点：资源利用率低，可能导致资源浪费。
动态分配：
- 根据进程的实时需求动态分配资源。
- 优点：资源利用率高。
- 缺点：需要复杂的调度算法，可能存在死锁风险。

实际应用中的资源管理

操作系统内核：负责管理系统中的各种资源，包括CPU、内存、I/O设备等。
数据库管理系统：管理并发事务，确保数据一致性和完整性。
网络服务器：管理网络连接和数据传输，确保高效的资源利用。

死锁的定义

概述

死锁是指两个或多个进程在执行过程中，因争夺资源而造成互相等待的现象，若无外力作用，它们都将无法推进下去。死锁是一种常见的多进程系统错误，会导致系统资源的浪费和性能的下降。

四个必要条件

死锁的发生需要满足以下四个必要条件：

互斥条件：资源只能被一个进程独占使用，不能被共享。
不可剥夺条件：进程已获得的资源不能被其他进程强行剥夺，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

举例说明

假设有两个进程 P1 和 P2，P1 需要资源 A 和 B，P2 需要资源 B 和 A。P1 先获得了资源 A，然后请求资源 B，但此时资源 B 被 P2 占有，P1 因此被阻塞。P2 先获得了资源 B，然后请求资源 A，但此时资源 A 被 P1 占有，P2 因此被阻塞。P1 和 P2 互相等待对方释放资源，形成了死锁。

死锁的处理方法

处理死锁的方法主要有预防、避免、检测和解除。

1. 预防死锁

预防死锁涉及破坏死锁发生的四个必要条件中的一个或多个：

互斥条件：尽可能避免资源的独占使用，使资源能够被多个进程共享。
保持与等待条件：要求进程在开始执行前，必须一次性请求所有所需资源，或者在一个进程持有资源时，不再允许它请求其他资源。
不剥夺条件：允许进程强制释放资源。如果某进程请求的资源不能立即获得，必须释放已持有的资源，然后重试。
循环等待条件：资源按某种顺序排序，进程需按顺序请求资源，确保不形成循环等待。

这些策略虽然能有效预防死锁，但有时可能会降低系统资源的利用率和进程的灵活性。

2. 避免死锁

避免死锁是通过动态地检测资源状态来确保系统不会进入不安全状态，其中最著名的方法是银行家算法：

银行家算法（Banker's Algorithm）：计算系统在分配资源后是否仍能满足所有进程的最大需求。只有当资源分配不会导致系统进入不安全状态时，才进行资源分配。在实现上，系统将模拟资源分配后，检查是否所剩资源足以满足某个进程的最大需求。如果模拟后的状态是安全的，才真正分配资源。

3. 检测死锁

死锁检测允许死锁的发生，但系统会定期进行检测以发现并解决死锁：

资源分配图：一种将进程及其所请求和持有的资源表示为图的方式。通过检测资源分配图中的环路，可以发现死锁。
检测算法：定期运行的算法，检查系统中是否存在资源分配的循环等待。

死锁检测适合于那些希望在死锁发生时能够及时识别并处理的系统，尽管会带来检测开销。

4. 解除死锁

一旦检测到死锁，系统需要采取措施解除死锁，常见的方法包括：

资源抢占：强制从某个进程中夺取资源，重新分配给其他进程，但要小心避免导致新的死锁。
终止进程：选择并终止一个或多个死锁进程，释放其占用的资源，让其他进程得以继续。选择进程时可以考虑如下标准：
- 先终止影响较小的进程。
- 先终止优先级较低的进程。
- 考虑终止代价，如已执行的时间、剩余的执行时间等。
回退进程：将进程返回到某个之前保存的检查点状态，再次尝试执行，确保在新的运行过程中避免死锁。

综合措施

实际系统中，有时会结合多种策略来处理死锁问题。例如，预防和避免死锁的方法可以在设计阶段引入，而检测和解除死锁的机制在运行时执行。这种综合措施能够提供更高级别的可靠性和灵活性。

资源分配图

概述

资源分配图是一种用于描述进程之间资源请求关系的图，它可以帮助我们理解和分析死锁。图中的节点表示进程或资源，有向边表示进程对资源的请求。如果图中存在环，则表明存在循环等待，可能发生死锁。

资源分配图的构建

资源分配图的构建步骤如下：

创建一个节点集合，其中每个节点表示一个进程或资源。
对于每个进程，创建一个有向边，指向它所请求的资源。
对于每个资源，创建一个有向边，指向它所在的进程。

资源分配图的分析

通过分析资源分配图，我们可以判断是否存在死锁。如果图中存在环，则表明存在循环等待，可能发生死锁。例如，以下资源分配图表示存在死锁：

A -> B
B -> C
C -> A

在这个图中，进程 A 请求资源 B，进程 B 请求资源 C，进程 C 请求资源 A，形成了循环等待。

资源分配图的应用

资源分配图可以用于以下目的：

分析死锁：资源分配图可以帮助我们理解和分析死锁，并找到死锁的发生原因。
预防死锁：通过分析资源分配图，我们可以采取措施预防死锁的发生，例如避免互斥条件、不可剥夺条件、请求和保持条件和循环等待条件。
解除死锁：如果死锁已经发生，我们可以通过分析资源分配图来选择合适的死锁解除方法，例如进程撤销、资源抢占或资源转换。

死锁预防

概述

死锁预防是指在分配资源时，破坏死锁产生的四个必要条件中的一个或几个，以防止死锁的发生。常见的死锁预防方法包括：

破坏不可剥夺条件

不可剥夺条件是指进程已获得的资源不能被其他进程强行剥夺，只能主动释放。破坏不可剥夺条件意味着允许在某些情况下剥夺进程已获得的资源，从而可以防止死锁的发生。常用的破坏不可剥夺条件的方法包括：

可抢占算法：可抢占算法允许在某些情况下剥夺进程已获得的资源，例如当其他进程对资源的需求更迫切时。
优先级算法：优先级算法为每个进程分配一个优先级，并根据优先级来分配资源。高优先级的进程可以剥夺低优先级的进程已获得的资源。

破坏请求和保持条件

请求和保持条件是指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。破坏请求和保持条件意味着进程只能在释放所有已获得的资源后再请求新的资源，从而可以防止死锁的发生。常用的破坏请求和保持条件的方法包括：

静态分配：静态分配是指进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。
动态分配：动态分配是指进程在运行过程中逐步申请资源。如果进程在请求资源时得不到满足，则必须立即释放所有已获得的资源，待以后需要时再重新申请。

破坏循环等待条件

循环等待条件是指存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。破坏循环等待条件意味着打破循环等待链，从而可以防止死锁的发生。常用的破坏循环等待条件的方法包括：

顺序资源分配：顺序资源分配法规定每个进程必须按编号递增的顺序请求资源。例如，如果系统中有三个资源 A、B 和 C，则规定进程只能按 A -> B -> C 的顺序请求资源。
银行家算法：银行家算法是一种静态的资源分配算法，它通过分析系统的资源分配情况来判断是否存在死锁，并采取措施防止死锁的发生。

死锁避免

死锁避免策略通过动态分析资源分配情况，确保系统始终处于安全状态，从而避免死锁的发生。银行家算法是其中最著名的一种方法。以下是对死锁避免的详细解释和银行家算法的深入探讨：

死锁避免的基本原理

死锁避免策略的核心在于通过实时监控系统的资源分配状态，确保每一次资源请求都不会将系统带入不安全状态。一个系统处于安全状态意味着存在一种资源分配顺序，使得所有进程都能顺利完成其任务而不发生死锁。

银行家算法

银行家算法由Edsger Dijkstra提出，主要用于多进程系统中的资源分配。该算法假设系统中的资源类似于银行家的贷款，银行家会根据当前的资源状况和客户的最大需求，决定是否满足客户的资源请求。

银行家算法的基本步骤

初始化：
- 设定系统中总资源数量。
- 初始化每个进程的最大需求矩阵（Max），当前持有资源矩阵（Allocation），和剩余需求矩阵（Need = Max - Allocation）。
资源请求：
- 当一个进程请求资源时，系统首先检查请求是否超过该进程的最大需求。
- 如果请求量超过了进程的最大需求，则拒绝请求并报错。
安全性检查：
- 假设临时分配资源给请求的进程，并更新相应的资源矩阵。
- 使用安全性算法检查系统是否处于安全状态。如果系统处于安全状态，则真正分配资源；否则，拒绝请求并恢复原状态。

安全性算法

安全性算法用于判断系统在假设分配资源后的状态是否安全。步骤如下：

初始化：
- 创建一个工作向量（Work），初始值为系统的可用资源向量（Available）。
- 创建一个完成向量（Finish），初始值为所有进程未完成（False）。
寻找可满足需求的进程：
- 找到一个进程，使其需求（Need）小于或等于工作向量（Work）。
- 如果找到这样的进程，则假设该进程完成（Finish[i] = True），并将其资源归还给工作向量（Work = Work + Allocation[i]）。
重复步骤2，直到所有进程都标记为完成（Finish[i] = True）或无法找到可满足需求的进程。
判断安全性：
- 如果所有进程都能顺利完成，则系统处于安全状态。
- 如果有进程无法完成，则系统处于不安全状态。

银行家算法示例

假设系统有三个资源类型A、B、C，总资源量为(10, 5, 7)。有五个进程P0, P1, P2, P3, P4，其最大需求矩阵（Max）和当前持有资源矩阵（Allocation）如下：

	Max(A, B, C)	Allocation(A, B, C)
P0	(7, 5, 3)	(0, 1, 0)
P1	(3, 2, 2)	(2, 0, 0)
P2	(9, 0, 2)	(3, 0, 2)
P3	(2, 2, 2)	(2, 1, 1)
P4	(4, 3, 3)	(0, 0, 2)

系统的可用资源向量（Available）为(3, 3, 2)。进程P1请求资源(1, 0, 2)。

检查请求是否超过最大需求：
- 请求(1, 0, 2) <= 进程P1的最大需求(3, 2, 2)，请求合法。
假设临时分配资源：
- 临时分配后，Available = (2, 3, 0)，Allocation[P1] = (3, 0, 2)，Need[P1] = (0, 2, 0)。
安全性检查：
- 初始化工作向量Work = (2, 3, 0)，完成向量Finish = (False, False, False, False, False)。
- 依次检查各进程的需求是否能被满足，更新工作向量和完成向量。
- 如果所有进程都能完成，则分配资源，否则拒绝请求。

实际应用中的死锁避免

银行家算法虽然理论上能够有效避免死锁，但在实际应用中由于其计算复杂度高和资源需求预测困难，较少被直接使用。实际应用中更多的是结合死锁预防、检测和恢复策略，通过综合手段来避免和处理死锁。

死锁的检测与解除

死锁的检测与解除是操作系统中处理死锁问题的重要策略。很多操作系统如 Unix、Linux 和 Windows，在面对死锁时，更注重检测和解除而非预防和避免。这种策略的核心在于能够及时识别死锁并采取适当措施来恢复系统的正常运行。

死锁的检测

1. 资源分配图（Resource Allocation Graph）

资源分配图是一种常用的方法来检测死锁。在这种图中：

节点：表示进程和资源。
边：从进程指向资源表示进程请求资源，从资源指向进程表示资源被分配给进程。

如果此图中存在一个环路，则表明可能存在死锁。

2. 死锁检测算法

通过周期性地运行死锁检测算法，可以识别系统中是否存在死锁。这些算法通常检查资源分配状态并试图找到资源等待环。例如：

基于矩阵的算法：矩阵形式的算法可以反映系统当前的资源分配和请求状态，通过分析这些矩阵计算是否存在死锁，例如"找可用比需求更多的资源，释放其资源，再重复这一过程，直到无法继续，这时候如果还有需求进程，说明有死锁"。

死锁的解除

在检测到死锁之后，操作系统可以采取以下几种方法进行恢复：

1. 资源剥夺法

挂起进程：挂起某些死锁进程，将其占有的资源剥夺下来，然后将这些资源分配给其他需要的进程。
选择进程：选择那些代价较小或优先级较低的进程进行资源剥夺，尽量减少对系统的影响。

2. 进程撤销法

完全撤销：强制撤销一个或多个死锁进程。
部分撤销：撤销某些特定的死锁进程，而不一定撤销所有进程。

选择撤销哪些进程时可以考虑这些因素：

已执行时间和剩余的执行时间。
进程优先级。
被撤销的代价，包括进程执行的长短和对系统其他部分的影响。

3. 进程回退法

回退到检查点：让进程回退到之前保存的某个检查点并重新执行，从而避免进入死锁状态。
历史信息：系统需要保留进程的历史信息，以便在检测到死锁时能够准确地回退。

在实现进程回退法时，保留检查点的信息对系统资源和性能有一定的要求，但可以有效避免和解决死锁。

综合实践

操作系统在实际应用中，可能会结合检测和解除方法来管理死锁。例如：

定期检测：定期运行死锁检测算法，确保系统能够及时识别死锁。
动态恢复：在检测到死锁后，根据情况选择资源剥夺、进程撤销和进程回退的方法来恢复系统运行。

总结

处理机死锁是操作系统中常见的一种问题，它可能导致系统性能下降甚至崩溃。了解死锁的定义、必要条件和处理方法，可以帮助我们更好地管理计算机系统中的资源，避免死锁的发生。同时，操作系统也提供了多种策略来预防、避免、检测和解除死锁，确保系统的稳定性和高效运行。

处理机死锁：操作系统中的棘手问题

死锁概述

资源问题

资源分类