操作系統(tǒng)-ch3-3.6死鎖課件

3.6死鎖3.6.1死鎖的產(chǎn)生3.6.2死鎖的定義3.6.3死鎖的防止3.6.4死鎖的避免3.6.5死鎖的檢測(cè)和解除

若干死鎖的例子(1)

例１進(jìn)程推進(jìn)順序不當(dāng)產(chǎn)生死鎖

設(shè)系統(tǒng)有打印機(jī)、讀卡機(jī)各一臺(tái)，被進(jìn)程Ｐ和Ｑ共享。兩個(gè)進(jìn)程并發(fā)執(zhí)行，按下列次序請(qǐng)求和釋放資源：進(jìn)程Ｐ進(jìn)程Ｑ請(qǐng)求讀卡機(jī)請(qǐng)求打印機(jī)請(qǐng)求打印機(jī) 請(qǐng)求讀卡機(jī)釋放讀卡機(jī) 釋放讀卡機(jī)釋放打印機(jī) 釋放打印機(jī)

若干死鎖的例子(2)

例２PV操作使用不當(dāng)產(chǎn)生死鎖

進(jìn)程Q1 進(jìn)程Q2 ………

………P(S1);P(s2);P(s2);P(s1);

使用r1和r2;使用r1和r2V(S1); V(s2);V(S2); V(S1);

若干死鎖的例子(3)

例３資源分配不當(dāng)引起死鎖

若系統(tǒng)中有m個(gè)資源被n個(gè)進(jìn)程共享，每個(gè)進(jìn)程都要求Ｋ個(gè)資源，而m<n·K時(shí)，即資源數(shù)小于進(jìn)程所要求的總數(shù)時(shí)，如果分配不得當(dāng)就可能引起死鎖。

若干死鎖的例子(4)

例４對(duì)臨時(shí)性資源使用不加限制引起死鎖

進(jìn)程通信使用的信件是一種臨時(shí)性資源，如果對(duì)信件的發(fā)送和接收不加限制，可能引起死鎖。進(jìn)程P1等待進(jìn)程P3的信件S3來到后再向進(jìn)程P2發(fā)送信件S1；P2又要等待P1的信件S1來到后再向P3發(fā)送信件S2；而P3也要等待P2的信件S2來到后才能發(fā)出信件S3。這種情況下形成了循環(huán)等待，產(chǎn)生死鎖。3.6.2死鎖的定義操作系統(tǒng)中的死鎖指：如果在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只能由該集合中的其他一個(gè)進(jìn)程才能引發(fā)的事件，則稱一組進(jìn)程或系統(tǒng)此時(shí)發(fā)生了死鎖。例如，n個(gè)進(jìn)程P1、P2，…，Pn，Pi因?yàn)樯暾?qǐng)不到資源Rj而處于等待狀態(tài)，而Rj又被Pi+1占有，Pn欲申請(qǐng)的資源被P1占有，此時(shí)這n個(gè)進(jìn)程的等待狀態(tài)永遠(yuǎn)不能結(jié)束，則說這n個(gè)進(jìn)程處于死鎖狀態(tài)。

產(chǎn)生死鎖的因素不僅與系統(tǒng)擁有的資源數(shù)量有關(guān)，而且與資源分配策略，進(jìn)程對(duì)資源的使用要求以及并發(fā)進(jìn)程的推進(jìn)順序有關(guān)。3.6.1死鎖的產(chǎn)生和定義

操作系統(tǒng)中的死鎖基于如下假定：任意一個(gè)進(jìn)程要求資源的最大數(shù)量不超過系統(tǒng)能提供的最大量如果一個(gè)進(jìn)程在執(zhí)行中提出的資源要求能夠得到滿足，那么它一定能在有限時(shí)間內(nèi)結(jié)束一個(gè)資源在任何時(shí)刻最多只為一個(gè)進(jìn)程所占有一個(gè)進(jìn)程申請(qǐng)資源，只在資源得不到滿足時(shí)才處于等待狀態(tài)一個(gè)進(jìn)程結(jié)束時(shí)釋放它所占有的全部資源系統(tǒng)具有有限個(gè)進(jìn)程和資源3.6.3死鎖防止(1)

形成死鎖的四個(gè)必要條件互斥條件：進(jìn)程互斥使用資源部分分配條件：申請(qǐng)新資源時(shí)不釋放已占有資源不剝奪條件：一個(gè)進(jìn)程不能搶奪其他進(jìn)程占有的資源環(huán)路條件：存在一組進(jìn)程循環(huán)等待資源的死鎖防止(2)

靜態(tài)分配策略（破壞條件2）

靜態(tài)分配是指一個(gè)進(jìn)程必須在執(zhí)行前就申請(qǐng)它所要的全部資源，并且直到它所要的資源都得到滿足后才開始執(zhí)行。死鎖的防止(3)

層次分配策略（破壞條件2和4）

資源被分成多個(gè)層次當(dāng)進(jìn)程得到某一層的一個(gè)資源后，它只能再申請(qǐng)較高層次的資源當(dāng)進(jìn)程要釋放某層的一個(gè)資源時(shí)，必須先釋放占有的較高層次的資源當(dāng)進(jìn)程得到某一層的一個(gè)資源后，它想申請(qǐng)?jiān)搶拥牧硪粋€(gè)資源時(shí)，必須先釋放該層中的已占資源死鎖防止(4)

層次策略的變種按序分配策略把系統(tǒng)的所有資源排一個(gè)順序，例如，系統(tǒng)若共有n個(gè)進(jìn)程,共有m個(gè)資源，用ri表示第i個(gè)資源，于是這m個(gè)資源是：r1,r2……,rm規(guī)定如果進(jìn)程不得在占用資源ri(1≤i≤m)后再申請(qǐng)rj(j<i)。不難證明，按這種策略分配資源時(shí)系統(tǒng)不會(huì)發(fā)生死鎖。死鎖防止(5)

反證法證明按序分配不會(huì)產(chǎn)生死鎖時(shí)刻t1，進(jìn)程P1處于等資源rk1狀態(tài)，則rk1必為另一進(jìn)程假定是P2所占用,所以一定在某個(gè)時(shí)刻t2，進(jìn)程P2占有資源rk1而處于永遠(yuǎn)等待資源rk2狀態(tài)。如此推下去，系統(tǒng)只有有限個(gè)進(jìn)程，必有某個(gè)n，在時(shí)刻tn時(shí)，進(jìn)程Pn永遠(yuǎn)等待資源rkn，而rkn必為前面某進(jìn)程Pi占用(i<n)。按照按序分配策略，當(dāng)P2占用了rk1后再申請(qǐng)rk2必有：k1＜k2

依此類推，可得：

k2＜k3＜…<ki<…

＜kn

但由于進(jìn)程Pi占有了rkn卻要申請(qǐng)rki，那么，必定有：

kn<ki

這就產(chǎn)生了矛盾。所以按序分配策略可以防止死鎖。3.6.4死鎖的避免銀行家算法銀行家擁有一筆周轉(zhuǎn)資金客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款銀行家應(yīng)謹(jǐn)慎的貸款，防止出現(xiàn)壞帳用銀行家算法避免死鎖操作系統(tǒng)（銀行家）操作系統(tǒng)管理的資源(周轉(zhuǎn)資金)進(jìn)程（要求貸款的客戶）

單種資源的銀行家算法對(duì)每個(gè)請(qǐng)求進(jìn)行檢查，是否會(huì)導(dǎo)致不安全狀態(tài)。若是，則不滿足該請(qǐng)求；否則便滿足檢查狀態(tài)是否安全的方法是看他是否有足夠的資源滿足一個(gè)距最大需求最近的客戶，如此反復(fù)下去。如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請(qǐng)求可以批準(zhǔn)

系統(tǒng)擁有某類資源10個(gè)進(jìn)程已有資源數(shù)還要申請(qǐng)資源數(shù)P44Q22R274個(gè)客戶每個(gè)都有一個(gè)貸款額度一個(gè)狀態(tài)被稱為是安全的條件是存在一個(gè)狀態(tài)序列能夠使所有的客戶均得到其所有的貸款。圖示b狀態(tài)是安全的，以使Marvin運(yùn)行結(jié)束，釋放所有的4個(gè)單位資金。這樣下去便可滿足Suzanne或Barbara的請(qǐng)求。不安全的狀態(tài)考慮給Barbara另一個(gè)她申請(qǐng)的資源，則得到的狀態(tài)是不安全的。如果忽然所有的客戶都申請(qǐng)，希望得到最大貸款額，而銀行家無法滿足其中任何一個(gè)的要求，則發(fā)生死鎖。資源軌跡圖多種資源的銀行家算法(1)總的資源E、已分配資源P、剩余資源A

多種資源的銀行家算法(2)查找右邊矩陣是否有一行，其未被滿足的設(shè)備數(shù)均小于或等于向量A。如果找不到，系統(tǒng)將死鎖，任何進(jìn)程都無法運(yùn)行結(jié)束若找到這樣一行，可以假設(shè)它獲得所需的資源并運(yùn)行結(jié)束，將該進(jìn)程標(biāo)記為結(jié)束，并將(已占有)資源加到向量A上重復(fù)以上兩步，直到所有進(jìn)程都標(biāo)記為結(jié)束，則狀態(tài)是安全的，否則將發(fā)生死鎖

銀行家算法的數(shù)據(jù)結(jié)構(gòu)(1)

考慮一個(gè)系統(tǒng)有n個(gè)進(jìn)程和m種不同類型的資源,現(xiàn)定義包含以下向量和矩陣的數(shù)據(jù)結(jié)構(gòu)：銀行家算法的數(shù)據(jù)結(jié)構(gòu)(2)

?系統(tǒng)每類資源總數(shù)--該m個(gè)元素的向量為系統(tǒng)中每類資源的數(shù)量

Resource=(R1,R2,…,Rm)?每類資源未分配數(shù)量--該m個(gè)元素的向量為系統(tǒng)中每類資源尚可供分配的數(shù)量

Available=(V1,V2,…,Vm)銀行家算法的數(shù)據(jù)結(jié)構(gòu)(3)最大需求矩陣--每個(gè)進(jìn)程對(duì)每類資源的最大需求量,Cij表示進(jìn)程Pi需Rj類資源最大數(shù)Claim=C11C12C1mC11C11C11Cn1Cn1Cnm………

銀行家算法的數(shù)據(jù)結(jié)構(gòu)(4)

分配矩陣—表示進(jìn)程當(dāng)前已分得的資源數(shù),Aij表示進(jìn)程Pi已分到Rj類資源的個(gè)數(shù)

Allocation=A11A12A1mA21A21A21An1An1Anm………銀行家算法中

下列關(guān)系式確保成立?

Ri=Vi+∑Aki

對(duì)i=1,..,m,k=1,..,n;

表示所有資源要么已被分配、要么尚可分配?

Cki≤Rj

對(duì)i=1,..,m,k=1,..,n;

表示進(jìn)程申請(qǐng)資源數(shù)不能超過系統(tǒng)擁有的資源總數(shù)?

Aki≤Cki

對(duì)i=1,..,m,k=1,..,n;

表示進(jìn)程申請(qǐng)任何類資源數(shù)不能超過聲明的最大資源需求數(shù)一種死鎖避免策略

系統(tǒng)中若要啟動(dòng)一個(gè)新進(jìn)程工作,其對(duì)資源Ri的需求僅當(dāng)滿足下列不等式：

Ri≥C(n+1)I+∑Cki

對(duì)i=1,..,m,k=1,..,n;

即應(yīng)滿足當(dāng)前系統(tǒng)中所有進(jìn)程對(duì)資源Ri的最大資源需求數(shù)加上啟動(dòng)的新進(jìn)程的最大資源需求數(shù)不超過系統(tǒng)擁有的最大數(shù)。系統(tǒng)安全性定義

在時(shí)刻T0系統(tǒng)是安全的,僅當(dāng)存在一個(gè)進(jìn)程序列P1,..,Pn,對(duì)進(jìn)程Pk(k=1,..,n)滿足公式

Cki-Aki≤Availablei+∑Aji

j=1,..,k;k=1,..,n;i=1,..,m

該序列稱安全序列,公式左邊表示進(jìn)程Pk尚缺少的各類資源;Availablei是T0時(shí)刻系統(tǒng)尚可用于分配且為Pk所想要的那類資源數(shù);∑Aji表示排在進(jìn)程Pk之前的所有進(jìn)程占用的Pk所需要的資源的總數(shù)。實(shí)例說明系統(tǒng)所處的安全或不安全狀態(tài)(1)

如果系統(tǒng)中共有五個(gè)進(jìn)程和A、B、C三類資源;A類資源共有10個(gè),B類資源共有5個(gè),C類資源共有7個(gè)。在時(shí)刻T0,系統(tǒng)目前資源分配情況如下：實(shí)例說明系統(tǒng)所處的安全或不安全狀態(tài)(2)

processAllocationClaimAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433實(shí)例說明系統(tǒng)所處的安全或不安全狀態(tài)(3)

每個(gè)進(jìn)程目前還需資源為Cki-AkiprocessCki-AkiABCP0743P1122P2600P3011P4431實(shí)例說明系統(tǒng)所處的安全或不安全狀態(tài)(4)

進(jìn)程P1申請(qǐng)資源request1=(1,0,2),檢查request1≤Available、比較(1,0,2)≤(3,3,2),結(jié)果滿足條件,試分配,得到新狀態(tài)：

processAllocationCki-Aki

AvailableABCABCABCP0010743230P1302020P2302600P3211011P4002431實(shí)例說明系統(tǒng)所處的安全或不安全狀態(tài)(5)判定新狀態(tài)是否安全?可執(zhí)行安全性測(cè)試算法，找到一個(gè)進(jìn)程序列{P1,P3,P4,P0,P2}能滿足安全性條件,可正式把資源分配給進(jìn)程P1;此時(shí),進(jìn)程P4請(qǐng)求資源(3,3,0),由于可用資源不足,申請(qǐng)被系統(tǒng)拒絕;此時(shí),系統(tǒng)能滿足進(jìn)程P0的資源請(qǐng)求(0,2,0);但可看出系統(tǒng)已處于不安全狀態(tài)了。銀行家算法的基本思想(1)系統(tǒng)中的所有進(jìn)程進(jìn)入進(jìn)程集合,在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請(qǐng)求后,先把資源試探性分配給它。系統(tǒng)用剩下的可用資源和進(jìn)程集合中其他進(jìn)程還要的資源數(shù)作比較，在進(jìn)程集合中找到剩余資源能滿足最大需求量的進(jìn)程,從而,保證這個(gè)進(jìn)程運(yùn)行完畢并歸還全部資源。銀行家算法的基本思想(2)把這個(gè)進(jìn)程從集合中去掉,系統(tǒng)的剩余資源更多了,反復(fù)執(zhí)行上述步驟。最后,檢查進(jìn)程集合,若為空表明本次申請(qǐng)可行,系統(tǒng)處于安全狀態(tài),可實(shí)施本次分配;否則,有進(jìn)程執(zhí)行不完，系統(tǒng)處于不安全狀態(tài),本次資源分配暫不實(shí)施,讓申請(qǐng)進(jìn)程等待。銀行家算法的程序及簡(jiǎn)短說明(4)

(1)申請(qǐng)量超過最大需求量時(shí)出錯(cuò),否則轉(zhuǎn)(2);(2)申請(qǐng)量超過目前系統(tǒng)擁有的可分配量時(shí),掛起進(jìn)程等待，否則轉(zhuǎn)(3);(3)系統(tǒng)對(duì)Pi進(jìn)程請(qǐng)求資源作試探性分配、執(zhí)行：allocation[i,*]:=allocation[i,*]+request[*]available[*]:=available[*]-request[*](4)執(zhí)行安全性測(cè)試算法,如果安全狀態(tài)則承認(rèn)試分配,否則拋棄試分配，進(jìn)程Pi等待。安全性算法系統(tǒng)所執(zhí)行的安全性算法描述如下：（1）設(shè)置兩個(gè)向量：currentavail和Finish，初始化currentavail=available,finish=false。（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：①Finish(i)=false②Needi≤currentavail（3）當(dāng)進(jìn)程Pi獲得資源后可順利執(zhí)行直到完成，然后釋放分配給它的資源，并作如下工作：①currentavil=currentavil+Allocation②Finish(i)=true（4）若所有進(jìn)程的Finish(i)的值都為true，則說明系統(tǒng)處于安全狀態(tài)；否則系統(tǒng)處于不安全狀態(tài)。3.6.5死鎖的檢測(cè)和解除

1資源分配圖和死鎖定理2借助于死鎖的安全性測(cè)試算法的死鎖檢測(cè)3warshall傳遞閉包算法的死鎖檢測(cè)

死鎖的檢測(cè)和解除

資源分配圖和死鎖定理解決死鎖問題的一條途徑是死鎖檢測(cè)和解除，這種方法對(duì)資源的分配不加任何限制，也不采取死鎖避免措施，但系統(tǒng)定時(shí)地運(yùn)行一個(gè)“死鎖檢測(cè)”程序，判斷系統(tǒng)內(nèi)是否已出現(xiàn)死鎖，如果檢測(cè)到系統(tǒng)已發(fā)性了死鎖，再采取措施解除它。進(jìn)程-資源分配圖PRAG約定Pi→Rj為請(qǐng)求邊，表示進(jìn)程Pi申請(qǐng)資源類Rj中的一個(gè)資源得不到滿足而處于等待Rj類資源的狀態(tài)，該有向邊從進(jìn)程開始指到方框的邊緣，表示進(jìn)程Pi申請(qǐng)Rj類中的一個(gè)資源。Rj→Pi為分配邊，表示Rj類中的一個(gè)資源已被進(jìn)程Pi占用，由于已把一個(gè)具體的資源分給了進(jìn)程Pi，故該有向邊從方框內(nèi)的某個(gè)黑圓點(diǎn)出發(fā)指向進(jìn)程。資源分配圖的一個(gè)例子

R1R2．．．．P1P2P3R3資源分配圖的另一個(gè)例子

R1R2P2P3P4P1資源分配圖的另一個(gè)例子

簡(jiǎn)化進(jìn)程-資源分配圖檢測(cè)系統(tǒng)是否處于死鎖狀態(tài)(1)

(1)如果進(jìn)程-資源分配圖中無環(huán)路，則此時(shí)系統(tǒng)沒有發(fā)生死鎖。(2)如果進(jìn)程-資源分配圖中有環(huán)路，且每個(gè)資源類中僅有一個(gè)資源，則系統(tǒng)中發(fā)生了死鎖，此時(shí)，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程。(3)如果進(jìn)程-資源分配圖中有環(huán)路，且涉及的資源類中有多個(gè)資源，則環(huán)路的存在只是產(chǎn)生死鎖的必要條件而不是充分條件。簡(jiǎn)化進(jìn)程-資源分配圖檢測(cè)系統(tǒng)是否處于死鎖狀態(tài)(2)

如果能在進(jìn)程-資源分配圖中消去此進(jìn)程的所有請(qǐng)求邊和分配邊，成為孤立結(jié)點(diǎn)。經(jīng)一系列簡(jiǎn)化，使所有進(jìn)程成為孤立結(jié)點(diǎn)，則該圖是可完全簡(jiǎn)化的；否則則稱該圖是不可完全簡(jiǎn)化的。系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的進(jìn)程-