面试题：操作系统并发与同步下死锁检测与恢复策略的优化

Question

描述死锁检测算法的基本原理，并说明如何优化这些算法以提高检测效率。另外，阐述在检测到死锁后，如何制定并实施有效的恢复策略，同时尽量减少对系统正常运行的影响。

Answer 1

死锁检测算法基本原理

1. 资源分配图算法：
   • 系统用资源分配图（RAG）来描述进程对资源的请求和分配情况。图中节点分为进程节点（$P_i$）和资源节点（$R_j$），有向边分为请求边（$P_i \to R_j$，表示进程$P_i$请求资源$R_j$）和分配边（$R_j \to P_i$，表示资源$R_j$已分配给进程$P_i$）。
   • 死锁检测算法基于资源分配图的化简。若能通过一系列化简操作（移除所有分配边和请求边）使图中不存在环，则系统无死锁；若化简后仍存在环，则环中的进程处于死锁状态。
2. 银行家算法扩展：
   • 银行家算法原本用于死锁预防，通过检查资源分配是否处于安全状态来避免死锁。在死锁检测中，可在此基础上进行扩展。
   • 记录每个进程的资源需求（$Need$）、已分配资源（$Allocation$）以及系统剩余资源（$Available$）。
   • 尝试寻找一个进程序列，使得每个进程都能在当前系统资源状态下获取所需资源并运行完成，释放其占用资源。若找不到这样的序列，则可能存在死锁。

算法优化以提高检测效率

1. 数据结构优化：
   • 使用更高效的数据结构来存储资源分配图或相关状态信息。例如，采用邻接表来表示资源分配图，相比于邻接矩阵，在稀疏图（实际系统中资源分配图通常是稀疏的）情况下可减少存储空间和操作时间。
   • 对于银行家算法扩展，可使用优先队列来存储进程，按照进程需求资源量或优先级排序，优先检查需求资源少或优先级高的进程，加快安全序列查找速度。
2. 减少检测频率：
   • 并非每次资源分配或释放操作都进行死锁检测，可设置一个阈值，当资源分配或释放的次数达到一定阈值时才进行检测，这样能减少不必要的检测开销。
   • 根据系统运行特点，在系统负载较低、资源变化相对稳定的时间段进行检测，避免在系统繁忙时增加额外负担。
3. 局部检测：
   • 当系统规模较大时，可将系统划分为多个区域或子系统，仅在资源分配发生变化的局部区域进行死锁检测，而不是对整个系统进行全面检测。例如，在分布式系统中，仅对发生资源请求和分配的节点所在子区域进行检测。

死锁恢复策略及减少对系统正常运行影响

1. 终止进程：
   • 选择牺牲进程：优先选择那些优先级较低、运行时间较短或已占用资源较少的进程进行终止。例如，在分时系统中，可选择后台作业进程。通过这种方式，能尽量减少对重要业务或用户交互进程的影响。
   • 逐步终止：不要一次性终止多个进程，而是逐个终止并重新检测死锁状态。每次终止一个进程后检查是否已解除死锁，若未解除则继续终止下一个进程，这样可以避免过度终止进程对系统造成不必要的破坏。
2. 资源剥夺：
   • 选择剥夺对象：从死锁进程中选择占用关键资源但对系统整体影响较小的进程，剥夺其部分或全部资源分配给其他进程。例如，若某进程占用了一个通用资源且其执行进度较慢，可剥夺该资源。
   • 补偿机制：对于被剥夺资源的进程，可提供一定的补偿措施，如在系统资源充足时优先满足其资源请求，或给予一定的资源配额，以尽量减少对该进程后续执行的影响。
3. 回滚进程：
   • 记录检查点：在系统运行过程中，定期为进程创建检查点，记录进程的状态和已分配资源情况。
   • 回滚操作：当检测到死锁时，选择部分死锁进程回滚到最近的检查点，释放这些进程在检查点之后获取的资源，使系统回到一个可能无死锁的状态。回滚进程相比终止进程，能保留进程之前的部分执行成果，对系统正常运行影响相对较小。