Linux內(nèi)核：進(jìn)程管理——死鎖檢測與解決

小強(qiáng)實驗室

【推薦閱讀】
Linux文件系統(tǒng)詳解
linux進(jìn)程管理---實時調(diào)度
linux內(nèi)核內(nèi)存管理-缺頁異常
linux內(nèi)核內(nèi)存管理-brk系統(tǒng)調(diào)用
一、預(yù)防死鎖

（一）破壞互斥條件
互斥條件：只有對必須互斥使用的資源的爭搶才會導(dǎo)致死鎖。
如果把只能互斥使用的資源改造為允許共享使用，則系統(tǒng)不會進(jìn)入死鎖狀態(tài)。比如: SPOOLing技術(shù)。操作系統(tǒng)可以采用 SPOOLing 技術(shù)把獨(dú)占設(shè)備在邏輯上改造成共享設(shè)備。比如，用SPOOLing技術(shù)將打印機(jī)改造為共享設(shè)備…

登錄/注冊后可看大圖

該策略的缺點(diǎn)：并不是所有的資源都可以改造成可共享使用的資源。并且為了系統(tǒng)安全，很多地方還必須保護(hù)這種互斥性。因此，很多時候都無法破壞互斥條件。
（二）破壞不剝奪條件
不剝奪條件：進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動釋放。
破壞不剝奪條件：
①、方案一：當(dāng)某個進(jìn)程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件。
②、方案二：當(dāng)某個進(jìn)程需要的資源被其他進(jìn)程所占有的時候，可以由操作系統(tǒng)協(xié)助，將想要的資源強(qiáng)行剝奪。這種方式一般需要考慮各進(jìn)程的優(yōu)先級（比如：剝奪調(diào)度方式，就是將處理機(jī)資源強(qiáng)行剝奪給優(yōu)先級更高的進(jìn)程使用）
該策略的缺點(diǎn)：
①、實現(xiàn)起來比較復(fù)雜。
②、釋放已獲得的資源可能造成前一階段工作的失效。因此這種方法一般只適用于易保存和恢復(fù)狀態(tài)的資源，如CPU。
③、反復(fù)地申請和釋放資源會增加系統(tǒng)開銷，降低系統(tǒng)吞吐量。
④、若采用方案一，意味著只要暫時得不到某個資源，之前獲得的那些資源就都需要放棄，以后再重新申請。如果一直發(fā)生這樣的情況，就會導(dǎo)致進(jìn)程饑餓。
（三）破壞請求和保持條件
請求和保持條件：進(jìn)程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進(jìn)程占有，此時請求進(jìn)程被阻塞，但又對自己已有的資源保持不放。
可以采用靜態(tài)分配方法，即進(jìn)程在運(yùn)行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運(yùn)行。一旦投入運(yùn)行后，這些資源就一直歸它所有，該進(jìn)程就不會再請求別的任何資源了。
該策略實現(xiàn)起來簡單，但也有明顯的缺點(diǎn)：
有些資源可能只需要用很短的時間，因此如果進(jìn)程的整個運(yùn)行期間都一直保持著所有資源，就會造成嚴(yán)重的資源浪費(fèi)，資源利用率極低。另外，該策略也有可能導(dǎo)致某些進(jìn)程饑餓。

登錄/注冊后可看大圖

（四）破壞循環(huán)等待條件
循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個進(jìn)程已獲得的資源同時被下一個進(jìn)程所請求。
可采用順序資源分配法。首先給系統(tǒng)中的資源編號，規(guī)定每個進(jìn)程必須按編號遞增的順序請求資源，同類資源（即編號相同的資源）一次申請完。
原理分析：一個進(jìn)程只有已占有小編號的資源時，才有資格申請更大編號的資源。按此規(guī)則，已持有大編號資源的進(jìn)程不可能逆向地回來申請小編號的資源，從而就不會產(chǎn)生循環(huán)等待的現(xiàn)象。

登錄/注冊后可看大圖

該策略的缺點(diǎn)：
①、不方便增加新的設(shè)備，因為可能需要重新分配所有的編號；
②、進(jìn)程實際使用資源的順序可能和編號遞增順序不一致，會導(dǎo)致資源浪費(fèi)；
③、必須按規(guī)定次序申請資源，用戶編程麻煩。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群：【977878001】整理一些個人覺得比較好得學(xué)習(xí)書籍、視頻資料！進(jìn)群私聊管理領(lǐng)取內(nèi)核資料包（含視頻教程、電子書、實戰(zhàn)項目及代碼）

登錄/注冊后可看大圖

內(nèi)核資料直通車：Linux內(nèi)核源碼技術(shù)學(xué)習(xí)路線+視頻教程代碼資料
學(xué)習(xí)直通車：Linux內(nèi)核源碼/內(nèi)存調(diào)優(yōu)/文件系統(tǒng)/進(jìn)程管理/設(shè)備驅(qū)動/網(wǎng)絡(luò)協(xié)議棧
二、避免死鎖

登錄/注冊后可看大圖

（一）什么是安全序列

登錄/注冊后可看大圖

登錄/注冊后可看大圖

登錄/注冊后可看大圖

登錄/注冊后可看大圖

（二）安全序列、不安全狀態(tài)、死鎖的聯(lián)系

登錄/注冊后可看大圖

所謂安全序列，就是指如果系統(tǒng)按照這種序列分配資源，則每個進(jìn)程都能順利完成。只要能找出一個安全序列，系統(tǒng)就是安全狀態(tài)。當(dāng)然，安全序列可能有多個。
如果分配了資源之后，系統(tǒng)中找不出任何一個安全序列，系統(tǒng)就進(jìn)入了不安全狀態(tài)。這就意味著之后可能所有進(jìn)程都無法順利的執(zhí)行下去。當(dāng)然，如果有進(jìn)程提前歸還了一些資源，那系統(tǒng)也有可能重新回到安全狀態(tài)，不過我們在分配資源之前總是要考慮到最壞的情況?！颈热鏏 先歸還了10億，那么就有安全序列T→B → A】
如果系統(tǒng)處于安全狀態(tài)，就一定不會發(fā)生死鎖。如果系統(tǒng)進(jìn)入不安全狀態(tài)，就可能發(fā)生死鎖（處于不安全狀態(tài)未必就是發(fā)生了死鎖，但發(fā)生死鎖時一定是在不安全狀態(tài)）
因此可以在資源分配之前預(yù)先判斷這次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，以此決定是否答應(yīng)資源分配請求。這也是“銀行家算法”的核心思想。
（三）銀行家算法
銀行家算法是荷蘭學(xué)者 Dijkstra 為銀行系統(tǒng)設(shè)計的，以確保銀行在發(fā)放現(xiàn)金貸款時，不會發(fā)生不能滿足所有客戶需要的情況。后來該算法被用在操作系統(tǒng)中，用于避免死鎖。
核心思想：在進(jìn)程提出資源申請時，先預(yù)判此次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)。如果會進(jìn)入不安全狀態(tài)，就暫時不答應(yīng)這次請求，讓該進(jìn)程先阻塞等待。

登錄/注冊后可看大圖

1.實現(xiàn)步驟

登錄/注冊后可看大圖

登錄/注冊后可看大圖

登錄/注冊后可看大圖

以此類推，共五次循環(huán)檢查即可將5個進(jìn)程都加入安全序列中，最終可得一個安全序列。該算法稱為安全性算法。可以很方便地用代碼實現(xiàn)以上流程，每一輪檢查都從編號較小的進(jìn)程開始檢查。實際做題時可以更快速的得到安全序列。
2.銀行家算法示例（手算）
手算（找到安全系列）

登錄/注冊后可看大圖

手算（找不到安全系列）

登錄/注冊后可看大圖

3.代碼實現(xiàn)
假設(shè)系統(tǒng)中有 n 個進(jìn)程，m 種資源
每個進(jìn)程在運(yùn)行前先聲明對各種資源的最大需求數(shù)，則可用一個 nm 的矩陣（可用二維數(shù)組實現(xiàn)）表示所有進(jìn)程對各種資源的最大需求數(shù)。不妨稱為最大需求矩陣 Max，Max[i, j]=K 表示進(jìn)程 Pi 最多需要 K 個資源Rj。同理，系統(tǒng)可以用一個 nm 的分配矩陣 Allocation表示對所有進(jìn)程的資源分配情況。Max – Allocation =Need 矩陣，表示各進(jìn)程最多還需要多少各類資源。
另外，還要用一個長度為m的一維數(shù)組 Available 表示當(dāng)前系統(tǒng)中還有多少可用資源。
某進(jìn)程Pi向系統(tǒng)申請資源，可用一個長度為m的一維數(shù)組 Requesti表示本次申請的各種資源量。

登錄/注冊后可看大圖

登錄/注冊后可看大圖

數(shù)據(jù)結(jié)構(gòu)：
①、長度為 m 的一維數(shù)組 Available 表示還有多少可用資源
②、n*m 矩陣 Max 表示各進(jìn)程對資源的最大需求數(shù)
③、n*m 矩陣 Allocation 表示已經(jīng)給各進(jìn)程分配了多少資源
④、Max – Allocation = Need 矩陣表示各進(jìn)程最多還需要多少資源
⑤、用長度為 m 的一位數(shù)組 Request 表示進(jìn)程此次申請的各種資源數(shù)
銀行家算法步驟：
①、檢查此次申請是否超過了之前聲明的最大需求數(shù)
②、檢查此時系統(tǒng)剩余的可用資源是否還能滿足這次請求
③、試探著分配，更改各數(shù)據(jù)結(jié)構(gòu)
④、用安全性算法檢查此次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)
安全性算法步驟：
①、檢查當(dāng)前的剩余可用資源是否能滿足某個進(jìn)程的最大需求，如果可以，就把該進(jìn)程加入安全序列，并把該進(jìn)程持有的資源全部回收。
②、不斷重復(fù)上述過程，看最終是否能讓所有進(jìn)程都加入安全序列。
系統(tǒng)處于不安全狀態(tài)未必死鎖，但死鎖時一定處于不安全狀態(tài)。系統(tǒng)處于安全狀態(tài)一定不會死鎖。
三、死鎖的處理策略——檢測和解除

登錄/注冊后可看大圖

如果系統(tǒng)中既不采取預(yù)防死鎖的措施，也不采取避免死鎖的措施，系統(tǒng)就很可能發(fā)生死鎖。在這種情況下，系統(tǒng)應(yīng)當(dāng)提供兩個算法：
①死鎖檢測算法：用于檢測系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。
②死鎖解除算法：當(dāng)認(rèn)定系統(tǒng)中已經(jīng)發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來。
（一）死鎖的檢測
為了能對系統(tǒng)是否已發(fā)生了死鎖進(jìn)行檢測，必須：
①用某種數(shù)據(jù)結(jié)構(gòu)來保存資源的請求和分配信息；
②提供一種算法，利用上述信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。

登錄/注冊后可看大圖

如果系統(tǒng)中剩余的可用資源數(shù)足夠滿足進(jìn)程的需求，那么這個進(jìn)程暫時是不會阻塞的，可以順利地執(zhí)行下去。
如果這個進(jìn)程執(zhí)行結(jié)束了把資源歸還系統(tǒng)，就可能使某些正在等待資源的進(jìn)程被激活，并順利地執(zhí)行下去。相應(yīng)的，這些被激活的進(jìn)程執(zhí)行完了之后又會歸還一些資源，這樣可能又會激活另外一些阻塞的進(jìn)程…

登錄/注冊后可看大圖

如果按上述過程分析，最終能消除所有邊，就稱這個圖是可完全簡化的。此時一定沒有發(fā)生死鎖（相當(dāng)于能找到一個安全序列）

登錄/注冊后可看大圖

如果最終不能消除所有邊，那么此時就是發(fā)生了死鎖
最終還連著邊的那些進(jìn)程就是處于死鎖狀態(tài)的進(jìn)程。

登錄/注冊后可看大圖

（二）死鎖的解除
一旦檢測出死鎖的發(fā)生，就應(yīng)該立即解除死鎖。
補(bǔ)充：并不是系統(tǒng)中所有的進(jìn)程都是死鎖狀態(tài)，用死鎖檢測算法化簡資源分配圖后，還連著邊的那些進(jìn)程就是死鎖進(jìn)程
解除死鎖的主要方法有：
①、 資源剝奪法 。掛起（暫時放到外存上）某些死鎖進(jìn)程，并搶占它的資源，將這些資源分配給其他的死鎖進(jìn)程。但是應(yīng)防止被掛起的進(jìn)程長時間得不到資源而饑餓。
②、 撤銷進(jìn)程法（或稱終止進(jìn)程法） 。強(qiáng)制撤銷部分、甚至全部死鎖進(jìn)程，并剝奪這些進(jìn)程的資源。這種方式的優(yōu)點(diǎn)是實現(xiàn)簡單，但所付出的代價可能會很大。因為有些進(jìn)程可能已經(jīng)運(yùn)行了很長時間，已經(jīng)接近結(jié)束了，一旦被終止可謂功虧一簣，以后還得從頭再來。
③、 進(jìn)程回退法 。讓一個或多個死鎖進(jìn)程回退到足以避免死鎖的地步。這就要求系統(tǒng)要記錄進(jìn)程的歷史信息，設(shè)置還原點(diǎn)。

登錄/注冊后可看大圖

原文作者：首頁 - 內(nèi)核技術(shù)中文網(wǎng) - 構(gòu)建全國最權(quán)威的內(nèi)核技術(shù)交流分享論壇
原文地址：Linux內(nèi)核：進(jìn)程管理--死鎖檢測與解決 - 圈點(diǎn) - 內(nèi)核技術(shù)中文網(wǎng) - 構(gòu)建全國最權(quán)威的內(nèi)核技術(shù)交流分享論壇（版權(quán)歸原文作者所有，侵權(quán)留言聯(lián)系刪除）

登錄/注冊后可看大圖

-----------------------------