愛鋒貝

標(biāo)題: Linux內(nèi)核：進程管理——死鎖檢測與解決 [打印本頁]
作者: 小強實驗室    時間: 2023-4-8 07:16
標(biāo)題: Linux內(nèi)核：進程管理——死鎖檢測與解決
【推薦閱讀】
Linux文件系統(tǒng)詳解
linux進程管理---實時調(diào)度
linux內(nèi)核內(nèi)存管理-缺頁異常
linux內(nèi)核內(nèi)存管理-brk系統(tǒng)調(diào)用
一、預(yù)防死鎖

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

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

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

(, 下載次數(shù): 108)
該策略的缺點：
①、不方便增加新的設(shè)備，因為可能需要重新分配所有的編號；
②、進程實際使用資源的順序可能和編號遞增順序不一致，會導(dǎo)致資源浪費；
③、必須按規(guī)定次序申請資源，用戶編程麻煩。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群：【977878001】整理一些個人覺得比較好得學(xué)習(xí)書籍、視頻資料！進群私聊管理領(lǐng)取內(nèi)核資料包（含視頻教程、電子書、實戰(zhàn)項目及代碼）

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


(, 下載次數(shù): 100)
（一）什么是安全序列

(, 下載次數(shù): 95)

(, 下載次數(shù): 91)

(, 下載次數(shù): 118)

(, 下載次數(shù): 97)
（二）安全序列、不安全狀態(tài)、死鎖的聯(lián)系

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

(, 下載次數(shù): 90)
1.實現(xiàn)步驟

(, 下載次數(shù): 106)

(, 下載次數(shù): 98)

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

(, 下載次數(shù): 83)
手算（找不到安全系列）

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

(, 下載次數(shù): 85)

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


(, 下載次數(shù): 92)
如果系統(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ā)生了死鎖進行檢測，必須：
①用某種數(shù)據(jù)結(jié)構(gòu)來保存資源的請求和分配信息；
②提供一種算法，利用上述信息來檢測系統(tǒng)是否已進入死鎖狀態(tài)。

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

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

(, 下載次數(shù): 103)
如果最終不能消除所有邊，那么此時就是發(fā)生了死鎖
最終還連著邊的那些進程就是處于死鎖狀態(tài)的進程。

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

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

(, 下載次數(shù): 111)

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



歡迎光臨 愛鋒貝 (http://7gfy2te7.cn/) Powered by Discuz! X3.4