[TOC] ## 死鎖的定義 在多道程序系統中，由于多個進程的并發執行，改善了系統資源的利用率并提高了系統 的處理能力。然而，多個進程的并發執行也帶來了新的問題——死鎖。所謂死鎖是指多個進 程因競爭資源而造成的一種僵局（互相等待），若無外力作用，這些進程都將無法向前推進。 下面我們通過一些實例來說明死鎖現象。 先看生活中的一個實例，在一條河上有一座橋，橋面很窄，只能容納一輛汽車通行。如 果有兩輛汽車分別從橋的左右兩端駛上該橋，則會出現下述的沖突情況。此時，左邊的汽車 占有了橋面左邊的一段，要想過橋還需等待右邊的汽車讓出橋面右邊的一段；右邊的汽車占 有了橋面右邊的一段，要想過橋還需等待左邊的汽車讓出橋面左邊的一段。此時，若左右兩 邊的汽車都只能向前行駛，則兩輛汽車都無法過橋。 在計算機系統中也存在類似的情況。例如，某計算機系統中只有一臺打印機和一臺輸入 設備，進程P1正占用輸入設備，同時又提出使用打印機的請求，但此時打印機正被進程P2 所占用，而P2在未釋放打印機之前，又提出請求使用正被P1占用著的輸入設備。這樣兩個進程相互無休止地等待下去，均無法繼續執行，此時兩個進程陷入死鎖狀態。 ## 死鎖產生的原因 ### 1) 系統資源的競爭 通常系統中擁有的不可剝奪資源，其數量不足以滿足多個進程運行的需要，使得進程在 運行過程中，會因爭奪資源而陷入僵局，如磁帶機、打印機等。只有對不可剝奪資源的競爭 才可能產生死鎖，對可剝奪資源的競爭是不會引起死鎖的。 ### 2) 進程推進順序非法 進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致死鎖。例如，并發進程 P1、P2分別保持了資源R1、R2，而進程P1申請資源R2，進程P2申請資源R1時，兩者都 會因為所需資源被占用而阻塞。 信號量使用不當也會造成死鎖。進程間彼此相互等待對方發來的消息，結果也會使得這 些進程間無法繼續向前推進。例如，進程A等待進程B發的消息，進程B又在等待進程A 發的消息，可以看出進程A和B不是因為競爭同一資源，而是在等待對方的資源導致死鎖。 ### 3) 死鎖產生的必要條件 產生死鎖必須同時滿足以下四個條件，只要其中任一條件不成立，死鎖就不會發生。 互斥條件：進程要求對所分配的資源（如打印機）進行排他性控制，即在一段時間內某 資源僅為一個進程所占有。此時若有其他進程請求該資源，則請求進程只能等待。 不剝奪條件：進程所獲得的資源在未使用完畢之前，不能被其他進程強行奪走，即只能 由獲得該資源的進程自己來釋放（只能是主動釋放)。 請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源 已被其他進程占有，此時請求進程被阻塞，但對自己已獲得的資源保持不放。 循環等待條件：存在一種進程資源的循環等待鏈，鏈中每一個進程已獲得的資源同時被 鏈中下一個進程所請求。即存在一個處于等待狀態的進程集合{Pl, P2, ..., pn}，其中Pi等 待的資源被P(i+1)占有（i=0, 1, ..., n-1)，Pn等待的資源被P0占有，如圖2-15所示。 直觀上看，循環等待條件似乎和死鎖的定義一樣，其實不然。按死鎖定義構成等待環所 要求的條件更嚴，它要求Pi等待的資源必須由P(i+1)來滿足，而循環等待條件則無此限制。 例如，系統中有兩臺輸出設備，P0占有一臺，PK占有另一臺，且K不屬于集合{0, 1, ..., n}。 Pn等待一臺輸出設備，它可以從P0獲得，也可能從PK獲得。因此，雖然Pn、P0和其他 一些進程形成了循環等待圈，但PK不在圈內，若PK釋放了輸出設備，則可打破循環等待, 如圖2-16所示。因此循環等待只是死鎖的必要條件。  資源分配圖含圈而系統又不一定有死鎖的原因是同類資源數大于1。但若系統中每類資 源都只有一個資源，則資源分配圖含圈就變成了系統出現死鎖的充分必要條件。 ## 死鎖的處理策略 為使系統不發生死鎖，必須設法破壞產生死鎖的四個必要條件之一，或者允許死鎖產生， 但當死鎖發生時能檢測出死鎖，并有能力實現恢復。 ### 預防死鎖 設置某些限制條件，破壞產生死鎖的四個必要條件中的一個或幾個，以防止發生死鎖。 ### 避免死鎖 在資源的動態分配過程中，用某種方法防止系統進入不安全狀態，從而避免死鎖。 ### 死鎖的檢測及解除 無需釆取任何限制性措施，允許進程在運行過程中發生死鎖。通過系統的檢測機構及時 地檢測出死鎖的發生，然后釆取某種措施解除死鎖。 預防死鎖和避免死鎖都屬于事先預防策略，但預防死鎖的限制條件比較嚴格，實現起來 較為簡單，但往往導致系統的效率低，資源利用率低；避免死鎖的限制條件相對寬松，資源 分配后需要通過算法來判斷是否進入不安全狀態，實現起來較為復雜。 死鎖的幾種處理策略的比較見表2-14。  ## 死鎖預防 防止死鎖的發生只需破壞死鎖產生的四個必要條件之一即可。 ### 1) 破壞互斥條件 如果允許系統資源都能共享使用，則系統不會進入死鎖狀態。但有些資源根本不能同時訪問，如打印機等臨界資源只能互斥使用。所以，破壞互斥條件而預防死鎖的方法不太可行，而且在有的場合應該保護這種互斥性。 ### 2) 破壞不剝奪條件 當一個已保持了某些不可剝奪資源的進程，請求新的資源而得不到滿足時，它必須釋放已經保持的所有資源，待以后需要時再重新申請。這意味著，一個進程已占有的資源會被暫時釋放，或者說是被剝奪了，或從而破壞了不可剝奪條件。 該策略實現起來比較復雜，釋放已獲得的資源可能造成前一階段工作的失效，反復地申請和釋放資源會增加系統開銷，降低系統吞吐量。這種方法常用于狀態易于保存和恢復的資源，如CPU的寄存器及內存資源，一般不能用于打印機之類的資源。 ### 3) 破壞請求和保持條件 釆用預先靜態分配方法，即進程在運行前一次申請完它所需要的全部資源，在它的資源未滿足前，不把它投入運行。一旦投入運行后，這些資源就一直歸它所有，也不再提出其他資源請求，這樣就可以保證系統不會發生死鎖。 這種方式實現簡單，但缺點也顯而易見，系統資源被嚴重浪費，其中有些資源可能僅在運行初期或運行快結束時才使用，甚至根本不使用。而且還會導致“饑餓”現象，當由于個別資源長期被其他進程占用時，將致使等待該資源的進程遲遲不能開始運行。 ### 4) 破壞循環等待條件 為了破壞循環等待條件，可釆用順序資源分配法。首先給系統中的資源編號，規定每個進程，必須按編號遞增的順序請求資源，同類資源一次申請完。也就是說，只要進程提出申請分配資源Ri，則該進程在以后的資源申請中，只能申請編號大于Ri的資源。 這種方法存在的問題是，編號必須相對穩定，這就限制了新類型設備的增加；盡管在為資源編號時已考慮到大多數作業實際使用這些資源的順序，但也經常會發生作業使甩資源的順序與系統規定順序不同的情況，造成資源的浪費；此外，這種按規定次序申請資源的方法，也必然會給用戶的編程帶來麻煩。 ## 死鎖避免 避免死鎖同樣是屬于事先預防的策略，但并不是事先釆取某種限制措施破壞死鎖的必要條件，而是在資源動態分配過程中，防止系統進入不安全狀態，以避免發生死鎖。這種方法所施加的限制條件較弱，可以獲得較好的系統性能。 ### 1. 系統安全狀態 避免死鎖的方法中，允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次資源分配的安全性。若此次分配不會導致系統進入不安全狀態，則將資源分配給進程； 否則，讓進程等待。 所謂安全狀態，是指系統能按某種進程推進順序( P1, P2, ..., Pn)，為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順序地完成。此時稱 P1, P2, ..., Pn 為安全序列。如果系統無法找到一個安全序列，則稱系統處于不安全狀態。 假設系統中有三個進程P1、P2和P3,共有12 臺磁帶機。進程P1總共需要10臺磁帶機，P2和P3 分別需要4臺和9臺。假設在T0時刻，進程P1、P2 和P3已分別獲得5合、2臺和2臺，尚有3臺未分配，見表2-15。 表2-15 資源分配 進程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 則在T0時刻是安全的，因為存在一個安全序列P2、Pl、P3，即只要系統按此進程序列分配資源，則每個進程都能順利完成。若在T0時刻后，系統分配1臺磁帶機給P3，則此時系統便進入不安全狀態，因為此時已無法再找到一個安全序列。 并非所有的不安全狀態都是死鎖狀態，但當系統進入不安全狀態后，便可能進入死鎖狀態；反之，只要系統處于安全狀態，系統便可以避免進入死鎖狀態。 ### 2. 銀行家算法 銀行家算法是最著名的死鎖避免算法。它提出的思想是：把操作系統看做是銀行家，操作系統管理的資源相當于銀行家管理的資金，進程向操作系統請求分配資源相當于用戶向銀行家貸款。操作系統按照銀行家制定的規則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先測試該進程已占用的資源數與本次申請的資源數之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統現存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。 1) 數據結構描述 可利用資源矢量Available：含有m個元素的歎組，其中的每一個元素代表一類可用的資源數目。Available[j]=K，則表示系統中現有Rj類資源K個。 最大需求矩陣Max：為n*m矩陣，定義了系統中n個進程中的每一個進程對m類資源的最大需求。Max[i, j]=K，則表示進程i需要Rj類資源的最大數目為K。 分配矩陣Allocation：為n*m矩陣，定義了系統中每一類資源當前已分配給每一進程的資源數。All0Cati0n[i, j]= K，則表示進程i當前已分得Rj類資源的數目為K。 需求矩陣Need：為n*m矩陣，表示每個進程尚需的各類資源數。Need[i, j]=K，則表示進程i還需要Rj類資源的數目為K。 上述三個矩陣間存在下述關系： Need[i, j] = Max[i, j] - Allocation[i, j] 2) 銀行家算法描述 設Requesti是進程Pi的請求矢量，如果Requesti[j]K，表示進程Pi需要Rj類資源K個。當Pi發出資源請求后，系統按下述步驟進行檢查： ①如果Requesti[j] <= Need[i, j]，便轉向步驟②；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。 ②如果Requesti[j] <= Available[j]，便轉向步驟③;否則，表示尚無足夠資源，Pi須等待。 ③系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值： Available[j] = Available[j] - Requesti[j]; Allocation[i, j] = Allocation[i, j] + Requesti[ j]; Need[i, j] = Need[i, j] - Requesti[j]; ④系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。 3) 安全性算法 ①設置兩個矢量。工作矢量Work；它表示系統可提供給進程繼續運行所需的各類資源數目，它含有所個元素，在執行安全算法開始時，Work=Available; Finish：它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時 Finish[i]=false；當有足夠資源分配給進程 Pi 時，再令 Finish[i]=true。 ②從進程集合中找到一個能滿足下述條件的進程：Finish[i]=false; Need[i, j]<=Work[j]; 若找到，執行下一步驟，否則，執行步驟4。 ③當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行： Work[j]=Work[j]+Allocation[i, j]; Finish[i]=true; go to step <2>; ④如果所有進程的Finish[i]=tme都滿足，則表示系統處于安全狀態；否則，系統處于不安全狀態。   ## 死鎖的檢測和解除 前面紹的死鎖預防和避免算法，都是在為進程分配資源時施加限制條件或進行檢測，若系統為進程分配資源時不釆取任何措施，則應該提供死鎖檢測和解除的手段。 ### 資源分配圖 系統死鎖，可利用資源分配圖來描述。如圖2-17所示，用圓圈代表一個進程，用框代表一類資源。由于一種類型的資源可能有多個，用框中的一個點代表一類資源中的一個資源。從進程到資源的有向邊叫請求邊，表示該進程申請一個單位的該類資源；從資源到進程的邊叫分配邊，表示該類資源已經有一個資源被分配給了該進程。  圖2-17 資源分配示例圖 在圖2-17所示的資源分配圖中，進程P1已經分得了兩個R1資源，并又請求一個R2 資源；進程P2分得了一個R1和一個R2資源，并又請求一個R1資源。 ### 死鎖定理 可以通過將資源分配圖簡化的方法來檢測系統狀態S是否為死鎖狀態。簡化方法如下： 1) 在資源分配圖中，找出既不阻塞又不是孤點的進程Pi（即找出一條有向邊與它相連，且該有向邊對應資源的申請數量小于等于系統中已有空閑資源數量。若所有的連接該進程的邊均滿足上述條件，則這個進程能繼續運行直至完成，然后釋放它所占有的所有資源）。消去它所有的請求邊和分配邊，使之成為孤立的結點。在圖2-18(a)中，P1是滿足這一條件的進程結點，將P1的所有邊消去，便得到圖248(b)所示的情況。 2) 進程Pi所釋放的資源，可以喚醒某些因等待這些資源而阻塞的進程，原來的阻塞進程可能變為非阻塞進程。在圖2-17中，進程P2就滿足這樣的條件。根據第1) 條中的方法進行一系列簡化后,若能消去圖中所有的邊，則稱該圖是可完全簡化的，如圖2-18(c)所示。 S為死鎖的條件是當且僅當S狀態的資源分配圖是不可完全簡化的,該條件為死鎖定理。 ### 死鎖的解除 一旦檢測出死鎖，就應立即釆取相應的措施，以解除死鎖。死鎖解除的主要方法有： 1) 資源剝奪法。掛起某些死鎖進程，并搶占它的資源，將這些資源分配給其他的死鎖進程。但應防止被掛起的進程長時間得不到資源，而處于資源匱乏的狀態。 2) 撤銷進程法。強制撤銷部分、甚至全部死鎖進程并剝奪這些進程的資源。撤銷的原則可以按進程優先級和撤銷進程代價的高低進行。  圖2-18 資源分配圖的化簡 3) 進程回退法。讓一（多）個進程回退到足以回避死鎖的地步，進程回退時自愿釋放資源而不是被剝奪。要求系統保持進程的歷史信息，設置還原點。