操作系统拾遗--死锁与死锁避免预防检测

0. 概念

死锁：一组进程中的每一个进程都在等待只有这组进程中的进程才能触发的事件，就像两个人玩拼图，各自拿了对方想要的一块拼图，又不主动把拿到的放回拼图池里，导致两个人都拼不好拼图。

安全序列：指对当前申请资源的进程排出一个序列，保证按照这个序列分配资源能使进程最终都能完成。

1. 死锁产生的原因与条件

1.1. 死锁的原因：
通常是资源不够用或资源使用不当。如竞争不可抢占资源、竞争可消耗资源可能引起死锁

1.2. 产生死锁的必要条件

• 互斥：在同一段时间内资源只能被一个进程使用，如果其他进程申请该资源必须等待；
• 请求与保持：一个线程在请求新资源时，其已经获得的资源并不释放，而是继续持有；
• 不可抢占：分配给进程的资源，除非进程自己释放，其他进程不可抢夺资源使用；
• 循环等待：发生死锁时，存在一个进程-资源-进程的等待循环链；

2. 解决死锁的办法

策略：

• 三不管：操作系统认为死锁不会发生，任由死锁发生。
• 死锁预防：破坏死锁产生的必要条件。
• 死锁避免：在每次资源分配之前，计算分配资源之后是否会导致死锁，如果判断可能会产生死锁则不分配资源。
• 死锁检测与恢复：等死锁发生之后再进行检测与恢复。

2.1. 死锁预防

只要破坏上述四个必要条件中的一个即可。

• 互斥：不太可能，如打印机本身就不能同时访问。
• 不可抢占：对已获取某些资源的进程如果获取不到新的资源则放弃自身所有的资源。-->增加系统开销，降低系统吞吐量
• 请求与保持：可一次申请全部资源-->导致资源浪费
• 循环等待：采用有序资源分配法-->限制新资源增加、资源浪费、编码复杂。

2.2. 死锁避免

在资源分配之前，计算分配是否能让系统处于安全状态[能否找到安全序列]。

下面说说常用的死锁避免算法---Dijkstra的银行家算法“
假设有当前系统中有n个进程，m种资源

用到的数据结构(二维数组/矩阵+一维数组)：
int n,m; // n个进程，m种资源
int Available[1..m]; // 资源当前可用数
int Allocation[1..n][1..m]; // 已分配给每个进程的各种资源数量
int Need[1..n][1..m]; // 当前每个进程还需分配的各种资源数量

// 判断系统安全性算法用到的两个数组
int Work[1..m];  // 当前可分配的各类资源数
boolean Finish[1..n];  // 系统是否拥有足够的资源使其完成运行

两个步骤

• 分配资源时算法：
  当P1进程申请k个资源时：
  ① 如果K≤Need，就继续步骤②；否则出错，因为请求资源数不能超过需要数。
  ② 如果 K <= Available，就继续步骤；否则出错，因为可用资源不足。
  ③ 系统分配资源：

  Available = Available - K；// 表示分配给P1进程K个资源后，可分配的资源数
  Allocation = Allocation + K；// 表示P1进程已获得资源数
  Need = Need - K；// 表示P1进程还需要的资源数
  

  ④ 此时系统执行判断安全性的算法，计算分配后系统是否处于安全状态。如果安全，则结束，不安全则将③中修改的变量复原。

• 判断安全性算法：
  Work数组初始化为当前可分配的各类资源数；Finish数组初始化为 false。
  ① 在进程集合中找到符合下面两个条件的进程
  Finish[i] = false; Need ≤ Work
  ② 找到符合条件的进程，执行下面操作，然后继续执行①
  Work = Work + Allocation; Finish [i] = true
  若找不到符合条件的进程，则跳到③
  ③ 若Finish数组元素都为true则系统处于安全状态，否则处于不安全状态。

银行家算法图解

图片来自 https://blog.csdn.net/qq_33414271/article/details/80245715

2.3 死锁检测与恢复

2.3.1 死锁检测

在单个实例化的资源类型中，如果系统中正在形成一个循环，那么肯定会出现死锁。
在多实例资源类型图中，检测周期不够。 我们必须通过将资源分配图转换为分配矩阵和请求矩阵来在系统上应用安全算法。

2.3.2 死锁恢复

• 简单终止一个或多个进程，打破循环等待。
• 从一个或多个死锁进程那里抢占资源。

---

参考
https://www.yiibai.com/os/os-deadlock-detection-and-recovery.html