# OS-Chap7 - Deadlock_死結
###### tags: `作業系統 Operating System note`, `110-1`, `2021`
# Contents
[TOC]

---

## 一、Definition
- 一組process互相等待對方資源，造成所有process無法繼續執行，導致CPU使用率降低。
(彼此holding住對方require的resource)

## 二、Model
- **Resource**: R1, R2, R3 ...
- 每個resource(Ri)有 Wi個instance。(Wi = 1, 2, 3...)
- EX : CPU cycles, memory space, I/O devices
- **Process**:
- 欲利用資源，必經以下三種階段：
- 1. 要求資源。(request)
- 2. 能夠使用資源。(use)
- 3. 釋放資源。(release)

## 三、欲產生Deadlock，必符合以下四個條件
###### (充要/充分/**必要**)(?)
- ## :heavy_exclamation_mark: 必考 :heavy_exclamation_mark:
- **Mutual Exclusion : (互斥)**
- 一次只有一個 process 能夠使用該資源。

- **Hold & Wait : (持有並等待)**
- 一個 process 持有部分 resource，同時間又在等待其他 processes 持有的 resource。

- **No preemtion : (不可搶奪/中斷)**
- 除非一 process 在 waiting 時，自願 release 自己 holding 的 resource，否則無法被其他人搶奪。

- **Circular wait : (循環等待)**
- 一組process等待另一個process，而形成循環。
- P0 →P1 →...→Pn →P0
- 因為 P0 的 resource 被 P1 占用，所以再等 P1 釋放

## 四、RAG___資源分配圖(Resource-Allocation Graph)
> 用 RAG 理解 deadlock
- 由 vetices(V) 和 edges(E) 組成。
- Vertices分成 processes 和 Resources 的點集合。
- P = {P1, P2, ... Pn}
- R = {R1, R2, ... }
- Edges 分成以下幾種edge：
- claim edge : 下方 deadlock avoidance/ algorithm/ single instance 提及
- **request edge : Pi 已經向 Rj 提出使用要求，並已經在 waiting 使用 Rj**
- **assigment edge : Rj 已經被 allocate 給 Pi，所以該 resource 的其中一個 instance 已經無法使用。**
- Pi → Rj : Pi 要求使用 Rj 的資源(Pi requests instance of Rj)
- Pi ← Rj : Pi 已經擁有 Rj 中的其中一個資源(Pi is holding an instance of Rj)
## :heavy_exclamation_mark: 必考 :heavy_exclamation_mark:
- 結論
- graph 無 cycle → no deadlock
- graph 有 cycle，且cycle 中經過的 resources
- 一個 resource 只含有一個 instance → deadlock
- 一個 resource 含有不只一個 instance → **"可能會"** 產生 deadlock

### Example : 沒有cycle、沒有deadlock

- #### 對每個 processes 而言
- P1
- 已經有 R2 中的一個 instance。
- 要求 R1 中的一個 instance。
- P2
- 已經有 R1 及 R2 中的一個 instance。
- 要求 R3 中的一個 instance。
- P3
- 已經有 R3 中的一個 instance。
- ##### 沒有cycle、沒有deadlock。

- #### 對各個 resource 而言
- R1 的 resource 被 P2 持有。
- R2 的 resource 被 P1 及 P2 持有。
- R3 的 resource 被 P3 持有。

- #### Waiting 關係
- P1 等待 P2 持有的 R1。
- P2 等待 P3 持有的 R3。
- #### 一旦 P3 用畢歸還 R3，就不會有 deadlock的產生。

### Example : 有cycle、有deadlock。

- #### 對每個 processes 而言
- P1
- 持有 R2 中的一個 instance。
- 要求 R1 中的一個 instance。
- P2
- 持有 R1 及 R2 中，各自的一個 instance。
- 要求 R3 中的一個 instance。
- P3
- 持有 R3 中的一個 instance。
- 要求 R2 中的一個 instance。

- #### 對各個 resource 而言
- R1 的 resource 被 P2 持有。
- R2 的 resource 被 P1 及 P2 持有。
- R3 的 resource 被 P3 持有。

- #### Waiting 關係
- P1 等待 P2 持有的 R1。
- P2 等待 P3 持有的 R3。
- P3 等待 P1 或 P2 持有的 R2。
- **大家都在等待彼此 holding 的 resource**
- ##### 有cycle、有deadlock。
- R2→P1→R1→P2→R3→P3→R2。(紅色箭頭)
- R2→P2→R3→P3→R2。(綠色箭頭)

### Example : 有cycle、沒有deadlock。

- #### 對每個 processes 而言
- P1
- 持有 R2 中的一個 instance。
- 要求 R1 中的一個 instance。
- P2
- 持有 R1 中的一個 instance。
- 沒有要求。
- P3
- 持有 R1 中的一個 instance。
- 要求 R2 中的一個 instance。
- P4
- 持有 R2 中的一個 instance。
- 沒有要求。

- #### 對各個 resource 而言
- R1 的 resource 被 P2 及 P3 持有。
- R2 的 resource 被 P1 及 P4 持有。

- #### Waiting 關係
- P1 等待 P2 或 P3 持有的 R1。
- 一旦 P2 歸還 R1，就不會有waiting發生。
- P3 等待 P1 或 P4 持有的 R2。
- 一旦 P4 歸還 R2，就不會有waiting發生。
- #### 有cycle、沒有deadlock。
- R2→P1→R1→P3→R2。(紅色箭頭)

## :heavy_heart_exclamation_mark_ornament: Deadlock 的重要觀念 :heavy_heart_exclamation_mark_ornament:
* #### 若 p 則 q = p ➙ q
1. 若 **deadlock 發生 ➙ 必產生一個 cycle**
2. 反推不成立 : **~~若產生一個 cycle ➙ 必有 deadlock 發生~~**
* #### 同義於 -> 若 ~q 則 ~p = ~q ➙ ~p
3. 若**沒有 cycle 產生 ➙ 必不會有 deadlock 發生**
#### :star: 反證法實例 :star2: :star2: :star2:
- chap7__HW 7.8
> :heavy_exclamation_mark: Review 邏輯:heavy_exclamation_mark:
> p ➙ q ≈ ~q ➙ ~p

## 五、Solution__解決方式
**分成三種方式解決**
- ### (一)保證絕對不會進入 deadlock state
> 用到上方 ~q ➙ ~p 的觀念
>> 若**沒有 cycle 產生 ➙ 必不會有 deadlock 發生**
- **prevention**
- 確保 deadlock 的**四個條件** (MuExc, Ho&Wt, Nopret, CircuWt) **不會同時成立**。
- **avoidance**
- 在**分配資源(resource-allocation)** 前，先用 **dynamical-allocation** 的方式**檢查(examine)**有沒有可能產生 deadlock，若可能產生 deadlock 則不進行 allocation。

- ### (二)允許進入 deadlock state，但能夠透過偵測而恢復(recovery)
- **detection**
- **recovery**

- ### (三)完全無視 deadlock state 問題，假裝此問題不曾發生
- 讓程式開發者自己處理這些問題。
- 現在大多 OS 都選擇這個方法。(因為找不到有效的解決方法)

### deadlock prevention
:heavy_exclamation_mark: **記好 :heavy_exclamation_mark: 必考** :heavy_exclamation_mark: :star2: :star2: :star2:
- 設計時就不讓 deadlock 產生 => 4 個條件其中一個不成立
- Mutual Exclusion(ME)
- 對於 unsharable resources 必成立
- ex. printer(印表機) ➙ impossible for 多個 processes 共用
- 對於 sharable recources(對該資源的存取量無上限，沒有獨佔性) 不用以 ME 的方式存取，所以也不會產生 deadlock。
- ex. read-only file(唯讀檔案) ➙ 許多 processes 可以同時開啟一個唯讀檔案。

- Hold & Wait
- 不讓此條件成立的方法 : 每一個 process 在要求 resources 時，不可以佔用(hold) 任何其他的資源。
- 資源使用率**低**。
- ex. 一個 process 要用到三種 resource (磁帶機→磁碟檔→印表機)，即便是最後才會用到印表機(前面的時間根本用不到)，但還是 holding 住該 resource
- 可能 starvation :
- 當一個 process(Pi) 需要用到許多 resources，只因其中一個 resource 一直被其他 process 佔用，而 Pi 就一直處於 waiting 。
- No preemption
> - 若資源進行同步機制，自然形成 no preemption
-
- 很難被某些 resources 實現
- ex. printers & tape drives
> 總共 100 頁，印到 99 頁被 interrupt，從頭開始（？？？？）
- Circular Wait
> - 形成 circular wait 必有 hold & wait
- 令線性。 :-1: 待補 :-1:

### deadlock avoidance
- 在 allocate 資源給 process 前，用**動態去檢查 resource-allocation 是否會產生 deadlock** ====> 是否是 safe state
- 永遠都不會進入 deadlock ≈ 永遠都不進入 unsafe state
- 用狀態進行分類，分成 safe 和 unsafe
- safe state(安全的狀態) : NO DeadLock
- 存在一連串的分配方式 ( a sequence of allocations )，讓 process 都能夠拿到自己需要的 resources (request) 完成自己的工作。
- unsafe state : possible of DeadLock

- ### algorithm : 以 instance 的個數進行分類
- #### single instance
- by **RAG**, based on **circle detections**
- #### multiple instance
- by **banker's algorithm**, based on **safe sequence detection**

- ### RAG Way
- Scheme
- Request edge : Pi → Rj
- process (Pi) 已經要求某 resource (Rj)，並且在**等待** Rj 的使用權，才能進行自己要執行的事。
- Assignment edge : Rj → Pi
- resource (Rj) 已經被分配給某 process (Pi)，且 Pi **持**有著 Rj 的使用權，別人無法使用。
- Claim edge : Pi → Rj
- 某 process 未來可能會要求的 edge (但目前沒有要求)

- situation of edge convert
- Claim edge → Request edge
- 可能需要資源 → 需要資源

- Request edge → Assignment edge
- 需要資源 → 擁有資源
> **-** 如上圖所示 : 紫色 → 綠色 → 紅色
- Assignment edge → Claim edge
- 當 process 使用完 resource 後，將 resource release，edge 型態會改變

- #### :heavy_exclamation_mark: 只有當沒有 cycle 存在時，才可以增加一個 request 到 cycle :heavy_exclamation_mark:
> :star: 判斷 Cycle 的 edge，不包含 Claim edge :star:
- ### banker's algorithm Way
- 用 safety algorithm 找尋是否有任何 safe sequence 存在，若有才可以進行 allocation

- #### **Safety Algorithm**
- 有safe sequence才allocate資源
- Algorithm
1. 找出每個 processes 所需要的 max resources
2. 從所有 process 中，找出符合當前 free resources 的所有 processes，就先執行這些 process
3. 該 process 使用完 free resources 後，除了要歸還借來使用的 free resources，還要將自己持有的 resources(allocation) 歸還至 free resources
4. 重複 2 直到所有 processes 都滿足(完成)
- #### safety Algorithm 的資料結構
- 設 n 為 processes 的數量； m 為 resources 的數量
- Available[m] :
- ex. Available[i] = a
➩ 對 Ri 來說，有 a 個 instances 可以被 process 使用
- Max[n][m] :
- ex. Max[i][j] = a
➩ Pi 需要 Rj 的 a 個 instances 才能執行
- Allocation[n][m] :
- ex. Allocation[i][j] = a
➩ Rj 已經有 a 個 instances 被分配給 Pi
- Need[n][m] :
- ex. Need[i][j] = a
➩ Pi 還需要 a 個 Rj 的 instances 才能執行

#### :heavy_check_mark: Need = Max - Allocation :heavy_check_mark:

- #### pseudo code
>- n 為 processes 的數量； m 為 resources 的數量
1. 令另外兩個一維的 array(vector)
- Work[m] = Available[m] //用來記錄當前某個 Resource 的 free instances，所以就要先複製一份出來
- Finish[n] = { false } //用來確認 process 能否被執行(是不是 safe process
2. 找到一個 Pi，使得
- Finish[i] = flase //還沒被執行的 process → Pi
- Need[i][j] ≤ Work[j] // Pi 還需要 Rj 的數量 ≤ 現 Rj free 的 instances
(這個地方需要用 loop 跑，因為要去確認整個 Pi 所需要的所有 Resources 是否 free ⇨ ⇨ ⇨ j = 0~(m-1) )
- 若有 i 存在，則繼續做 3.
- 若沒有 i 存在，則跳到 4.
3. 找到符合的 Pi 時，將此 Pi 設成走過，也將此 Pi hold 住 Resource 的 instances free 掉(≡把 allocation 加入 work array)
- Finish[i] = true //此時 Pi 就被執行，所以改成 true
- Work[j] = Work[j] + Allocation[j]//
(這個地方也要用 loop 跑，因為要去確認整個 Pi 所需要的所有 Resources 是否 free ⇨ ⇨ ⇨ j = 0~(m-1) )
4. 最後檢查所有 Process (Finish array) 是否都為 true，都為 true 就代表 safety state

- #### **Resource-Request Algorithm**

- #### Resource-Request Algorithm 的資料結構
- 設 n 為 processes 的數量； m 為 resources 的數量
- Available[m] :
- ex. Available[i] = a
➩ 對 Ri 來說，有 a 個 instances 可以被 process 使用
- Max[n][m] :
- ex. Max[i][j] = a
➩ Pi 需要 Rj 的 a 個 instances 才能執行
- Allocation[n][m] :
- ex. Allocation[i][j] = a
➩ Rj 已經有 a 個 instances 被分配給 Pi
- Need[n][m] :
- ex. Need[i][j] = a
➩ Pi 還需要 a 個 Rj 的 instances 才能執行
- Reguest[n][m] :
- ex. Reguest[i][j] = a
➩ Pi 想要和 resource j 要求 a 個 Rj 的 instances 加入自己的 Allocation

- #### pseudo code
>- n 為 processes 的數量； m 為 resources 的數量
1. Request[i][0~(m-1)] <= Need[i][0~(m-1)]
- 確認 process i 要求的資源是否超過本身的需求，若超過本身需求就回傳 error 的條件
2. Request[i][0~(m-1)] <= Available[i][0~(m-1)]
- 確認 process i 要求的資源是否超過 free resources，若超過就沒辦法 allocation 給 Pi
3. 若 Pi 在上方這兩個檢查都能夠符合條件，則做以下事情。(改變各變數的值)
- Available[i][0~(m-1)] -= Request[i][0~(m-1)]; //因為要分配給 Pi ，所以 free instances 要扣掉
- Allocation[i][0~(m-1)] += Request[i][0~(m-1)]; //再加入 allocation
- Need[i][0~(m-1)] -= Request[i][0~(m-1)]; //和減去缺少的(Need) instances
4. 最後判斷是否為 safety process。
- 可以產生 safe sequence ⇨ safe ⇨ 可以將 request 的資源給 Process
- 無法產生 safe sequence ⇨ unsafe ⇨ 不能將 request 的資源給 Process

### deadlock detection
- 允許進入 deadlock 的狀態，經由偵測到之後，再進行解決
- ### Wait - For graph
- 畫法 : 把 RAG 圖的 resource node 拔掉並連接起來後，兩兩 processes 之間的 waiting 關係就很清楚了。
- 右上圖為例 : P1 在等待被 P2 hold 住的 resources ...。

### deadlock recovery
看 ppt~~~

# HomeWork
> 7.7, 7.8, 7.9, 7.12, 7.13
## 7.7

## 7.8

## 7.9
- When one philosopher makes a request for the first chopstick, do not award the request if there is no other philosophers with two chopsticks and if there is only one chopstick remaining.

- 
> - 
> - 

## 7.12

**上面的答案是錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的錯的**
**寫錯了啦~~~~~~~~~~~~~~~~~~~~。**

## 7.13
> [參考算法](https://www.ques10.com/p/3750/consider-the-following-snapshot-of-a-system/?)
>