死鎖的解決

1. 死鎖的預防（打疫苗）
2. 死鎖的避免（戴口罩）
3. 死鎖的檢測（做核酸）

死鎖的預防

前面我們提到了死鎖的四個必要條件

• 防止前三個必要條件，就是間接預防
• 防止最后一個必要條件–循環等待，就是直接預防

接下來我們討論一下這四個條件如何預防

1. 互斥訪問：系統屬性不可修改，必須支持
2. 保持和請求：要求一次性請求所需的全部資源
   • 進程得到資源前要阻塞很長時間
   • 降低了系統利用率和并發程度
   • 有可能無法預先知道所需資源
3. 不可剝奪：修改為可剝奪
   1. OS可以實現，適用于資源的使用狀態可以保存并恢復
   2. 處理器和內存的資源可剝奪（上下文、頁面置換算法）
4. 循環等待：
   1. 需要定義一個資源類型的線性序，資源在申請的時候必須按照這個序
   2. 效率不高，減緩了進程的推進，以及不必要地拒絕資源訪問

死鎖的避免

系統需要動態作出決定：如果當前資源分配請求滿足，是否會導致死鎖。

• 需要未來的進程資源請求
• 動態判定當下情況有沒有可能發生死鎖

兩種方式：

1. 拒絕進程啟動：如果進程資源請求可能導致死鎖則不啟動進程

2. 拒絕資源訪問：如果本次分配可能導致死鎖，則拒絕進程的增量資源請求

拒絕進程啟動

系統中有n個進程，m種資源

• R是資源總數矩陣
• V是可用的資源矩陣
• claim是最大需求矩陣
• allocation是已經分配的資源矩陣

保守策略

e.g.

假設銀行有賬面200萬，有三個客戶來貸款，總量分別是100、80、60萬。按照保守策略，銀行對第一個用戶和第二個用戶貸款申請可以批準一次付清，但是第三個用戶就不能批準了，相當于拒絕了第三個用戶的貸款申請（類比進程啟動）。

拒絕資源分配

著名的銀行家算法

假設按照上述案例，銀行分批貸款，第一次分配完后賬面只剩下10萬，此時第二輪分期只能給user2，否則user1和3滿足不了，后期也收不回本金。所以，銀行只能一直拒絕兩者的催款直到user2還款。（類比系統資源，OS會根據當前狀況動態決定資源分配，是否需要拒絕進程的資源申請）。

這里就要找到安全序列，該序列可以依次滿足不同用戶的最大需求。

來看OS如何進行資源分配

R = V + A（資源總數 = 可用資源+已經分配的資源）

這里遍歷矩陣C - A每行和V對比，找到某個在有限時間內可以執行完將資源歸還給系統的進程。經過多次分配，直到所有進程運行完畢，然后得到安全分配序列。
如上圖，能符合011的就只有P2進程可以滿足，也就是說OS接下來只能一次滿足P2進程的資源申請要求，此時安全隊列中加入P2。P2執行結束之后釋放自己的所有資源，此時可用資源就變成了673。

同理，我們按照之前的分配策略，可以發現對于這四個進程的唯一安全分配序列是P2→P1→P3→P4.

舉一個不安全示例
當進程1在第一次剩余資源分配的時候請求資源R3，如果OS分配出去，會導致進程2也不能滿足最大需求，這個時候就找不到安全分配序列，很容易發生死鎖，所以之前就要拒絕進程1的資源分配請求。

教科書上給了偽代碼，感興趣的小伙伴可以看一下

避免死鎖有一些優勢，但是缺點也很明顯。
優勢

• 不需要如死鎖檢測一樣搶占、回滾進程
• 同死鎖預防相比，資源分配限制少
  缺點
• 需要提前聲明最大資源請求
• 設計進程獨立且無同步需求
• 分配資源數目固定
• 當擁有資源時進程不退出

一般通用的OS很難滿足上述需求，所以只能是理論上分析。但是對于一些嵌入式系統，由于代碼和硬件固化，或許可以按照銀行家算法去設計避免死鎖。

死鎖的檢測

檢測頻率

檢測的頻率如何控制呢？
如果每次資源請求的時候都檢查是否有死鎖，系統開銷就會很大

兩個思路

• 進程阻塞時間過長則檢測
• 資源利用率下降則檢測

這里可以使用拓撲排序找資源分配回路（需提前簡化，以防偽回路）
這個涉及圖論中的鄰接矩陣的表示，利用的也是前面的V、A，還有一個請求矩陣Q
所有進程都要先打上“未死鎖”標簽，然后檢查進程序列的標簽中是否有“死鎖”

具體執行過程見PPT，這里不做重點

讓我們來分析一些各個進程的情況：
首先，p4肯定沒問題，因為它的的分配矩陣行全為0，第一步就被標記了。p3在p4的基礎上沒問題，因為執行第三步的時候發現p3滿足條件1，于是第四步p3被標記。
而p1、p2死鎖，因為返回到步驟三發現此時已經找不到符合條件的進程了，檢測終止，此時兩個進程未標記符合死鎖條件。

當然，也可以用上一節學的進程請求/資源分配圖來看，更直觀一些。

恢復策略

• 中止所有死鎖進程
• 死鎖進程回退到某個預定義的檢查點，重新啟動所有進程（下一次可能還會發生死鎖）
• 依次中止死鎖進程，可以逐步解決
• 剝奪進程死鎖的資源

而上述選擇中止的死鎖進程準則

• 到目前為止，使用處理器時間最少（有效執行時間最短）
• 到目前為止，產生輸出最少（比如寫數據最少）
• 估計剩余的執行時間最長（第九章調度策略）
• 到目前為止，分配資源最少的（擁有的資源最少）
• 考慮進程的優先級最低的進程

亦可以采用復合準則加權統一各個原則

綜合死鎖策略

舉例

• 將各種資源歸入若干不同的資源類
• 每一類資源使用線性序申請預防
• 對同一資源類中的資源，采用適當的方法

例如數據庫管理系統

• Swappable space: 對換用的磁盤塊（空間足夠），一次性分配所需所有資源來預防或死鎖避免
• Process resources: 可分配資源（磁帶機、文件），避免或基于資源排序的預防
• Main memory: 頁或段，基于剝奪的預防
• Internal resources: 如 I/O channels，基于資源排序的預防（早期的磁帶機等）

總結