1 死鎖

??死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種互相等待的現(xiàn)象分瘾，若無(wú)外力作用疮蹦，這些進(jìn)程都將無(wú)法向前推進(jìn)。

2 死鎖撕阎、饑餓和死循環(huán)的區(qū)別

??饑餓：由于長(zhǎng)期得不到想要的資源而導(dǎo)致進(jìn)程無(wú)法向前推進(jìn)的現(xiàn)象缀皱。如在進(jìn)程調(diào)度算法中的短進(jìn)程優(yōu)先算法中斗这，若有源源不斷的短進(jìn)程到來(lái)，則長(zhǎng)進(jìn)程一直得不到處理機(jī)啤斗，從而發(fā)生了長(zhǎng)進(jìn)程饑餓表箭。
??死循環(huán)：某進(jìn)程執(zhí)行的過(guò)程中一直跳不出某種循環(huán)的現(xiàn)象。死循環(huán)可能是因?yàn)槌绦騜ug或者程序員有意為之钮莲。

3 死鎖產(chǎn)生的必要條件

??(1) 互斥條件盯桦。只有對(duì)必須互斥使用的資源爭(zhēng)搶?zhuān)ㄈ绱蛴C(jī)設(shè)備）才能導(dǎo)致死鎖。
??(2) 不剝奪條件渤刃。進(jìn)程所獲得的資源在未使用完之前拥峦，不能由其他進(jìn)程強(qiáng)行奪走，只能主動(dòng)釋放卖子。如果進(jìn)程可以搶奪其他進(jìn)程持有自己需要的資源的話(huà)略号，也就不會(huì)產(chǎn)生死鎖了，需要資源直接搶就行了洋闽。
??(3) 請(qǐng)求和保持條件玄柠。進(jìn)程已經(jīng)保持了至少一個(gè)資源，但是又提出了新的資源需求喊递，而該資源又被其他進(jìn)程占有随闪，此時(shí)請(qǐng)求進(jìn)程被阻塞，但是又對(duì)自己持有的資源保持不放骚勘。也是很簡(jiǎn)單的道理铐伴，如果一個(gè)進(jìn)程請(qǐng)求的資源被阻塞，就釋放了自己持有的資源俏讹，其他進(jìn)程就可以獲取它釋放的資源当宴，也就不會(huì)發(fā)生相互等待而導(dǎo)致死鎖了。
??(4) 循環(huán)等待條件泽疆。存在一種進(jìn)程資源的循環(huán)等待鏈户矢，鏈中的每一個(gè)進(jìn)程已經(jīng)獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求。

4 死鎖發(fā)生的時(shí)機(jī)

??(1) 對(duì)系統(tǒng)資源的爭(zhēng)搶殉疼。各進(jìn)程對(duì)不可剝奪資源的競(jìng)爭(zhēng)可能會(huì)引起死鎖梯浪。
??(2) 進(jìn)程推進(jìn)順序非法。如果請(qǐng)求資源的順序不當(dāng)也會(huì)導(dǎo)致死鎖瓢娜，如上面的圖挂洛，雙方請(qǐng)求的資源被對(duì)方占有而導(dǎo)致死鎖。
??(3) 信號(hào)量的使用不當(dāng)眠砾。并發(fā)執(zhí)行進(jìn)程時(shí)虏劲，如果信號(hào)量使用的順序不當(dāng)也會(huì)到導(dǎo)致死鎖。
??總之，對(duì)不可剝奪的資源的不合理分配柒巫，可能導(dǎo)致死鎖励堡。

5 死鎖處理策略

??(1) 預(yù)防死鎖。破壞死鎖產(chǎn)生的四個(gè)必要條件中的一個(gè)或幾個(gè)堡掏。
??(2) 避免死鎖应结。用某種方法防止系統(tǒng)進(jìn)入安全狀態(tài)，從而避免死鎖（銀行家算法）泉唁。
??(3) 死鎖的檢測(cè)和解除摊趾。允許死鎖的發(fā)生，不過(guò)操作系統(tǒng)會(huì)負(fù)責(zé)檢測(cè)出死鎖的發(fā)生游两，然后才去某種措施解除死鎖。

6 死鎖處理策略——預(yù)防死鎖

?? 6.1 破壞互斥條件

??如果把只能互斥使用的資源改造成允許共享使用漩绵，則系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)贱案。如SPOOLing技術(shù)。操作系統(tǒng)可以采用SPOOLing技術(shù)吧獨(dú)占設(shè)備在邏輯上改造成共享設(shè)備止吐。它由專(zhuān)門(mén)負(fù)責(zé) I/O 的常駐內(nèi)存進(jìn)程以及輸入宝踪、輸出井組成。比如碍扔，用SPOOLing技術(shù)將打印機(jī)改造為共享設(shè)備...

??缺點(diǎn)：并不是所有的資源都可以改造成共享使用的資源瘩燥。并且為了系統(tǒng)安全，有時(shí)候還需要保護(hù)這種互斥性不同。

?? 6.2 破壞不可剝奪性

??方案一：當(dāng)某個(gè)進(jìn)程請(qǐng)求新的資源得不到滿(mǎn)足時(shí)厉膀，它必須立即釋放保持的所有資源，待以后需要時(shí)重新申請(qǐng)二拐。
??方案二：申請(qǐng)的資源被其他進(jìn)程占用時(shí)服鹅，借助操作系統(tǒng)的協(xié)助，剝奪進(jìn)程資源百新，至于剝奪哪個(gè)進(jìn)程資源可以根據(jù)優(yōu)先級(jí)考慮企软。
??缺點(diǎn)：實(shí)現(xiàn)復(fù)雜。暫時(shí)請(qǐng)求不到某個(gè)資源饭望，之前獲取的資源就需要釋放仗哨，以后重新申請(qǐng)，如果一直這樣可能會(huì)導(dǎo)致饑餓铅辞。

?? 6.3 破壞請(qǐng)求和保持條件

??可以采用靜態(tài)分配方法厌漂，即進(jìn)程在運(yùn)行前一次申請(qǐng)完它所需要的全部資源，在它的資源未滿(mǎn)足之前巷挥，不讓它運(yùn)行桩卵。一旦運(yùn)行，這些資源在運(yùn)行期間一直歸它所有，該進(jìn)程就不會(huì)再請(qǐng)求別的任何資源雏节。
??缺點(diǎn)：如果有些資源只需要用很短的時(shí)間胜嗓，因此如果進(jìn)程運(yùn)行時(shí)間長(zhǎng)，在運(yùn)行期間都會(huì)保持持有所有資源钩乍，就會(huì)造成資源浪費(fèi)辞州，資源利用率低。此外寥粹，該策略可能導(dǎo)致某些進(jìn)程饑餓变过。如下，如果C類(lèi)進(jìn)程需要資源1和資源2涝涤，如果有大量的A或B類(lèi)進(jìn)程媚狰，就會(huì)導(dǎo)致C類(lèi)進(jìn)程一直不能一次獲取全部需要的資源，導(dǎo)致饑餓阔拳。

?? 6.4 破壞循環(huán)等待條件

??可采用順序資源分配法崭孤。首先給系統(tǒng)中的資源編號(hào)，規(guī)定每個(gè)進(jìn)程必須按編號(hào)遞增的順序請(qǐng)求資源糊肠，同類(lèi)資源一次申請(qǐng)完辨宠。
??原理：一個(gè)進(jìn)程只要已占有小編號(hào)的資源時(shí)，才有資格申請(qǐng)更大號(hào)編號(hào)的資源货裹。按照這樣的規(guī)則嗤形，已持有大編號(hào)的資源就不會(huì)逆向回來(lái)申請(qǐng)小編號(hào)的資源，從而就不會(huì)產(chǎn)生循環(huán)等待的現(xiàn)象弧圆。
??缺點(diǎn)：
??(1) 實(shí)現(xiàn)復(fù)雜赋兵。
??(2) 不方便增加新的設(shè)備，因?yàn)橐匦路峙渌芯幪?hào)墓阀。
??(3) 進(jìn)程實(shí)際使用資源的順序可能和資源編號(hào)遞增順序不一致毡惜，會(huì)導(dǎo)致資源浪費(fèi)。例如打印機(jī)設(shè)備編號(hào)2斯撮，輸出設(shè)備編號(hào)為1经伙，那么一個(gè)進(jìn)程請(qǐng)求打印機(jī)設(shè)備前，必須先請(qǐng)求輸出設(shè)備勿锅，而輸出設(shè)備在請(qǐng)求打印機(jī)設(shè)備這一段時(shí)間內(nèi)根本沒(méi)有發(fā)揮作用帕膜，其他進(jìn)程也不能訪(fǎng)問(wèn)，造成資源浪費(fèi)溢十。

7 死鎖處理策略——避免死鎖（銀行家算法）

??7.1 引入

??假如你是一個(gè)成功的銀行家垮刹，手里有100個(gè)小目標(biāo)資金....現(xiàn)在有三家公司A、B张弛、C分別向從你貸款

A 表示：大哥荒典，我最多會(huì)跟你借70億....
B 表示：大哥酪劫，我最多會(huì)跟你借40億....
C 表示：大哥，我最多會(huì)跟你借50億....

??然而寺董，有個(gè)規(guī)則覆糟，如果借給企業(yè)的錢(qián)達(dá)不到企業(yè)提出的最大需求，那么錢(qián)可能就一去不復(fù)返了.....
??剛開(kāi)始遮咖，三家公司分別從你這里借了20滩字、10、30億.......

??此時(shí)御吞，手里還要40億麦箍，此時(shí)B表示還要借20億，那么你需要考慮可以借嗎陶珠？
??如果給B借了20億.....此時(shí)手里還要有20億挟裂。

??之后看手里剩下的錢(qián)能不能周轉(zhuǎn)過(guò)來(lái)，現(xiàn)在可以將剩下的20億借給C揍诽，C就達(dá)到了最大需求话瞧，之后C還錢(qián)50億，然后借給A寝姿，A達(dá)到最大需求，最后A還70億划滋，最后A........還好借給B20億后饵筑，可以通過(guò)C->A->B這個(gè)順序周轉(zhuǎn)，所以這20億可以借处坪。
??現(xiàn)在看另一種情況根资，回到最初狀態(tài)，現(xiàn)在手里還有40億

?? 7.2 安全序列

??對(duì)于上面的第一種借給B20億是安全的，因?yàn)闀?huì)存在C->A->B這樣的周轉(zhuǎn)路徑（安全序列）呕童，不會(huì)血本無(wú)歸漆际。
??安全序列：如果系統(tǒng)按照這種序列分配資源，則每個(gè)進(jìn)程都能順利完成夺饲。只要能找出一個(gè)安全序列奸汇，系統(tǒng)就是安全的施符。一個(gè)系統(tǒng)的安全序列可能有多個(gè)。
??如果分配了資源之后擂找，系統(tǒng)中找不到任何一個(gè)安全序列戳吝，系統(tǒng)進(jìn)入了不安全狀態(tài)，這就意味著之后可能所有的進(jìn)程都無(wú)法順序執(zhí)行下去婴洼。當(dāng)然骨坑，如果有進(jìn)程提前歸還了一些資源（如對(duì)上面的第二中情況，如果B提前還10億柬采，那么就可以周轉(zhuǎn)了....）欢唾，那系統(tǒng)也可能重新回到安全狀態(tài)，不過(guò)在分配資源之前總是考慮最壞情況 粉捻。
??如果系統(tǒng)處于安全狀態(tài)礁遣，就一定不會(huì)發(fā)生死鎖。如果系統(tǒng)進(jìn)入了不安全狀態(tài)未必一定發(fā)生死鎖肩刃，但是發(fā)生了死鎖一定是在不安全狀態(tài)祟霍。

?? 7.3 銀行家算法

??銀行家算法核心思想：在進(jìn)程提出資源請(qǐng)求時(shí)，先預(yù)先判斷此次分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)盈包，如果進(jìn)入不安全狀態(tài)沸呐，就暫時(shí)不答應(yīng)這次請(qǐng)求，讓該進(jìn)程先阻塞呢燥。
??銀行家算法步驟：

(1) 檢查此次申請(qǐng)是否超過(guò)了之前聲明的最大需求數(shù)崭添。
(2) 檢查此時(shí)系統(tǒng)剩余的可用資源是否還能滿(mǎn)足這次請(qǐng)求。
(3) 試探分配叛氨，更改各數(shù)據(jù)結(jié)構(gòu)呼渣。
(4) 用安全性算法檢查此次分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)。
??安全性算法檢查步驟：
檢查當(dāng)前剩余可用資源是否能滿(mǎn)足某個(gè)進(jìn)程的最大需求寞埠，如果可以屁置，就把該進(jìn)程加入安全序列，并把該進(jìn)程的所有資源回收仁连。不斷重復(fù)這個(gè)過(guò)程蓝角，看最終是否能讓所有進(jìn)程都加入安全序列。

7 死鎖處理策略——檢測(cè)和解除

??如果系統(tǒng)中既不采取預(yù)防死鎖的措施饭冬，也不采取避免死鎖的措施帅容，系統(tǒng)就很可能發(fā)生死鎖。在這種情況下伍伤，系統(tǒng)應(yīng)當(dāng)提供兩個(gè)算法：
??(1) 死鎖檢測(cè)算法：用于檢測(cè)系統(tǒng)狀態(tài)并徘，以確定系統(tǒng)中是否發(fā)生了死鎖。
??(2) 死鎖解除算法：當(dāng)認(rèn)定系統(tǒng)中已經(jīng)發(fā)生了死鎖扰魂，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來(lái)麦乞。

??7.1 死鎖的檢測(cè)

??系統(tǒng)死鎖可利用資源分配圖來(lái)描述蕴茴。

注：(1) P1、P2表示進(jìn)程姐直；R1倦淀、R2表示資源，R1類(lèi)資源數(shù)為3声畏，R2類(lèi)資源數(shù)為2.
(2) 綠色箭頭表示分配給進(jìn)程的資源數(shù)撞叽，藍(lán)色箭頭表示進(jìn)程向資源節(jié)點(diǎn)請(qǐng)求的資源數(shù)。

??上圖可以看到插龄，R1類(lèi)資源的資源數(shù)已經(jīng)全部分配完了愿棋，R2類(lèi)資源還有一個(gè)資源。P1進(jìn)程向R2類(lèi)資源請(qǐng)求一個(gè)資源均牢，P2進(jìn)程向R1類(lèi)資源請(qǐng)求一個(gè)資源糠雨。
??如果系統(tǒng)中剩余可用的資源數(shù)足夠滿(mǎn)足進(jìn)程的需求，那么這個(gè)進(jìn)程暫時(shí)是不會(huì)阻塞的徘跪，可以順利的執(zhí)行下去甘邀。如果這個(gè)進(jìn)程執(zhí)行結(jié)束了把資源歸還給系統(tǒng)，就可能使某些正在等待的資源的進(jìn)程重新被激活垮庐，并順利的執(zhí)行下去松邪。相應(yīng)的，這些被激活的進(jìn)程執(zhí)行完后又會(huì)歸還一些資源哨查，這樣可能又會(huì)激活另外一些阻塞的進(jìn)程...

??按照上面的過(guò)程分析测摔，最終能消除所有邊，就稱(chēng)這個(gè)圖是可完全簡(jiǎn)化的解恰。此時(shí)一定沒(méi)有發(fā)生死鎖（相當(dāng)于找到一個(gè)安全序列）。如果最終不能消除所有邊浙于，那么此時(shí)就是發(fā)生死鎖了护盈。
??最終還連著邊的進(jìn)程就是處于死鎖狀態(tài)的進(jìn)程。
??檢測(cè)死鎖的算法：

(1) 在資源分配圖中羞酗，找到既不阻塞又不是孤點(diǎn)的進(jìn)程Pi（即找出一條有向邊與它相連腐宋，且該有向邊對(duì)應(yīng)點(diǎn)額資源申請(qǐng)樹(shù)齡小于等于系統(tǒng)中已有空閑資源數(shù)量。如下圖中檀轨，R1沒(méi)有空閑資源胸竞，R2有一個(gè)空閑資源，P1進(jìn)程請(qǐng)求一個(gè)R2資源参萄，滿(mǎn)足繼續(xù)運(yùn)行的條件卫枝，而P2請(qǐng)求一個(gè)R1資源，此時(shí)R1沒(méi)有資源讹挎，所以P2此刻不滿(mǎn)足運(yùn)行條件）校赤。消去所有的請(qǐng)求邊和資源分配邊吆玖，使之成為孤立的節(jié)點(diǎn)。下圖中P1進(jìn)程是滿(mǎn)足繼續(xù)運(yùn)行的節(jié)點(diǎn)马篮，故將P1消去沾乘。
(2) 進(jìn)程Pi所釋放的資源，可以喚醒某些因等待這些資源的進(jìn)程浑测，原來(lái)阻塞的進(jìn)程可能變成非阻塞進(jìn)程翅阵。由于P1釋放了R1資源，所以P2又滿(mǎn)足了運(yùn)行的條件迁央，可以將P2的邊都消去掷匠，最終消去了所有邊，所以原圖是可完全簡(jiǎn)化的漱贱。

??死鎖定理：如果某時(shí)刻系統(tǒng)的資源分配圖是不可完全簡(jiǎn)化的槐雾，那么此時(shí)系統(tǒng)死鎖。
??下圖是一個(gè)系統(tǒng)死鎖的圖：

??即使P3釋放了資源幅狮，P1和P2進(jìn)程都不滿(mǎn)足繼續(xù)運(yùn)行的條件仰泻，所以此時(shí)P1和P2就是死鎖進(jìn)程。

??7.2 死鎖的解除

??解除死鎖的方法有：
??(1) 資源剝奪法一屋。掛起（暫時(shí)放在外存上）某些死鎖進(jìn)程辈赋，并搶占它的資源，將這些資源分配給其他進(jìn)程逐抑，但是應(yīng)防止被掛起長(zhǎng)時(shí)間導(dǎo)致饑餓鸠儿。
??(2) 撤銷(xiāo)進(jìn)程法。強(qiáng)制撤銷(xiāo)部分厕氨、甚至全部死鎖進(jìn)程进每，并剝奪這些進(jìn)程的資源。這中方法實(shí)現(xiàn)簡(jiǎn)單命斧，但是也是有代價(jià)的田晚，如果有些已經(jīng)運(yùn)行了很長(zhǎng)時(shí)間了，離成功只有一步之遙了国葬，此時(shí)撤銷(xiāo)導(dǎo)致功虧一簣贤徒，還需要從頭再來(lái)....
??(3) 進(jìn)程回退法。讓一個(gè)或多個(gè)死鎖進(jìn)程回退到足以避免死鎖的地步汇四。這就要求系統(tǒng)要記錄進(jìn)程的歷史信息接奈，設(shè)置還原點(diǎn)。

??那么對(duì)哪些進(jìn)程動(dòng)手呢通孽？可以考慮優(yōu)先對(duì)以下的進(jìn)程處理：
??(1) 優(yōu)先級(jí)低的進(jìn)程序宦。
??(2) 執(zhí)行時(shí)間段的進(jìn)程。
??(3) 距離運(yùn)行結(jié)束剩余時(shí)間長(zhǎng)的進(jìn)程背苦。
??(4) 使用資源多的進(jìn)程挨厚。
??(5) 批處理式而不是交互式的進(jìn)程堡僻。

8小結(jié) 死鎖處理策略

本文完