操作系统原理学习笔记（十七）-死锁检测与死锁解除(2023/11/10更新)

操作系统原理学习笔记目录排版可是越来越好看了呢！有点尴尬，突然发现连续八篇文章都忘标目录了，还好还没发布。2021/1/3：改正一个错别字，以及更通顺的语义。

2023/11/10：一个局部最优死锁算法的复杂度似乎算错了，见文章底部。

死锁检测算法与死锁解除算法

不采取预防死锁或避免死锁的OS，可能发生死锁，因此应当提供两个算法：

• 死锁检测算法：检测OS状态，是否发生死锁。
• 死锁解除算法：OS发生死锁后，解除死锁。

死锁检测

为了检测死锁，OS需要：

• 保存有关资源的请求与分配信息。
• 提供算法，根据以上信息来检测死锁。

资源分配图(Resource Allocation Graph)

资源分配图描述系统死锁，由一组结点N与一组边E组成的对偶G=(N, E)。

• 结点N由两个互斥子集构成，分别是进程P与资源R。
• 边E表示 进程请求资源/资源分配进程，
  • 如E={(P1, R2), (R2, P2), (P2, R1), (R1, P1)}表示下图的(a)图，
    表示P1申请R2资源，R2资源分配给P2，P2申请R1资源，R1分配给P1资源。
    注：图P124原图是如此画的，但有六条边，说示出两条请求两条分配，我不太清楚是不是说漏了。

死锁定理

通过简化资源图的方式，将进程资源分配与资源释放的过程表示出来，一步步简化，直到无E时，表示安全。

1. 在上面的资源分配图(a)中，找到一不阻塞且非独立的结点P1，为其分配资源，并释放资源。
   • 即，将连接结点的边去除，形成图(b)。
2. 再次循环这个过程，分配并释放P2结点的资源，形成图(c)。
3. 经过上述简化过程后，图中边已全部消去，此时图被完全简化。

死锁检测中的数据结构

类似银行家算法的数据结构。
下面有点怪，不像数据结构，更像流程。

1. Available[]：可利用资源向量数目。
2. L表：不占资源进程的集合。
   • 即Allocation==0的进程集合。
3. 找到Request[i, j]<=Work[j]的进程，分配并释放资源，Work[j]+=Allocation[j]。
   将进程i记录L表。
   • 这里的下标又乱了，书上的数组下标真成下标了，为了和前篇文章统一，这里的下标我改成数组下标。
4. 若所有进程都进入L表，则资源分配图是可完全简化的，否则，则是不可完全简化的，可能发生死锁。

死锁解除

检测到死锁时，最简单的处理措施是人工处理，另一种措施是使用死锁解除算法，常用的两种方法：

• 抢占资源：从若干进程中抢占足够资源，分配给死锁进程。
• 终止进程：终止若干个死锁进程，打破循环，解除死锁状态。

终止死锁的办法

• 终止所有死锁进程。
  • 最简单，但是代价极大。
• 逐个终止进程。
  难以确定终止顺序，但可根据以下几点进行度量：
  • 进程优先级大小？
  • 进程已运行时间，剩余运行时间？
  • 进程已使用资源，还需使用资源？
  • 交互式还是批处理？

付出代价最小的死锁解除算法

• 一种找到付出代价最小的终止顺序，但成本高的算法：
  1. 先从死锁进程组中取出一个，形成第一层终止，若有n个死锁进程，则有n个第一层。
  2. 再从n个第一层中取一个，形成第二层终止，每个第一层又有n-1个第二层终止。
  3. 如此循环，直到解除死锁，将各层的总代价计算，得到最小的终止顺序。
  4. 注：于P126有图示，但总体来说，是多重遍历，循环次数为n!，即n(n-1)(n-2)…

• 另一种比较有效的算法：
  1. 找到死锁进程组中，终止代价最小的，将其从死锁进程组中删去。
  2. 再从新的死锁进程组中，找到终止代价最小的，删去。
  3. 如此循环，直到解除死锁。
  4. 注：书上太复杂了，差点没看懂，
     实际上就是只找到局部最优，再从局部最优继续找局部最优，
     n个进程最多只需要n次寻找即可。（2023/11/10注：存疑，似乎是n+(n-1)+...+1，因为第一次寻找需要n次，随后每次减少，仅在当次寻找中局部最优）