【操作系統】死鎖（詳細）
一、死鎖的概念
操作系統中的死鎖是指：
如果在一個進程集合中的每個進程都在等待只能有該集合中的其它進程才能引起的事件，而無限期陷入僵持的局面稱爲死鎖。
二、死鎖的產生因素
1、系統擁有的資源數量
2、資源分配策略
3、進程對資源的使用要求
4、併發進程的推薦順序
三、死鎖的必要條件
1、互斥條件
進程互斥使用資源，一旦某個資源被佔用，欲使用該資源的進程必須等待。
2、佔有和等待條件（部分分配條件）
進程申請新資源得不到滿足而等待時，不釋放已佔有資源。
3、不剝奪條件
一個進程不能搶奪其它進程佔有的資源。
4、循環等待條件（環路條件）
存在一組進程循環等待資源的現象。
前三個條件是死鎖產生的必要條件，不是充分條件。第四個條件是前三個條件同時存在時產生的結果。只要破壞這四個條件之一，死鎖就可防止。
四、死鎖防止
死鎖防止通過破壞產生死鎖的四個條件之一來實現。
1、破壞互斥條件
使資源可同時訪問而不是互斥使用。
該辦法對於磁盤適用，對於磁帶機、打印機等多數資源不僅不能破壞互斥使用條件，還要加以保證。
2、破壞佔有和等待條件
靜態分配可以破壞佔有和等待條件。
靜態分配是指一個進程必須在執行前就申請它所需要的全部資源，並且直到它所需要的資源都得到滿足後纔開始執行。資源利用率低。
3、破壞不剝奪條件
採用剝奪式調度方法。
當進程申請資源未獲准許時，在等待前主動釋放資源。剝奪調度方法目前只適用於內存資源和處理器資源。
4、破壞循環等待條件
採用層次分配策略可以破壞循環等待條件。
層次分配策略將資源被分成多個層次，進程按照由低到高的層次順序申請和得到資源，按照由高到低的層次順序釋放資源。當進程得到某一層的一個資源後，如果需要申請該層的另一個資源，則必須先釋放該層中的已佔資源。
五、死鎖避免
1、避免死鎖的策略
死鎖避免方法允許系統中同時存在死鎖的三個必要條件，即互斥、佔有且等待和非搶佔；
每當進程提出資源申請時，系統分析滿足該資源請求時系統是否會發生死鎖，若不會發生則實施分配，否則拒絕分配。
銀行家算法就是避免死鎖的一種方法。
2、銀行家算法思想
一個銀行家擁有資金 M，被 N 個客戶共享，銀行家對客戶提出下列約束條件：
① 每個客戶必須預先說明自己所要求的最大資金量；
② 每個客戶每次提出部分資金量申請和獲得分配；
③ 如果銀行滿足了客戶對資金的最大需求量，則客戶在資金運作後一定可以很快歸還資金。
3、銀行家算法在死鎖問題上的應用
步驟：
① 系統中的所有進程進入進程集合；
② 在安全狀態下對進程請求的資源進行試探性分配；
③ 系統用剩餘的可用資源和進程集合中其它進程還要的資源數作比較，找到剩餘資源能滿足最大需求量的進程 A，保證 A 運行完畢並歸還全部資源；
④ 把進程 A 從集合中去掉，相當於回收其資源。如果進程集合非空，則返回②；
⑤ 若進程集合爲空，則系統處於安全狀態，可實施本次分配；否則，系統處於不安全狀態，本次資源分配暫不實施，申請進程等待。
安全狀態與不安全狀態：
如果系統能夠按某種進程順序（P1，P2，… … ，Pn）（稱 <P1，P2，… … ，Pn> 序列爲安全序列），爲每個進程 Pi 分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都能順利完成，則稱系統處於安全狀態。
如果找不到這樣的安全序列，則稱系統處於不安全狀態。
例：
4、銀行家算法的缺點
① 使用銀行家算法時，很難在進程運行前知道其所需的資源最大量；② 算法要求系統中的進程必須是無關的，相互間沒有同步要求；③ 進程的個數和分配的資源數目應該是固定的；這些要求事先難以滿足，因而銀行家算法缺乏實用價值。
六、死鎖檢測與解除
1、死鎖檢測策略
死鎖檢測和解除對資源分配不加任何限制，也不採取死鎖避免措施，但系統定時運行一個 “死鎖檢測” 程序，如果檢測到系統發生了死鎖，再採取措施解除它。
進程 - 資源分配圖是描述進程和資源間申請與分配關係的一種有向圖，可用以檢測系統是否處於死鎖狀態。
2、進程 - 資源分配圖的結構
進程 - 資源分配圖由進程結點 P、資源結點 R 和有向邊組成。
有向邊：
① 請求邊：
從進程指向資源的有向邊 Pi→Rj 爲請求邊，表示進程 Pi 申請資源類 Rj 中的一個資源。
② 分配邊：
從資源指向進程的有向邊 Rj→Pi 爲分配邊，表示 Rj 類中的一個資源已分配給進程 Pi。
3、進程 - 資源分配圖與死鎖判斷的關係
① 如果進程 - 資源分配圖中無環路
——> 則此時系統沒有發生死鎖
② 如果進程 - 資源分配圖中有環路，且每個資源類中僅有一個資源
——> 則系統中發生了死鎖，此時，環路是系統發生死鎖的充要條件，環路中的進程便爲死鎖進程
③ 如果進程 - 資源分配圖中有環路，且涉及的資源類中有多個資源
——> 則環的存在只是產生死鎖的必要條件而不是充分條件
4、死鎖的檢測和解除方法
死鎖定理
系統爲死鎖狀態的充分條件是：當且僅當該狀態的進程 - 資源分配圖是不可完全簡化的。該充分條件稱爲死鎖定理。
簡化進程 - 資源分配圖
① 從進程 - 資源分配圖中找到一個既不阻塞又非獨立的進程，消去所有與該進程相連的有向邊，相當於該進程能夠執行完成而釋放資源，回收資源使之成爲孤立結點。
② 然後將所回收的資源分配給其它進程，再從進程 - 資源分配圖中找到下一個既不阻塞又非獨立的進程，消去所有與該進程相連的有向邊，使之成爲孤立結點。
③ 不斷重複該過程，直到所有進程成爲孤立結點，則稱該圖是可完全化簡的；否則稱該圖是不可完全化簡的。
死鎖檢測實例：
問題求解：
解決思路：無法應用死鎖判定原則，需要化簡。按照 P1、P2 和 P3 的順序逐一考察每個進程，判斷其是否孤立和阻塞。
① P1、P2 和 P3 三個進程均不孤立，接下來需要判斷它們是否阻塞。
② P1：該進程請求資源 R1，而 R1 僅有的一個資源已經分配給 P2，所以 P1 阻塞；
③ 該進程請求資源 R2，而 R2 僅有的一個資源已經分配給 P3，所以 P2 阻塞。
④ 該進程請求資源 R3，而 R3 的兩個資源已經分別分配給 P1 和 P2，所以 P3 阻塞。
結論：進程 - 資源分配圖無法完全化簡，因此進程集合發生死鎖。
5、死鎖檢測算法與死鎖避免算法比較
① 死鎖檢測算法考慮了檢查每個進程還需要的所有資源能否滿足要求；
死鎖避免算法則僅根據進程的當前申請資源量來判斷系統是否進入了不安全狀態。
② 死鎖檢測算法處理的進程 - 資源圖中可以同時存在多個進程的請求邊。
在銀行家算法中，一次僅允許一個進程提出資源請求，做安全分析並分配資源後，才允許下一個進程提出資源請求。
6、死鎖的解除方法
① 立即結束所有進程的執行，並重新啓動操作系統。以前工作全部作廢，損失可能很大。
② 剝奪陷於死鎖的進程佔用的資源，但並不撤銷它，直至死鎖解除。
③ 撤銷陷於死鎖的所有進程，解除死鎖繼續運行。
④ 逐個撤銷陷於死鎖的進程，回收其資源，直至死鎖解除。
⑤ 根據系統保存的檢查點，使所有進程回退，直到足以解除死鎖。
⑥ 當檢測到死鎖時，如果存在某些未捲入死鎖的進程，且它們會進一步建立一些新的抑制進程能執行到結束，則它們可能釋放足夠的資源來解除死鎖。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/9E7c-RJF_BX-uzEwJDRq3w