Deadlock Detection

Deadlock Detection

• 系統必須提供一個演算法去檢視是否有deadlock發生
• 需要一個演算法來回復deadlock

single instance

• 當有cycle的時候會發生deadlock
• an edge from P_i to P_j 代表 P_i 在等 P_j 釋放一個 P_i 需要的資源
• 圖(b)叫做 wait-for graph

several instance

• data structure
  • Available
  • Allocation
  • Request
    • $n\times m$ matrix
    • Request[i, j] = k 代表P_i 正請求k個R_j

1. Initialize

   ​​​​Work = Available;
   ​​​​for (i = 1; i <= n; i++)
   ​​​​    if (Allocation[i] != 0)
   ​​​​        Finish[i] = false;
   ​​​​    Finish[i] = true;
   

2. Find an index i

   • Finish[i] == false&& Request_i ≤ Work
   • 如果 i 不存在，跳到4

3. 可以執行

   • Work = Work + Allocation[i] process釋放資源
   • Finish[i] = true 工作完成
   • 回到2

4. If Finish[i] == false , for some i, 1 ≤ i ≤ n, then the system is in deadlock state

   • Finish[i] == false → P_i is deadlocked

---

last edit

dotTue, Jul 28, 2020 11:04 PM

HOME PAGE

tags: OS CSIE