Lecture 11 Deadlocks （死锁）

1 死锁的特征

哲学家用餐死锁问题

DEADLOCKS

• 在进程并发环境中，多个进程可能争夺有限数量的资源。
• 一个进程请求资源;如果资源不是此时可用，进程进入等待状态。
• 有时，等待过程再也无法更改状态，因为它请求的资源是由其他等待进程持有。
• 这种情况称为死锁。

死锁与饥饿

• 饥饿：进程长时间的等待
  • e.g.低优先级进程总是等待高优先级所占有的进程
• 死锁：循环等待资源
  • A和B分别占有打印机和扫描仪
  • 同时分别申请扫描仪和打印机
• 死锁 => 饥饿 (反之不亦然)
  • 饥饿可能终止
  • 如果无外部干涉，死锁无法终止

产生死锁的四个必要条件

• 互斥使用
  • 一个时刻，一个资源仅能被一个进程占有
• 不可剥夺
  • 除了资源占有进程主动释放资源，其它进程都不可抢夺其资源
• 占有和等待
  • 一个进程请求资源得不到满足等待时，不释放已占有资源
• 循环等待(上面三个条件同时存在产生的结果)
  • 每一个进程分别等待它前一个进程所占有的资源

三种观点

• 保守派：不允许出现死锁。我们必须防止或避免死锁状态。
• 进步派：允许出现死锁，但系统可以检测到他们和恢复。
• 佛系派：我们假装系统中从未发生过死锁。

死锁的解决方案

• 死锁的防止 (Prevention)
  • 破坏四个必要条件之一
• 死锁的避免 (Avoidance)
  • 允许四个必要条件同时存在，在并发进程中做出妥善安排避免死锁的发生
• 死锁的检测和恢复 (Detection)
  • 允许死锁的发生，系统及时地检测死锁并解除它
    

2 死锁的防止

破坏死锁任一必要条件

• 互斥使用
• 不可剥夺
• 占有和等待
• 循环等待
  

3 死锁的避免


死锁的避免

• 系统对进程的每一次资源申请都进行详细的计算，根据结果决定是分配资源还是让其等待，确保系统始终处于安全状态，避免死锁的发生。
• 银行家算法（Banker’s algorithm）
  • 已知系统中所有资源的种类和数量
  • 已知进程所需要的各类资源最大需求量
  • 该算法可以计算出当前的系统状态是否安全(寻找安全序列)

银行家算法的优缺点

• 优点：允许死锁必要条件同时存在
• 缺点：缺乏实用价值
  • 进程运行前就要求知道其所需资源的最大数量
  • 要求进程是无关的，若考虑同步情况，可能会打乱安全序列
  • 要求进入系统的进程个数和资源数固定
    

4 死锁的检测

死锁的检测与恢复

• 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生
• 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
• 死锁检测的时机
  • 当进程等待时检测死锁（系统开销大）
  • 定时检测
  • 系统资源利用率下降时检测死锁


死锁定理

• 如果能在“资源分配图”中消去某进程的所有请求边和分配边，则称该进程为孤立结点。
  • 可完全简化
  • 不可完全简化
• 系统为死锁状态的充分条件是：当且仅当该状态的“进程―资源分配图”是不可完全简化的。该充分条件称为死锁定理。

死锁的解除

• 中止进程，强制回收资源
  • 交通问题：将某列火车吊起来
  • 哲学家问题：将某个哲学家射死
• 剥夺资源，但不中止进程
• 进程回退(roll back)
  • 就像DVD的回退，好像最近一段时间什么都没有发生过
  • 交通问题：让某列火车倒车
  • 哲学家问题：让某个哲学家放下一把叉子
• 重新启动
  • 没有办法的办法，但却是一个肯定有效的办法

当发生死锁时操作系统会做什么

• 在缺乏算法来检测和恢复的情况下死锁，我们可能会遇到系统的情况处于僵局状态，但无法识别什么已经发生了。在这种情况下，未检测到的死锁将导致系统性能下降，因为资源被无法运行的进程占用，并且因为越来越多的流程，因为他们提出请求资源，将进入死锁状态。最终，系统将停止运行，需要手动地重新启动。
• 尽管这种方法似乎不是一种可行的方法对于死锁问题，它仍然用于大多数操作系统。