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

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

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

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

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

• 可用-长度为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是一个全为真的向量，所以在这个例子中没有死锁。

---