## **一、死鎖的概念** 在許多應用中進程需要以**獨占**的方式訪問資源，當操作系統允許多個進程并發執行時可能會出現進程永遠被阻塞現象，如兩個進程分別等待對方所占的資源，于是兩者都不能執行而**處于永遠等待狀態**，此現象稱為**死鎖**。 > 死鎖通常被定義為：如果一個進程集合中的每個進程都在等待只能由此集合中的其他進程才能引發的事件，而無限期陷入僵持的局面稱為死鎖。 ## **二、死鎖產生的條件** * 互斥條件 臨界資源是獨占資源，進程應互斥且排他的使用這些資源。 * 占有和等待條件 進程在請求資源得不到滿足而等待時，不釋放已占有資源。 * 不剝奪條件 又稱不可搶占，已獲資源只能由進程自愿釋放，不允許被其他進程剝奪。 * 循環等待條件 又稱環路條件，存在循環等待鏈，其中，每個進程都在等待鏈中等待下一個進程所持有的資源，造成這組進程處于永遠等待狀態。 **死鎖只有在這四個條件同時滿足時出現。** ## **三、死鎖產生的原因** 死鎖產生的原因有很多，如： * 進程順序不當 * PV操作使用不妥 * 同類資源分配不均 * 對某些資源的使用未加限制 等等。 > 可見，產生死鎖的原因不僅與系統擁有的資源數量有關，而且與資源分配策略、進程對資源的使用要求以及進程的推進順序有關。 ## **四、死鎖解決的方法** 主要有一下三種方法： * 死鎖防止 * 死鎖避免 * 死鎖檢測和恢復 ## **4.1 死鎖防止** **在程序運行之前防止發生死鎖。** 前面說了死鎖產生的條件有四個，分別是：互斥條件、占有和等待條件、不剝奪條件、循環等待條件。 **而死鎖防止的策略就是至少破壞這四個條件其中一項。** ### **4.1.1 破壞互斥條件** 使資源同時訪問而非互斥使用，就沒有進程會阻塞在資源上，從而不發生死鎖。 > 只讀數據文件、磁盤等軟硬件資源均可采用這種辦法管理； > 但是許多資源是獨占性資源，如可寫文件、鍵盤等只能互斥的占有； > 所以這種做法在許多場合是不適用的。 ### **4.1.2 破壞占有和等待條件** 采用靜態分配的方式，靜態分配的方式是指進程必須在執行之前就申請需要的全部資源，且直至所要的資源全部得到滿足后才開始執行。 > 實現簡單，但是嚴重的減低了資源利用率。 > 因為在每個進程占有的資源中，有些資源在運行后期使用，有些資源在例外情況下才被使用，可能會造成進程占有一些幾乎用不到的資源，而使其他想使用這些資源的進程等待。 ### **4.1.3 破壞不剝奪條件** 剝奪調度能夠防止死鎖，但是只適用于內存和處理器資源。 方法一：占有資源的進程若要申請新資源，必須主動釋放已占有資源，若需要此資源，應該向系統重新申請。 方法二：資源分配管理程序為進程分配新資源時，若有則分配；否則將剝奪此進程已占有的全部資源，并讓進程進入等待資源狀態，資源充足后再喚醒它重新申請所有所需資源。 ### **4.1.4 破壞循環等待條件** 給系統的所有資源編號，規定進程請求所需資源的順序必須按照資源的編號依次進行。 > 采用層次分配策略，將系統中所有的資源排列到不同層次中 * 一個進程得到某層的一個資源后，只能申請較高一層的資源 * 當進程釋放某層的一個資源時，必須先釋放所占有的較高層的資源 * 當進程獲得某層的一個資源時，如果想申請同層的另一個資源，必須先釋放此層中已占有的資源 ## **4.2死鎖避免** > 各種死鎖防止方法能夠防止發生死鎖，但必然會降低系統并發性，導致低效的資源利用率。 **在程序運行時避免發生死鎖。** ### **4.2.1 安全狀態**  圖 a 的第二列 Has 表示已擁有的資源數，第三列 Max 表示總共需要的資源數，Free 表示還有可以使用的資源數。從圖 a 開始出發，先讓 B 擁有所需的所有資源（圖 b），運行結束后釋放 B，此時 Free 變為 5（圖 c）；接著以同樣的方式運行 C 和 A，使得所有進程都能成功運行，因此可以稱圖 a 所示的狀態時安全的。 定義：如果沒有死鎖發生，并且即使所有進程突然請求對資源的最大需求，也仍然存在某種調度次序能夠使得每一個進程運行完畢，則稱該狀態是安全的。 安全狀態的檢測與死鎖的檢測類似，因為安全狀態必須要求不能發生死鎖。下面的銀行家算法與死鎖檢測算法非常類似，可以結合著做參考對比。 ### **4.2.2單個資源的銀行家算法** 一個小城鎮的銀行家，他向一群客戶分別承諾了一定的貸款額度，算法要做的是判斷對請求的滿足是否會進入不安全狀態，如果是，就拒絕請求；否則予以分配。  上圖 c 為不安全狀態，因此算法會拒絕之前的請求，從而避免進入圖 c 中的狀態。 ### **4.2.3 多個資源的銀行家算法**  上圖中有五個進程，四個資源。左邊的圖表示已經分配的資源，右邊的圖表示還需要分配的資源。最右邊的 E、P 以及 A 分別表示：總資源、已分配資源以及可用資源，注意這三個為向量，而不是具體數值，例如 A=(1020)，表示 4 個資源分別還剩下 1/0/2/0。 檢查一個狀態是否安全的算法如下： * 查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那么系統將會發生死鎖，狀態是不安全的。 * 假若找到這樣一行，將該進程標記為終止，并將其已分配資源加到 A 中。 * 重復以上兩步，直到所有進程都標記為終止，則狀態時安全的。 如果一個狀態不是安全的，需要拒絕進入這個狀態。 ## **4.3 死鎖檢測和恢復** > 對資源的分配加以適當限制可防止或避免死鎖發生，但不利于進程對系統資源的充分共享。 **不試圖阻止死鎖，而是當檢測到死鎖發生時，采取措施進行恢復。** > 如果進程 - 資源分配圖中無環路，此時系統沒有發生死鎖。 > 如果進程 - 資源分配圖中有環路，則可分為以下兩種情況： * 每種資源類中僅有一個資源，則系統發生了死鎖。此時，環路是系統發生死鎖的**充分必要條件**，環路中的進程就是死鎖進程。 * 每種資源類中有多個資源，則環路的存在只是產生死鎖的**必要不充分條件**，系統未必會發生死鎖。 **下面詳細說一下這兩種情況：** ### **4.3.1 每種資源類中僅有一個資源的死鎖檢測**  上圖為資源分配圖，其中方框表示資源，圓圈表示進程。資源指向進程表示該資源已經分配給該進程，進程指向資源表示進程請求獲取該資源。 圖 a 可以抽取出環，如圖 b，它滿足了環路等待條件，因此會發生死鎖。 > 比如：進程D需要的資源是U、T；進程G需要的資源是V、U；進程E需要的資源是T、V > 此時進程D占有資源U，進程E占有資源T，進程G占有資源V > 所以此時導致進程D、E、G所申請的資源不能得到全部滿足，陷入死鎖。 **死鎖檢測算法：** 每種類型一個資源的死鎖檢測算法是通過檢測有向圖是否存在環來實現，從一個節點出發進行深度優先搜索，對訪問過的節點進行標記，如果訪問了已經標記的節點，就表示有向圖存在環，也就是檢測到死鎖的發生。 ### **4.3.2 每種資源類中有多個資源的死鎖檢測**  每個資源類用一個方框表示，方框中的原點表示此資源類中的各個資源； 每個進程用一個圓圈來表示，用有向邊表示進程申請資源和資源分配情況。 約定方框→圓圈表示資源分配，圓圈→方框表示申請資源。 這種情況下，圖3-6 發生了死鎖，而圖3-7沒有發生死鎖。  **死鎖檢測算法:**  上圖中，有三個進程四個資源，每個數據代表的含義如下： * E 向量：資源總量 * A 向量：資源剩余量 * C 矩陣：每個進程所擁有的資源數量，每一行都代表一個進程擁有資源的數量 * R 矩陣：每個進程請求的資源數量 進程 P1 和 P2 所請求的資源都得不到滿足，只有進程 P3 可以，讓 P3 執行，之后釋放 P3 擁有的資源，此時 A = (2 2 2 0)。P2 可以執行，執行后釋放 P2 擁有的資源，A = (4 2 2 1) 。P1 也可以執行。所有進程都可以順利執行，沒有死鎖。 算法總結如下： 每個進程最開始時都不被標記，執行過程有可能被標記。當算法結束時，任何沒有被標記的進程都是死鎖進程。 1. 尋找一個沒有標記的進程 Pi，它所請求的資源小于等于 A。 2. 如果找到了這樣一個進程，那么將 C 矩陣的第 i 行向量加到 A 中，標記該進程，并轉回 1。 3. 如果沒有這樣一個進程，算法終止。 ### **4.3.3 死鎖恢復** * 資源剝奪法 剝奪陷于死鎖的進程所占用的資源，但并不撤銷此進程，直至死鎖解除。 * 進程回退法 根據系統保存的檢查點讓所有的進程回退，直到足以解除死鎖，這種措施要求系統建立保存檢查點、回退及重啟機制。 * 進程撤銷法 * 撤銷陷入死鎖的所有進程，解除死鎖，繼續運行。 * 逐個撤銷陷入死鎖的進程，回收其資源并重新分配，直至死鎖解除。 可選擇符合下面條件之一的先撤銷： 1.CPU消耗時間最少者 2.產生的輸出量最小者 3.預計剩余執行時間最長者 4.分得的資源數量最少者后優先級最低者 * 系統重啟法 結束所有進程的執行并重新啟動操作系統。這種方法很簡單，但先前的工作全部作廢，損失很大。