面试题：并发与同步之死锁检测技术基础

Question

请简述死锁检测的常用算法有哪些，并说明其中一种算法的基本原理。

Answer 1

死锁检测常用算法

1. 资源分配图算法（Resource Allocation Graph Algorithm）：通过分析系统资源分配图来检测死锁。
2. 银行家算法（Banker's Algorithm）：该算法可用于预防死锁，也能在一定程度上检测死锁，它基于资源分配状态和进程对资源的需求预测来判断系统是否处于安全状态，进而判断是否可能发生死锁。
3. 深度优先搜索算法（Depth - First Search Algorithm）：在资源分配图的基础上，使用深度优先搜索遍历图来检测是否存在环，环的存在意味着可能发生死锁。

资源分配图算法基本原理

1. 资源分配图：由进程节点（P）和资源节点（R）组成。有向边从进程指向资源表示进程请求资源，从资源指向进程表示资源已分配给该进程。
2. 算法步骤：
   • 简化资源分配图：找出既不阻塞又非孤立的进程节点。这类进程可运行直至完成，并释放其占用的所有资源，此时从图中移除该进程的所有相关边。
   • 重复简化过程：持续寻找可移除的进程节点并移除其边，直至无法继续简化。
   • 死锁判断：若最终图中所有节点都被移除，说明系统无死锁；若图中仍存在无法移除的节点，这些节点构成的子图就是死锁环，表明系统发生死锁。