Deadlock Avoidance

• 要求系統要預先知道可用的資訊有多少。
• 最簡單也最有用的model，要求每個process都要事先宣布可能需要資源的最大量。
• Daedlock-avoidance algorithm會進行檢查，確保在resources allocation中不會形成circular-wait condition。
• Avoidance-->就是確保系統不會進入「unsafe state」。

Safe State

• 定義：當Processes要求一個資源，且存在一個Processes序列；每個process依照其順序取得資源，就能確保每個process都擁有資源，不會發生deadlock的狀況，則說此process在「safe state」中。

1. 如果一個process並不需要立即得到資源的話，它可以等到另一個process結束並釋放資源給它，再繼續執行。
2. 當一個process Pj結束，Pi可以獲得需要的資源，接著執行，並歸還被分配的資源然後終止。
3. 當上一個process結束並釋放資源後，下一個有需要的process就可以得到資源，如此形成一個循環。

Basic Facts

• 如果系統在safe state中--->無deadlocks。
• 如果系統在unsafe state中--->有可能產生deadlock。
• Avoidance--->確保系統永遠不會進入unsafe state。

Avoidance Algorithms

• 單一資源類型的instance：使用resource-allocation graph--->Circle Detection。
• 多重資源類型的instance：使用banker's algorithm。

Resource-Allocation Graph Scheme

• Claim edge：當Pi向Rj請求資源時，在圖案上我們以虛線表示關係。
• 當process請求資源時，claim edge便轉換成request edge。
• 當資源被分配給process時，request edge就被轉換成assignment edge。
• 當資源被process釋放時，assignment edge就重新轉變成claim edge。
• 在系統中，資源們需要事先知道process需要多少、哪些資源。

Resource-Allocation Graph Algorithm

• 先假設Process Pi向資源Rj要求資源。
• 僅當將request edge轉乘assignmemt edge，且不會在圖形中形成cycle，才能分配到資源，否則就不會被分配到。

Banker's Algorithm

• 多重instances。
• 需事先知道每個process需要多少資源，才能進行下一步。
• 當process請求資源時，可能會需要等待。
• 當process得到資源並執行完畢後，就必須在時間限制內將資源歸還。

Data Structures for the Banker's Algorithm

• 設定有n個process，有m個資源類型。
• Available：長度為m。如果available[l]=k，表示Rj有k個資源可用。
• Max：大小為n * m。如果Max[i,j]=k，則表示Pi要求資源最大數量為k。
• Allocation：大小為n * m的矩陣。如果Allocation[i,j]=k，則表示Pi占用k個資源Rj。
• Need：大小為n * m的矩陣。如果Need[i,j]=k，表示Pi還需要k個資源Rj。

1. Need[i,j] = Max[i,j] - Allocation[i,j]

Safety Algorithm

• 假設Work和Finish分別長度為m、n。

1. Work = Available
2. Finish[l] = false for i = 0,1,....,n-1。

• 尋找i是否包含兩者條件：
  Finisn[l] = false
  Need>=Work --->Finisn[l] = false，轉到下一個步驟。
  如果沒有任何i存在，則直接跳到最後步驟。
• Work = Work + Allocation(i)
  Finish[l] = true --->轉到下一個步驟。
  Finish[l] = false --->回到上一個步驟。
• 如果所有i都為Finish[l] == true，則此系統是存在safe state。

Resource-Request Algrithm for Process Pi

• Requesti = Pi的要求長度。如果Requesti[l]=k，則表示Pi需要k個Rj。

1. 如果Requesti<=Needi，便轉到第二步驟。否則提出錯誤情況，因為所需要的資源量大於宣布需要的最大量。
2. 如果Requesti<=Available，便轉到第三步驟。否則表示Pi需等待，因為目前尚無足夠資源可提供。
3. 藉由以下公式，可以知道需要分配多少資源：
   Available = Available - Requesti；
   Allocationi = Allocationi + Requesti；
   Needi = Needi - Requesti；
   1-如果safe，則資源分配給Pi。
   2-如果是unsafe，則Pi必須等待，以及舊resource-allocation state重新恢復。

明天將說明關於Banker's Alogrithm的相關例子。