操作系统中的死锁检测算法详细指南

2021年3月29日16:55:42 发表评论 1,591 次浏览

如果系统既没有使用死锁防护, 也没有使用避免死锁算法则可能发生死锁情况。在这种情况下-

  • 应用算法检查系统状态以确定是否已发生死锁。
  • 应用算法从死锁中恢复。有关更多信息, 死锁恢复

死锁避免算法/银行家算法:

该算法采用了几种时变数据结构

  • 可用-长度为m的向量表示每种类型的可用资源数。
  • 分配-n * m矩阵定义当前分配给进程的每种类型的资源数。列代表资源, 资源代表过程。
  • 请求-n * m矩阵表示每个进程的当前请求。如果request [i] [j]等于k, 则处理P一世正在请求k个资源类型R的更多实例Ĵ.

现在,银行家算法包括一个安全算法/死锁检测算法
判断系统是否处于安全状态的算法描述如下:

算法步骤:

  1. 设Work和Finish分别为长度为m和n的向量。初始化Work=Available。其中i= 0,1,...,n-1,如果Request(i) = 0,那么Finish[i] = true;否则,Finish[i]= false。
  2. 找到一个索引i,满足:
    a)Finish [i] ==false
    b)Request(i)<=Work
    如果这种索引i不存在, 请转到步骤4。
  3. Work= Work+ Allocation(i)
    Finish[i]= true
    转到步骤2。
  4. 如果Finish[i]== false对于某些i, 0<=i<n,则系统处于死锁状态。而且,如果Finish[i]==false进程Pi死锁。

例如,

分配,请求矩阵
  1. 在此, Work = [0, 0, 0] & Finish = [false, false, false, false, false]
  2. i=0被选择为Finish[0] = false和[0,0,0]<=[0,0,0]。
  3. Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] & Finish = [true, false, false, false, false].
  4. i=2被选择为Finish[2] = false和[0,0,0]<=[0,1,0]。
  5. Work =[0,1,0]+[3,0,3] =>[3,1,3] & Finish = [true, false, true, false, false]。
  6. i = 1选择Finish [1] = false且[2, 0, 2] <= [3, 1, 3]。
  7. Work= [3, 1, 3] + [2, 0, 0] => [5, 1, 3]&
    Finish= [true, true, true, false, false]。
  8. i = 3被选择为Finish [3] = false和[1, 0, 0] <= [5, 1, 3]。
  9. Work= [5, 1, 3] + [2, 1, 1] => [7, 2, 4]&
    Finish= [true, true, true, true, false]。
  10. i = 4选择Finish [4] = false且[0, 0, 2] <= [7, 2, 4]。
  11. Work= [7, 2, 4] + [0, 0, 2] => [7, 2, 6]&
    Finish= [true, true, true, true, true]。
  12. 因为Finish是一个全为真的向量,所以在这个例子中没有死锁。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: