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

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

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

消費者的信號量解法不合理的信號量使用會導致… 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信號量后又阻塞在emptyBuffers信號量上。而消費者阻塞在mutex上，不能喚醒生產(chǎn)者……最后誰也沒法執(zhí)行……死鎖現(xiàn)象看一個實際的例子現(xiàn)在分析這個例子競爭使用資源:道路A占有道路1，又要請求道路2，B占有…DABC12341A占有2B等待3D4C形成了無限等待死鎖概念(Deadlock)死鎖:

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

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

進程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()…并不形成死鎖資源請求需要形成環(huán)路等待才死鎖，如何描述這種等待關系?死鎖與調(diào)度有關，是非確定的!資源分配圖資源分配圖模型一個進程集合{P1,P2,…,Pn}記號R1R2P1P2一資源類型集合{R1,R2,…,Rm}資源類型Ri有Wi個實例資源請求邊：有向邊Pi

Rj資源分配邊：有向邊RiPkR2P1P2資源分配圖實例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個必要條件互斥使用(Mutualexclusion)資源的固有特性，如道口不可搶占(Nopreemption)資源只能自愿放棄，如車開走以后請求和保持(Holdandwait)進程必須占有資源，再去申請循環(huán)等待(Circularwait)在資源分配圖中存在一個環(huán)路1ABCD234如何消除死鎖？

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

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

i

n)需要資源

剩余資源+分配給Pj(1

j<i)資源Banker()int

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

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

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

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

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

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

這樣的進程是能夠完成的）：

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

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

a）Finish[i]=trueb）Work=Work+Allocation[i]GOTO第②步，繼續(xù)查找④如果所有進程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)判定（實現(xiàn)）：死鎖避免之銀行家算法實例

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

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

?

這樣的序列是唯一的嗎？死鎖避免之資源請求算法externBanker();intRequest[1..m];/*進程Pi的資源申請*/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)用銀行家算法判定是否會死鎖*/

拒絕Request;/*若算法判定deadlock則拒絕請求，資源回滾*/死鎖避免之資源請求實例(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申請資源(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>是安全的此次申請允許死鎖避免之資源請求實例(2)P0再申請(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

進程P0,P1,P2,P3,P4一個也沒法執(zhí)行，死鎖進程組此次申請被拒絕

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

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

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

能很快就會釋放，由于會使整體進程處于不安全狀

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

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

if(Allocation[i]

==0)

Finish[i]=true;