2017年8月23日 星期三

OS - Ch7 死結 Deadlock

 

網路上好多交通 deadlock 的圖,真的很酷,不過塞在裡面的人應該很不爽XD

2015.1.15 初版
2017.8.23 二版




一、Deadlock 簡介


Deadlock 意思是系統中存在一組 process 陷入互相等待對方所擁有的資源的情況,造成所有的 process 無法往下執行,使得 CPU 利用度大幅降低。



Deadlock 發生須符合以下四項充要條件 :

  • Mutual exclusion:某些資源在同一個時間點最多只能被一個 process 使用
  • Hold and wait:某 process 持有部分資源,並等待其他 process 正在持有的資源
  • No preemption:process 不可以任意強奪其他 process 所持有的資源
  • Circular waiting:系統中存在一組 processes $P = {P_0, P_1, \dots ,P_n}$,其中 $P_0$ 等待 $P_1$ 所持有的資源 ... $P_n$ 等待 $P_0$ 所持有的資源,形成循環式等待。(因此,deadlock不會存在於single process環境中)


[用心去感覺] Deadlock vs Starvation 



[用心去感覺] 關於 deadlock 的充要條件

網友題問,deadlock 四個條件是充要條件還是必要條件?下面是原論文的說明:

  1. A circuit (directed loop) in the request graph is a necessary and sufficient condition for a deadlock, assuming the first three conditions given above are operative. (i.e., there is only one resource of each type)
  2. For the general ease of more than one resource of the same type, a state graph was defined. With this definition a circuit in the state graph is a necessary, but no longer a sufficient, condition for the existence of deadlocks. 

References: E. G. Coffman, M. Elphick, and A. Shoshani. 1971. System Deadlocks. ACM Comput. Surv. 3, 2 (June 1971), 67-78. DOI=http://dx.doi.org/10.1145/356586.356588




二、Deadlock 的處理方法


Deadlock 三種處理方法:

  • Deadlock prevention
  • Deadlock avoidance
  • Deadlock detection & recovery

prevention 和 avoidance 保證系統不會進入 Deadlock,但資源利用度低;而 detection 資源利用度較高,但若 Deadlock 需要做 recovery,則 cost 極高。


1. Deadlock prevention


打破必要條件四項之一,即可保證 Deadlock 永不發生。

  • 打破 Mutual exclusion:為資源與生俱來之性質,無法打破。
  • 打破 Hold and wait:系統產能低。
    1. 除非 proces 可以一次取得所有工作所需的資源,才允許持有資源。
    2. process 執行之初可持有部分資源,但要再申請資源前,要先釋放手中所有資源。
  • 打破 Preemption : 讓高優先 process 搶低優先 process 的資源,會造成 starvation。
  • 打破 Circular waiting:Process須按照資源編號遞增方式申請資源。


2. Deadlock avoidance


當 process 提出資源申請時,OS 會執行Banker algorithm 來判斷系統在「假設核准該申請後」是否處於 Safe state,是則核准,否則請 process 等待。

  • safe state : 存在 safe sequence
  • unsafe state : 可能有 deadlock 



[重要] Banker Algorithm


設所有 process 在 set P 中;n 為 process 數目,m 為資源種類。

一維陣列:

  • R_i[m] : process i 提出的資源申請量。
  • Avail[m] : 系統目前各類資源的可用數量。
  • Finish[n] : 各個 process 是否完成。

二維陣列:

  • Alloc[n,m] : 目前各 process 持有的資源量。
  • Max[n,m] : 各 process 需要多少資源才可以完成工作。
  • Need[n,m] : 還要多少資源才可以完成工作。 (Need = Max - Alloc)

虛擬碼:

while( Finish is not all TRUE ){
    found = FALSE;
    foreach (i in process set P) {
        if ( Need[i,:] <= Avail ) {
             Avail = Avail + Alloc[i,:];
             P = P - {i};
             found = TRUE;
        }
    }
    if (!found) return FAIL;
}
return OK;


例題:

// 基本變數設置

 Allocation   Max   Available
   ABCD  ABCD  ABCD
 P1 0014  0656  1520 
 P2 1432  1942 
 P3 1354  1356
 P4 1000  1750

// 算出 need

 NEED
 ABCD
 0642 
 0510
 0002
 0750

// 宣告確認是否完成的變數

 FINISH
 false
 false
 false
 false

// loop : 持續找出可以釋放的 process 並更新 finish
// 直到找不到或 finish 全為 true

 NEED    Available
 ABCD  ABCD
 0642  1520
 0510<-
 0002
 0750

 NEED    Available
 ABCD  ABCD
 0642  1520
 0000 +1432
 0002-------
 0750  2952

 FINISH
 false
 true
 false
 false


3. Deadlock Detection


Allow system to enter deadlock state.

Detection algorithm :

  • Single instance : topological sort (using wait-for graph)
    • 使用 adjcent matrix : $O(n^2)$
    • 使用 adjcent list : $O(V+E)$
  • Several instance : 用 Banker algorithm 判斷系統是否已經在 unsafe state

Recovery scheme :

  • 終止 process (成本都高)
    • 全部刪除
    • 一次刪一個 process,直到打破 deadlock。
  • 資源搶奪
    • 剝奪 victim process 資源 (可能造成 starvation)
    • 恢復無該資源前狀態 (cost 高)


[重要] Resource allocation graph


Some facts about RAG :

  • If graph contains no cycles => no deadlock. 
  • If graph contains a cycle
    • one instance <=> deadlock.
    • several instances, possibility of deadlock. ( deadlock => cycle )


(a) Resource allocation graph
(b) Corresponding wait-for graph





References


wiki - 銀行家演算法
https://zh.wikipedia.org/wiki/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95

Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720

聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/

洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057






技術提供:Blogger.