# OS筆記-Chapter 7: Deadlocks

###### tags: `OS`
---
#### 目錄
* 總論
[Chapter 1: Introduction](https://hackmd.io/NoZq3J7IQvOQpcbo_tctjA)
[Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A)
* 行程管理
[Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ)
[Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw)
[Chapter 5: CPU Scheduling](https://hackmd.io/IT5g2wHzTdOtMSDXPVEpOw)
[Chapter 6: Process Synchronization](https://hackmd.io/rv-PNe3ESxi08PElyUTc4Q)
<font color="red">Chapter 7: Deadlocks</font>
* 記憶體管理
[Chapter 8: Main Memory](https://hackmd.io/4KS_yPkBQzGZfHDisPciog)
[Chapter 9: Virtual Memory](https://hackmd.io/yirxZFn8Rz2wT56AAR7Sxw)
* 儲存裝置
[Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg)
[Chapter 11: File System Implementation](https://hackmd.io/bFcrlmefQsGp6hZdbI1MHQ)
[Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q)
[Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg)
* 保護和安全
[Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw)
[Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg)
---

### 系統模型(System Model)
* 例證(instance):每種型式的資源含有數種相同的例證，當某行程要求某一型式的例證實，配置這型之任一例證均可滿足
* 例如:一個系統有兩個CPU，則CPU這種型式有兩個例證

* 一個行程只能依據下列的順序來使用資源:
* 要求:若此要求不能立即被認可，則行程必須等候以獲得此資源
* 使用:行程能夠在此資源上運作
* 釋放:行程釋放資源

* 作業系統應先確定此資源已被要求，才能分配這項資源給此行程使用

* 一個集合中的每一行程若是在等待這集合其他行程所產生的事件，則此集合中所有行程均為死結狀態

### 死結的特性(Deadlock Characterization)
* 下列狀況在系統中同時成立時，死結才有可能發生:
* 互斥(Mutual exclusion):至少有一資源是不可共用
* 佔用與等待(Hold and wait):必須存在一個行程至少已佔用一個資源，且此行程正等待其他行程已佔用的另外資源
* 不可搶先(No preemption):資源不能被搶先
* 循環式等候(Circular wait):集合{P₀,P₁,...,Pₙ}，P₀等待的資源被P₁占用，P₁等候的資源被P₂占用，以此類推，Pₙ₋₁等待的資源被Pₙ占用

* 系統資源配置圖(system resource-allocation graph)
* 方塊:資源型式
* 點:該資源型式的例證
* 要求邊(request edge):行程P指向資源R
* 分配邊(assignment edge):資源R指向行程P
* 分配邊必須指向點，要求邊只需指向方塊
* 若此圖中出現循環，則可能存在死結(若每個資源型式只有一個例證，則一定有死結)

### 處理死結的方法(Methods for Handling Deadlocks)
* 一般來說使用以下三種方法:
* 使用某一協議，防止或避免死結
* 預防死結(deadlock prevention):確保死結必要條件有一項不會發生
* 避免死結(deadlock avoidance):要求作業系統能先取得行程將會要求的資源，作業系統可以決定行程的要求可以被滿足或必須延遲
* 允許死結，偵測出來再想辦法恢復
* 以一個演算法來檢查其狀態
* 另一套演算發來恢復
* 忽視此問題
* 被大部分的作業系統採用，所以由應用程式開發人員寫處理死結的程式
* 系統可能停止工作，必須重啟

### 預防死結(Deadlock Prevention)
* 產生死結時，四個必須條件必須成立，所以只要這些條件有一個不成立，就能預防死結
* 互斥:我們不可能藉由排除此條件來預防死結
* 占用與等候:保證行程在要求資源時，不佔用任何資源
* 每一行程在執行之前必須先要求並取得所需的資源
* 讓每一行程只有在未占用資源的狀況下才能要求資源
* 缺點:
* 資源使用率不佳
* 飢餓問題
* 不可搶先:
* 目前所持有的資源應該可以由他人搶先使用(可搶先)
* 通常適用於資源狀態能輕易被保存或稍後可恢復的情況
* 不適用於互斥鎖和號誌
* 循環式等候:
* 對所有的資源型式強迫安排一個線性的順序，行程要求資源時必須依數字大小，遞增提出要求
* 證明:如果是循環式等待則{P₀,P₁,...,Pₙ}，P₀等待P₁，Pₙ等待P₀，又P₀占用的資源R₀順序小於P₁占用的資源R₁，R₀<R₁<...<Rₙ<R₀，R₀<R₀矛盾，因此不會有循環式等待

### 避免死結(Deadlock Avoidance
* 要求每一個行程聲明其所需每種型式的資源之最大數量

* 安全狀態(Safe State):系通能以某種順序將其資源分配給各個行程，而且能避免死結者

* 系統必須決定是否立刻把資源分配給行程，或是該行程進入等待，因此資源利用率可能比沒避免死結的狀況更低

* 資源配置圖演算法
* 申請邊(claim edge):表示行程P可能在未來須要求資源R
* 若無循環此要求被允許
* 若發生循環，則需使行程進入等待(P₁等待)

* 銀行家演算法(Banker’s Algorithm)
* 資源配置圖演算法不適用於有多個例證的資源
* 當一個使用者要求一組資源時，就必須決定系統是否會因為這些資源的佔用而脫離安全狀態
* m為資源型式的數量，n為行程數
* 可用的(Available):長度m的向量，表示每種類型可用的例證(Available[j]=k)
* 最大值(Max):n*m之矩陣，表示行程最大需求資源(Max[i][j]=k，Pᵢ至多要求k個Rⱼ)
* 占用(Allocation):n*m之矩陣，表示行程目前佔用的資源(Allocation[i][j]=k)
* 需求(Need):n*m之矩陣，表示行程剩餘的需求量(Need[i][j]=k)
* 安全演算法(Safety Algorithm):
* Finish[n]=false表示行程是否能完成，Work=Available表示可用的資源
* 尋找Finish[i]=false且Need<Work的行程
* Work=Work + Allocation
* Finish[i]=True
* 重複尋找
* 如果找不到符合條件的，則檢查Finish[n]是否全為True，則此系統為安全狀態
* m*n²次運算
* 資源要求演算法(Resource-Request Algorithm)
* Request為行程的要求向量(Request[i][j]=k)
* 如果Request>Need則發生錯誤，因為行程超過他的最大需求
* 如果Request>Available則行程必須等待
* 假設系統已配置行程所要求的資源:
* Available = Available - Request
* Allocation = Allocation + Request
* Need = Need - Request
* 舉例:
* Need = Max - Allocation
* 順序<P1,P3,P4,P2,P0>可滿足

### 死結的偵測(Deadlock Detection)
* 若所有資源只具單一例證，則我們可以使用等候圖(wait-for graph)定義出一種偵測死結的演算法
* 等候圖上Pᵢ->Pⱼ代表Pᵢ必須等候Pⱼ釋放行程
* 資源配置圖與其轉換的等候圖
* 若等候圖有循環則必定有死結
* 需n²次的運算

* 具多個例證的資源型式
* 使用一些類似銀行家演算法的資料結構
* Work=Available表示可用的資源，Allocation=0，Finish[i]=True，否則Finish[i]=False
* 尋找Finish[i]=false且Request<Work的行程
* Work=Work + Allocation
* Finish[i]=True
* 重複尋找
* Finish[i]=false則系統處於死結，行程Pᵢ陷入死結
* m*n²次運算

* 何時使用偵測演算法
* 多久會產生一次死結
* 有多少個行程受死結發生影響
* 例如:當CPU使用率低落時使用或每小時使用一次

### 死結恢復(Recovery from Deadlock)
* 終止死結的方法:
* 取消一個或多個行程，以終止循環式等候
* 取消所有死結中的行程
* 一次取消一個，直到死結結束
* 搶先一個或多個行程，或的其資源
* 選擇犧牲者(Selecting a victim):最小花費
* 回撤(Rollback):將被搶先行程撤回到安全狀態，再重新開始
* 最簡單的方法，全部撤回，再重新開始
* 最有效率的方法，撤回到能解開死結的狀況，再重新開始
* 飢餓(starvation):為避免同一行程一直被搶先，將撤回的次數包括在成本因素