第六章 作业管理与死锁处理
第三节 死锁处理
概述
本节内容深入探讨操作系统中死锁的概念及其处理方法。死锁是多道程序设计和资源共享环境下常见且严重的问题，若不能有效管理，可能导致系统性能急剧下降甚至完全停顿。学习本节，考生将掌握死锁的定义、产生条件、检测与解除策略，以及预防和避免死锁的常用方法。通过详细的原理分析和典型案例，帮助考生理解死锁处理的核心思想，并能在实际操作系统环境中识别和解决死锁问题。
学习目标：
- 理解死锁的概念和产生条件
- 掌握死锁的检测与解除技术
- 熟悉死锁的预防与避免策略
- 通过案例分析增强实际问题处理能力
- 识别常见误区，提升死锁处理的准确性
核心概念
死锁（Deadlock）
- 是指两个或多个进程在执行过程中因竞争资源而造成一种互相等待的状态，若无外力干涉，无法继续执行。
资源分配图（Resource Allocation Graph）
- 一种表示系统资源分配和进程请求状态的图形，顶点表示进程和资源，边表示请求或分配关系。
互斥条件（Mutual Exclusion）
- 指资源不能被多个进程共享，某时刻只有一个进程能占用该资源。
占有且等待（Hold and Wait）
- 进程至少已占有一个资源，同时又请求新的资源。
不可剥夺（No Preemption）
- 资源不能被强制从占有它的进程上夺取，必须由进程自行释放。
循环等待（Circular Wait）
- 存在一个进程环，每个进程等待环中下一个进程占有的资源。
死锁检测（Deadlock Detection）
- 通过算法检测系统是否进入死锁状态。
死锁解除（Deadlock Recovery）
- 采取措施终止死锁，恢复系统正常运行。
死锁预防（Deadlock Prevention）
- 通过破坏产生死锁的必要条件来避免死锁。
死锁避免（Deadlock Avoidance）
- 通过动态资源分配策略，确保系统永远不进入死锁状态。
原理分析
死锁的产生是由于系统中多个进程竞争资源时，满足“死锁的四个必要条件”：互斥、占有且等待、不可剥夺、循环等待。理解这四个条件是分析和解决死锁的基础。
- 互斥条件保证资源的独占性，防止资源被同时使用导致错误。
- 占有且等待使得进程在持有资源的同时等待其他资源，增加了死锁发生的可能。
- 不可剥夺意味着资源不能被强制收回，若进程不释放资源，其他等待的进程将被阻塞。
- 循环等待是死锁的核心特征，形成等待环路，导致进程相互牵制。
死锁处理策略主要有三种：
- 预防：破坏至少一个必要条件，确保死锁不发生。
- 避免：动态监控资源分配，确保系统不会进入不安全状态。
- 检测与解除：允许死锁发生，及时发现并采取措施恢复。
系统设计中往往根据不同需求选择合适策略，权衡资源利用率和系统复杂度。
详细内容
1. 死锁的定义与四个必要条件
死锁是指两个或多个进程因相互等待对方占用的资源，导致每个进程都无法继续执行的状态。死锁的发生需要同时满足以下四个条件：
- 互斥条件：资源不可共享，某时刻只被一个进程占用。
- 占有且等待条件：进程已占有资源且等待其他资源。
- 不可剥夺条件：资源不能被强制抢夺，只能由占用进程释放。
- 循环等待条件：存在一个进程环，每个进程等待下一个进程占用的资源。
这四个条件缺一不可，任何一项不满足，死锁就不会发生。
2. 资源分配图与死锁检测
资源分配图用来描述系统中进程与资源的分配状态，包括：
- 请求边（Request Edge）：从进程指向资源，表示进程请求该资源。
- 分配边（Assignment Edge）：从资源指向进程，表示资源已分配给进程。
死锁检测方法：
- 若资源分配图中存在环，则系统可能处于死锁状态。
- 对于单实例资源，存在环即死锁。
- 对于多实例资源，存在环不一定死锁，需要进一步检测。
检测算法一般周期执行，保证及时发现死锁。
3. 死锁解除方法
一旦检测到死锁，系统必须采取措施恢复，包括：
- 终止进程：强制撤销一个或多个死锁进程，释放资源。
- 资源剥夺：从某些进程中抢占资源，分配给其他进程。
选择终止进程时需考虑进程重要性、进度等因素；资源剥夺可能导致进程状态不一致，需谨慎处理。
4. 死锁预防技术
通过设计系统，破坏死锁的四个必要条件之一：
- 破坏互斥条件：部分资源可共享，减少死锁概率。
- 破坏占有且等待条件：要求进程一次性申请所有资源，或者释放所有资源后再申请。
- 破坏不可剥夺条件：允许强制抢占资源。
- 破坏循环等待条件：对资源编号，进程按顺序申请资源，避免循环等待。
预防策略简单有效，但可能降低资源利用率。
5. 死锁避免策略
死锁避免通过动态检测系统状态，确保系统永远不进入不安全状态，典型算法有：
- 银行家算法：根据进程最大需求和当前分配，判断是否安全。
- 安全序列判定：系统只分配资源，保证存在一个所有进程能顺利完成的序列。
死锁避免需要提前了解进程的最大资源需求，适用范围有限。
6. 死锁处理的权衡与选择
- 预防简单但资源利用率低。
- 避免算法复杂，适合需求明确的系统。
- 检测与解除适合资源紧张、进程动态的系统。
系统设计时应结合实际情况，选择合适的策略。
实例分析
案例一：打印机与扫描仪死锁
背景：两个进程P1和P2，P1需要打印机和扫描仪，P2也需要这两个资源。P1先获得打印机，P2先获得扫描仪，随后双方等待对方释放资源。
分析：
- 互斥条件满足，打印机和扫描仪不可共享。
- 占有且等待条件满足，P1和P2都持有资源且等待另一个。
- 不可剥夺条件满足，资源只能由进程释放。
- 形成循环等待，P1等待扫描仪，P2等待打印机。
结论：发生死锁。解决方案可采用资源剥夺或终止一个进程。
案例二：银行家算法避免死锁
背景：系统有3个资源单位，三个进程分别最大需求为(2,1,1)，当前分配(1,0,0)。系统通过银行家算法判断分配请求是否安全。
分析：
- 当进程请求资源时，系统模拟分配后通过安全性检测。
- 若存在安全序列，则分配资源。
- 否则拒绝请求，避免进入死锁状态。
结论：银行家算法有效避免了死锁，保证系统运行安全。
案例三：资源剥夺解除死锁
背景：系统检测到死锁，选择剥夺进程P3的资源，分配给等待的进程P1。
分析：
- 剥夺资源后，P3回滚或重新申请。
- P1获得足够资源后完成，释放资源。
- 其他进程继续运行，死锁解除。
结论：资源剥夺是有效的死锁解除方法，但需注意进程状态管理。
常见误区
误区：死锁等价于资源竞争
- 资源竞争是普遍现象，死锁是资源竞争的极端情况，必须满足四个条件。
- 正确做法：区分资源竞争和死锁，死锁需满足特定条件。
误区：只要检测到循环等待就一定死锁
- 多实例资源存在环不一定死锁。
- 正确做法：结合资源实例数，进一步分析是否真正死锁。
误区：死锁预防一定消除所有死锁可能
- 预防提高系统资源浪费，可能导致进程饥饿。
- 正确做法：结合系统需求合理设计，权衡资源利用和死锁风险。
误区：死锁解除总是通过终止进程
- 资源剥夺也是常用解除策略。
- 正确做法：根据实际情况选择最小代价的解除方案。
误区：银行家算法适用于所有系统
- 需要提前知道最大资源需求，不适合动态需求系统。
- 正确做法：根据需求动态性选择合适算法。
应用场景
多任务操作系统资源管理
- 各类系统资源（打印机、磁盘、内存）共享，防止死锁保证系统稳定。
数据库并发控制
- 事务锁机制避免死锁，保证数据一致性和系统吞吐。
分布式系统资源协调
- 跨网络资源请求，死锁检测与恢复机制保障系统可靠性。
嵌入式系统资源调度
- 实时任务资源分配，避免死锁导致系统卡死。
云计算与虚拟化管理
- 虚拟机资源分配，防止资源争用引起死锁，提升资源利用率。
知识拓展
死锁与饥饿（Starvation）区别：死锁是循环等待导致所有相关进程阻塞；饥饿是某进程长时间得不到资源，但系统整体不死锁。
死锁检测算法复杂度分析：资源分配图检测环的算法复杂度与系统规模相关，优化检测周期是研究重点。
分布式死锁检测：由于资源分布在不同节点，检测及解除更为复杂，涉及全局状态一致性问题。
软实时系统中的死锁处理：允许一定程度的资源抢占和任务回滚，保证系统响应时间。
现代操作系统中的死锁处理实例：Linux内核死锁检测机制、Windows资源管理策略等。
总结回顾
本节详细探讨了死锁的定义、产生条件和处理方法，重点如下：
- 死锁发生必须满足互斥、占有且等待、不可剥夺和循环等待四个必要条件。
- 资源分配图是分析死锁的重要工具，环的检测是判断死锁的关键。
- 死锁处理策略包括预防、避免和检测与解除，适用于不同系统需求。
- 典型算法如银行家算法实现死锁避免，资源剥夺及进程终止用于解除死锁。
- 通过案例分析，理解死锁产生的实际场景及解决方案。
- 识别常见误区，避免理论与实践中的错误理解。
- 死锁处理广泛应用于操作系统、数据库、分布式系统等领域。
掌握本节内容，考生将能够系统理解并实际解决死锁问题，为操作系统学习和应用打下坚实基础。