1、死鎖產(chǎn)生的四個必要條件
- 互斥條件：進程對所分配到的資源進行排他性使用咏雌，即在某一段時間內某資源只能由一個進程占用斩郎，在資源被占用期間請求資源的進程只能等待資源釋放。
- 請求和保持條件：進程請求某個資源虏劲，但是該資源已經(jīng)被其他進程占有，此時進程只能阻塞等待資源釋放褒颈，但又不釋放已占有的其他資源柒巫。
- 不剝奪條件：進程獲得的資源只能由進程本身釋放，不能被外部程序剝奪谷丸。
- 環(huán)路等待條件：指在發(fā)生死鎖時必然存在一個進程-資源喚醒鏈堡掏，鏈的下一個節(jié)點等待上一個節(jié)點釋放資源，如 P0等待 P1釋放資源刨疼，P1等待 P0釋放資源泉唁。
2鹅龄、處理死鎖的三種基本方法
處理死鎖的基本方法有：預防死鎖、避免死鎖亭畜、檢測死鎖四種方法扮休。
預防死鎖：通過設置一些限制條件，破壞產(chǎn)生死鎖的四個必要條件的一個或多個拴鸵，來預防發(fā)生死鎖玷坠。預防死鎖實現(xiàn)簡單，但是往往因為限制條件太過嚴格劲藐，導致系統(tǒng)資源利用率和吞吐量減少八堡。
避免死鎖：這種方法同樣屬于事先預防的策略，但是它不用事先設置限制條件聘芜，而是在資源分配的過程中使用某種方法避免系統(tǒng)進入不安全狀態(tài)兄渺，從而避免發(fā)生死鎖。這種方法只需要事先設置較弱的限制條件厉膀，便可獲得較高的資源利用率和吞吐量溶耘。
檢測死鎖：這種方法事先不采取任何措施二拐，也不檢查系統(tǒng)是否進入不安全區(qū)服鹅，而是允許系統(tǒng)在運行時發(fā)生死鎖。但是在系統(tǒng)發(fā)生死鎖時可以及時的檢測出死鎖的發(fā)生百新，并定位和死鎖有關的線程和資源企软，然后采取措施解除死鎖。
3饭望、預防死鎖的方法
預防死鎖通過破壞死鎖產(chǎn)生的四個必要條件來達到預防死鎖產(chǎn)生的目的仗哨。但采用這種方法時不能破壞互斥條件，因為它是由設備的固有特性決定的铅辞，破壞會影響程序的正常運行厌漂。
既然不能破壞互斥條件，我們就來看看如何破壞其他三個條件斟珊，以及這些方法對系統(tǒng)吸能的影響苇倡。
破壞”請求和保持“條件：
所有進程在開始運行前必須一次性申請所有在運行中要用到的資源，如果申請成功則開始運行囤踩，否則讓進程等待旨椒。因為進程開始運行前一次性申請了所有所需的資源，所以進程在運行時不會再申請資源堵漱，這樣就破壞了請求條件综慎。同樣的，進程在等待期間不占用任何資源勤庐，因此也破壞了保持條件示惊。
這種預防死鎖的方法簡單好港、易于實現(xiàn)且安全。但是卻會造成資源的嚴重浪費米罚，一些資源可能很少使用媚狰，但進程卻在運行期間一直占用，導致其他真正需要該資源的進程無法開始阔拳。另外崭孤，一次性申請所有資源失敗的可能性較高，這樣就會導致一些進程因為申請資源一直失敗而延遲執(zhí)行糊肠。
破壞”不剝奪“條件：
進程在申請資源時如果不能立即滿足辨宠，進程需要釋放已經(jīng)占有的所有資源并等待，當進程再次運行時需要重新申請所需資源货裹。這種方法的缺點是某些資源的被迫釋放可能導致前面的工作失效嗤形，比如某個進程占有打印機，在進程在打印時被剝奪了打印機的占有弧圆，當進程再次獲得打印機時前面可能有其他進程的打印內容赋兵。另外，這種方法還有可能導致進程反復釋放和請求資源搔预，從而使進程無限期的等待下去霹期。
破壞”環(huán)路等待“條件：
系統(tǒng)對所有資源按類型進行線性排隊，并賦予遞增的序號拯田，進程在申請資源時必須按照順序進行申請历造。這種方式限制了新類型設備的添加，而且在用戶使用資源的順序和系統(tǒng)規(guī)定的順序不一致時會造成浪費船庇。另外吭产，這種強制的按順序申請資源的方式限制了用戶簡單、自主的編程鸭轮。
4臣淤、避免死鎖的方法
在避免死鎖的算法中，系統(tǒng)允許進程動態(tài)申請資源窃爷，但為進程分配資源前邑蒋，要先計算這次資源分配的安全性，如果這次分配不會導致系統(tǒng)進入不安全的狀態(tài)吞鸭，則將資源分配給進程寺董，否則讓進程等待。
安全狀態(tài)是指系統(tǒng)能夠按照某種序列，來為系統(tǒng)中的每個進程分配資源，直至滿足每個進程對資源的最大需求肆资，使每個進程都能順利完成磅崭。如果系統(tǒng)找不到這樣一個序列御吞，則稱系統(tǒng)處于不安全狀態(tài)麦箍。
系統(tǒng)進入不安全狀態(tài)并不意味著一定會進入死鎖狀態(tài)，但如果系統(tǒng)處于安全狀態(tài)陶珠，則一定不會進入死鎖狀態(tài)挟裂，所以避免死鎖可以轉換為避免系統(tǒng)進入不安全狀態(tài)。
最有代表性的避免死鎖的算法揍诽，是 Dijkstra的銀行家算法诀蓉。這是由于該算法能用于銀行
系統(tǒng)現(xiàn)金貸款的發(fā)放而得名的。
銀行家算法：
數(shù)據(jù)結構：
- 可利用資源向量 Available：這是一個含有 m個元素的數(shù)組暑脆，其中每一個元素代表一類可利用的資源的數(shù)目渠啤，初始值使系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而改變添吗。
- 最大需求矩陣 Max：這是一個 n*m的矩陣沥曹，它定義了系統(tǒng)中 n個進程各自對 m類資源的最大需求。如果 Max[i,j]=K碟联，則表示進程 i所需要的 j類資源的最大數(shù)目為 K妓美。
- 分配矩陣 Allocation：這是一個 n*m的矩陣，它定義了系統(tǒng)中每類資源已經(jīng)分配給對應進程的總數(shù)鲤孵。如果 Allocation[i,j]=K壶栋，則表示進程 i已分配 j類資源的數(shù)目為 K。
- 需求矩陣 Need：這是一個 n*m的矩陣裤纹，它定義了每一個進程尚需的各類資源數(shù)目委刘。如果 Need[i,j]=K丧没，則表示進程 i還需要 j類資源的數(shù)目為 K鹰椒。
算法：
設 Request是進程 P（進程號為 i）的請求向量，Request[j]=K表示進程 P需要 j類資源的數(shù)目為 K呕童，當進程發(fā)出請求后漆际，系統(tǒng)執(zhí)行以下步驟進行檢查：
如果 Request[j] <= Need[i,j]，轉向步驟 2夺饲；否則認為出錯奸汇，因為進程請求的資源已經(jīng)超過了它之前宣布的最大值。
如果 Request[j] <= Available[i,j]往声，轉向步驟 3擂找；否則認為出錯，因為進程請求的資源數(shù)已經(jīng)超過了當前可用的資源數(shù)量浩销。
-
系統(tǒng)將嘗試資源分配給進程 P贯涎，并更新 Max、Available和 Allocation的值：
Available[j] = Available[j] - Request[j] Allocation[i,j] = Allocation[i,j] + Request[j] Need[i,j] = Need[i,j] - Request[j] 系統(tǒng)執(zhí)行安全性算法慢洋，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)塘雳。若安全陆盘，則正式將資源分配給進程 P，否則败明，讓進程 P等待隘马。
安全性檢查算法：
設置兩個數(shù)組 Work和 Finish，Work的初始值為 Available的值妻顶，Work表示系統(tǒng)當前可用的所有資源數(shù)目酸员，可以把 Work看作是動態(tài)更新的 Available；Finish全部初始化為 false讳嘱，表示對應進程是否完成沸呐，最開始所有進程都未完成。
-
從進程集合中找到一個滿足下述條件的進程
- Finish[i] =false呢燥；進程未完成
- Need[i]<=Work崭添；這個不等式表示 Need[i]中的所有元素都小于等于 Work中對應的元素，即表示當前系統(tǒng)可用的資源數(shù)目可以滿足進程 i順利執(zhí)行完成叛氨。
如果找到這樣的進程則執(zhí)行步驟 3呼渣，否則執(zhí)行步驟 4.
-
經(jīng)過步驟 2的檢查可以確認進程 j可以順利執(zhí)行完成，當進程執(zhí)行完成后釋放資源（這里模擬進程執(zhí)行完成之后釋放資源的操作）
Work[j] = Work[j] + Allocation[i,j] Finish[i] = true轉向步驟 2寞埠。
如果所有進程的 Finish都是 false說明進程可以按照某個順序順利執(zhí)行完成屁置，即系統(tǒng)處于安全狀態(tài)；否則說明有一個或多個進程無法順利執(zhí)行完成仁连，即系統(tǒng)處于不安全的狀態(tài)蓝角。
在經(jīng)過足夠的執(zhí)行次數(shù)后，最后剩下的 Finish為 false的進程就是發(fā)生了死鎖的進程饭冬。
安全性算法是對進程執(zhí)行的一種簡單模擬使鹅，一個進程如果能夠順利執(zhí)行完，就會釋放所占有的資源昌抠，其他需要該進程所占有資源的進程最終也能獲得所需資源患朱。而如果一個或多個進程之間發(fā)生了死鎖，那它們最終無法執(zhí)行完成炊苫，即它們互相占有對方需要的資源裁厅，從而導致所有剩余進程都不能通過步驟 2中的檢查（Need[i]<=Work）。
