《操作系統(tǒng)》第七章：死鎖

第7章死鎖第7章死鎖主要內(nèi)容1.死鎖的概念2.死鎖特征分析

產(chǎn)生死鎖的4個(gè)必要條件3.死鎖處理方法（1）死鎖預(yù)防（2）死鎖避免（3）死鎖檢測(cè)（4）死鎖恢復(fù)生產(chǎn)者

消費(fèi)者的信號(hào)量解法不合理的信號(hào)量使用會(huì)導(dǎo)致… Consumer(){

mutex.P();

fullBuffers.P();

item=Dequeue();

mutex.V();

emptyBuffers.V();

}

Producer(item){

mutex.P();

emptyBuffers.P();

Enqueue(item);

mutex.V();

fullBuffers.V();}生產(chǎn)者占有mutex信號(hào)量后又阻塞在emptyBuffers信號(hào)量上。而消費(fèi)者阻塞在mutex上，不能喚醒生產(chǎn)者……最后誰也沒法執(zhí)行……死鎖現(xiàn)象看一個(gè)實(shí)際的例子現(xiàn)在分析這個(gè)例子競(jìng)爭(zhēng)使用資源:道路A占有道路1，又要請(qǐng)求道路2，B占有…DABC12341A占有2B等待3D4C形成了無限等待死鎖概念(Deadlock)死鎖:

多個(gè)進(jìn)程因循環(huán)等待資源而造成無法執(zhí)行的現(xiàn)象。資源2資源1進(jìn)程B進(jìn)程A等待等待占有占有死鎖會(huì)造成進(jìn)程無法執(zhí)行死鎖會(huì)造成系統(tǒng)資源的極大浪費(fèi)(資源無法釋放)為什么會(huì)產(chǎn)生死鎖問題？

我們來分析一下!資源的分析多個(gè)進(jìn)程因等待資源才造成死鎖資源:進(jìn)程在完成其任務(wù)過程所需要的所有對(duì)象CPU，內(nèi)存，磁盤塊，外設(shè)，文件，信號(hào)量等…顯然有些資源不會(huì)造成死鎖，而有些會(huì)只讀文件是不會(huì)造成進(jìn)程等待的，也就不會(huì)死鎖打印機(jī)一次只能讓一個(gè)進(jìn)程使用，就會(huì)造成死鎖稱為互斥訪問資源顯然，資源互斥訪問是死鎖的必要條件死鎖并不總是發(fā)生一簡(jiǎn)單實(shí)例進(jìn)程Ax.P();y.P();y.V();x.V();

進(jìn)程By.P();x.P();x.V();y.V();

考慮序列：A:x.P()，B:y.P()，B:x.P()，A:y.P()…形成循環(huán)等待，出現(xiàn)死鎖考慮序列：A:x.P()，A:y.P()，B:y.P()，B:x.P()…并不形成死鎖資源請(qǐng)求需要形成環(huán)路等待才死鎖，如何描述這種等待關(guān)系?死鎖與調(diào)度有關(guān)，是非確定的!資源分配圖資源分配圖模型一個(gè)進(jìn)程集合{P1,P2,…,Pn}記號(hào)R1R2P1P2一資源類型集合{R1,R2,…,Rm}資源類型Ri有Wi個(gè)實(shí)例資源請(qǐng)求邊：有向邊Pi

Rj資源分配邊：有向邊RiPkR2P1P2資源分配圖實(shí)例1A占有2B等待3D4C1ABCD234存在環(huán)路:1→A→2→B→3→C→4→D→1P1P2P3R2R1P4存在環(huán)路:P1→R1→P3→R2→P1但并不死鎖，仍可繼續(xù)執(zhí)行產(chǎn)生死鎖死鎖的4個(gè)必要條件互斥使用(Mutualexclusion)資源的固有特性，如道口不可搶占(Nopreemption)資源只能自愿放棄，如車開走以后請(qǐng)求和保持(Holdandwait)進(jìn)程必須占有資源，再去申請(qǐng)循環(huán)等待(Circularwait)在資源分配圖中存在一個(gè)環(huán)路1ABCD234如何消除死鎖？

有什么方法？死鎖處理方法概述死鎖預(yù)防破壞死鎖的必要條件“nosmoking”，預(yù)防火災(zāi)死鎖避免檢測(cè)每個(gè)資源請(qǐng)求，如果造成死鎖就拒絕檢測(cè)到煤氣超標(biāo)時(shí)，自動(dòng)切斷電源死鎖檢測(cè)+恢復(fù)檢測(cè)到死鎖出現(xiàn)時(shí)，剝奪一些進(jìn)程的資源發(fā)現(xiàn)火災(zāi)時(shí)，立刻拿起滅火器死鎖忽略就好像沒有出現(xiàn)死鎖一樣在太陽上可以對(duì)火災(zāi)全然不顧死鎖預(yù)防:破除死鎖的必要條件之(1)(2)破壞互斥使用資源的固有特性，通常無法破除，如打印機(jī)破除不可搶占如果一個(gè)進(jìn)程占有資源并申請(qǐng)另一個(gè)不能立即分配的資源，那么已分配資源就可被搶占（即持有不用即可搶占）如果申請(qǐng)的資源得到滿足，則搶占其他資源需一次性分配給該進(jìn)程只對(duì)狀態(tài)能保存和恢復(fù)的資源(如CPU，內(nèi)存空間)有效，對(duì)打印機(jī)等外設(shè)不適用死鎖預(yù)防:破除死鎖的必要條件之(3)破除請(qǐng)求和保持在進(jìn)程執(zhí)行前，一次性申請(qǐng)所有需要的資源缺點(diǎn)1:需要預(yù)知未來，編程困難缺點(diǎn)2:許多資源分配后很長(zhǎng)時(shí)間后才使用，資源利用率低死鎖預(yù)防:破除死鎖的必要條件之(4)破除循環(huán)等待對(duì)資源類型進(jìn)行排序，資源申請(qǐng)必須按序進(jìn)行缺點(diǎn):如果編程時(shí)就需考慮，用戶會(huì)覺得很別扭；否則需要釋放某些資源(申請(qǐng)序號(hào)小的資源)，進(jìn)程可能會(huì)無法執(zhí)行例如：所有的進(jìn)程必須先申請(qǐng)磁盤驅(qū)動(dòng)，再申請(qǐng)打印機(jī)，再….，如同日常交通中的單行道總之，破除死鎖的必要條件會(huì)引入不合理因素，實(shí)際中很少使用。死鎖避免思想:判斷此次請(qǐng)求是否造成死鎖

若會(huì)造成死鎖，則拒絕該請(qǐng)求不死鎖就成了問題的核心!安全狀態(tài)定義:如果系統(tǒng)中的所有進(jìn)程存在一個(gè)可完成的執(zhí)行序列P1，…Pn，則稱系統(tǒng)處于安全狀態(tài)都能執(zhí)行完成當(dāng)然就不死鎖安全序列:上面的執(zhí)行序列P1，…Pn如何找到這樣的序列?死鎖避免之銀行家算法安全序列P1，…Pn應(yīng)該滿足的性質(zhì)：Pi(1

i

n)需要資源

剩余資源+分配給Pj(1

j<i)資源Banker()int

n,m;//系統(tǒng)中進(jìn)程總數(shù)n和資源種類總數(shù)mint

Available[1..m];//每種資源剩余數(shù)量int

Allocation[1..n,1..m];

//當(dāng)前給分配給每個(gè)進(jìn)程的各種資源數(shù)量intNeed[1..n,1..m];//當(dāng)前每個(gè)進(jìn)程還需分配的各種資源數(shù)量intWork[1..m];//當(dāng)前可分配的資源boolFinish[1..n];//進(jìn)程是否結(jié)束死鎖避免之銀行家算法安全狀態(tài)判定（思路）：①初始化設(shè)定：

Work=Available（動(dòng)態(tài)記錄當(dāng)前剩余資源）

Finish[i]=false（設(shè)定所有進(jìn)程均未完成）②查找這樣的進(jìn)程Pi（未完成但目前剩余資源可滿足其需要，

這樣的進(jìn)程是能夠完成的）：

a）Finish[i]=falseb）Need[i]Work

如果沒有這樣的進(jìn)程Pi，則跳轉(zhuǎn)到第④步③（若有則）Pi一定能完成，并歸還其占用的資源，即：

a）Finish[i]=trueb）Work=Work+Allocation[i]GOTO第②步，繼續(xù)查找④如果所有進(jìn)程Pi都是能完成的，即Finish[i]=ture

則系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)死鎖避免之銀行家算法BooleanFound;Work=Available;Finish[1..n]=false;while(true){Found=false;

for(i=1;i<=n;i++){

if(Finish[i]==false&&Need[i]<=Work){

Work=Work+Allocation[i];Finish[i]=true;Found=true;}}

if(Found==false)break;}for(i=1;i<=n;i++)

if(Finish[i]==false)return“deadlock”;T(n)=O(mn2)安全狀態(tài)判定（實(shí)現(xiàn)）：死鎖避免之銀行家算法實(shí)例

AllocationNeedAvailable

ABC ABC

ABC

P0 0

1

0

7

4

3

3

3

2

P1 2

0

01

2

2

P2 3

0

2

6

00

P3 2

1

10

1

1

P4 0

0

2

4

3

1

當(dāng)前狀態(tài):Work=[332]安全序列是<P1,P3,P2,P4,P0>Work=[532]P1Work=[743]P3Work=[1045]P2Work=[1047]P4Work=[1057]P0?

?

這樣的序列是唯一的嗎？死鎖避免之資源請(qǐng)求算法externBanker();intRequest[1..m];/*進(jìn)程Pi的資源申請(qǐng)*/if(Request>Need[i])return“error”;if(Request>Available)sleep();Available=Available-Request;Allocation[i]=Allocation[i]+Request;Need[i]=Need[i]-Request;

/*先將資源分配給Pi*/if(Banker()==“deadlock”)/*調(diào)用銀行家算法判定是否會(huì)死鎖*/

拒絕Request;/*若算法判定deadlock則拒絕請(qǐng)求，資源回滾*/死鎖避免之資源請(qǐng)求實(shí)例(1)

AllocationNeedAvailable

ABC

ABC

A

BC

P0 0

1

0

7

4

3

3

3

2

P1 2

0

0 1

2

2

P2 3

0

2600

P3 2

1

1 0

1

1

P4 0

0

2

4

3

1

P1申請(qǐng)資源(1,0,2)

AllocationNeedAvailable

ABC

A

BC

A

BC

P0 010

7

4

3

2

3

0

P1 3

02

0

20

P2 3

0

260

0

P3 2

1

10

1

1

P4 0

0

2

4

31

序列<P1,P3,P2,P4,P0>是安全的此次申請(qǐng)?jiān)试S死鎖避免之資源請(qǐng)求實(shí)例(2)P0再申請(qǐng)(0,2,0)

AllocationNeedAvailable

ABC

ABC

A

BC

P0 0

10

743

23

0

P1 3

02

0

20

P2 3

0

26

0

0

P3 2

1

1 0

1

1

P4 0

0

2

4

31

進(jìn)程P0,P1,P2,P3,P4一個(gè)也沒法執(zhí)行，死鎖進(jìn)程組此次申請(qǐng)被拒絕

AllocationNeedAvailable

ABC

ABC

A

B

C

P0 0

3

0

7

2

3

2

1

0

P1 3

02

0

20

P2 3

0

26

00

P3 2

1

1 0

1

1

P4 0

0

2

4

3

1

銀行家算法討論：每個(gè)進(jìn)程進(jìn)入系統(tǒng)時(shí)必須告知所需資源的最大數(shù)量對(duì)應(yīng)用程序員要求高安全序列尋找算法（安全狀態(tài)判定算法）計(jì)算時(shí)間

復(fù)雜度為O(mn2)，過于復(fù)雜若每次資源請(qǐng)求都要調(diào)用銀行家算法，耗時(shí)過大，系統(tǒng)效率降低采用此算法，存在情況：當(dāng)前有資源可用，盡管可

能很快就會(huì)釋放，由于會(huì)使整體進(jìn)程處于不安全狀

態(tài)，而不被分配，致使資源利用率大大降低死鎖檢測(cè)+恢復(fù):死鎖檢測(cè)基本原因：每次申請(qǐng)都執(zhí)行O(mn2)，效率低對(duì)策：只要可用資源足夠，則分配，發(fā)現(xiàn)問

題再處理定時(shí)檢測(cè)或者當(dāng)發(fā)現(xiàn)資源利用率低時(shí)檢測(cè)Finish[1..n]=false;

if(Allocation[i]

==0)

Finish[i]=true;