網路上好多交通 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 四個條件是充要條件還是必要條件？下面是原論文的說明：
- 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)
- 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：系統產能低。
- 除非 proces 可以一次取得所有工作所需的資源，才允許持有資源。
- 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 ＡＢＣＤ ＡＢＣＤ ＡＢＣＤ P1 ００１４ ０６５６ １５２０ P2 １４３２ １９４２ P3 １３５４ １３５６ P4 １０００ １７５０ // 算出 need NEED ＡＢＣＤ ０６４２ ０５１０ ０００２ ０７５０ // 宣告確認是否完成的變數 FINISH false false false false // loop : 持續找出可以釋放的 process 並更新 finish // 直到找不到或 finish 全為 true NEED Available ＡＢＣＤ ＡＢＣＤ ０６４２ １５２０ ０５１０<- ０００２ ０７５０ NEED Available ＡＢＣＤ ＡＢＣＤ ０６４２ １５２０ ００００ ＋１４３２ ０００２－－－－－－－ ０７５０ ２９５２ 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
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
發表文章
