目录

• 必要条件
• 处理方法
  • 鸵鸟策略
  • 死锁检测与死锁恢复
    • 1.每种类型一个资源的死锁检测
    • 2.每种类型多个资源的死锁检测
    • 3.死锁恢复
  • 死锁预防
    • 1.破坏互斥条件
    • 2.破坏占有和等待条件
    • 3.破坏不可抢占条件
    • 4.破坏环路等待
  • 死锁避免
    • 1.安全状态
    • 2.单个资源的银行家算法
    • 3.多个资源的银行家算法

1.必要条件

• 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。

• 占有和等待：已经得到了某个资源的进程可以再请求新的资源。

• 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。

• 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

2.处理方法

2.1.鸵鸟策略

• 定义：忽略死锁，就像鸵鸟把头埋在沙子里，假装根本没发生问题。

• 适用场景：

  • a）解决死锁问题的代价很高
  • b）发生死锁时不会对用户造成多大影响
  • c）发生死锁的概率很低(资源充足)

• Tips：大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

2.2.死锁检测与死锁恢复

• 定义：不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

每种类型一个资源的死锁检测

• 通过检测有向图是否存在环来实现

  从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

每种类型多个资源的死锁检测

• EACR算法
  每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

每种类型多个资源的死锁检测

• EACR算法
  每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

死锁恢复

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

2.3.死锁预防

• 定义：在程序运行之前预防发生死锁。

• 预防方法：

  • a）破坏互斥条件
    打印机守护进程允许多个进程同时输出
  • b）破坏占有和等待条件
    一次性申请全部资源，再进行占有
  • c）破坏不可抢占条件
    允许抢夺其他进程的资源
  • d) 破坏环路等待
    资源统一编号，按照编号顺序来进行请求（哲学家进餐问题解决思路——破坏环路等待，给筷子编号，并且只允许先从编号小的筷子开始申请）

2.4.死锁避免

• 定义：在程序运行时避免发生死锁。

• 方法：

  • a）安全状态算法——Has Max矩阵 存在合法调度顺序的为安全状态
  • b）单个资源的银行家算法
  • c）多个资源的银行家算法

原文

https://github.com/CyC2018/CS-Notes/blob/master/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%20-%20%E6%AD%BB%E9%94%81.md