Dead Lock Detection & Recovery

若 Dead Lock Prevention 與 Avoidance 都不用，則系統中可能存在 DeadLock。 ∴ 有必要提供下列機制：

• 偵測死結是否存在

• 若死結存在，則必須打破死結，恢復正常

• 優點：
  • Resource Utilization 較高
  • Throughput 提升
• 缺點：
  • Cost 太高

• Dead Lock Detection 與 Dead Lock Recovery 是一體的

Dead Lock Detection

• 偵測所有的 Process，看是否會進入死結 (勿和銀行家演算法搞混)
• 系統環境:
  • 有 m 類可用資源，每類資源的數量不一
  • 有 n 個 Process

Data Structures

• \(Available[1…m]\): 表示系統目前可用的資源數量
• \(Allocation[1…n, 1…m]\): 表示各 Process 目前所持有的資源數量
• \(Request[1…n, 1…m]\): 表示各個 Process 目前所提出的資源申請量
• \(Work[1…m]\): 表示系統目前可用之資源數量之累計 (初值 = Available)
• \(Finish[1…n] of Boolean\): 初始值設定規則為 ( 紀錄每個 Process 是否完成工作 )
  • If \(Allocation_i = 0\), then \(Finish[i] = True\) (Process 沒有持有任何資源，即可假定它已完成)

    Process i 不見得真的完成了它的工作，只是因為目前 Process i 沒有持有任何資源 ∴ O.S. 認為此時的 Process 不會產生 Hold and Wait 的情況 ∴ 假設 Process i 可順利完成工作

  • If \(Allocation_i ≠ 0\), then \(Finish[i] = False\) (尚未完成，且 Process 持有資源)

Algorithm

1. 設定 Work 與 Finish 初始值
   • Work = Available
   • \(Finish[i]\) 的初値視 Process i 是否持有資源而定
     • True, if \(Allocation_i = 0\)
     • False, if \(Allocation_i ≠ 0\)
2. 找到一個滿足下列兩條件的 Process i。若找到，則 go to 3，否則 go to 4:
   • \(Finish[i] = False\) (此 Process 尚未做完)
   • \(Request_i ≤ Work\) (此 Process 當下所提出的申請，系統可以應付)
3. 設定 \(Finish[i] = True\)，Work = Work + Allocationi, go to 2
4. 檢査 Finish 陣列
   • 若皆為 True，則表示系統目前無死結。
   • 若不是皆為 True，則表示有 Dead Lock，且 \(Finish[i] = False\) 者，皆陷入此 Dead Lock 中

範例

一個系統目前有五個處理程序 \(P_0\) ~ \(P_4\) 及三種資源 A, B, C。其中資源 A 有 7 個裝置，B 有 2 個裝置，C 有 6 個裝置，假設在時間 \(T_0\) 時，系統的資源分配狀態如下所示：

• 問題 1 : 求系統目前有無死結？

Ans:

1. 設定初値
   • Work = Available = (0, 0, 0)
   • Finish =
2. 找到 \(P_i\)，滿足 \(Finish[i] = False\)，且 \(Request_i ≤ Work\)
   • 找到 \(P_0\)，滿足 \(Finish[0] = False\)，且 \(Request_0 ≤ Work\)。∴先找 \(P_0\)，then go to 3
3. 設定 \(Finish[i] = True\)，且 \(Work = Work + Allocation_i\)
   • 設定 \(Finish[0] = True\)，且 \(Work = Work + Allocation_0\) = (0, 0, 0) + (0, 1, 0) = (0, 1, 0)。Go to 2

步驟 2 與 3 交互執行，可依序得到 \(P_2, P_1, P_3, P_4\) 滿足條件且完成工作

4. 檢査 Finish 陣列，發現都為 True，∴系統無 Dead Lock

• 問題 2 : 假設在時間 \(T_0\) 時，系統的資源分配狀態如下所示： 求系統目前有無死結？若有，哪些 Process 陷入死結？

• Ans: \(P_0\) 可完成工作，但 \(P_1, P_2, P_3, P_4\) 陷入死結

優缺點

• 優點：
  • 可以偵測出系統是否有死結存在。且若有死結，可知哪些 Processes 陷入死結
• 缺點：
  • 此演算法須花費 \(O(n^2m)\) 的時間複雜度 (n: Process 個數; m: Resource 種類)

Dead Lock Recovery

• 終止 Process
  • Delete All
    • ∵ 這些 Process 之前完成的工作全部白費! ∴ 成本太高
  • 每次只終止一個 Process，直到 Dead Lock 打破為止
    • 毎刪一個 Process 後皆需再執行 Dead Lock Detection Algo.，判斷有無死結
    • 若刪一個 Process，Dead Lock 仍在，則表示該 Process 亦白殺
    • 成本亦高 (偵測、刪除都要成本)
• 資源搶奪
  • 程序：
    1. 選擇犧牲者 Process ( Victim Process )
    2. 剝奪其資源
    3. 恢復到此 Victim process 原先無該資源的狀態 ( 困難 )
       • Cost 高!!∵ O.S. 需要記錄毎一個 Process 的毎一次資源使用狀況
  • 需考量 Starvation 問題之產生 ( ∵ 可搶奪 )
    • \([解法]\) 把被剝奪的次數列入選擇犧牲者 Process 之考量因素