OS: 面试
OS: 面试
ExisfarOS: 面试
如何避免死锁？
死锁的避免（Deadlock Avoidance）是一种通过动态评估资源分配的安全性来预防死锁的策略。其核心思想是在分配资源前预测是否会导致系统进入不安全状态，从而决定是否允许该次分配。以下是死锁避免的关键方法和技术：
1. 安全状态与不安全状态
• 安全状态：存在至少一个资源分配序列（安全序列），使得所有进程都能顺利完成，不会导致死锁。
• 不安全状态：不存在这样的序列，可能引发死锁（但不一定立即发生）。
死锁避免算法通过确保系统始终处于安全状态来预防死锁。
2. 银行家算法（Banker’s Algorithm）
最经典的死锁避免算法，由Dijkstra提出，模拟银行家放贷的过程：
核心数据结构
• Available：当前可用资源向量。
• Max：每个进程声明的最大资源需求矩阵。
• Allocation：已分配给各进程的资源矩阵。
• Need：每个进程还需要的资源矩阵（Need = Max - Allocation）。
算法步骤
-
安全性检查：
• 寻找一个进程，其Need≤Available。• 假设该进程完成并释放资源，更新
Available。• 重复上述过程，若所有进程都能完成，则系统处于安全状态。
-
资源请求处理：
• 当进程请求资源时，假设分配后检查系统是否仍安全。• 若安全则分配，否则拒绝请求（进程等待）。
示例
假设系统有3类资源（A/B/C），初始可用资源为 (10, 5, 7)：
• 进程P1请求 (1, 0, 2)：
• 检查请求是否 ≤ Need 和 Available。
• 模拟分配后执行安全性算法，若存在安全序列则批准。
3. 资源分配图算法（适用于单实例资源）
若每种资源只有一个实例，可通过在资源分配图中引入虚边（claim edge）预测环路：
• 虚边：表示进程未来可能请求某资源（用虚线表示）。
• 算法：仅在将虚边转为实边（实际请求）时不会形成环路才允许分配。
4. 死锁避免 vs. 死锁预防
| 特性 | 死锁避免 | 死锁预防 |
|---|---|---|
| 时机 | 动态（运行时决策） | 静态（设计时约束） |
| 方法 | 安全性检查（如银行家算法） | 破坏死锁必要条件之一（如互斥、持有等待） |
| 灵活性 | 高（按需分配） | 低（严格限制资源访问） |
| 开销 | 较高（需实时计算） | 较低（无需运行时检查） |
5. 局限性
• 适用场景受限：需要预先知道进程的最大资源需求（不适用于动态需求）。
• 性能开销：频繁的安全性检查可能影响系统吞吐量。
• 单实例资源扩展难：银行家算法在多实例资源中有效，但单实例资源需用其他方法。
总结
死锁避免通过动态评估资源分配的安全性来主动规避死锁，尤其适合资源需求可预测的系统。尽管实现复杂，但在关键系统（如操作系统、数据库）中能有效平衡安全性与效率。实际应用中常结合死锁检测（允许死锁发生后再恢复）和预防（如超时机制）形成多层级策略。
