延續前一天提到的Banker's Algorithm來做舉例說明

• 假設目前有5個Process，從P0~P4；有3個資源類型，A(10 instances)、B(5 instances)、C(7 instances)
• 在T0的時間中：
  Allocation--------Max----------Available-------Need
  ----A B C-----------A B C----------A B C---------A B C
  P0--0 1 0-----------7 5 3----------3 2 2---------7 4 3
  P1--2 0 0-----------3 2 2------------------------1 2 2
  P2--3 0 2-----------9 0 2------------------------6 0 0
  P3--2 1 1-----------2 2 2------------------------0 1 1
  P4--0 0 2-----------4 3 3------------------------4 3 1
  總和 7 2 5
  ==>Need = Max - Allocation
  ==>Available = A、B、C個別的instances - (P0~P4個別的Allocation想加總合)
• 如果系統是按照{P1、P3、P4、P2、P0}這個順序執行的話，代表是在safe state中，而如何安排順序呢?

1. 依照Available的各個資源量，然後再對照到個process的Need行列，如果Available可以滿足其中任一process的話，便先將資源分配給它，以此例子來說就是先給予P1，然後P1執行完畢後回連帶將它擁有跟分配到的資源釋放出來，如此一來便可以再分配給合適的process，因此才有這種安排產生，也才符合safe state的定義。

P1 Request(1,0,2)

• 檢查Request是否小於等於Available((1,0,2)<=(3,3,2))，如果是的話=>true
  Allocation------Need------Available
  -----A B C---------A B C------A B C
  P0--0 1 0---------7 4 3------2 3 0
  P1--3 0 2---------0 2 0
  P2--3 0 2---------6 0 0
  P3--2 1 1---------0 1 1
  P4--0 0 2---------4 3 1
• 如果是依照{P1、P3、P4、P0、P2}的順序執行的話，便是符合safe state的要求。

Deadlock Detection

• 簡單來說，就是允許系統進入deadlock狀態，然後再透過Detection Algorithm偵測到deadlock，再recover回去。

Single Instance of Each Resource Type

• 維持wait-for的圖形。

1. 在圖形中，node代表process。
2. Pi -> Pj ，就代表Pi在等待Pj中。

• 週期性的搜尋看看系統中有無cycle在發生，如果有的話便表示有deadlock的存在。
• 此演算法就是為了要發現圖形中是否有cycle的存在，有的話便是deadlock狀態；其算法需要n^2次操作順序，而n便是在圖形中的node。

Several Instances of a Resource Type

• Available：長度為m；表示每個資源種類的可用數量。
• Allocation：大小是n * m的矩陣；表示為每個類型的資源數量分配多少給process。
• Request：大小為n * m的矩陣；如果Request[i,j]= k，就表示Pi請求k個資源Rj。

Detection Algorithm

• 假設Work跟Finish的個別長度為m、n

1. Work = Available (等於資源種類，看資源還剩多少，將可用的分配到Work中)
2. 設i = 1,2,...,n，如果Allocationi不等於0的話，則Finish[i] = false，否則Finish[i]i = true。

• 尋找是否i還存在，使的以下兩種情形：

1. Finish[i] == false
2. Requesti<=Work
3. 如果沒有任何i存在的話，就跳到最後一個步驟。

• Work = Work + Allocationi
  Finish[i] = true
  回到上一步
• 如果Finish[i] = false，讓i範圍在1<=i<=n，則系統便是在deadlock state中，且Pi會被deadlocked。

Example of Detection Algorithm

• 假設有假設目前有5個Process，從P0~P4；有3個資源類型，A(7 instances)、B(2 instances)、C(6 instances)
• 在T0的時間中：
  Allocation------Request------Available------Request
  -----A B C---------A B C---------A B C---------A B C
  P0--0 1 0---------0 0 0---------0 0 0---------0 0 0
  P1--2 0 0---------2 0 2-----------------------2 0 2
  P2--3 0 3---------0 0 0-----------------------0 0 1
  P3--2 1 1---------1 0 0-----------------------1 0 0
  P4--0 0 2---------0 0 2-----------------------0 0 2
  ==>其順序安排定義跟Banker's Algorithm相同，所以此例子順序為{P0,P2,P3,P1,P4}，若按照此順序進行，就會讓所有i成為Finish[i] = true，就不會有deadlock的狀態。
• 如果P2請求資源C的話，會是甚麼情況呢?

1. 乍看之下，可以發現P0釋放出來一個B資源，可是P2要求的是C資源，所以並不符合P2的要求，因此P1、P2、P3、P4之間便存在著deadlock的狀態，P0則沒有，因為它已經釋放資源，所以與他無關。

Detection-Algorithm Usage

• 何時使用以及多常使用，其依賴的條件是什麼呢?

1. Deadlock大概多常發生呢?
2. 多少process需放下資源，退回某一步驟，需要仔細考量。

• 如果Detection Algorithm被隨意調度，則容易resource graph中產生cycle，所以我們並不能告訴在眾多deadlocked proess中，哪個造成了deadlock。

Recovery from Deadlock：Process Termination

• 所有deadlocked processes的退出
• 是終止全部process還是其中一個，看看是否可以解決deadlock。
• 可以依照以下條件，尋找哪一個process是需要被終止的：

1. Process的優先權大小。
2. Process已經花費多久時間計算，以及還需要多久時間可以完成。
3. Process需要多少資源。
4. 多少process將被終止。
5. Process的方法是interactive還是bath。
   ==>需要考慮很多條件。

Recovery from Deadlock：Resource Preemption

• Selecting a victim：選擇最少花費、影響最小的process。
• Rollback：當deadlock解決了，被終止的process會回到當初終止的狀態，繼續執行下去。
• Starvation：很容易抓到相同的victim，導致其process一直無法執行，便形成了starvaction的狀態。
  ==>其實Detection Algorithm對於系統來說負擔很大，可卻是目前系統中最常使用的演算法。