操作系统原理学习笔记(十七)-死锁检测与死锁解除(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次,随后每次减少,仅在当次寻找中局部最优)

版权声明:
作者:MWHLS
链接:https://mwhls.top/1243.html
来源:无镣之涯
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
打赏
< <上一篇
下一篇>>
文章目录
关闭
目 录