面试题：操作系统并发与同步：死锁检测与恢复机制

Question

假设在一个多进程系统中，已知当前各进程的资源分配情况和资源请求情况，如何设计一个算法来检测系统是否处于死锁状态？如果检测到死锁，有哪些常用的死锁恢复方法，它们各自的优缺点是什么？

Answer 1

检测系统是否处于死锁状态的算法设计

1. 资源分配图算法（如死锁定理）：
   • 构建资源分配图，图中的节点分为进程节点和资源节点。进程节点到资源节点的边表示进程请求资源，资源节点到进程节点的边表示资源已分配给进程。
   • 尝试对资源分配图进行化简，若能完全化简（所有进程节点都能被消除），则系统没有死锁；否则，系统处于死锁状态。
2. 银行家算法的扩展：
   • 记录系统中每种资源的总量 Available，每个进程已分配的资源量 Allocation，每个进程还需要的资源量 Need。
   • 尝试寻找一个进程 P_i，使得 Need[i] <= Available，若能找到，则假设将这些资源分配给该进程，更新 Available = Available + Allocation[i]，并将该进程标记为可运行完成。
   • 重复上述步骤，若所有进程都能被标记为可运行完成，则系统没有死锁；否则，系统处于死锁状态。

死锁恢复方法及优缺点

1. 终止进程：
   • 优点：实现简单直接，快速打破死锁。
   • 缺点：若终止的是重要进程，可能导致系统功能部分丧失，数据丢失，对系统影响较大。而且可能需要终止多个进程才能解除死锁。
2. 资源剥夺：
   • 优点：可以在不终止进程的情况下解除死锁，对系统的影响相对较小，能保持部分进程的运行。
   • 缺点：选择剥夺资源的进程比较困难，可能导致被剥夺资源的进程运行异常，甚至需要重新执行之前的操作，增加系统开销。而且可能导致“饥饿”现象，某些进程一直被剥夺资源无法执行。
3. 回滚进程：
   • 优点：保留进程运行成果，仅将进程回滚到之前某个状态，重新执行，相对终止进程对进程的影响小。
   • 缺点：需要记录进程运行的历史状态，占用额外的存储空间，回滚操作本身也有一定开销，并且难以确定回滚到哪个状态最合适。