本文章將主要解釋死鎖的消除方法

一、死鎖的概念

? ? ? ? 這是《操作系統(tǒng)》對(duì)于死鎖的定義：

有并發(fā)進(jìn)程P1,P2,…Pn，它們共享資源R1,R2,…Rm (n>0,m>0, n>=m)。其中，每個(gè)Pi(1≤i≤n)擁有資源Rj(1≤j ≤m)，直到不再有剩余資源。同時(shí)，各Pi又在不釋放Rj的前提下要求Rk(k≠j,1≤k ≤m)，從而造成資源的互相占有和互相等待。在沒有外力驅(qū)動(dòng)的情況下，該組并發(fā)進(jìn)程停止往前推進(jìn)，陷入永久等待狀態(tài)。

? ? ? ? 說人話就是，我自己的資源不給別人，別人的資源不給我，導(dǎo)致兩個(gè)人都因?yàn)闇惒积R資源而不能執(zhí)行相關(guān)操作而一直等待，這就是死鎖。結(jié)構(gòu)圖如下所示：

?二、死鎖產(chǎn)生的必要條件

? ? ? ? 如果產(chǎn)生死鎖則一定會(huì)滿足以下條件：

1、互斥條件。一個(gè)資源不能同時(shí)被兩個(gè)或兩個(gè)以上的進(jìn)程所擁有。

2、不剝奪條件。一個(gè)進(jìn)程未結(jié)束前，任何進(jìn)程都不能得到該進(jìn)程的資源。

3、部分分配。進(jìn)程每次申請(qǐng)所需要的一部分資源，在等待申請(qǐng)其他資源的時(shí)間里，不會(huì)釋放它已經(jīng)擁有的資源。

4、環(huán)路條件。如下圖所示：

而只要上述的條件被破壞就不會(huì)產(chǎn)生死鎖，這就是我們解決死鎖問題的思路。

三、死鎖的消除方法

1、死鎖預(yù)防

? ? ? ? 死鎖預(yù)防是一種靜態(tài)的消除死鎖的方法。它是采用某種策略，限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時(shí)間都不滿足。

方法：

①、互斥條件是資源固有屬性，不能避免

②、破壞“部分分配（請(qǐng)求和保持）”條件。預(yù)先全分配，等待釋放。缺點(diǎn)：資源嚴(yán)重浪費(fèi)（不使用也被占用）、降低進(jìn)程并發(fā)性

③、破壞“不剝奪”條件。缺點(diǎn)：增加系統(tǒng)開銷，且進(jìn)程前段工作可能失效。

④、破壞“環(huán)路等待”條件。將資源分類并按順利排列，規(guī)定按遞增順序請(qǐng)求資源；如果需要多個(gè)資源，必須同時(shí)請(qǐng)求（先低后高），如果占用了高的資源而請(qǐng)求低的資源時(shí)，必須先釋放高的資源。如此可以避免形成環(huán)路。缺點(diǎn)：限制進(jìn)程對(duì)資源的請(qǐng)求，系統(tǒng)開銷大。具體操作如下圖所示，P3占有s3資源，當(dāng)它想申請(qǐng)s2資源時(shí)必須釋放s3資源。

2、死鎖避免

? ? ? ? 死鎖避免可被稱為動(dòng)態(tài)預(yù)防，因?yàn)橄到y(tǒng)采用動(dòng)態(tài)分配資源，在分配過程中預(yù)測(cè)出死鎖發(fā)生的可能性并加以避免的方法。?

方法：

• 進(jìn)程啟動(dòng)拒絕：如果進(jìn)程對(duì)資源的申請(qǐng)可能導(dǎo)致死鎖，就不啟動(dòng)這個(gè)進(jìn)程
• 資源分配拒絕：如果進(jìn)程對(duì)資源的申請(qǐng)可能導(dǎo)致死鎖，就不給進(jìn)程分配該資源?

詳解：

進(jìn)程啟動(dòng)拒絕

該表說明表達(dá)的意思如下：

(j=1…m)

由公式知道，只有當(dāng)申請(qǐng)的資源小于剩余的資源，就會(huì)分配給進(jìn)程資源，否則就不分配進(jìn)程資源。

? ? ? ?僅當(dāng)滿足以上條件時(shí)，才啟動(dòng)一個(gè)新進(jìn)程Pn+1（即：只有滿足新進(jìn)程的請(qǐng)求及所有當(dāng)前進(jìn)程的最大請(qǐng)求量時(shí)，才啟動(dòng)該進(jìn)程） 這個(gè)策略不是最優(yōu)的，因?yàn)樗僭O(shè)了最壞的情況：所有進(jìn)程同時(shí)發(fā)出它們的最大請(qǐng)求

資源分配拒絕

避免死鎖的著名算法——銀行家算法（Dijkstra）

類比的問題：

客戶向銀行申請(qǐng)貸款的數(shù)量是有限的 每個(gè)客戶在第一次申請(qǐng)貸款時(shí)要聲明完成該項(xiàng)目所需的最大資金量 在滿足所有貸款要求時(shí)，客戶應(yīng)及時(shí)歸還貸款 銀行家在客戶申請(qǐng)的貸款數(shù)量不超過自己擁有的最大值時(shí)，都應(yīng)盡量滿足客戶的需要

例子：

設(shè)銀行家有10萬元資金，有三個(gè)客戶A、B、C，分別需要8、3、9萬元貸款完成項(xiàng)目 客戶要求分期貸款，目前A已貸到4萬 此時(shí)，B要申請(qǐng)2萬，C要申請(qǐng)4萬 銀行家需要評(píng)估貸款請(qǐng)求的安全性，避免出現(xiàn)壞賬 ? ?B借2萬，C借4萬，能借嗎？在這個(gè)例子中銀行家是操作系統(tǒng)， 資金是資源 ，客戶是要申請(qǐng)資源的進(jìn)程。

允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源，在系統(tǒng)分配資源之前，先計(jì)算此次分配是否安全

? ? 本次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配， 否則，本次請(qǐng)求資源的進(jìn)程等待

安全狀態(tài)

? ? 本次分配之后，存在一個(gè)進(jìn)程安全序列{P1, …, Pn}，對(duì)其中每一個(gè)Pi來說，它還需要的資源量不超過系統(tǒng)當(dāng)前剩余的資源量與所有Pj (j<i)占有的資源量之和

不安全狀態(tài)

? ? 不存在安全序列

算法中用到的數(shù)據(jù)結(jié)構(gòu)

?Available可用資源數(shù)組

? ? Available[j] = k ?? ?目前資源j有k個(gè)

Max最大需求矩陣

? ? Max[i,j] = l?? ??? ?進(jìn)程Pi對(duì)資源j的最大需求數(shù)量是l個(gè)

Allocation分配矩陣??

? ? Allocation[i, j] = m ?? ?進(jìn)程Pi已分配到資源j的數(shù)量是m個(gè)

Need需求矩陣

? ? Need[i, j] = n ?? ?進(jìn)程Pi還需要資源j的數(shù)量是n個(gè)

Request[i]資源請(qǐng)求

? ? 若Request[i, j] = q， 進(jìn)程Pi請(qǐng)求資源j的數(shù)量是q個(gè)

流程圖如下：

分配資源流程圖

?文章來源地址http://www.zghlxwxcb.cn/news/detail-555509.html

釋放資源流程圖：

Work：系統(tǒng)運(yùn)行過程中可用資源數(shù)量，初值=Available

Finish[i]：系統(tǒng)是否有足夠資源分配給進(jìn)程Pi，使其運(yùn)行結(jié)束，初始為false

?

到了這里，關(guān)于【操作系統(tǒng)】死鎖問題---死鎖的消除方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！