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

小強(qiáng)實(shí)驗(yàn)室

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

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

該策略的缺點(diǎn)：
①、不方便增加新的設(shè)備，因?yàn)榭赡苄枰匦路峙渌械木幪?hào)；
②、進(jìn)程實(shí)際使用資源的順序可能和編號(hào)遞增順序不一致，會(huì)導(dǎo)致資源浪費(fèi)；
③、必須按規(guī)定次序申請(qǐng)資源，用戶編程麻煩。

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

登錄/注冊(cè)后可看大圖

內(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ū)動(dòng)/網(wǎng)絡(luò)協(xié)議棧
二、避免死鎖

登錄/注冊(cè)后可看大圖

（一）什么是安全序列

登錄/注冊(cè)后可看大圖

登錄/注冊(cè)后可看大圖

登錄/注冊(cè)后可看大圖

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

1.實(shí)現(xiàn)步驟

登錄/注冊(cè)后可看大圖

登錄/注冊(cè)后可看大圖

登錄/注冊(cè)后可看大圖

以此類推，共五次循環(huán)檢查即可將5個(gè)進(jìn)程都加入安全序列中，最終可得一個(gè)安全序列。該算法稱為安全性算法?？梢院芊奖愕赜么a實(shí)現(xiàn)以上流程，每一輪檢查都從編號(hào)較小的進(jìn)程開(kāi)始檢查。實(shí)際做題時(shí)可以更快速的得到安全序列。
2.銀行家算法示例（手算）
手算（找到安全系列）

登錄/注冊(cè)后可看大圖

手算（找不到安全系列）

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

如果系統(tǒng)中剩余的可用資源數(shù)足夠滿足進(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)程…

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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

登錄/注冊(cè)后可看大圖

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