面试题：并发与同步之死锁检测特殊场景下的基础应对思路

Question

在一个多线程并发的操作系统环境中，假设存在进程资源分配图，其中有进程 P1、P2、P3，资源 R1、R2、R3 。P1 持有 R1 并请求 R2，P2 持有 R2 并请求 R3，P3 持有 R3 并请求 R1，这种典型的死锁场景下，简述死锁检测算法的基本步骤以及如何打破死锁？

Answer 1

死锁检测算法基本步骤

1. 构建资源分配图：根据进程和资源的分配与请求关系，构建进程资源分配图（如题目中的P1、P2、P3与R1、R2、R3的关系）。
2. 化简资源分配图：
   • 寻找一个既不阻塞又非孤立的进程节点。若存在这样的进程，意味着该进程能获得所需资源并运行完成，释放其占有的所有资源。
   • 从资源分配图中移除该进程及其相关的边（包括请求边和分配边），这相当于模拟该进程运行结束释放资源的过程。
   • 重复上述步骤，持续化简资源分配图。
3. 判断是否存在死锁：若最终资源分配图能化简为空图，则系统不存在死锁；若无法化简为空图，即存在不可化简的子图，则说明系统出现死锁，不可化简子图中的进程处于死锁状态。

打破死锁的方法

1. 终止进程：
   • 选择一个或多个死锁进程终止：可选择终止那些资源占有量少、优先级低或预计运行时间长的进程，释放它们占有的资源，使其他进程能继续运行。例如终止P1，释放R1，P3获取R1后可运行完成并释放R3，P2获取R3后也能运行完成，从而打破死锁。
   • 一次性终止所有死锁进程：这种方法简单直接，但可能导致较大损失，因为所有死锁进程的工作都白费了，一般在没有更好办法时才使用。
2. 剥夺资源：
   • 从死锁进程中剥夺资源：选择一个死锁进程，剥夺其占有的部分资源给其他进程使用。例如从P2剥夺R2给P1，P1运行完成释放R1给P3，P3运行完成释放R3给P2，打破死锁。
   • 需要考虑资源的可剥夺性：某些资源（如打印机）可能不适合剥夺，需选择可剥夺的资源进行操作，同时要保证剥夺操作不会对进程产生过大影响。