Deadlock avoidance

Deadlock avoidance

• 可以利用演算法避免deadlock
• safe state
  • a save sequence {P₁, P₂, …, P_n}
  • P_i最多可以請求的資源數 = available resources + resources held by all P_j , with j < i
• unsafe state
  • may lead to a deadlock
    • not all unsafe states are deadlocks

• Ex: P₂在t₁時多拿了一個資源

Resource-Allocation-Graph Algorithm

• For one instance of each resource type only

• A direct edge from P_i → R_j is called a request edge

• A direct edge from R_j → P_i is called a assignment edge

• claim edge

  • P_i → R_j 代表 P_i 未來某個時間點可以請求 R_j
  • 虛線表示
  • 當P_i請求R_j，P_i → R_j會轉換成request edge(實線)
  • 當P_i釋放R_j， assignment edge R_j → P_i 會轉換成claim edge

• P_i 開始執行之前，所有的claim edge都要出現在圖上

• 如果edge的方向轉換後會造成cycle，就不能讓請求成立

Banker's Algorithm

• For multiple instance of each resource type

• Data structure

  • n = number of processes

  • m = number of resources types

  • Available

    • 長度為 m 的一維陣列
    • Available[j] = k 代表R_j有k個可用資源

  • Max

    • $n\times m$ 的二維陣列
    • Max[i, j] = k 代表P_i最多可以請求 k 個 R_j 資源

  • Allocation

    • $n\times m$ 的二維陣列
    • Allocation[i, j] = k 代表 P_i 已經有 k 個 R_j

  • Need

    • $n\times m$ 的二維陣列
    • Need[i, j] = k 代表 P_i 需要再 k 個 R_j 才能完成任務

  • Need[i, j] = Max[i, j] - Allocation[i, j]

    • P_i 需要的 R_j 資源數 = P_i 最多可以請求的 R_j 數 - P_i 已經有的 R_j 數

Safety algorithm

• 用來決定一個特定狀態是不是safe

1. Initialize

   • Let Work and Finish be vectors of length m and n
   • Work = Available
   • Finish[i] = false, i = 0, 1, …, n-1

2. Find an i

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

3. 可以執行

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

4. 如果 Finish中全部都是 true，代表系統現在是 safe state

Resource-request algorithm

• 用來決定一個新的請求是不是safe，如果是safe就讓它執行

1. If Request_i ≤ Need_i go to step 2

   • Request_i不能比Need_i大，否則會超過P_i最多可請求的資源數

2. If Request_i ≤ Available_i go to step 3

   • If not, P_i must wait

3. $$\begin{gathered} Available=Available-Reques{t}_i \\ Allocatio{n}_i=Allocatio{n}_i+Reques{t}_i \\ Nee{d}_i=Nee{d}_i-Reques{t}_i \end{gathered}$$
   • 可用資源被該process請求資源扣掉
   • 該process所佔有的資源增加
   • 該process還需要的資源減少
   • 如果結果是safe → 把資源給P_i
   • 如果結果是unsafe → wait

---

last edit

dotTue, Jul 28, 2020 10:38 PM

HOME PAGE

tags: OS CSIE