Ch7:Deadlocks - HackMD

--- title: Ch7:Deadlocks --- # 作業系統Ch7: Deadlocks ###### tags: `Operating System` `Review` `Ch7` ## Deadlock Characterization ### Deadlock Problem - 一組塞住 (blocked) 的 processes，每一個都持有某些資源且等待著拿到在同組內另一 process 持有的一個資源。 > 這裡資源可能是硬體，也可能 memory content 等等。 - E.g., 2 processes and 2 tape drivers - 每個 process 握有一個 tape drive - 每個 process 請求另一 tape drive - E.g., 2 processes and semaphores A & B - $P1(hold\ B,\ wait\ A):\ wait(A),\ signal(B)$ - $P2(hold\ A,\ wait\ B):\ wait(B),\ signal(A)$ ### Necessary Conditions - Mutual exclusion: - 一次只能有一個 process 使用同一個資源 > 對於 synchronization problem，會因為透過 mutex 等處理機制反而達成 Mutual exclusion 的條件。 - Hold & Wait: - 一個 process 持有某些資源且正等待另一資源 - No preemption: - 一個資源只能由 process 自願地釋放 - Circular wait: - 有一組等待 process $\{P_{0},\ P_{1},\ P_{2},....,\ P_{n}\}$ 使得 $P_{0}\ \rightarrow\ P_{1}\ \rightarrow\ P_{2}\ \rightarrow\ P_{3}\ \rightarrow\ ....\ \rightarrow\ P_{n}\ \rightarrow\ P_{0}$ - 對於 **possible** deadlock，所有四個 conditions 一定要成立。 ### System Model - 資源種類 $R_{1},\ R_{2},\ ...,\ R_{n}$ - E.g., CPU, memory pages, I/O devices - 每個 resource type $R_{i}$ 有 $W_{i}$ instances - E.g., 一台電腦有兩個 CPUs - 每個 process 利用一資源如下: - $Request\ \rightarrow\ use\ \rightarrow\ release$ ### Resource-Allocation Graph - 3 processes, $P1\ \sim\ P3$ - 4 resources, $R1\ \sim\ R4$ - $R1$ and $R3$ each has one instance - $R2$ 有兩個 instances - $R4$ 有三個 instances - Request edges: - $P1\ \rightarrow\ R1$: $P1$ 請求 $R1$ - Assignment edges: - $R2\ \rightarrow\ P1$: $R2$ 的一個 instances 分配給 $P1$ > $P1$ 正在持有 $R2$ 的一個 instance，等待著 $R1$ 的一個 instance。 ![](https://i.imgur.com/n2E1is2.png) #### Resource-Allocation Graph w/ Deadlock - 如果圖包含 cycle，那麼 deadlock 可能存在 ![](https://i.imgur.com/SF0OAt7.png) > $P1$ 正在等待著 $P2$ 釋放資源，$P2$ 正等著 $P3$ 釋放資源，所以 $P1$ 也正等待著 $P3$ 釋放資源。因為 $P3$ 正等待著 $P1$ or $P2$，且他們同樣等待著 $P3$，所以有 deadlock 產生。 #### RA Graph w/ Cycle but w/o Deadlock ![](https://i.imgur.com/mbX8kjc.png) > $P1$ 正在等待著 $P2$ or $P3$；$P3$ 正在等待著 $P1$ or $P4$。因為 $P2$ 和 $P4$ 沒有等待 process，所以在 $P1$ 和 $P3$ 之間沒有 deadlock。 ### Deadlock Detection - 如果圖沒有包含 cycle，那麼不會有 deadlock，因為 Circular wait 不可能成立。 - 如果圖包含一 cycle - 又如果每一資源種類只有 one instance $\rightarrow$ deadlock。 - 又如果每一資源種類有多個 instances $\rightarrow$ deadlock 的可能性。 ### Handling Deadlocks - 確保系統永不進入 **deadlock state** - **deadlock prevention**: 確定至少有一個necessary condition 不能成立。 - **deadlock avoidance**: dynamically 分配前檢查 resource-allocation state。 > 也就是在 runtime 時，去做檢查如果分配資源後會造成 deadlock，那麼就不會分配，反之，就分配資源給要求的 process。 - 允許進入一 deadlock state，然後 recovery - **deadlock detection** - **deadlock recovery** - 忽略 deadlock 且假裝在系統裡從來沒有發生過 - 用於大部分作業系統，包含 UNIX。 > 因為大部分 deadlock prevention 的方法花費成本遠遠高過忽略它，且也會對於 process 有額外限制。忽略 deadlock，最嚴重情況下就是重開機，造成 data loss，所以如果 data loss 是可以容忍的話，那麼 ignoring deadlock 是較好的方法。 ## Deadlock Prevention & Deadlock Avoidance ### Deadlock Prevention 要達到 Deadlock Prevention，只要讓四個 necessary conditions 的其中一個**不滿足**即可。 - Mutual exclusion (ME) - 在 sharable resources 不要求 ME。 - e.g., 在「唯讀」的檔案上，不需要確保 ME。但是，某些資源不是能共享的，像是 printer。 - Hold & Wait - 當一 process 請求一 resource，它不再持有任何資源。 > 也就是 process 需要其他資源，它必須先釋放手上持有資源。 - 執行前預先分配所有資源。 > resource utilization 是低的；而且可能有 process 需要特定別人占用資源，但是一直拿不到 (且釋放手上資源)，產生餓死 (starvation)。 - No preemption - 當一 process 正在等待資源，所有它手上的資源是可被搶奪的。 - e.g., $P1$ 請求已經分配給 $P2$ 的 $R1$，且 $P2$ 等待 $R2$。 > $P1\ \rightarrow\ R1\ \rightarrow\ P2\ \rightarrow\ R2$ - $R1$ 可以被搶奪並且重分配給 $P1$ - 適用在其資源狀態很容易儲存且之後恢復 - e.g., CPU registers & memory - 它不易適用在其他資源 - e.g., printers & tape drives - Circular wait - 強迫所有資源類型按總順序 - 一個 process 請求資源是以遞增順序 - 令 $R\ =\ \{R_{0},\ R_{1},\ ...,\ R_{N}\}$ 是資源類型的集合 - 當請求 $R_{k}$，應該要釋放所有 $R_{i},\ i\ \geq\ k$ - Example: - $F(tape\ drive)\ =\ 1,\ F(disk\ drive)\ =\ 5,\ F(printer)\ =\ 12$ - 一個 process 一定要請求 tape 和 disk drive 早於請求 printer - proof: counter-example 不存在 - $P_{0}(R_{0})\ \rightarrow\ R_{1},\ P_{1}(R_{1})\ \rightarrow\ R_{2},\ ...,\ P_{N}(R_{N})\ \rightarrow\ R_{0}$ - 矛盾: $R_{0}\ <\ R_{1}\ <\ R_{1}\ <\ R_{2}\ <\ ...\ R_{N}\ <\ R_{0}$ > $P_{N}$ 持有 $R_{N}$ 等待 $R_{0}$，不會符合 process 請求資源是以遞增順序。 ### Avoidance Algorithms - Single instance of a resource type - **resource-allocation graph (RAG) algorithm** 基於 circle detection - Multiple instances of a resource type - **banker's algorithm** 基於 safe sequence detection #### RAG Algorithm - **Request edge**: $Pi \rightarrow Rj$ - **Assignment edge**: $Rj \rightarrow Pi$ - **Claim edge** $Pi \rightarrow Rj$ > Process $Pi$ 在未來可能請求 $Rj$ - Claim edge 轉變成 request edge - 當一資源被 process 請求時。 - Assignment edge 轉變成 claim edge - 當一資源被 process 釋放時。 ![](https://i.imgur.com/HUmkCDZ.png) - Resources 一定要在系統中「先驗」 claimed。 > 也就是 Thread $Ti$ 開始執行前，所有它的 claim edges 一定會出現在 RAG 中。 - 如果**沒有 cycle** 被 created，核准 a request。 - 使用 cycle-detection algorithm $O(n^{2})$ 以檢查安全。 > n 為 thread # - Example: $R2$ 不能被分配給 $P2$ > 當 $R2$ 被分配給 $P2$，$P1$ 可能會在下一刻請求 $R2$，同時它本身握有著 $R1$，而 $P2$ 原本有請求 $R1$，因此會造成 cycle，形成 deadlock。 ![](https://i.imgur.com/iV0baDL.png) ### Deadlock Avoidance - safe state - 如果存在有分配序列 (a sequence of allocations)可以去滿足所有 processes 的請求，那麼該系統就是在 safe state 中。 > 這 sequence of allocations 稱作 **safe sequence**。 - safe state $\rightarrow$ no deadlock - unsafe state $\rightarrow$ 有 deadlock 的**可能性**。 - deadlock avoidance $\rightarrow$ 確保系統永不進入 unsafe state ![](https://i.imgur.com/2FutLP2.png) #### Safe State with Safe Sequence 有 12 tape drives - 假設在 $t_{0}$，還有 3 個 tape drives ![](https://i.imgur.com/bQCuLlB.png) > <$P1,\ P0,\ P2>$ 是 a safe sequence。 > 1. P1 satisfies its allocation with 3 available resources > 2. P0 satisfies its allocation with 5 available resources > 3. P2 satisfies its allocation with 10 available resources #### Un-safe State w/o Safe Sequence - 假設在 $t_{1}$ ![](https://i.imgur.com/vj2m7Ap.png) - 如果 $P2$ requests 且被多分配一個 tape drive - 不會有 safe sequence 存在 - 這樣分配使系統進入到 unsafe state - 只有當分配使系統處於安全狀態時才授予請求 ### Banker's Algorithm - 用於每一種 resource type 有多個 multiple instances - Banker's algorithm: - 使用一通用 **safety algorithm** 去預先決定是否在分配後有任何 safe sequence 存在 - 只會在 safe sequence 存在情況下進行分配 - Safety algorithm: 1. 假設 processes 需要最大資源量 2. 找到一個 process 可以被未分配的資源所滿足 3. 釋放 process 資源使用量 4. 重複第二個步驟直到所有 processes 都滿足 #### Banker's Algorithm Example i (Safe Algo.) - 總資源 instances: $A:\ 10,\ B:\ 5,\ C:\ 7$ - 可得到資源 instances: $A:\ 3,\ B:\ 3,\ C:\ 2$ ![](https://i.imgur.com/31hSkPJ.png) > Safe sequence: $P1,\ P3,\ P4,\ P2,\ P0$ > Safe sequence 不一定只有一種可能性。 #### Banker's Algorithm Example ii - 總資源 instances: $A:\ 10,\ B:\ 5,\ C:\ 7$ - 可得到資源 instances: $A:\ 3,\ B:\ 3,\ C:\ 2$ ![](https://i.imgur.com/T7ufmA4.png) - If Request ($P1$) = ($1,\ 0,\ 2$): $P1$ allocation $\rightarrow\ 3, 0, 2$ - 進入另一 safe state (Safe sequence: $P1,\ P3,\ P4, P0, P2$) > 如果 P1 需要多要一個 A、二個 C，那麼我們就先假設分配給 $P1$ 總共三個 A、兩個 C，去找看看有無 safe sequence。(此時，可得到資源會變成 $A:\ 2,\ B:\ 3,\ C:\ 0$，且 $P1$ Need 會變成 $A:\ 0,\ B:\ 2,\ C:\ 0$) - If Request ($P4$) = ($3,\ 3,\ 0$): $P4$ allocation $\rightarrow\ 3, 3, 2$ - 進入到 unsafe state (no safe sequence can be found!) ## Deadlock Detection & Deadlock Recovery ### Deadlock Detection - each resource type 的 single instance - 轉換 request/assignment edges 到 wait-for graph - 如果在 wait-for graph 有 cycle，那麼 deadlock 就存在。 ![](https://i.imgur.com/fz7kA1L.png) - Multiple-Instance for Each Resource Type - 總資源 instances: $A:\ 7,\ B:\ 2,\ C:\ 6$ - 可得到資源 instances: $A:\ 0,\ B:\ 0,\ C:\ 0$ ![](https://i.imgur.com/OaPEBVs.png) > 這邊是目前系統狀態，所以不用管 max resource，而且請求 resource 是直接給予，沒有 avoidance 機制。 - The system is in a safe state $\rightarrow\ P0,\ P2,\ P3, P1, P4\rightarrow\ no\ deadlock$ - If $P2$ request = ($0,\ 0,\ 1$) $\rightarrow$ 沒有 safe sequence 可以找到，系統可能產生 deadlock。 ### Deadlock Recovery - Process termination - 中止所有 deadlocked processes - 一次中止一個相關 process 直到 deadlock cycle 被消滅。 - 誰要被砍掉? - Resource preemption - 選擇一個受害者: 哪一個應該被搶佔? - rollback: partial rollback(check point) or total rollback? - starvation: 可以同一個 prcoess 總是被搶佔嗎? ## Ref [1] [上課影片 link](https://www.youtube.com/playlist?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX) [2] [投影片 link](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)