死锁检测 (Deadlock Detection)

死锁检测是处理死锁的一种策略,它不预防也不避免死锁,而是周期性地检查系统状态,一旦发现进程间形成循环等待就判定死锁并采取恢复措施。这与死锁预防和死锁避免形成对比,后者在事前限制资源分配。

概述

死锁的四个必要条件是互斥、持有并等待、不可剥夺和循环等待。当这些条件同时满足时,若干进程会互相等待对方持有的资源而永久阻塞。死锁检测放宽了对分配的限制,让系统正常运行,只在必要时才检查,适合死锁发生频率较低的场景。

核心原理

• 资源分配图:用节点表示进程和资源,用有向边表示请求与占用关系。
• 单实例检测:若每类资源只有一个实例,图中存在环即表示死锁。
• 多实例检测:资源有多个实例时,单纯有环不足以判定,需用类似银行家算法的检测算法,尝试寻找可完成的进程序列。
• 检测时机:可在每次资源请求时检测,也可定时或在CPU利用率下降时触发。
• 死锁恢复:发现死锁后可终止部分进程、抢占资源或回滚到安全检查点。

应用场景

数据库管理系统广泛使用死锁检测,当多个事务因锁互相等待时,数据库会检测到等待环并选择代价最小的事务作为牺牲者回滚。分布式系统和某些操作系统内核也用类似机制处理资源竞争。

常见问题

问:死锁检测和死锁避免有什么不同?答:死锁避免在分配前判断是否会进入不安全状态从而拒绝分配;死锁检测则允许死锁发生,事后再发现并恢复,运行时限制更少但需要恢复代价。

问:检测到死锁后如何选择牺牲进程?答:通常按优先级、已运行时间、占用资源数量、回滚代价等因素综合评估,选择终止或回滚代价最小的进程,并注意避免同一进程反复被选造成饥饿。