計算機課件補2死鎖

補充2

死鎖

提綱

■2.1死鎖的概念

■2.2死鎖的排除方法

2.1死鎖的概念

■1,死鎖的定義

□所謂死鎖，是指各并發(fā)進程彼此互相等待對方

所擁有的資源，且這些并發(fā)進程在得到對方的

資源之前不會釋放自己所擁有的資源。從而造

成大家都想得到資源而又都得不到資源，各并

發(fā)進程不能繼續(xù)向前推進的狀態(tài)。

例1:

一系統(tǒng)有2臺磁帶機(Til》

一兩個進程PIP2

PiP2

request(T^);request(TJ;

requesfffJ;request(TA);

useiTVT2);useiTvT2);

re/ease(T1yT2);re/easefT^Tj);

例2：

信號量A、8,初值1

P1P2

P(A)；P(B)

P(B)；P(A)

□□

例4：哲學(xué)家就餐

當每個哲學(xué)家均拿起左手的叉子時,都在等待右手叉子，陷入死鎖。

■死鎖的形式定義：

有并發(fā)進程P1,P2,…，Pn,它們共享資源R1,

R2,…，Rm(n>0,m>0,n>=m)。

□其中，每個Pid<i<n)擁有資源Rj(1<j<m),

直到不再有剩余資源。

□同時，各Pi又在不釋放Rj的前提下要求得到Rk

(k#j,1<k<m),從而造成資源的互相占有和

互相等待。

在沒有外力驅(qū)動的情況下，該組并發(fā)進程停止往

前推進，陷入永久等待狀態(tài)。

2.產(chǎn)生死鎖的必要條件

■⑴互斥條件(Mutualexclusion)o并發(fā)進程所要求和占

有的資源是不能同時被兩個以上進程使用或操作的，進程

對它所需要的資源進行排他性控制。

■(2)不剝奪條件(Nopreemption)。進程所獲得的資源在

未使用完畢之前，不能被其他進程強行剝奪，而只能由獲

得該資源的進程自己釋放。

■(3)部分分配(Holdandwait)。進程每次申請它所需要

的一部分資源，在等待新資源的同時繼續(xù)占用已分配到的

資源。

■(4)環(huán)路條件(Circularwait)。存在一種進程循環(huán)鏈，

鏈中每一個進程已獲得的資源同時被下一個進程所請求。

顯然，只要使上述4個必要條件中的某一個不滿足，則死鎖

就可以排除。

資源分配圖

頂點集：V；邊集E

V兩種類型：

P={P1,P2,…，Pn},系統(tǒng)包含的所有進程集合.

R={R1,R2,Rm},系統(tǒng)包含的所有資源集合.

請求邊：PifRj

分配邊：Rj-Pi

%

資源分配圖示例含有死鎖的資源分配圖示例

基本結(jié)論：

如果資源分配圖不含環(huán)路n沒有死鎖

如果資源分配圖含有環(huán)路n

—如果每類資源中包含1個資源，

則死鎖。

—如果每類資源中包含多個資源,

則可能死鎖。

含有環(huán)路，但沒有死鎖的資源分配圖

2.2死鎖的排除方法

■一般方法

□預(yù)防

□避免

口檢測與恢復(fù)

■有的系統(tǒng)(UNIX,Windows)

對死鎖采取忽略的策略，以減少系統(tǒng)開銷。

1.死鎖預(yù)防(DeadlockPrevention)

■采用某種策略，使得死鎖的必要條件在系統(tǒng)執(zhí)行的

任何時間都不滿足。

■主要方法：

□(1)打破資源的互斥和不可剝奪兩個必要條件

□(2)打破資源的部分分配必要條件。

□(3)打破死鎖的環(huán)路必要條件

(1)打破資源的互斥和不可剝奪兩個必要條件

■例如：允許進程同時訪問某些資源等。

■缺陷：不能解決訪問那些不允許被同時訪問的資源

時所帶來的死鎖問題。

■通常是不可取的。

(2)打破資源的部分分配必要條件

■預(yù)先靜態(tài)分配法：

□預(yù)先分配各并發(fā)進程所需要的全部資源。

□如某個進程的資源得不到滿足時等待。

■缺點：

□(1)進程在執(zhí)行之前需提出它所需要的全部資源

□(2)進程只有在所有要求資源都得到滿足后才開始執(zhí)行

□(3)資源利用率低

□(4)降低了進程的并發(fā)性

(3)打破死鎖的環(huán)路必要條件

把資源分類按順序排列，使進程在申請、保持資源時不形成

環(huán)路。

有序資源使用法：

如有m種資源，則列出<口2

若進程Pi提出申請資源Ri,則它今后只能申請比Ri級別更高的

資源Rj(Ri<Rj)。

釋放資源時必須是Rj先于Ri被釋放，從而避免環(huán)路的產(chǎn)生。

例如:F(tapedrive)=1F(diskdrive)=5F(Printer)=12

如果一個進程一旦申請了磁盤驅(qū)動器，則不能再申請磁帶機。

缺點：限制了進程對資源的請求。

證明：

假設(shè)系統(tǒng)存在環(huán)路：P1F2F3,…Pn

???F(Ri)vF(R2);F(R2)<F(R3)；F(R3)<F(R4);...F(Rn)<F(%)

???F(Ri)<F(凡);

即產(chǎn)生矛盾結(jié)果，所以系統(tǒng)不會存在環(huán)路。

思考：對哲學(xué)家就餐問題，分別用以上兩種方法預(yù)防死

鎖如何實現(xiàn)。

2.死鎖避免(DeadlockAvoidance)

■系統(tǒng)在分配資源時，根據(jù)資源的使用情況提前做出

預(yù)測，從而避免死鎖的發(fā)生。

設(shè)并發(fā)進程pLp2….pn(nN1)共享不同類型的資源R1,

R2,…，Rm(m>1),每一Ri有固定的單元數(shù)目Ci

(1<i<n)o

安全八亦_,

------k分酉己

可滿足請求檢測

不安全,不分配

系統(tǒng)處于安全狀態(tài):存在安全進程序列<pl,p2，…,pn>

進程序列<pLp2…一pn>安全,pl,p2,…,pn可依次進行完。

例：設(shè)某系統(tǒng)共有3個進程(PLP2、P3),共享12臺磁

帶機，系統(tǒng)在某時刻的狀態(tài)為：

進程最大需求已分配還需

P11055

P2422

P3927

系統(tǒng)可用的磁帶機：3

問題：

(1)此時系統(tǒng)是否安全？

(2)P3申請一臺磁帶機，能否滿足?

(3)P1申請一臺磁帶機，能否滿足?

銀行家算法（ContJ

Bankersalgorithm,E.W.Dijkstra.

進程：事先申明所需資源最大量（并不分配）

系統(tǒng)：對每個可滿足的資源申請命令進行安全性檢查。

P={pl,p2,…,pn};

R={rl/r2,.../rm）;

銀行家算法（ContJ

數(shù)據(jù)結(jié)構(gòu)：

Available：array[l..m]ofinteger;〃系統(tǒng)可用資源

Max：array[l..n/l..^n]ofinteger;〃進程最大需求

Allocation：array[l..n/l..m]ofinteger;//當前分酉己

Need：array[l..n/l..m]ofinteger;〃尚需資源

Request：array[l..n/l..m]ofinteger;〃當前請求

臨時變量：

Work：array[l..m]ofinteger;

Finish：array[l..n]ofboolean;

銀行家算法（ContJ

設(shè)X,Y為下標L.m的一維數(shù)組：

X<Y?Vj(l<j<m)9X[j]<Y[j]

X:=Y?Vj(l<j<m)9X[j]:=Y[j]

X:=coVj(l<j<m),X[j]:=c

X±Y<^Vj(l<j<m),X[j]±Y[j]

資源分配

Pi請求資源

T，F(xiàn)

-----Request[I]<Need[I]-----

安全性檢測算法

Work:=Available;

Finish:=false;

T有滿足條件的j：F

Finish[j]=false"

F

'rNeed[j]<Work

Vj,finish[j]=true——

Finish|j]=true;

Work:=Work+Allocation[j]

安全不安全

銀行家算法例子

R二{A(10),B(5),C(7)}

P={p0,pl,p2,p3,p4}

MaxAllocationNeedAvailableWorkFinish

ABCABCABCABCABC

PO:753010743332

pl:322200122

p2:902302600

p3:222211011

p4:433002431

安全進程序列：<pl,p3,p4,p2,p0>

p1請求:Request[1]=(1,0,2)

銀行家算法例子

假定分配：

ClaimAllocationNeedAvailableWorkFinish

ABCABCABCABCABC

PO:753010743230

pl:322302020

p2:902302600

p3:222211011

p4:433002431

安全進程序列：<pl,p3,p4,p0,p2>

p4請求:Request[4]=(3,3,0),

不能滿足，等待；

p0請求：Request[0]=(052,0),

不安全，等待。

銀行家算法的保守性

例子：R={A,B},申請a,b;釋放a,E

P={pl,p2}?pl:abab;p2:bbbaab

MaxAllocationNeedAvailableWorkFinish

ABABABABAB

pl：11001111

p2：110011

Request[l]=(l,O),

安全，分配。

銀行家算法的保守性

例子：R={A,B},申請a,b;釋放a,E

P={pl,p2}?pl:abab;p2:bbbaab

分配后:

ClaimAllocationNeedAvailable[WorkFinish

ABABABAB：AB

pl：11100101：

p2：1100iii

Request[2]=(0,l),

不安全，不分配

(分配不導(dǎo)致死鎖)

銀行家算法的缺點：

(1)死鎖避免需要占去系統(tǒng)較大的開銷。

(2)銀行家算法需要用戶給出各進程需要的最大

資源量。

銀行家算法練習(xí)

R={AB&D}

P={pl,p2,p3,p4,p5}

MaxAllocationNeedAvailable

ABCDABCDABCDABCD

Pl:001200121520

p2:17501000

p3:23561354

p4:06520632

p5:06560014

(1)此時，系統(tǒng)是否安全？如果安全，給出安全序列。

(2)若此時p2請求:Request[2]=(0,4,2,0),系統(tǒng)能否馬上滿足?

3,死鎖的檢測

■資源分配圖的化簡:

(1)找一進程Pi,其請求邊均能滿足，找不到轉(zhuǎn)(3)

(2)刪去與進程Pi相關(guān)的所有請求邊、分配邊，對Pi作

“已化簡”標記，goto(1)；

(3)若所有進程均“已化簡”，則稱該資源分配圖是

可化簡的，否則該資源分配圖是不可化簡的。

■死鎖定理：

當且僅當狀態(tài)S對應(yīng)的資源分配圖是不可化簡的,

則S處于死鎖狀態(tài)，不可化簡的進程是死鎖進程。

反之，系統(tǒng)處于安全狀態(tài)。

資源分配圖示例含有死鎖的資源分配圖示例

死鎖的檢測算法：

數(shù)據(jù)結(jié)構(gòu)：

Available:arrayofinteger;

Allocation:array[l..n,l..m]ofinteger;

Request:array[l..n,l..m]ofinteger;

臨時變量：

Work:array[l..m]ofinteger;

Finish:array[1..n]ofboolean;

Work:=Available;

Finish:=false;

T有滿足條件的i：F

Finish[i]=false--------------------1

Request[i]<WorkTIF

-Vi,finish[i]=true—

Finish[i]=true;

ir

Work:=Work+Allocation[i]

無死鎖