5.死锁

如果一个进程集合中的每一个进程都在等待只能由该进程集合中的其它进程才能引发的事件，那么该进程集合就是死锁（deadlock）的。

大部分死锁和资源有关。资源是进程/线程为了完成工作，所需要的实体

• 可重用资源：CPU、内存、文件、设备……
• 可消耗资源：缓冲区产品、IPC的消息、中断……
• 可抢占资源：CPU、内存（有挂起）……
• 不可抢占资源：打印机、内存（无挂起）、文件……

死锁发生的条件

• 互斥（Mutual exclusion）

• 任何时刻只能有一个进程使用一个资源实例

• 请求和保持（Hold-and-wait，持有并等待 ）

• 进程持有至少一个资源，并正在等待获取其他进程持有的资源

• 不可抢占（No preemption）

• 资源只能在进程使用后自愿释放

• 循环等待（Circular Wait）

• 存在一个进程集合{P0，P1，...，PN}
• P0正在等待P1所占用的资源，P1 正在等待P2占用的资源……PN正在等待P0所占用的资源

如果四个条件中的任何一个不满足，死锁将不会发生

如果发生了死锁，四个条件一定都已满足

死锁的预防

死锁预防（Deadlock Prevention）

破坏四个必要条件之一，确保系统永远不会进入死锁状态

• 破坏“互斥”条件（资源不可分享，任一时刻只有一个进程可以使用该资源的一个实例）
  
• 破坏“持有并等待”条件（进程持有至少一个资源，并正在等待获取其他进程持有的资源）进程在开始执行时，一次请求所有需要的资源，要么拥有全部资源，要么不拥有资源例：申请全局锁后再申请全部资源缺点：

1. 资源利用率低，并发性被降低；
2. 饥饿，如果所需资源不断被其它进程使用

• 破坏“不可抢占”条件（资源只能在进程使用后自愿释放）如果资源本身是可以抢占的，则并不会死锁。当进程请求了不能立即分配的资源，则将自己已占用的资源也释放。在交通死锁的例子中，车辆如果发现不能通过就倒车缺点：

1. 代价太大（打印机、刻录机、扫描仪）
2. 可能造成反复申请-释放资源，进程的执行被无限制的延迟（活锁）

• 破坏“循环等待”条件（存在一个进程-资源的循环链）对资源排序，要求进程按顺序请求资源缺点：

1. 应用程序员完全可以无视此规定
2. 由于大型程序资源依赖关系复杂且普遍封装，难以设计和测试

小结

死锁避免（Deadlock Avoidance）

• 提前进行判断，只允许不会出现死锁的进程请求资源

避免死锁就是确保系统不会进入不安全状态

安全状态一定不会死锁，不安全状态可能死锁

所谓安全状态，是指系统能按某种进程顺序如<P1，P2，…，Pn>，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。

若系统不存在这样一个安全序列，称系统处于不安全状态

银行家算法：判断是否存在某个进程执行顺序，让系统能安全运行，并找到他

死锁检测和恢复（Deadlock Detection & Recovery）

• 在检测到运行系统进入死锁状态后，进行恢复

资源分配图，可以看出是否出错

终极方法：鸵鸟方法

操作系统忽略死锁，不做任何处理