面试题：并发与同步：死锁预防策略中的资源分配图算法原理

Question

请简述死锁预防策略中资源分配图算法（如资源分配图算法（RAG）算法）的基本原理，并说明如何利用它来检测和预防死锁。

Answer 1

资源分配图算法（RAG）基本原理

资源分配图（Resource Allocation Graph）由节点和边组成。节点分为进程节点（用圆圈表示）和资源节点（用方框表示，方框内的小点表示该资源类型的实例数量）。边分为请求边（从进程节点指向资源节点，表示进程请求该资源）和分配边（从资源节点指向进程节点，表示资源已分配给该进程）。

利用RAG检测死锁

1. 算法步骤：
   • 查找图中是否存在环。如果不存在环，则系统没有死锁；若存在环，且环中的每个资源类型都只有一个实例，那么系统处于死锁状态。
   • 若环中的资源类型有多个实例，还需进一步分析。可以通过尝试打破环来判断，比如暂时剥夺某个进程已分配的资源，看环是否能消除。如果不能通过合理的资源剥夺消除环，则存在死锁。
2. 检测方法示例：
   • 可以使用深度优先搜索（DFS）算法来检测环。从某个进程节点开始，沿着请求边和分配边进行遍历，若在遍历过程中再次访问到已访问过的进程节点，说明存在环。

利用RAG预防死锁

1. 策略：
   • 每次资源请求发生时，构建或更新资源分配图。然后运行死锁检测算法。如果检测到可能产生死锁（例如即将形成环），则拒绝此次资源请求，从而预防死锁的发生。
   • 例如，当一个进程请求资源时，系统先假设将该资源分配给该进程，构建新的资源分配图，检测是否形成环。若形成环，就不进行资源分配，避免死锁。