09 死锁 | 《操作系统》笔记

这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

死锁问题

• 一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源

系统模型

• 可重复使用的资源
  • 在一个时间只能一个进程使用且不能被删除
  • 进程获得资源，后来释放由其他进程重用
  • 处理器、I/O 通道、主和副存储器、设备和数据结构，如文件、数据库和信号量
  • 如果每个进程拥有一个资源并请求其它资源，死锁可能发生
• 如何使用资源
  • 创建和销毀
  • 在 I/O 缓冲区的中断、信号、消息、信息
  • 如果接收消息阻塞可能会发生死锁
  • 可能少见的组合事件会引起死锁
• 资源分配图：一组顶点 V 和边 E 的集合
  • 
  • 
  • 几个例子
    • 无死锁
    • 有死锁（有环路）
    • 有环路但没有死锁
  • 总结
    • 如果图中不包含循环
      • 没有死锁
    • 如果图中包括循环
      • 如果每个资源类只有一个实例，那么死锁
      • 如果每个资源类有几个实例，可能死锁

死锁特征

• 死锁出现后会出现这四种情况，出现这四种情况有可能会有死锁
  • 互斥：在一个时间只能有一个进程使用资源
  • 持有并等待：进程保持至少一个资源正在等待获取其他进程持有的额外资源
  • 无抢占：一个资源只能被进程自愿释放，进程已经完成了它的任务之后
  • 循环等待：存在等待进程集合 {P0,P1,…,PN}，P0 正在等待 P 所占用的资源，P1 正在等待 P2 占用的资源，……，PN-1 在等待 N 所占用资源，PN 正在等待 P0 所占用的资源

死锁处理方法

• 死锁预防 (Deadlock prevention)
  • 限制申请方式（打破必要条件）
    • 互斥：只占用共享资源（不太可行）
    • 持有并等待：拿到全部需要的资源后才执行（资源利用率低，可能发生饥饿）
    • 无抢占：kill 掉持有目的资源的进程（暴力、极端、强势）
  • 循环等待：对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请（嵌入式系统中应用较多，因为其中资源类型有限）
• 死锁避免 (Deadlock avoidance)：比预防放松了条件限制
  • 需要系统具有一些额外的先验信息提供
    • 最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目
    • 资源的分配状态是通过限定提供与分配的资源数量，和进程的最大需求
    • 死锁避免算法动态检査的资源分配状态，以确保永远不会有一个环形等待状态
  • 当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态
  • 系统处于安全状态指：针对所有进程，存在安全序列
  • 
  • 概念比较
    • 如果系统处于安全状态：无死锁。
    • 如果系统处于不安全状态：可能死锁
    • 避免死锁：确保系统永远不会进入不安全状态
    • 
  • 银行家算法
    • 银行家算法 (Banker’s algorithm) 是一个死锁避免的著名算法，是由艾兹格·迪杰斯特拉在 1965 年为 T.H.E 系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行
    • 略
• 死锁检测 (Deadlock detection)：允许系统进入死锁状态，再一次放松了条件限制
  • 
  • 死锁检测算法
    • 略
  • 使用死锁检测算法中需要关注的问题
    • 何时、使用什么样的频率来检测依赖于死锁多久可能会发生？
    • 何时、使用什么样的频率来检测依赖于多少进程需要被回滚？one for each disjoint cycle
    • 如果检测算法多次被调用，有可能是资源图有多个循环，所以无法分辨出多个可能死锁进程中的哪些“造成”死锁
• 死锁恢复 (Recovery from deadlock)
  • 终止所有的死锁进程
  • 在一个时间内终止一个进程直到死锁消除
  • 终止进程的顺序应该是
    • 进程的优先级
    • 进程运行了多久以及需要多少时间才能完成
    • 进程占用的资源
    • 进程完成需要的资源
    • 多少进程需要被终止
    • 进程是交互还是批处理