# Chap. 07 - Deadlock

> 課程內容 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

**Note:** [#deadlock](#Q-請說明何謂-deadlock-) [#requirement](#Q-請說明-deadlock-發生的必要條件-) [#prevention](#Q-如何預防-deadlock-的發生-) [#avoidance](#Q-如何在-run-time-期間避免-deadlock-的發生-?)

## Content

* [Introduction](#Introduction)
* [1. Necessary conditions](#1-Necessary-conditions)
* [2. System model](#2-System-model)
* [3. Holding deadlock](#3-Holding-deadlock)
* [Deadlock prevention](#Deadlock-prevention)
* [1. Mutual exclusion](#1-Mutual-exclusion)
* [2. Hold & wait](#2-Hold-amp-wait)
* [3. No preemption](#3-No-preemption)
* [4. Circular wait](#4-Circular-wait)
* [Deadlock avoidance](#Deadlock-avoidance)
* [1. RAG algorithm](#1-RAG-algorithm)
* [2. Banker's algorithm](#2-Bankers-algorithm)
* [2.1 Example 1: single type](#21-Example-1-single-type)
* [2.2 Example 2: multiple type](#22-Example-2-multiple-type)
* [Deadlock detection](#Deadlock-detection)
* [Recovery from deadlock](#Recovery-from-deadlock)

## Introduction

> **Definition**
> A set of blocked processes each holdig some resources and waiting to acquire a resource held by another and waiting to acquire a resource held by another process in the set.

**死結(deadlock)** 指的是 process **==掌握資源的同時，又在等待其他的資源==**，是一種資源使用與分配上的問題。

:::info
此處的資源(resource)是一種抽象觀念，泛指程式碼、CPU core、memory 等有限資源。
:::

> [!Tip] **Interview Ques.**
> ##### Q: 請說明何謂 deadlock ?
> 死鎖(deadlock)是一種資源使用與分配上的問題。當兩個以上的 process 互相等待對方持有的資源，導致所有 process 都無法執行的狀態時就是 deadlock，會造成系統停擺。

### 1. Necessary conditions

Deadlock 的發生需要**同時滿足**以下 4 個**必要條件**

* **Mutual exclusion**: 至少一個**資源不可共享**，每次只允許一個 process 使用一個資源
* **Hold and wait**: process **掌握某些資源**的同時又在**等待**其他的資源
* **No preemption**: 資源**不可被搶先**。process 所掌握的資源必須 **==主動==自願釋放**，沒辦法被強迫釋放資源(i.e. priority 較高)
* **Circular wait**: process 之間**互相等待**取得資源(類似 hold and wait)

當以上 4 個條件都滿足時就 **==有可能==** 會發生 deadlock。搭配以下的交通資源示意圖為例：

* Mutual exclusion 指的是道路寬度只允許一輛車通行
* Hold and wait 指的是霸佔路權(取得資源)的同時又在等待通行(等待資源)
* No preemption 指的是沒有其他優勢車種(Ex: 救護車)存在使得其他車輛不願意主動放棄資源
* Circular wait 指的是所有車輛之間互相等待，交通大打結


> [!Tip] **Interview Ques.**
> ##### Q: 請說明 deadlock 發生的必要條件 ?
> 1. (Mutual exclusion)系統中至少一個資源不能共享，每次只允許一個 process 使用
> 2. (Hold and wait)每個 process 掌握資源的同時又在等待其他資源
> 3. (Non preemption)每個 process 掌握的資源無法被其他 process 搶佔，除非主動釋放
> 4. (Circular wait)所有 process 的持有與等待狀況形成一個封閉循環

### 2. System model

描述 deadlock 發生的機制可以使用一個**系統模型**簡化

* 資源類型(resource type): R$_1$, R$_2$, ..., R$_n$
* Ex: CPU, memory page, I/O devices
* 每種資源類型 R$_i$ 又包含了 W$_i$ 的 instance(實例)
* Ex: CPU 有多個核心(core)
* 每個 process 使用 resource 的順序都依照: request :arrow_right: use :arrow_right_hook: release

Deadlock 是 process 與 resource 之間**使用調度上產生的問題**，所以可以透過 graph 描述 process 與 resource 之間的關係。以下圖為例，包含了：

<img src="https://hackmd.io/_uploads/HJwEErOKJl.png" width=200>

* Node
* 3 個 process: P$_1$, P$_2$, P$_3$
* 4 種 resource type: R$_1$, R$_2$, R$_3$, R$_4$
* R$_1$ 與 R$_3$ 只有 1 個 instance
* R$_2$ 有 2 個 instance
* R$_4$ 有 3 個 instance
* Eage
* Request edges: P$_i$ $\rightarrow$ P$_j$ 表示 P$_i$ 要求 R$_j$ 的資源(實例)
* Ex: P$_1$ $\rightarrow$ R$_1$
* Assignment edges: R$_i$ $\rightarrow$ P$_j$ 表示 R$_i$ 將資源(實例)分配(allocate)給 P$_j$
* Ex: R$_2$ $\rightarrow$ P$_1$

以上圖的 P$_1$ 為例，P$_1$ 掌握(hold on) R$_2$ 的一個 instance 同又在等待(waiting) R$_1$ 的一個 instance。

可用上述的圖論(Recource Alocation Graph, RAG)建立一個簡化過的系統模型來描述 deadlock 的發生，並從中找到解決方法。

##### Example: RAG with deadlock

<img src="https://hackmd.io/_uploads/Byw18r_Y1g.png" width=200>

上圖的 system model 中：

* P$_1$ 在等待(waitint) P$_2$
* P$_2$ 在等待(waitint) P$_3$
* P$_3$ 在等待(waitint) P$_1$ 與 P$_2$

RAG 包含了一個 cycle，所以 process 之間會發生 deadlock。

##### RAG with cycle but no deadlock

<img src="https://hackmd.io/_uploads/HkIUurutyg.png" width=200>

上圖的 system model 中：

* P$_1$ 在等待(waitint) P$_2$ 或 P$_3$
* P$_3$ 在等待(waitint) P$_1$ 或 P$_4$

因為 P$_2$ 與 P$_4$ 沒有在等待其他的 process，所以不會發生 deadklock

##### Conclusion

* 若 RAG **不包含 cycle**: 沒有 deadlock(因為 curcular wait 不成立)
* 若 RAG **包含 cycle**
* 每個 recource type 只有一個 instance: deadlock
* 每個 resource type 有很多個 instance: 可能發生 deadlock

### 3. Holding deadlock

**(1) 確保系統不會進入 deadlock 狀態**。有兩種方式可以確保系統不會發生 deadlock:

* Deadlock **prevention**(預防)
* 從系統角度來看，將 deadlock 發生的 4 個**必要條件拿掉一個**就不會發生 deadlock
* Deadlock **avoidance**(避免)
* 在 runtime 期間，分配資源前動態檢查 resource allocation 的狀態，如果會發生 deadlock 則不分配資源

**(2) 允許系統進入 deadlock 狀態之後再復原**。解決 deadlock 的問題需要考慮兩點

* Deadlock **detection**(偵測)
* Deadlock **recovery**(復原)

**(3) 忽略 deadlock 問題**。雖然 deadllock 出現時會佔用資源，但 **deadlock 的處理成本==代價很高==**，且**也==不容易==發生**，所以多數系統發生 deadlock 時會直接 **==忽略問題==**，交由使用者自行解決(通常是直接砍掉所有的 process)

## Deadlock prevention

根據 deadlock 發生的 4 個條件，從系統的角度討論該如何讓這 4 個條件不成立以(事先)**預防 deadlock 的發生**。

### 1. Mutual exclusion

對共享資源不使用 mutual exclusion，因為**有些共享資源並==不會==造成同步問題**，例如 read-only 的 memory。可以把 resource 做分類，不需要 mutual lock 的就可以不使用 mutual exclusion，反之則需要使用 mutual exclusion。

### 2. Hold & wait

避免 process 掌握資源的同時又需要取得其他資源。可以將其設計成 process 必須**一次性拿到所有的資源才能夠執行**，如果少一個 資源就必須**全部釋放**(release)後再重新取得。

但缺點會造成資源使用效率低，可能發生 starvation problem。

### 3. No preemption

當 process 在等待某個資源時，它所掌握的資源能夠**隨時被動地被打斷**，將資源的使用狀況紀錄下來等其他 process 完成後再還原此 process。例如 CPU 的 context switch。這種方式適用在可以輕易儲存與恢復狀態的資源上，例如 register 與 memory。

### 4. Circular wait

Circular wait 造成 deadlock 的原因是因為 process 執行的**優先順序會形成一個循環**(cycle)，導致最優先執行的反而會等待最慢執行的。
解決方式是**對所有的資源種類強加一個整體的順序**(total ordering)，process **要求 resource type 的行為必須是遞增**的。不可以(已經)拿取較高優先的資源後再要求較低優先的 resource。

假設 R = {R$_1$, R$_2$, ..., R$_n$}是 resource type 的集合。當某個 process 已經掌握 R$_5$ 時，若再要求 R$_3$ 則需要先釋放 R$_5$。

> [!Tip] **Interview Ques.**
> ##### Q: 如何預防 deadlock 的發生 ?
> 1. (Mutual exclusion)不會造成同步問題(Ex. 唯讀檔案)的資源，可以不需要 mutex lock
> 2. (Hold and wait)可以設計成必須要一次性取得所有資源才能執行，否則就要釋放全部資源
> 3. (No preemption)將資源設計成可以被搶佔，紀錄使用狀況之後再還原(context switch)
> 4. (Circular wait)對所有資源制定順序，必須依照遞增順序取得資源
>
> (四個條件拿掉一個即可，挑一到兩個說明就好)

## Deadlock avoidance

Avoidance 是在 **runtime 期間**避免 deadlock 的發生。考慮執行期間 resource 使用上的最壞狀況(worse case)，當最壞狀況都不會發生 deadlock 時表示可以讓 processes 繼續進行。

分為兩種類型：

* single instance of a resource type
* RAG algorithm
* Multiple instance of a resource type
* Banker's algorithm

### 1. RAG algorithm

Resource Allocation Graph(RAG) 的邊(edges) 可以分為 3 種(如圖)

* <font color="ff0000">**Request edge**</font>: P$_i$ $\rightarrow$ R$_j$
* P_i 正在等待 R_j
* 表示已經發生 request resource
* <font color="#00A600">**Assignment edge**</font>: R$_j$ $\rightarrow$ P$_i$
* R_j 被分配給 P_i
* 表示已經發生 assign resource
* <font color="#5B00AE">**Claim edge**</font>: P$_i$ $\rightarrow$ R$_j$
* P_i 可能會要求 R_j
* 事前預估的情況，尚未發生但未來可能發生

當 process 要求某個 resource 時，<font color="#5B00AE">claim edge</font> 會轉成 <font color="ff0000">**request edge**</font>。當 resource 被釋出給 process 時，<font color="#00A600">**assignment edge**</font> 會轉成 <font color="#5B00AE">**claim edge**</font>

<img src="https://hackmd.io/_uploads/rkeg8YKtyg.png" width=300>

以上圖為例討論如下

(1) 當 edge 1 轉成 <font color="#00A600">**assignment edge**</font> 時：
就算 edge 2 轉成 <font color="ff0000">**request edge**</font> 也不會有 cucle 產生，因此不會發生 deadlock。

(2) 當 edge 2 轉成 <font color="#00A600">**assignment edge**</font> 時：
如果 edge 1 轉成 <font color="ff0000">**request edge**</font> 則會形成 cycle，可能會發生 deadlock。

(3) 結論：<font color="#5B00AE">**claim edge 2**</font> 絕對不能變成 <font color="#00A600">**assignment edge**</font>。但使用 cycle detection algorithm 的代價太高($O(n^2)$)所以通常是放著不管。

### 2. Banker's algorithm

適用單一 resource type 有多個 instance 的情況。整個系統可以分為 3 個種類

* safe state: 絕對不可能發生 deadlock 的情況
* unsafe sate: worse case 的情況下可能發生 deadlock
* deadlock: 真的發生 deadlock

我們的目的是要找到一組資源分配的順序(sequence of allocation, also called safe sequence)使得 process 保持在 safe state 之中。

<img src="https://hackmd.io/_uploads/H1uDtYttkl.png" width=300>

> [!Tip] **Interview Ques.**
> ##### Q: 如何在 run time 期間避免 deadlock 的發生 ?
> 每次分配資源之前模擬分配結果，判斷分配後會不會導致系統進入不安全的狀態 :
> * 會，拒絕資源分配請求
> * 不會，允許分配資源

#### 2.1 Example 1: single type

假設 tape driver(一種 resource type) 有 12 個 instance，在 t$_0$ 時刻有 3 個 processes 狀況如下

| Process No. | Max Needs | Current holding | Need | Available |
| :-: | :-: | :-: | :-: | :-: |
| P$_0$ | 10 | 5 | 5 | 0 |
| P$_1$ | 4 | 2 | 2 | 5 |
| P$_2$ | 9 | 2 | 7 | 0 |

(Max need 指的是 worse case 的情況下 process 同時會使用到的最多 resource instance)
(Avaliable 指的是目前可用的 resource instance)

(1) t$_1$ 時刻，available = 12 - 5 - 2 - 2 = 3
P$_1$ 需要的資源最少，先將可用的資源分配給 P$_1$ 滿足需求。

(2) t$_2$ 時刻， available = 3 + 2 = 5
P$_1$ 執行完後會把前一刻取得的資源(available=3)與原有的資源(current=2)釋出，此時 P$_0$ 需要的資源最小，再將可用的資源(available=5)分配給 P$_0$

| Process No. | Max Needs | Current holding | Need | Available |
| :-: | :-: | :-: | :-: | :-: |
| P$_0$ | 10 | 5 | 5 | 10 |
| P$_1$ | 4 | 0 | 0 | 0 |
| P$_2$ | 9 | 2 | 7 | 0 |

(3) t$_3$ 時刻，available = 5 + 5 = 10
P$_1$ 執行完後同樣釋出取得的資源(available=5)與原有資源(available=5)，最後在分配給 P$_2$。

| Process No. | Max Needs | Current holding | Need | Available |
| :-: | :-: | :-: | :-: | :-: |
| P$_0$ | 10 | 0 | 0 | 0 |
| P$_1$ | 4 | 0 | 0 | 0 |
| P$_2$ | 9 | 2 | 7 | 10 |

<P$_1$, P$_0$, P$_2$> 為其中一組 safe sequence

但當 P$_2$ 的持有資源變為 3 就是 unsafe state，因為無法找到一組 safe sequence。

| Process No. | Max Needs | Current holding | Need | Available |
| :-: | :-: | :-: | :-: | :-: |
| P$_0$ | 10 | 5 | 5 | 0 |
| P$_1$ | 4 | 2 | 2 | 2 |
| P$_2$ | 9 | 3 | 6 | 0 |

#### 2.2 Example 2: multiple type

Banker's algorithm 適用在單一個 resource type 有多個 instance 的情況，會事先預估在分配 resource 後會不會存在 safe sequence。只有當 safe sequence 存在才會繼續進行。

以下為例，有 3 種 resource type(instance): A(10), B(5), C(7) 與 4 個 process

| Process No. | Max Needs | Current holding | Need | Available | Run |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | (A, B, C) | (A, B, C) | (A, B, C) | (A, B, C) | |
| P$_0$ | (7, 5, 3) | (0, 1, 0) | (7, 4, 3) | (0, 0, 0) | |
| P$_1$ | (3, 2, 2) | (2, 0, 0) | (1, 2, 2) | (0, 0, 0) | |
| P$_2$ | (9, 0, 2) | (3, 0, 2) | (6, 0, 0) | (0, 0, 0) | |
| P$_3$ | (2, 2, 2) | (2, 1, 1) | (0, 1, 1) | (0, 0, 0) | |
| P$_4$ | (4, 3, 3) | (0, 0, 2) | (4, 3, 1) | (0, 0, 0) | |

3 種 type 需要同時滿足 available > need 才能夠執行。

(1) t$_1$ 時刻 available = (3, 3, 2)，執行 P$_1$
| Process No. | Max Needs | Current holding | Need | Available | Run |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | (A, B, C) | (A, B, C) | (A, B, C) | (A, B, C) | |
| P$_0$ | (7, 5, 3) | (0, 1, 0) | (7, 4, 3) | (0, 0, 0) | |
| P$_1$ | (3, 2, 2) | (2, 0, 0) | (1, 2, 2) | (3, 3, 2) | :ballot_box_with_check: |
| P$_2$ | (9, 0, 2) | (3, 0, 2) | (6, 0, 0) | (0, 0, 0) | |
| P$_3$ | (2, 2, 2) | (2, 1, 1) | (0, 1, 1) | (0, 0, 0) | |
| P$_4$ | (4, 3, 3) | (0, 0, 2) | (4, 3, 1) | (0, 0, 0) | |

(2) t$_2$ 時刻 available = (5, 3, 2)，執行 P$_3$
| Process No. | Max Needs | Current holding | Need | Available | Run |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | (A, B, C) | (A, B, C) | (A, B, C) | (A, B, C) | |
| P$_0$ | (7, 5, 3) | (0, 1, 0) | (7, 4, 3) | (0, 0, 0) | |
| P$_1$ | (3, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_2$ | (9, 0, 2) | (3, 0, 2) | (6, 0, 0) | (0, 0, 0) | |
| P$_3$ | (2, 2, 2) | (2, 1, 1) | (0, 1, 1) | (5, 3, 2) | :ballot_box_with_check: |
| P$_4$ | (4, 3, 3) | (0, 0, 2) | (4, 3, 1) | (0, 0, 0) | |

(3) t$_3$ 時刻 available = (7, 4, 3)，執行 P$_4$
| Process No. | Max Needs | Current holding | Need | Available | Run |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | (A, B, C) | (A, B, C) | (A, B, C) | (A, B, C) | |
| P$_0$ | (7, 5, 3) | (0, 1, 0) | (7, 4, 3) | (0, 0, 0) | |
| P$_1$ | (3, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_2$ | (9, 0, 2) | (3, 0, 2) | (6, 0, 0) | (0, 0, 0) | |
| P$_3$ | (2, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_4$ | (4, 3, 3) | (0, 0, 2) | (4, 3, 1) | (7, 4, 3) | :ballot_box_with_check: |

(4) t$_4$ 時刻 available = (7, 4, 5)，執行 P$_2$
| Process No. | Max Needs | Current holding | Need | Available | Run |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | (A, B, C) | (A, B, C) | (A, B, C) | (A, B, C) | |
| P$_0$ | (7, 5, 3) | (0, 1, 0) | (7, 4, 3) | (0, 0, 0) | |
| P$_1$ | (3, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_2$ | (9, 0, 2) | (3, 0, 2) | (6, 0, 0) | (7, 4, 5) | :ballot_box_with_check: |
| P$_3$ | (2, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_4$ | (4, 3, 3) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |

(4) t$_5$ 時刻 available = (10, 4, 7)，執行 P$_0$
| Process No. | Max Needs | Current holding | Need | Available | Run |
| :-: | :-: | :-: | :-: | :-: | :-: |
| | (A, B, C) | (A, B, C) | (A, B, C) | (A, B, C) | |
| P$_0$ | (7, 5, 3) | (0, 1, 0) | (7, 4, 3) | (10, 4, 7) | :ballot_box_with_check: |
| P$_1$ | (3, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_2$ | (9, 0, 2) | (3, 0, 2) | (6, 0, 0) | (7, 4, 5) | |
| P$_3$ | (2, 2, 2) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |
| P$_4$ | (4, 3, 3) | (0, 0, 0) | (0, 0, 0) | (0, 0, 0) | |

safe sequence: <P$_1$, P$_3$, P$_4$, P$_2$, P$_0$>

## Deadlock detection

關注現在的狀況並用 **avoid alogorithm** 的方式思考。以 single instance 為例，要盡量避免 cycle 的產生。

## Recovery from deadlock

當真的發生 deadlock 後該怎麼復原，有 2 種方法

* Process **==termination==**: 直接**終止 process 的執行**，可以選擇**全部終止**或是**一次只終止一個**直到沒有 deadlock
* Resource preemption: 打斷 process 並**釋放**其有的資源給別的 process 使用，但須要考慮打斷哪一個 process