深入解析死锁现象及其预防策略
2023-10-316.6k 阅读
死锁现象基础概念
死锁的定义
死锁是指在多进程（或多线程）系统中，一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，从而导致没有任何一个进程能够继续执行的一种僵持局面。简单来说，就是进程们相互等待对方释放资源，最终都无法推进。
例如，假设有两个进程 P1 和 P2，P1 持有资源 R1 并请求资源 R2，而 P2 持有资源 R2 并请求资源 R1。此时，P1 和 P2 就陷入了死锁状态，因为它们都在等待对方释放自己所需的资源，却又都不愿意主动放弃已持有的资源。
死锁产生的四个必要条件
- 互斥条件：资源在同一时间只能被一个进程所使用。例如，打印机在打印文档时，不能同时被另一个进程用来打印不同的文档。这种特性确保了数据的一致性和正确性，但也为死锁的产生埋下了伏笔。
- 占有并等待条件：进程已经占有了至少一个资源，但又请求新的资源，并且在等待新资源分配的同时，继续占有已有的资源。比如，进程 P 持有文件 A 的读写权限，现在它还想要获取文件 B 的读写权限，在等待文件 B 资源分配的过程中，它不会释放文件 A 的权限。
- 不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，只能由获得该资源的进程自己主动释放。以数据库锁为例，一旦一个事务获取了某条数据的锁，其他事务不能直接从它手中抢走这把锁，只有持有锁的事务完成操作并释放锁后，其他事务才有机会获取。
- 循环等待条件：存在一个进程资源的循环链，链中的每一个进程都在等待下一个进程所占用的资源。假设有进程 P1、P2、P3，P1 等待 P2 持有的资源，P2 等待 P3 持有的资源，P3 又等待 P1 持有的资源，这样就形成了一个循环等待的死锁局面。
这四个条件是死锁产生的必要条件，只有当这四个条件同时满足时，死锁才会发生。因此，要预防死锁，就需要破坏其中至少一个条件。
死锁的影响与危害
系统资源浪费
死锁发生时，参与死锁的进程所占用的资源无法被其他进程使用，这些资源被闲置，造成了系统资源的极大浪费。例如，在一个多进程的文件处理系统中，若两个进程因死锁分别持有一个文件的部分锁，且都在等待对方释放锁以完成文件的读写操作，那么这两个文件在死锁解除前都无法被正常处理，相关的磁盘 I/O 资源、内存缓冲区等也都处于无效占用状态。
系统性能下降
死锁不仅会导致参与死锁的进程无法推进，还会影响整个系统的性能。操作系统需要花费额外的时间和资源来检测和处理死锁，这会占用系统的 CPU 时间和内存空间。同时，由于死锁进程占用了资源，其他正常进程可能因为资源不足而无法及时执行，导致系统整体的响应时间变长，吞吐量下降。在一个服务器系统中，如果多个用户请求的处理进程陷入死锁，那么新的用户请求也会因为系统资源紧张而得不到及时响应，严重影响服务质量。
系统不稳定甚至崩溃
严重的死锁情况可能导致整个系统变得不稳定，甚至崩溃。当死锁范围扩大，涉及到系统关键进程或大量资源时，操作系统可能无法有效调度资源，进而无法维持正常的运行状态。例如，在一个实时操作系统中，若负责控制硬件设备的进程与其他进程发生死锁，可能导致硬件设备无法正常工作，进一步引发系统故障，最终导致系统崩溃，所有正在运行的任务都将失败。
死锁的检测与定位
死锁检测算法
- 资源分配图算法 资源分配图是一种描述进程与资源之间关系的有向图。在图中，节点分为进程节点和资源节点，有向边分别表示进程请求资源（从进程节点指向资源节点）和资源分配给进程（从资源节点指向进程节点）。通过对资源分配图进行简化操作，如果最终图中存在不可简化的环，则表示存在死锁。 例如，假设有进程 P1、P2，资源 R1、R2。P1 持有 R1 并请求 R2，P2 持有 R2 并请求 R1，画出资源分配图后，可以发现存在一个环，这就表明存在死锁。
以下是使用 Python 简单模拟资源分配图检测死锁的代码示例：
# 定义资源分配图
resource_allocation_graph = {
'P1': ['R1'],
'R1': ['P1'],
'P2': ['R2'],
'R2': ['P2'],
'P1': ['R2'],
'P2': ['R1']
}
def has_cycle(graph, start, visited, recursion_stack):
visited[start] = True
recursion_stack[start] = True
for neighbor in graph[start]:
if neighbor not in visited:
if has_cycle(graph, neighbor, visited, recursion_stack):
return True
elif recursion_stack[neighbor]:
return True
recursion_stack[start] = False
return False
def detect_deadlock(graph):
visited = {node: False for node in graph}
recursion_stack = {node: False for node in graph}
for node in graph:
if not visited[node]:
if has_cycle(graph, node, visited, recursion_stack):
return True
return False
if detect_deadlock(resource_allocation_graph):
print("存在死锁")
else:
print("不存在死锁")
- 银行家算法的扩展
银行家算法原本是用于避免死锁的算法，但它也可以扩展用于死锁检测。通过定期检查系统的资源分配状态，假设所有进程都按照最大需求申请资源，看是否会出现无法满足的情况。如果出现，则可能存在死锁。具体步骤如下：
- 首先，记录系统中每种资源的总量（Available）、每个进程已分配的资源量（Allocation）以及每个进程对每种资源的最大需求量（Max）。
- 然后，尝试找到一个进程，其需要的资源量（Need = Max - Allocation）小于等于当前系统可用资源量（Available）。如果找到这样的进程，则假设该进程获得资源并运行结束，释放它所占有的资源，更新 Available。
- 重复上述步骤，如果所有进程都能按照这种方式运行结束，则系统不存在死锁；否则，系统可能存在死锁。
死锁定位方法
- 日志记录与分析 在进程运行过程中，记录详细的资源请求和分配日志。当死锁发生时，通过分析日志可以了解到每个进程在什么时间请求了什么资源，以及资源的分配顺序。例如，在 Java 应用程序中，可以使用 Log4j 等日志框架记录如下信息：
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
public class ResourceManager {
private static final Logger logger = LogManager.getLogger(ResourceManager.class);
public void requestResource(Process process, Resource resource) {
logger.info(process.getName() + " 请求资源 " + resource.getName());
// 资源分配逻辑
}
}
通过查看日志文件，可以梳理出进程间资源请求的依赖关系，从而定位死锁发生的具体位置。
2. 系统监控工具
操作系统通常提供了一些系统监控工具，如 Linux 系统中的 top、ps 命令以及 strace 工具等。top 命令可以实时查看系统中各个进程的资源使用情况，如 CPU 使用率、内存占用等。ps 命令可以获取进程的详细状态信息。strace 工具则可以跟踪进程的系统调用，查看进程在请求资源时的具体操作。例如，通过 strace -p <pid> 命令可以查看指定进程 ID 的进程所进行的系统调用，从而分析其资源请求行为，帮助定位死锁。
死锁预防策略
破坏互斥条件
在某些情况下，可以通过改变资源的使用方式来破坏互斥条件。例如，对于一些只读资源，可以允许多个进程同时访问，而不需要互斥。以文件系统为例，如果文件只用于读取操作，多个进程可以同时打开文件进行读取，而不会产生数据一致性问题。然而，对于大多数资源，如打印机、数据库锁等，互斥是保证数据完整性和正确性的必要条件，很难完全破坏。因此，这种方法适用范围相对较窄。
破坏占有并等待条件
- 资源一次性分配 进程在启动之前，一次性申请它所需要的所有资源。只有当系统能够满足进程的全部资源需求时，才允许该进程启动运行。例如，在一个多媒体处理程序中，该程序可能需要占用 CPU 资源、内存资源以及显卡资源等，在程序启动时，操作系统检查这些资源是否足够，如果足够则一次性分配给该程序，这样就避免了进程在运行过程中因为请求新资源而陷入死锁。
以下是一个简单的 C 语言示例，模拟资源一次性分配：
#include <stdio.h>
#include <stdbool.h>
#define PROCESS_NUM 3
#define RESOURCE_NUM 3
// 资源总量
int available[RESOURCE_NUM] = {3, 3, 2};
// 每个进程已分配的资源
int allocation[PROCESS_NUM][RESOURCE_NUM] = {
{0, 1, 0},
{2, 0, 0},
{3, 0, 2}
};
// 每个进程对资源的最大需求
int max[PROCESS_NUM][RESOURCE_NUM] = {
{7, 5, 3},
{3, 2, 2},
{9, 0, 2}
};
bool is_safe() {
int work[RESOURCE_NUM];
for (int i = 0; i < RESOURCE_NUM; i++) {
work[i] = available[i];
}
bool finish[PROCESS_NUM] = {false};
int count = 0;
while (count < PROCESS_NUM) {
bool found = false;
for (int i = 0; i < PROCESS_NUM; i++) {
if (!finish[i]) {
int j;
for (j = 0; j < RESOURCE_NUM; j++) {
if (max[i][j] - allocation[i][j] > work[j]) {
break;
}
}
if (j == RESOURCE_NUM) {
for (int k = 0; k < RESOURCE_NUM; k++) {
work[k] += allocation[i][k];
}
finish[i] = true;
found = true;
count++;
}
}
}
if (!found) {
break;
}
}
return count == PROCESS_NUM;
}
int main() {
if (is_safe()) {
printf("系统处于安全状态，可以进行资源一次性分配\n");
} else {
printf("系统处于不安全状态，无法进行资源一次性分配\n");
}
return 0;
}
- 运行中释放资源 进程在请求新资源之前，先释放它已占有的所有资源，然后再重新申请所需的全部资源。例如，一个进程在处理复杂任务时，可能先占用了一些临时文件资源，当它需要申请新的网络资源时，先释放临时文件资源，再同时申请临时文件资源和网络资源。这样做虽然可以避免占有并等待条件导致的死锁，但可能会增加系统开销，因为资源的释放和重新申请会涉及到额外的系统调用和资源管理操作。
破坏不可剥夺条件
- 优先级剥夺 当一个低优先级进程占用了高优先级进程所需的资源时，操作系统可以剥夺低优先级进程的资源分配给高优先级进程。例如，在一个实时操作系统中，实时任务具有较高的优先级。如果一个后台任务占用了实时任务所需的 CPU 资源，操作系统可以暂停后台任务，将 CPU 资源分配给实时任务。然而，这种方法需要操作系统具备完善的优先级管理机制，并且在剥夺资源时要确保低优先级进程的状态能够被正确保存和恢复，否则可能导致低优先级进程运行异常。
- 超时剥夺 为进程设置资源占用超时时间。如果一个进程在规定时间内没有完成对资源的使用，操作系统自动剥夺其资源。比如，在数据库系统中，一个事务获取了某条数据的锁，如果在一定时间内（如 10 秒）没有完成操作并释放锁，数据库管理系统可以强制剥夺这把锁，分配给其他等待的事务。这种方法的关键在于合理设置超时时间，时间过短可能导致进程频繁被剥夺资源，影响正常运行；时间过长则可能无法及时解除死锁。
破坏循环等待条件
- 资源分配顺序法 为系统中的资源分配一个全局的顺序，例如按照资源的类型或编号进行排序。进程在申请资源时，必须按照这个顺序依次申请。假设系统中有资源 R1、R2、R3，规定申请顺序为 R1 -> R2 -> R3。如果一个进程需要 R2 和 R3 资源，它必须先申请 R1（即使它实际上并不需要 R1），然后申请 R2，最后申请 R3。这样就避免了循环等待的情况，因为按照这种顺序申请资源，不会形成资源请求的环。
以下是一个简单的 Java 示例，演示资源分配顺序法：
import java.util.ArrayList;
import java.util.List;
class Resource {
private int id;
public Resource(int id) {
this.id = id;
}
public int getId() {
return id;
}
}
class Process {
private int id;
private List<Resource> resources = new ArrayList<>();
public Process(int id) {
this.id = id;
}
public boolean requestResources(List<Resource> requestedResources) {
// 假设资源已经按照规定顺序排列
List<Resource> availableResources = new ArrayList<>();
// 模拟获取可用资源
for (Resource resource : requestedResources) {
if (availableResources.contains(resource)) {
resources.add(resource);
availableResources.remove(resource);
} else {
// 资源不足，申请失败
return false;
}
}
return true;
}
}
public class ResourceAllocationOrder {
public static void main(String[] args) {
Resource r1 = new Resource(1);
Resource r2 = new Resource(2);
Resource r3 = new Resource(3);
List<Resource> process1Request = new ArrayList<>();
process1Request.add(r1);
process1Request.add(r2);
List<Resource> process2Request = new ArrayList<>();
process2Request.add(r1);
process2Request.add(r3);
Process p1 = new Process(1);
Process p2 = new Process(2);
if (p1.requestResources(process1Request)) {
System.out.println("进程 1 资源申请成功");
} else {
System.out.println("进程 1 资源申请失败");
}
if (p2.requestResources(process2Request)) {
System.out.println("进程 2 资源申请成功");
} else {
System.out.println("进程 2 资源申请失败");
}
}
}
- 层次分配法 将资源划分为不同的层次，进程只能从较低层次的资源开始申请，只有当较低层次的资源全部申请成功后，才能申请更高层次的资源。例如，在一个大型项目管理系统中，可以将资源分为基础数据资源层、业务逻辑资源层和用户界面资源层。进程必须先获取基础数据资源，再获取业务逻辑资源，最后获取用户界面资源。这种方法同样可以避免循环等待，因为资源申请是按照层次逐步进行的，不会出现环。
死锁避免策略
银行家算法
- 算法原理 银行家算法是一种经典的死锁避免算法，它基于系统资源分配的安全性检查。假设一个银行家拥有一定数量的资金，多个客户分别需要不同数量的贷款。银行家在给每个客户贷款时，要确保不会因为贷款而导致自己无法满足其他客户的合理需求，从而避免出现资金链断裂（类似死锁）的情况。 在操作系统中，银行家算法将系统资源类比为银行家的资金，进程类比为客户，进程对资源的请求类比为客户对贷款的请求。算法通过检查系统当前的资源分配状态，判断是否存在一种安全序列，即所有进程都能按照某种顺序依次获得所需资源并运行结束。如果存在安全序列，则系统处于安全状态，可以满足进程的资源请求；否则，系统处于不安全状态，不能满足该请求，以避免死锁。
- 算法步骤
- 数据结构定义：
Available：表示系统中每种资源的可用数量，是一个一维数组。Max：表示每个进程对每种资源的最大需求量，是一个二维数组，Max[i][j]表示进程i对资源j的最大需求量。Allocation：表示每个进程当前已分配到的每种资源的数量，也是一个二维数组，Allocation[i][j]表示进程i当前已分配到的资源j的数量。Need：表示每个进程还需要的每种资源的数量，Need[i][j] = Max[i][j] - Allocation[i][j]，同样是一个二维数组。
- 安全性检查：
- 初始化一个数组
Work，其值等于Available。 - 初始化一个布尔数组
Finish，表示每个进程是否已经完成，初始值都为false。 - 寻找一个进程
i，使得Need[i][j] <= Work[j]对于所有的资源类型j都成立，并且Finish[i]为false。 - 如果找到了这样的进程
i，则假设该进程获得所需资源并运行结束，更新Work和Finish。Work[j] = Work[j] + Allocation[i][j]，Finish[i] = true。 - 重复上述步骤，直到所有进程都满足
Finish[i] = true，则系统处于安全状态；否则，系统处于不安全状态。
- 初始化一个数组
- 资源请求处理：
- 当一个进程
Pi发出资源请求Requesti时，首先检查Requesti[j] <= Need[i][j]对于所有的资源类型j是否成立，如果不成立，则表示进程Pi的请求超过了它的最大需求，拒绝请求。 - 然后检查
Requesti[j] <= Available[j]对于所有的资源类型j是否成立，如果不成立，则表示当前系统资源不足，无法满足请求，拒绝请求。 - 如果上述两个条件都满足，则假设系统将资源分配给进程
Pi，即Available[j] = Available[j] - Requesti[j]，Allocation[i][j] = Allocation[i][j] + Requesti[j]，Need[i][j] = Need[i][j] - Requesti[j]。 - 接着进行安全性检查，如果分配后系统仍然处于安全状态，则实际分配资源；否则，撤销刚才的假设分配，拒绝请求。
- 当一个进程
- 数据结构定义：
以下是一个用 Python 实现的银行家算法示例：
# 定义资源总量
available = [3, 3, 2]
# 定义每个进程对资源的最大需求量
max_demand = [
[7, 5, 3],
[3, 2, 2],
[9, 0, 2]
]
# 定义每个进程当前已分配到的资源数量
allocation = [
[0, 1, 0],
[2, 0, 0],
[3, 0, 2]
]
def is_safe(available, max_demand, allocation):
need = []
for i in range(len(max_demand)):
need.append([max_demand[i][j] - allocation[i][j] for j in range(len(available))])
work = available.copy()
finish = [False] * len(max_demand)
count = 0
while count < len(max_demand):
found = False
for i in range(len(max_demand)):
if not finish[i]:
can_allocate = True
for j in range(len(available)):
if need[i][j] > work[j]:
can_allocate = False
break
if can_allocate:
for j in range(len(available)):
work[j] += allocation[i][j]
finish[i] = True
found = True
count += 1
if not found:
break
return count == len(max_demand)
def request_resources(process_id, request, available, max_demand, allocation):
need = [max_demand[process_id][j] - allocation[process_id][j] for j in range(len(available))]
for j in range(len(available)):
if request[j] > need[j]:
print("进程请求超过最大需求，拒绝请求")
return False
if request[j] > available[j]:
print("系统资源不足，拒绝请求")
return False
for j in range(len(available)):
available[j] -= request[j]
allocation[process_id][j] += request[j]
need[j] -= request[j]
if is_safe(available, max_demand, allocation):
print("资源分配成功")
return True
else:
print("分配后系统不安全，拒绝请求")
for j in range(len(available)):
available[j] += request[j]
allocation[process_id][j] -= request[j]
need[j] += request[j]
return False
# 模拟进程请求资源
request = [0, 1, 0]
process_id = 0
request_resources(process_id, request, available, max_demand, allocation)
资源分配图算法的优化
- 资源分配图的化简与检测 在资源分配图算法的基础上进行优化，通过不断化简资源分配图来检测死锁并避免死锁的发生。当一个进程请求资源时，先将请求边加入资源分配图，然后尝试对图进行化简。化简的过程是找到一个既不请求资源（其请求边集合为空），又持有资源（其分配边集合不为空）的进程，将该进程及其相关的边从图中删除。重复这个过程，如果最终图中所有进程都被删除，则系统处于安全状态，可以满足该请求；否则，图中存在不可化简的环，系统处于不安全状态，拒绝请求。
- 动态资源分配与检测 该优化方法可以实时根据系统资源的动态变化对资源分配图进行更新和检测。例如，当一个进程释放资源时，及时更新资源分配图中相关的边，并重新进行化简操作，以判断系统是否仍然处于安全状态。这样可以更灵活地应对系统资源的动态变化，避免因资源的动态释放和重新分配而导致死锁。
死锁解除策略
资源剥夺法
- 基于优先级的资源剥夺 操作系统根据进程的优先级来决定剥夺哪些进程的资源。当死锁发生时，优先剥夺低优先级进程的资源，分配给参与死锁的高优先级进程，使高优先级进程能够继续运行，从而打破死锁局面。例如，在一个多任务操作系统中，实时任务通常具有较高的优先级。如果实时任务与普通任务发生死锁，操作系统可以剥夺普通任务的资源，确保实时任务能够正常运行。在剥夺资源时，需要保存被剥夺进程的状态，以便在合适的时候恢复其运行。
- 基于资源类型的资源剥夺 根据资源的类型来决定剥夺哪些资源。对于一些可恢复性较好的资源，如内存空间、文件描述符等，可以优先剥夺这些资源。例如，当死锁发生时，如果某个进程占用了大量的内存资源，而其他进程因为缺少内存无法运行，操作系统可以剥夺该进程的部分内存，分配给其他进程，以解除死锁。同时，要确保被剥夺资源的进程在后续能够重新获取这些资源并正常运行。
进程终止法
- 终止单个进程 在死锁发生时，选择终止参与死锁的一个进程。选择的依据可以是进程的优先级、已运行时间、资源占用量等因素。例如，选择优先级最低、已运行时间较短且资源占用量较大的进程进行终止。终止进程后，它所占用的资源将被释放，其他进程可能因此获得足够的资源而继续运行，从而解除死锁。然而，这种方法可能会导致被终止进程的工作丢失，需要谨慎选择终止的进程。
- 终止多个进程 当终止单个进程无法解除死锁时，可以考虑终止多个进程。操作系统可以按照一定的策略，如同时终止参与死锁的所有进程，或者按照一定顺序逐步终止多个进程，直到死锁解除。例如，在一个复杂的分布式系统中，可能存在多个进程相互死锁，此时可以通过终止多个相关进程来快速恢复系统的正常运行。但这种方法对系统的影响较大，可能会导致大量的工作丢失和系统性能的波动，因此应尽量在其他方法无效时才使用。
重启系统法
- 软重启 软重启是指在不关闭硬件设备的情况下，重新启动操作系统。当死锁非常严重，其他方法都无法有效解除死锁时，可以选择软重启。软重启可以快速恢复系统的正常运行状态，所有进程重新开始启动。然而，软重启会导致正在运行的所有进程的工作丢失，并且在重启过程中可能会对系统数据造成一定的影响，如未保存的文件可能丢失。因此，在进行软重启之前，应尽量尝试其他解除死锁的方法。
- 硬重启 硬重启是指直接关闭计算机的电源，然后再重新开机。这是一种极端的解除死锁方法，只有在系统完全瘫痪，软重启也无法进行的情况下才使用。硬重启会对硬件设备造成一定的冲击，可能会损坏硬盘等存储设备上的数据，同时也会丢失所有正在运行的进程的工作。所以，硬重启应作为最后的手段，并且在重启后需要对系统进行全面的检查和修复。