# 學習目標
1. 說明當使用互斥鎖時如何發生deadlock
2. 定義構成deadlock的四個必要條件
3. 在資源分配圖中識別deadlock情況
4. 評估預防deadlock的四種不同方法
5. 應用銀行家算法以避免deadlock
6. 應用deadlock檢測算法
7. 評估從deadlock中恢復的方法

# 系統模型
1. 系統由有限數量的資源組成,將在競爭的進程之間分配。
2. 每種資源類型Ri有Wi個實例。
3. 每個進程按以下方式使用資源:
* 請求使用、釋放

# 死鎖特徵
1. 互斥條件:一次只有一個進程可以使用資源
2. 佔有並等待條件:一個進程持有至少一個資源,卻在等待獲取其他進程持有的額外資源
3. 不可剝奪條件:資源只能由佔有它的進程主動釋放,且是在該進程完成任務後
4. 循環等待條件:存在一組{P0, P1, ..., Pn}等待中的進程,其中P0等待P1持有的資源、P1等待P2持有的資源、...、Pn-1等待Pn持有的資源、Pn等待P0持有的資源。

:::warning
**只有上述四個條件同時滿足時,才會產生死鎖。**
:::

# 資源分配圖
V被分為兩種類型:
1. P = {P1, P2, ..., Pn}, 系統中所有進程的集合
2. R = {R1, R2, ..., Rm}, 系統中所有資源類型的集合

資源分配圖可視化描述了進程與資源之間的分配情況,用於檢測系統中是否存在環路,進而檢測是否存在死鎖。

# 資源分配圖中的一些基本事實
1. 如果圖中不含環路(cycle) 則一定不存在死鎖
2. 如果圖中含有環路:
* 如果每種資源類型只有一個實例,那麼一定存在死鎖
* 如果有些資源類型擁有多個實例,則有可能存在死鎖,需進一步分析

換言之,圖中存在環路是死鎖存在的必要條件,但如果某些資源類型有多個實例,環路的存在不是充分條件,仍需要進一步檢查實例分配情況來確定是否真的存在死鎖。

因此,分析資源分配圖的關鍵在於:
1. 檢查是否存在環路
2. 對於存在環路的情況,進一步檢查每種資源的實例數量

通過這種分析,可以有效地檢測系統中是否存在死鎖。

# 處理死鎖的方法
1. 確保系統永不進入死鎖狀態:
* 死鎖預防(Deadlock prevention)
* 死鎖避免(Deadlock avoidance)
2. 允許系統進入死鎖狀態,然後從中恢復。
* 系統可以提供一種算法來檢查系統狀態,確定是否發生了死鎖
* 並提供一種從死鎖中恢復的算法
3. 完全忽視這個問題,假裝系統中不會發生死鎖

其中第三種做法顯然是不可取的,因為死鎖一旦發生將導致系統資源無法正常使用。
較為合理的做法是:
* 預防或避免死鎖發生(第一種方法)
* 如果無法避免,則設計檢測和恢復機制(第二種方法)

具體選擇哪種方法需要根據系統的資源使用模型、資源數量,以及對死鎖發生頻率和影響的評估來權衡。

# 死鎖預防的四種方法
1. 互斥條件
* 對於可共享的資源(如只讀文件),互斥條件不是必需的
* 對於不可共享的資源(如打印機、同步方法),必須滿足互斥條件
2. 佔有並等待條件
* 必須保證進程在請求新資源時,不持有任何其他資源
* 要求進程在開始執行前請求並獲得所有需要的資源,或者允許進程在執行過程中請求所需的資源,但在獲得時暫時釋放已持有的資源
3. 不可剝奪條件
* 如果一個進程請求資源而被拒絕,則該進程保持已獲得的資源
* 該進程將被終止或將其已獲得的資源全部剝奪,從而支援不可剝奪條件
4. 循環等待條件
* 按某種順序為資源編號,規定進程申請編號較小的資源後,才能申請編號較大的資源
* 使用單一且強制性的資源佔有順序,循環等待狀態即無法構成

只要上述四個條件中有一個條件不滿足,就可以預防死鎖的發生。但實現上述條件也會增加額外的成本和限制。

# 預防死鎖
1. 要求進程在開始執行前請求並獲得所有需要的資源。
2. 允許進程僅在沒有分配到任何資源時,才能請求資源。

這兩種方式都可以避免進程已持有某些資源時仍請求其他資源的情況,從而預防死鎖發生。但是它們也有一些缺陷:
1. 可能導致資源利用率低落
* 如果進程一次性請求所有可能需要的資源,即使實際上只使用部分,將導致許多資源處於閒置狀態。
2. 可能導致進程飢餓(starvation)
* 進程需要獲取所有請求的資源才能開始執行,如果有些資源長期被其他進程佔用,該進程將無法獲取完整資源而永遠處於等待狀態。

* 互斥條件 - 對於可共享資源(例如只讀檔案)不需要互斥條件;但對於不可共享資源(如印表機、同步方法)必須滿足互斥條件。
* 佔有並等待條件 - 必須保證當進程請求資源時,它不持有任何其他資源。
* 不可剝奪條件
* 如果一個持有部分資源的進程請求另一個暫時無法獲得的資源,則該進程當前持有的所有資源都會被釋放。
* 被剝奪的資源將被加入該進程等待獲得的資源列表中。
* 該進程只有在能夠重新獲得其之前持有的資源及新請求的資源時,才會重新啟動。
* 這種做法常應用於狀態可以被輕易保存和恢覆的資源,如CPU暫存器和記憶體空間。但無法應用於印表機和磁帶機等資源。
* 循環等待條件
* 對所有資源類型強制賦予一個完全順序。
* 要求每個進程按遞增的順序來請求資源。

# 循環等待
* 無效化循環等待條件是最常見的。
* 只需為每個資源（即互斥鎖）分配一個唯一的編號。
* 資源必須按順序獲取。
# 死鎖避免(Deadlock Avoidance)
* 最簡單且最有用的模型要求每個進程聲明其可能需要的每種類型的最大資源數量
* 避免死鎖的算法動態地檢查資源分配狀態，以確保永遠不會出現循環等待條件
* 資源分配狀態由可用和已分配資源的數量以及進程的最大需求所定義
# 安全狀態(Safe State)
* 當一個進程請求一個可用資源時，系統必須決定即時分配是否將系統留在一個安全狀態
* 如果存在一個系統中所有進程的序列 <P1, P2, ..., Pn>，使得對於每個Pi，Pi仍然可以請求的資源可以由當前可用資源 + 所有Pj所持有的資源滿足，其中j < i
* 如果不存在這樣的序列，則系統被認為是不安全的
* 只有當將請求邊轉換為分配邊不會導致資源分配圖中形成循環時，才能授予請求。
* 如果沒有循環存在，則資源的分配將使系統處於安全狀態。否則，進程必須等待。
# 基本事實(Basic Facts)
* 如果系統處於安全狀態→沒有死鎖
* 安全狀態不是死鎖狀態。
* 死鎖狀態是一個不安全的狀態。
* 如果系統處於不安全狀態→有死鎖的可能性
* 不是所有不安全的狀態都是死鎖。
* 不安全的狀態可能導致死鎖。
* 在不安全的狀態下，作業系統無法阻止進程請求資源並導致死鎖：進程的行為控制著不安全的狀態。
* Avoidance→確保系統永遠不會進入不安全的狀態。

# 避免算法(Avoidance Algorithms)
* 單個資源類型的情況
* 使用資源分配圖
* 多個資源類型的情況
* 使用銀行家算法

# 銀行家算法
* 多個資源實例
* 每個進程必須事先聲明最大使用量
* 當一個進程請求一個資源時，可能需要等待
* 當一個進程獲得所有資源時，必須在有限時間內將它們返回
# 死鎖檢測
* 允許系統進入死鎖狀態。

系統應該提供：
* 一個檢測算法，檢查系統的狀態以確定是否發生了死鎖。
* 一個從死鎖中恢復的算法。
* 維護必要信息、執行檢測算法以及恢復時可能損失的開銷。
# 檢測算法的使用
* 何時以及多久調用取決於：
1. 死鎖可能發生的頻率？
2. 需要回滾多少進程？
* 如果死鎖頻繁發生，則應該經常調用檢測算法。
* 在極端情況下，我們可以在每次無法立即授予分配請求時調用死鎖檢測算法。
* 如果任意調用檢測算法，可能會在資源圖中產生許多循環，因此我們將無法確定許多進程中的哪些造成了死鎖。

# 從死鎖中恢復
### 進程終止
* 中止所有死鎖進程
* 丟棄並重新計算部分計算成本高昂。
* 逐個中止進程直到死鎖循環被消除
* 在每個進程被中止後調用死鎖檢測算法的開銷。
* 我們應該中止那些在終止時將產生最小成本的進程。

我們應該按照什麼順序中止？
1. 進程的優先級
2. 進程已計算的時間，以及完成還需要多長時間
3. 進程已使用的資源
4. 進程完成所需的資源
5. 需要終止多少進程
6. 進程是交互式還是批處理的？
### 資源搶占
* 連續地從進程中搶占一些資源，並將這些資源分配給其他進程，直到死鎖循環被打破。需要解決三個問題：
1. 選擇受害者 - 要搶占哪些資源和哪些進程？我們必須確定順序以最小化成本。考慮因素包括：
* 死鎖進程持有的資源數量
* 死鎖進程消耗的時間
2. 回滾 - 返回到某個安全狀態，從該狀態重新啟動進程。系統需要保留更多有關所有運行中進程狀態的信息。
3. 飢餓 - 可能總是選擇同一個進程作為受害者。成本因素應該包括回滾的次數。

# <font color="blue">*Important sentence*
**<font color="blue">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**