# What is deadlock?

在一個 task 想要向 OS 索取 resource (資源) 的時候，如果這些 resource 並非能夠馬上使用的，就會使這個 task 進入 wait (等待) 的狀態，如果這些 resource 又被其他正在 wait 的 task 所持有，將會使這個正在 wait 的 task 永遠無法改變其 wait 的狀態，這個現象就是 **deadlock (死結)**

> 這邊的 task 指的是一個抽象的執行單位，可能是 process 或是 thread，姜媽的講義似乎都以 thread 表示

:::info
對死結的最佳說明要回溯到美國堪薩斯州在 20 世紀初所制定的一條法律來詮釋，部分內容為: 當兩輛火車同時到達一交叉路口時，雙方都必須完全停止，待一輛駛去之後，另一輛再通過
:::

# 系統模型

一個 OS 包含可分配給 task 的**有限** resource。這些 resource 可區分成許多 class (類型)，每種都會含有一至數個相同類型的 instance (實例)

一個 task 在使用一 resource 前必須先進行 **request (請求)**，並在使用完後 **release (釋放)**

在正常運作模式下，一個 task 都只能依下方順序去使用資源:

1. request

> 若此請求無法馬上被認可，例如這個 resource 正在被使用，則 task 進入 wait 的狀態等待此 resource

2. use

> task 得以使用此 resource

3. release

> task 釋放此 resource，告知 OS 這個 resource 變回可用的狀態

:::info
例如在撰寫 C 程式時，使用 `malloc()` 去 request 一塊動態的記憶體空間跟使用完後使用 `free()` release 這一段記憶體空間
:::

:::warning
一個 task 所要求的 resource 不可超過 OS 可用的 resource 總數
:::

# 範例: mutex (互斥鎖) 的 deadlock

以下程式碼範例初始化了倆 mutex

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

接下來，產生 `thread_one` 跟 `thread_two` 分別執行 `do_work_one()` 跟 `do_work_two()` 兩個 function

/* thread one runs in this function */
void *do_work_one(void *param) {
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    /** * Do some work */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    pthread_exit(0);
}

/* thread two runs in this function */
void *do_work_two(void *param) {
    pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    /** * Do some work */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    pthread_exit(0);
}

`thread_one` 嘗試以

1. `first_mutex`
2. `second_mutex`

取得 mutex

`thread_two` 嘗試以

1. `second_mutex`
2. `first_mutex`

取得 mutex

當 `thread_two` 獲得 `second_mutex` 時，若 `thread_one` 獲得 `first_mutex`，則**有可能造成 deadlock**

# 造成 deadlock 的四個"必要"條件

> 全部**同時成立**，才會造成 deadlock

## Mutual exclusion 互斥

一次只能有一 task 使用此 resource，意即 Non-shareable (不可共享的)

## Hold and Wait 佔用與等待

存在一已 hold (佔用) resource 的 task，且正在 wait 被其他 task 佔用的 resource

## No Preemption 不可搶先

resource 無法被 preemption (搶先)，意即這個 resource 只能被 hold 的 task 去 release

## Circular wait 循環等待

存在一等待彼此的 task 集合，假設有 {A, B, C} 三個 tasks，A 等 B，B 等 C，C 等 A，形成迴圈就是 circular wait

:::info
四個條件事實上息息相關，像

- 處於 circular wait 的狀態時，也包含了 hold and wait
- 又或是 task 0 在等待 task 1 時，若 task 0 能夠搶奪 task 1 的資源，就不會發生等待，所以一定也有 no preemtion 這個條件
:::

# Resource-Allocation Graph (資源分配圖)

deadlock 現象可用 system resource-allocation graph (系統資源配置圖) 表示

- 由一組 vertices (頂點) V 和一組 edges (邊) E 組成
- V 又具有兩種類型
- T 表示正在執行之 task 集合，$T = \{ T_1, T_2, ..., T_n \}$
- R 表示 OS 所有 resource class 的集合，$R = \{R_1, R_2, ..., R_n\}$
- E 也有兩種
- request edge (請求邊)，由 T 指向 R，意即 task T 已要求 class R 的 resource instance，且正在 wait，通常這樣表示 $T_i \rightarrow R_i$
- assignment edge (分配邊)，由 R 指向 T，意即 class R 的某個 resource instance 已被 task T 持有，處於 hold 的狀態，通常這樣表示 $R_i \rightarrow T_i$

## 例圖


- 集合 $T$ $R$ $E$
- $T = \{T_1, T_2, T_3\}$
- $R = \{R_1, R_2, R_3, R_4\}$
- $E = \{T_1 \rightarrow R_1 , T_2 \rightarrow R_3, R_1 \rightarrow T_2, R_2 \rightarrow T_2, R_2 \rightarrow T_1, R_3 \rightarrow T_3\}$
- resource instance (黑點點)
- class $R_1$ 的 resource 有 1 個 instance
- class $R_2$ 的 resource 有 2 個 instance
- class $R_3$ 的 resource 有 1 個 instance
- class $R_4$ 的 resource 有 3 個 instance
- task 狀態
- $T_1$ 正在 hold $R_2$ 的一個 instance，並在等待一個 $R_1$ 的 instance
- $T_2$ 正在 hold $R_1$ 以及 $R_2$ 的各一個 instance，並在等待一個 $R_3$ 的 instance
- $T_3$ 正在 hold $R_3$ 的一個 instance

:::info
- 如果此圖中沒有 cycle (循環) 存在，則此系統中不會發生 deadlock
- 若此圖中具有 cycle 且所有 class 的 resource 都只有一個 instance 就會發生 deadlock
- 若此圖中具有 cycle 且所有 class 的 resource 有多個 instance 則**有可能** (不一定) 發生 deadlock
:::

# 處理 deadlock 的方式

一般來說，可以從以下三種方法之一來處理 deadlock:

- 使用某種 protocol (協議) 以**預防**或是**防止** deadlock
- deadlock prevention
- deadlock avoidance
- 允許系統進入 deadlock 的狀態，**偵測**到後再想辦法**恢復**
- deadlock detection
- deadlock recovery
- ignore (忽視) deadlock，假裝系統從沒發生 deadlock

:::info
第三種方法被大部分的 OS 所採用，包含 UNIX-like 以及 Windows，因此處理 deadlock 通常由系統程式開發人員自行處理
:::

# Deadlock prevention (預防)

提供一組方法，確保之前提及的四個產生 deadlock 的必要條件，至少有一項不被滿足，以下分別進行說明

## Mutual exclusion

若 mutual exclusion 成立，則代表至少有一項 resource 是不可共享的，反之，可共享的 resource 就不必以 mutex 的方式進行存取，所以就不會產生 deadlock

假設有很多 task 都想要開啟一個 read-only (唯讀) 的檔案，則可以讓它們同時存取此檔案

:::info
但實務上來說，幾乎不可能透過排除 mutual exclusion 來預防 deadlock，因為許多 resource **本質上就是無法共用**的
:::

## Hold and Wait

為了使此條件不成立，需要保證一個 task 在 request 一項 resource 時，不可 hold 其他 resource，以下介紹兩種方式

- 每個 task 在執行前，都必須先 request 並被 OS 成功分配所需的 resource
- 只允許 task 在未 hold 任何 resource 的情況下才能夠 request resource，意即一個 task 在需要某些 resource 時，在進行 request 前必須先 release 掉所有正 hold 的 resource

這邊假設有一 task，要從 DVD 複製資料至一 disk file，然後對其進行排序，最後將結果由印表機印出

如果使用第一種方法，此 task 就必須一開始就 request DVD、disk file 跟印表機，雖在最後才使用到印表機，但這個 task 整個執行過程中都 hold 著印表機

第二種方法允許這個 task 一開始只 request DVD 跟 disk file，等此 task 將 DVD 的資料複製完畢後，就要把 DVD 跟 disk file 都 release 掉，然後再要求 disk file 跟印表機，待列印完成後再 release 掉這兩項 resource

:::info
這兩種方式有兩個主要的缺點:

- 資源使用率 (resource utilization) 有可能很低，因為大部分時間許多 resource 可能只是被分配而未實際使用
- 有可能產生 starvation (飢餓) 現象，當一個 task 需要用到的許多 resource，其中一樣被其他 task 使用，這個 task 將會永遠處於 wait 狀態
:::

## No Preemption

要避免此條件，有以下幾種方法:

- 如果某 task 已經 hold 著一些 resource，而它要 request 一個無法立即獲得的 resource (也就是它會處於 wait 的狀態)，則此 task hold 的 resource 應該要給其他 task 搶先使用，意即處於 wait 狀態後會 implicitly (隱含地) release 所有 resource
- 如果某 task 需要幾項 resource，須先檢查 resource 是否可被使用，如果可以就直接分配，如果不是，就再往下檢查說這些 resource 是否被一些其他正在 wait 的 task hold 著，如果是的話就從這些正在 wait 的 task 把 resource 搶先分配給此 task，如果真的無法立即分配此 task 就會進入 wait 的狀態，同理它原本 hold 的 resource 就能夠被其他 task 搶先

> 上方提及的方式，被搶先或者處於 wait 的 task，只有能夠重新獲得原本 hold 的 resource 再加上正 request 的 resource 時，才會繼續執行

:::info
此些做法，通常適用於 resource 的狀態能夠輕易被保存及恢復的情況下，像是 memory 以及 CPU register，不適用於 mutex 或是 semaphore 這類的 resource
:::

## Circular wait

確保不會發生此條件的方法是: 對所有 resource class 強迫安排一線性的順序，task 在 request resource 時必須依照數字大小，遞增的提出 request

為了方便說明，假設 $R = \{R_1, R_2, R_3, ..., R_m\}$ 為 resource class 的集合，然後定義一函數 $F: R \rightarrow N$ 來產生一對一的正整數，舉例來說，若 resource class 集合 $R$ 中有包含 DVD drive、disk drive 還有印表機則可能表示如下

- $F(DVD) = 1$
- $F(disk) = 5$
- $F(printer) = 12$

然後接下來可以考慮以下做法來預防 deadlock:

- 每一 task 只能依遞增的方式去 request resource，以上方的例子來說，若有一 task 需要同時使用 DVD 跟印表機，則必須先要求 DVD 才能再要求印表機 (因為 $F(printer)$ > $F(DVD)$)
- 若一 task 要求 resource class $R_j$ 時，並定要先 release 所有的資源 $R_i$，其中 $R_j \ge R_i$

:::info
上方提及的預防 deadlock 的方式，都會有一些副作用，就是

- low device utilization (降低資源使用率)
- reduced system throughput (降低系統效能)
:::

# Deadlock avoidance (避免)

避免 deadlock 主要的概念就是，要讓 task 提供多一些關於 request resource 的相關資訊，其中最簡單的且最有用的方式就是，每個 task 都需要宣告其所需每種 class 的 resource 之最大數量

使用這類資訊就能建立出一演算法去保證系統不會進入 deadlock ，這種演算法會動態檢查 resource-allocation state (資源分配狀態)，以確保不會出現 circular wait

:::info
resource-allocation state 會被三個元素決定:

- available (可被使用的) resources 數量
- allocated (已分配的) resources 數量
- task 對 resource 的 maximum demands (最大需求)
:::

## safe state (安全狀態)

如果 OS 能以某種順序將 resource 分配給各個 task (符合其最大值)，且不會產生 deadlock，就稱為 safe state

或者說一個 OS 只有在 safe sequence 存在時，才算處於 safe state

> safe sequence 是指一群 task 的執行順序，此順序能夠使這些 task 能夠在不產生 deadlock 的情況下順利執行完畢

:::info
- 如果 OS 處於 safe state 則**不會**發生 deadlock
- 如果 OS 處於 unsafe state 則**有可能**發生 deadlock
- deadlock avoidance 的主要方式就是確保 OS 永遠不會進入 unsafe state
:::

## Resource-Allocation Graph Algorithm

如果有一 resource 分配系統，其中所有 resource class 都各**只有一個 instance**，則之前提及的 resource-allocation graph 可用來避免 deadlock

這邊要再額外加上一個新的 claim edge (申請邊)，此種邊與 request edge 相似，都是由 T 指向 R，但以**虛線**表示，意義是 T 有可能會需要 R，當 T request R 時，要將 claim edge 轉為 request edge，然後在 T release R 時，要將 assignment edge 再轉回 claim edge

### 例圖


這邊假設 $T_2$ 想要 request $R_2$，雖然此時 $R_2$ 可用，但不能將 $R_2$ 分配給 $T_2$，因為將會在圖中產生 cycle，而系統就會處於 unsafe state，這時如果 $T_1$ request $R_2$ 且 $T_2$ 要求 $R_1$ 就會產生 deadlock

:::info
- resource-allocation graph algorithm 不適用於有多個 instance 的 resource 分配系統
- 使用 cycle detection 去判斷系統是否處於 safe state
:::

## Banker's Algorithm

- 如果是在所有 resource class 有很多 instance 的狀況，banker's algorithm 就會是個較好的選擇
- 當一新的 task 進入系統時，必須先宣告可能需要的每種 resource class 的最大數量，此數量不能超過系統所有資源的總數
- 當一 task request 一組 resource 時，就要馬上評估是否會因此進入 unsafe state，若仍能處於 safe state，就能將這些 resource 分配給此 task，否則此 task 就必須 wait 直到其他 task release 足夠的 resource

:::info
此名稱是出自銀行系統中，確保可用資金都能滿足客戶需求的分配方式
:::

### 例題

- 有 5 個 task
- $T_0$
- $T_1$
- $T_2$
- $T_3$
- $T_4$
- 有 3 種 resource class
- A (10 個 instance)
- B (5 個 instance)
- C (7 個 instance)

目前的狀態如下

- Allocation (已分配的 resource)

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 0 | 1 | 0 |
| $T_1$ | 2 | 0 | 0 |
| $T_2$ | 3 | 0 | 2 |
| $T_3$ | 2 | 1 | 1 |
| $T_4$ | 0 | 0 | 2 |

- Max (最大需求)

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 7 | 5 | 3 |
| $T_1$ | 3 | 2 | 2 |
| $T_2$ | 9 | 0 | 2 |
| $T_3$ | 2 | 2 | 2 |
| $T_4$ | 4 | 3 | 3 |

試求出 safe sequence

### 解法

1. 先求出 Available

A 可從題目中條件知道有 10 個 instance
所以去剪掉 Allocation 中已被分配出去的部分即可得出:

A = 10 - (0 + 2 + 3 + 2 + 0) = 3

B, C 同理

B = 5 - (1 + 0 + 0 + 1 + 0) = 3

C = 7 - (0 + 0 + 2 + 1 + 2) = 2

- Available (可用資源)

| A | B | C |
|:---:|:---:|:---:|
| 3 | 3 | 2 |

2. 再求出 Need

求出 Need 的公式為 Max - Allocation

T0 = (7, 5, 3) - (0, 1, 0) = (7, 4, 3)
T1 = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)
T2 = (9, 0, 2) - (3, 0, 2) = (6, 0, 0)
T3 = (2, 2, 2) - (2, 1, 1) = (0, 1, 1)
T4 = (4, 3, 3) - (0, 0, 2) = (4, 3, 1)

- Need

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 7 | 4 | 3 |
| $T_1$ | 1 | 2 | 2 |
| $T_2$ | 6 | 0 | 0 |
| $T_3$ | 0 | 1 | 1 |
| $T_4$ | 4 | 3 | 1 |

3. 判定目前是否有 safe sequence

目前已知 Available =  (3, 3, 2)
檢查看看目前 T0 ~ T4 的 Need 當中是否有可以被成功分配的 (就是要 <= (3, 3, 2))

1. T1 (1, 2, 2) <= (3, 3, 2)
2. 成功執行後釋放資源 Available (3, 3, 2) 從 T1 獲得 Allocation (2, 0, 0)
3. 所以 Available 變為 (3, 3, 2) + (2, 0, 0) = (5, 3, 2)
4. 重新開始找尋剩下的 task 中是否有可以成功分配的

最終可得 T1, T3, T4, T2, T0 這個 safe sequence

### 如果原始狀態中，$T_1$ 額外 request (1, 0, 2) 的 resource 呢?

1. 首先先檢查 (1, 0, 2) 有沒有超過 Need 且 Available 夠用

原始狀態中 T1 的 Need = (1, 2, 2)，(1, 0, 2) <= (1, 2, 2) 所以條件成立
原始狀態中 Available = (3, 3, 2)，(1, 0, 2) <= (3, 3, 2) 所以能夠分配

2. 狀態改變

因應這額外的分配，需要調整相應的狀態
Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
T1 的 Allocation = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
T1 的 Need = (3, 2, 2) - (3, 0, 2) = (0, 2, 0)

得出狀態如下

- Allocation (已分配的 resource)

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 0 | 1 | 0 |
| $T_1$ | 3 | 0 | 2 |
| $T_2$ | 3 | 0 | 2 |
| $T_3$ | 2 | 1 | 1 |
| $T_4$ | 0 | 0 | 2 |

- Need

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 7 | 4 | 3 |
| $T_1$ | 0 | 2 | 0 |
| $T_2$ | 6 | 0 | 0 |
| $T_3$ | 0 | 1 | 1 |
| $T_4$ | 4 | 3 | 1 |

- Available (可用資源)

| A | B | C |
|:---:|:---:|:---:|
| 2 | 3 | 0 |

3. 判定目前是否有 safe sequence

參考上方做法，可得出 safe sequence: T1, T3, T4, T0, T2

所以這個 request 是可行的

:::info
- 在此新狀態中，若 $T_4$ 想要再額外 request (3, 3, 0) 就是不可行的，因為 Available 已經不夠用了
- 但在此新狀態中，$T_0$ 再額外 request (0, 2, 0)，就算 Available 夠用也不能答應，因為會找不到 safe sequence，意即進入 unsafe state
:::

# Deadlock detection (偵測)

假設 OS 沒有 deadlock prevention 跟 deadlock avoidance 的機制，此時系統就須提供

- 檢察系統狀態判斷是否有 deadlock 產生的演算法
- 從 deadlock 恢復的機制

## Wait-for Graph

- 適用於所有 resource class 都各**只有一個 instance** 的系統
- 同樣變化自 resource-allocation graph
- 也同樣是判斷是否有 cycle 的存在
- 簡單來說就是拿掉所有 resource 並把等待的邊連起來

假設有一 resource-allocation graph 如下


則 wait-for graph 如下


:::info
- 若 wait-for graph 中有 cycle，則系統必有 deadlock
- 為了偵測 deadlock，系統必須一直維護此圖
:::

## Deadlock Detection Algorithm

- 適用於所有 resource class 都**有多個 instance** 的系統

### 例題

- 有 5 個 task
- $T_0$
- $T_1$
- $T_2$
- $T_3$
- $T_4$
- 有 3 種 resource class
- A (7 個 instance)
- B (2 個 instance)
- C (13 個 instance)

目前的狀態如下

- Allocation

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 0 | 1 | 0 |
| $T_1$ | 2 | 0 | 0 |
| $T_2$ | 3 | 0 | 3 |
| $T_3$ | 2 | 1 | 1 |
| $T_4$ | 0 | 0 | 2 |

- Request

| | A | B | C |
|:-----:|:---:|:---:|:---:|
| $T_0$ | 0 | 0 | 0 |
| $T_1$ | 2 | 0 | 2 |
| $T_2$ | 0 | 0 | 0 |
| $T_3$ | 1 | 0 | 0 |
| $T_4$ | 0 | 0 | 2 |

- Available

| A | B | C |
|:---:|:---:|:---:|
| 0 | 0 | 0 |

1. 找尋 safe sequence

1. 看看 Available (0, 0, 0) 能否執行任何一個 task
2. T0 的 Request (0, 0, 0) <= Avaiable (0, 0, 0)，可以執行
3. T0 release resource 給 Available (0, 0, 0) + (0, 1, 0) = (0, 1, 0)
4. 看看 Available (0, 1, 0) 能否執行任何一個剩下的 task，並依此類推

最終可得 T0, T2, T3, T1, T4

:::info
- 假設在初始狀態，$T_2$ 額外進行請求 (0, 0, 1)，將會導致 deadlock 發生，因為沒有足夠的 resource 進行任何 task
:::

### Detection-Algorithm 的使用

需要考慮下方兩種因素，去判斷什麼時候該使用 detection-algorithm

- 多久會發生一次 deadlock
- 有多少個 task 被 deadlock 影響

若經常發生 deadlock，則演算法的執行將會變得頻繁，但在解決 deadlock 前，系統又會不斷地把 resource 分配給 task，因此受到 deadlock 影響的 task 可能會越來越多

# Recovery (恢復) from deadlock

當偵測到 deadlock 之後，可以有兩種結束 deadlock 的方式

- 直接終止一或多個 task
- 搶先一或多個陷入 deadlock 的 task 所持有的 resource

## 終止 task

藉由中止 task 來消除 deadlock 有兩種方法

- 直接終止所有在 deadlock 中的 task
- 雖然這樣可以消除 deadlock，但代價會很大，因為這些 task 有可能已經執行了很長時間，而這些計算結果將會被拋棄，並且極有可能要重新計算
- 一次終止一個 task 直到 deadlock 消失
- 這樣會有不小的系統開銷，因為在每終止一個 task 之後，都必須重新執行 detection-algorithm 去判斷 deadlock 是否還存在

:::info
如果使用第二種方法，就必須決定要終止哪些 task 來消除 deadlock，但許多元素都可以決定要選擇哪個 task

- task 的優先權
- task 工作了多久? 還需要多少時間?
- task 使用了多少 resource，都是哪些 class
- task 還需要多少 resource，才能夠完成
- 有多少 task 需要被終止
- task 的類型
:::

## 搶先陷入 deadlock 的 resource

為了透過 preemption 來消除 deadlock，需要考慮以下三個議題:

- select a victim (選擇犧牲者)
- 以最小開銷的方式去做選擇
- rollback (回溯)
- 因 resource 被搶先，所以 task 已經不能正常執行，要能夠讓被搶先的 task 能夠回溯到某個能正確執行的狀態
- starvation (飢餓問題)
- 保證 task 不會一直被搶先

---

# 考古題

- **Deadlock prevention** provides a set of methods to ensure that at least one of the necessary conditions cannot hold.
- **Deadlock avoidance** requires that OS be given additional information in advance concerning which resources a thread will request and use during its lifetime.
- **low device utilization** and **reduced system throughput** are possible side effects of Preventing Deadlocks.
- When a thread requests an available resource, system must decide if immediate allocation leaves the system in a **safe state**
- **Circular Wait**, which is one way of deadlock prevention,impose a total ordering of all resource types.
- OS will break **hold and wait** to prevent deadlock,which means that OS will require each thread to request and be allocated all its resources before it begins execution.
- When system has only one instance of each resource type, OS can use **Resource-Allocation Graph Algorithm** to execute deadlock avoidance


> allocation: 已獲得的資源數量
> max: 完成工作所需的最大資源量
> available: 系統目前的可用資源

- 將 max - allocation 得出 need
- 接著看 available 是否可以負擔 need
- 若有某一個 thread 可以負擔，完成後須把 allocation 的數字加回去