# System Model
* 系統由有限數量的資源組成，這些資源分佈在競爭進程之間。
* 資源類型 R1、R2、 Rm
* CPU 週期、記憶體空間、I/O 設備
* 每個資源類型Ri都有Wi實例。
* 每個行程使用資源如下：
* 請求
* 使用
* 釋放

## Deadlock with Semaphores
* 資料：
* A semaphore S1初始化為1
* A semaphore S2初始化為1
* Two processes P1 and P2
* P1:

wait(s1)
wait(s2)

* P2:

wait(s2)
wait(s1)

# Deadlock Charcterization
如果四個條件同時滿足，就會出現**Deadlock**
* Mutual exclusion(相互排斥)：一次只有一個程序可以使用一種資源
* Hold and wait(持有&等待)：持有至少一個資源的程序正在等待獲取其他程序持有的額外資源
* No preemption(無搶佔)：資源只能由持有此資源的進程在完成其任務後自願釋放
* Circular wait(循環等待)：存在一組等待進程{P0，P1，...，Pn}，其中P0正在等待P1所持有的資源，P1正在等待P2所持有的資源，... , Pn–1 正在等待Pn 持有的資源，Pn 正在等待P0 所持有的資源

## Resource-Allocation Graph
一組頂點(vertices) V 和一組邊(edges) E
* V分為兩種：
* P = {P1,P2,...,Pn}，系統中所有行程組成的集合
* R = {R1, R2, ..., Rm}，系統中所有資源類型組成的集合
* request edge-有向邊(directed edge) Pi->Rj
* assignment edge-有向邊 Rj->Pi

## Resource-Allocation Graph
* 進程 => 
* 具有 4 個實例的資源類型 => 
* Rj 的 Pirequests 實例 => 
* Pi 持有 Rj 的一個實例 => 
* 請求邊緣僅指向正方形 Rj，而分配邊緣也必須指定正方形中的一個點

## Resource Allocation Graph Example
* R1 的一個實例(R1裡1個點)
* R2 的兩個實例(R2裡2個點)
* R3 的一個實例(R3裡1個點)
* R4 的三個實例(R4裡3個點)
* T1 持有 R2 的一個實例還有正在等待 R1 的實例(R2其中一個點指向T1，T1指向R1)
* T2 持有 R1 的一個實例，R2 的一個實例，並且正在等待 R3 的實例(R1中的點和R2另一個點指向T2，T2指向R3)
* T3 持有 R3 的一個實例(R3中的點指向T3)

## Resource Allocation Graph With A Deadlock

## Graph With A Cycle But No Deadlock

## Basic Facts
* 如果圖**不包含循環(contains no cycle)** => no deadlock
* 如果圖**包含循環(contains a cycle)** =>
* 如果每個資源類型**只有一個實例**，則deadlock
* 如果每個資源類型**有多個實例**，則**可能發生deadlock**

# Methods for Handling Deadlocks
* 確保系統永遠不會進入死鎖狀態：
* 死鎖預防 => 確保至少一個必要條件不成立的一組方法
* 死鎖避免 => 為作業系統提供有關進程和資源的信息，以決定滿足或延遲請求
* 允許系統進入死鎖狀態然後恢復。
=>系統可以提供一種演算法來檢查系統的狀態以確定是否發生了死鎖，以及一種從死鎖中恢復的演算法。
* 忽略該問題並假裝系統中從未發生死鎖

# Deadlock Prevention
**=> 透過使死鎖的四個必要條件之一無效，我們可以防止死鎖的發生**
* 互斥(Mutual Exclusion)－可共享資源不需要（例如唯讀文件）；必須持有不可共享資源(printers, synchronized method)
* 保持與等待(Hold and Wait) – 必須保證每當進程請求資源時，它不會持有任何其他資源
* 要求進程在開始執行之前請求並分配其所有資源，或僅當進程沒有分配資源時才允許進程請求資源
* 資源利用率低；可能會挨餓




* 無搶佔(No Preemption)
* 如果一個正在佔用某些資源的進程請求另一個無法立即分配給它的資源，則當前佔用的所有資源將被釋放
* 搶佔的資源被加入到進程正在等待的資源清單中
* 只有當進程可以重新獲得舊資源以及它所要求的新資源時，才會重新啟動進程
* 通常應用於狀態可以輕鬆保存並在以後恢復的資源，例如 CPU 暫存器和記憶體空間。它不能應用於印表機和磁帶機等資源
* 循環等待(Circular Wait) - 對所有資源類型進行總排序，並要求每個行程以遞增的枚舉順序請求資源

## Circular Wait
* 使循環等待條件無效是最常見的。
* 只需為每個資源（即互斥鎖）分配一個唯一的編號。
* 資源必須按順序取得。
* If：

first_mutex = 1
second_mutex = 5 

`thread_two`的程式碼不能寫成如下：

/*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)
}

# Deadlock Avoidance
**要求系統有一些額外的可用先驗信息**
* 最簡單和最有用的模型要求每個進程聲明它可能需要的每種類型的最大資源數量
* 死鎖避免演算法動態檢查資源分配狀態，以確保永遠不會出現循環等待情況
* 資源分配狀態由可用和已分配資源的數量以及進程的最大需求來定義

## Safe State
* 當進程請求可用資源時，系統必須決定立即分配是否使系統處於安全狀態。
* 系統處於安全狀態如果存在系統中所有進程的序列<P1，P2，...，Pn>，例如對於每個Pi，Pi仍然可以請求的資源可以由當前可用資源+所有Pj擁有的資源來滿足，其中j < i
* 即：如果系統可以在一定時間內為每個進程分配資源，則狀態是安全的順序，仍然避免死鎖。
* 如果Pi 資源需求不能立即可用，則Pi 可以等待，直到所有Pj 完成。
* 當Pj 完成時，Pi 可以獲得所需資源，執行，返回分配的資源，並終止。
* 當Pi 終止時， Pi+1可以獲得其所需的資源，依此類推。
* 如果不存在這樣的序列，則稱系統不安全

## Basic Facts
* 如果系統處於安全狀態 => 沒有死鎖
* 安全狀態不是死鎖狀態。
* 死鎖狀態是一種不安全狀態。
* 如果系統處於不安全狀態 => 發生死鎖的可能性
* 並非所有不安全狀態都是死鎖。
* 不安全狀態可能導致死鎖。
* 在不安全狀態下，作業系統無法阻止進程請求資源並導致死鎖：進程的行為控制不安全狀態。
* 避免 => 確保系統永遠不會進入不安全狀態

## Safe State Example
* 12 tape drives, 3 processes

| | max needs | current holding |
|:---:|:---------:|:---------------:|
| P0 | 10 | 5 |
| P1 | 4 | 2 |
| P2 | 9 | 2 |
* 對於<P1,P0,P2>是安全的
* 如果P2再請求一個，系統進入不安全狀態

## Safe, Unsafe, Deadlock State
* 如果系統處於安全狀態 => 沒有死鎖。
* 如果系統處於不安全狀態 => 可能出現死鎖。
* 避免 => 確保系統永遠不會進入不安全狀態。

## Avoidance Algorithms
* 資源類型的單一實例
* 使用資源分配圖
* 資源類型的多個實例
* 使用銀行家演算法

### Resource-Allocation Graph Scheme
* Claim Edge Pi->Rj 表示流程 Pj 可以請求資源 Rj；以虛線表示
* 當行程請求資源時，宣告邊轉換為請求邊
* 當資源分配給行程時，請求邊轉換為分配邊
* 當行程釋放資源時，分配邊重新轉換為宣告邊緣
* 資源必須在系統中預先聲明

### Safe State
* 只有當將請求邊轉換為分配邊不會導致資源分配圖中形成環時，才能授予請求。
* 如果不存在環，則資源的分配將使系統處於安全狀態狀態。否則，進程必須等待

### Banker’s Algorithm
* 資源的多個實例
* 每個行程必須事先宣告最大使用量
* 當行程請求資源時，它可能必須等待
* 當行程取得所有資源時，它必須在有限的時間內回傳它們

### Data Structures for the Banker’s Algorithm
**令 n = 進程數，m = 資源類型數。**
* Available：長度為m的向量。如果available [j] = k，則存在資源類型 Rj available的實例
* Max：n x m矩陣。如果 Max [i,j] = k，則進程 Pi 最多可以請求資源類型 Rj 的 k 個實例
* Allocation：n x m 矩陣。如果 Allocation[i,j] = k，則 Pi 目前指派了 Rj 的 k 個實例
* need： n x m 矩陣。如果 Need[i,j] = k，則 Pi 可能需要 k 個 Rj 實例才能完成其任務
Need[i,j] = Max[i,j] - Allocation[i,j]

### Safety Algorithm
1. 設 Work 和 Finish 分別為長度為 m 和 n 的向量。
* 初始化：

    Work = available
    Finish [i] = false for i = 0, 1, ..., n- 1

2. 找到一個滿足以下條件的i：
(a) Finish [i] = false
(b) Needi <= Work
**如果不有這樣的情況，請轉至步驟 4**
3.

Work = Work + Allocationi
Finish[i] = true

**轉至步驟 2**
4. 如果 `Finish [i] == true` 對於所有 i，則系統處於安全狀態

### Resource-Request Algorithm for Process Pi
Requesti = 進程 Pi 的請求向量。如果 Requesti[j] = k，則進程 Pi 想要資源型別 Rj 的 k 個實例
1. 如果Requesti <= Needi ， 執行步驟2。否則，引發錯誤條件，因為進程已超出其最大聲明數
2. 如果Requesti <= Available，則前往步驟3。否則Pi必須等待，因為資源不可用
3. 假裝透過修改狀態來將請求的資源分配給 Pi，如下所示：
**Available = Available – Requesti;**
**Allocationi= Allocationi + Requesti;**
**Needi= Needi – Requesti;**
* 如果安全 => 資源分配給 Pi 如果不安全
* Pi 必須等待，然後恢復舊的資源分配狀態

## Example 1

* safe
* process1,2或4可以請求其最大頁數並完成
* 例如：進程1完成

* 現在任何進程都可以請求最大頁數並完成
* 假設進程 3 完成

* 任何人都可以完成。
* 但是，允許所有進程完成的一系列請求並不表示永遠處於安全狀態

* 從一開始，如果進程 3 請求 4 個可用頁面，並且每個進程隨後再請求 1 個頁面，則係統將陷入死鎖。
* 但是，這並不一定會發生。 ....不安全狀態並不意味著死鎖將不可避免地發生

## Example 2
* 如果每個進程都聲明其聲明，就會發生死鎖
* unsafe！

## Banker’s Algorithm

| | Allocation | Max | Available |
|:---:|:----------:|:-----:|:---------:|
| | A B C | A B C | A B C |
| P0 | 0 3 0 | 7 5 3 | 2 1 0 |
| P1 | 3 0 2 | 3 2 2 | |
| P2 | 3 0 2 | 9 0 2 | |
| P3 | 2 1 1 | 2 2 2 | |
| P4 | 0 0 2 | 4 3 3 | |

| | Need |
|:---:|:-----:|
| | A B C |
| P0 | 7 2 3 |
| P1 | 0 2 0 |
| P2 | 6 0 0 |
| P3 | 0 1 1 |
| P4 | 4 3 1 |

* 安全狀態。 <P1, P3, P4, P2, P0>
* 如果 request1=(1,0,2)
* 對於 < P1, P3, P4, P0, P2 >
* Request4=(3,3,0)
* 不能授予。沒有資源
* Request0 =(0,2,0)
* 會導致不安全狀態

## Deadlock Detection
* 讓系統進入死鎖狀態
* 系統應該提供：
* 一種檢查系統狀態以確定是否發生死鎖的偵測演算法。
* 一種從死鎖中恢復的演算法。
* 它需要開銷，包括
* 維護必要的資訊
* 執行檢測演算法
* 恢復時的潛在損失

## Single Instance of Each Resource Type
* 維護等待圖(Maintain wait-for graph)：透過刪除資源類型的節點並折疊適當的邊，從資源分配圖中獲得
* 節點是進程
* Pi => Pj 如果 Pi 正在等待 Pj 釋放 Pi needs 的資源
* 需要維護等待圖並定期調用在圖中搜尋循環的演算法。如果存在循環，則存在死鎖
* 偵測圖中迴圈的演算法需要 n**2 次操作，其中 n 是圖中的頂點數

## Resource-Allocation Graph and Wait-for Graph

## Detection-Algorithm Usage
* 呼叫的時間和頻率取決於：
* 死鎖可能發生的頻率？
* 需要回滾多少個進程？
* 每個不相交週期回滾一個進程
* 如果死鎖頻繁發生，那麼應該頻繁調用檢測演算法。
* 在極端情況下，我們可以在每次分配請求無法立即獲得批准時調用死鎖檢測演算法 => Expensive

## Several Instances of a Resource Type
* Available：長度為m的向量表示每種類型的可用資源數量
* Allocation：n x m 矩陣定義目前分配給每個行程的每種類型的資源數量
* Request：n x m 矩陣表示每個行程的目前請求。如果 Request [i][j] = k，則 processPi 正在請求 k 個資源類型 Rj 的更多實例

## Detection Algorithm
1. 設 Work 和 Finish 分別為長度為 m 和 n 的向量 初始化：
(a) Work = available
(b)對於 i = 1,2, ..., n，如果 Allocationi 0，則 Finish[i] = false；否則，Finish[i] = true2。

2. 找到索引，使得：
(a)Finish[i] == false
(b)Requesti <= Work
如果不存在這樣的i，則轉到步驟4

3. Work = Work + Allocationi
Finish[i] = true
轉到步驟 2

4. 如果Finish[i] == false，對於某些i，1≤i≤n，則系統處於死鎖狀態。此外，如果 Finish[i] == false，則 Pi 陷入僵局

**演算法需要 O(m x n2) 次操作來偵測系統是否處於死鎖狀態**

## Example of Detection Algorithm
五個行程 P0 到 P4；三種資源類型 A（7 個實例）、B（2 個實例）和 C（6 個實例）
Snapshot at time T0:

| | Allocation | Request | Available |
|:---:|:----------:|:-------:|:---------:|
| | A B C | A B C | A B C |
| P0 | 0 1 0 | 0 0 0 | 0 0 0 |
| P1 | 2 0 0 | 2 0 2 | |
| P2 | 3 0 3 | 0 0 0 | |
| P3 | 2 1 1 | 1 0 0 | |
| P4 | 0 0 2 | 0 0 2 | |

* 序列 <P0, P2, P3, P1, P4> 將導致所有 i 的 Finish[i] = true
=> no delocked

* P2 請求額外的 typeC 實例

| Request | |
|:-------:|:-----:|
| A B C | |
| P0 | 0 0 0 |
| P1 | 2 0 2 |
| P2 | 0 0 1 |
| P3 | 1 0 0 |
| P4 | 0 0 2 |

* 系統狀態？
* 可以回收進程P0所佔用的資源，但資源不足以滿足其他進程的請求。
* 存在死鎖，由進程P1、P2、P3和P4組成

## Detection-Algorithm Usage
* 呼叫的時間和頻率取決於：
* 死鎖可能發生的頻率？
* 需要回滾多少個進程？
* 每個不相交循環一個
* 如果任意呼叫偵測演算法，資源圖中可能存在許多循環，因此我們無法判斷眾多死鎖進程中的哪一個「導致」了死鎖

# Recovery from Deadlock: Process Termination
* 中止所有死鎖進程
* 丟棄並重新計算部分計算的成本高昂。
* 一次中止一個行程，直到消除死鎖循環
* 每個行程中止後呼叫死鎖偵測演算法的開銷。
* 我們應該中止那些在終止時會產生最小成本的進程

* 我們應該選擇中止的順序？
1. 進程的優先權
2. 進程計算了多長時間，以及需要多長時間才能完成
3. 進程已使用的資源
4. 進程需要完成的資源
5. 需要終止多少個流程
6. 流程是互動的(interactive)還是批次的(batch)？
=> interactive，

# Recovery from Deadlock: Resource Preemption
* 依序從進程中搶佔一些資源，並將這些資源交給其他進程，直到死鎖循環被打破。解決了三個問題：
* 選擇受害者(Selecting a victim)－哪些資源和哪些流程將被搶佔？我們必須確定順序以最小化成本。因素包括：
* 死鎖程序佔用的資源數
* 死鎖程序消耗的時間量
* 回滾(Rollback) – 返回某個安全狀態，從該狀態重新啟動進程。要求系統保留有關所有正在運行的進程的狀態的更多信息
* 飢餓(Starvation)－相同的進程可能總是被選為受害者。成本因素應包括回滾次數

# Important Sentence
1. If safe sequence is available then the system is in safe state
2. for all process to go to the maximum and finish? => Return the resource.
3. each process asks for more => deadlock，Because they're waiting.