計(jì)算機(jī)課件補(bǔ)2死鎖

補(bǔ)充2

死鎖

提綱

■2.1死鎖的概念

■2.2死鎖的排除方法

2.1死鎖的概念

■1,死鎖的定義

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

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

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

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

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

例1:

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

一兩個(gè)進(jìn)程PIP2

PiP2

request(T^);request(TJ;

requesfffJ;request(TA);

useiTVT2);useiTvT2);

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

例2：

信號(hào)量A、8,初值1

P1P2

P(A)；P(B)

P(B)；P(A)

□□

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

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

■死鎖的形式定義：

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

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

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

直到不再有剩余資源。

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

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

互相等待。

在沒(méi)有外力驅(qū)動(dòng)的情況下，該組并發(fā)進(jìn)程停止往

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

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

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

有的資源是不能同時(shí)被兩個(gè)以上進(jìn)程使用或操作的，進(jìn)程

對(duì)它所需要的資源進(jìn)行排他性控制。

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

未使用完畢之前，不能被其他進(jìn)程強(qiáng)行剝奪，而只能由獲

得該資源的進(jìn)程自己釋放。

■(3)部分分配(Holdandwait)。進(jìn)程每次申請(qǐng)它所需要

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

資源。

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

鏈中每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求。

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

就可以排除。

資源分配圖

頂點(diǎn)集：V；邊集E

V兩種類型：

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

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

請(qǐng)求邊：PifRj

分配邊：Rj-Pi

%

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

基本結(jié)論：

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

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

—如果每類資源中包含1個(gè)資源，

則死鎖。

—如果每類資源中包含多個(gè)資源,

則可能死鎖。

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

2.2死鎖的排除方法

■一般方法

□預(yù)防

□避免

口檢測(cè)與恢復(fù)

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

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

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

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

任何時(shí)間都不滿足。

■主要方法：

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

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

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

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

■例如：允許進(jìn)程同時(shí)訪問(wèn)某些資源等。

■缺陷：不能解決訪問(wèn)那些不允許被同時(shí)訪問(wèn)的資源

時(shí)所帶來(lái)的死鎖問(wèn)題。

■通常是不可取的。

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

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

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

□如某個(gè)進(jìn)程的資源得不到滿足時(shí)等待。

■缺點(diǎn)：

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

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

□(3)資源利用率低

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

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

把資源分類按順序排列，使進(jìn)程在申請(qǐng)、保持資源時(shí)不形成

環(huán)路。

有序資源使用法：

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

若進(jìn)程Pi提出申請(qǐng)資源Ri,則它今后只能申請(qǐng)比Ri級(jí)別更高的

資源Rj(Ri<Rj)。

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

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

如果一個(gè)進(jìn)程一旦申請(qǐng)了磁盤驅(qū)動(dòng)器，則不能再申請(qǐng)磁帶機(jī)。

缺點(diǎn)：限制了進(jìn)程對(duì)資源的請(qǐng)求。

證明：

假設(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ì)存在環(huán)路。

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

鎖如何實(shí)現(xiàn)。

2.死鎖避免(DeadlockAvoidance)

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

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

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

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

(1<i<n)o

安全八亦_,

------k分酉己

可滿足請(qǐng)求檢測(cè)

不安全,不分配

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

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

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

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

進(jìn)程最大需求已分配還需

P11055

P2422

P3927

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

問(wèn)題：

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

(2)P3申請(qǐng)一臺(tái)磁帶機(jī)，能否滿足?

(3)P1申請(qǐng)一臺(tái)磁帶機(jī)，能否滿足?

銀行家算法（ContJ

Bankersalgorithm,E.W.Dijkstra.

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

系統(tǒng)：對(duì)每個(gè)可滿足的資源申請(qǐng)命令進(jìn)行安全性檢查。

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;〃進(jìn)程最大需求

Allocation：array[l..n/l..m]ofinteger;//當(dāng)前分酉己

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

Request：array[l..n/l..m]ofinteger;〃當(dāng)前請(qǐng)求

臨時(shí)變量：

Work：array[l..m]ofinteger;

Finish：array[l..n]ofboolean;

銀行家算法（ContJ

設(shè)X,Y為下標(biāo)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請(qǐng)求資源

T，F(xiàn)

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

安全性檢測(cè)算法

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

安全進(jìn)程序列：<pl,p3,p4,p2,p0>

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

銀行家算法例子

假定分配：

ClaimAllocationNeedAvailableWorkFinish

ABCABCABCABCABC

PO:753010743230

pl:322302020

p2:902302600

p3:222211011

p4:433002431

安全進(jìn)程序列：<pl,p3,p4,p0,p2>

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

不能滿足，等待；

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

不安全，等待。

銀行家算法的保守性

例子：R={A,B},申請(qǐng)a,b;釋放a,E

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

MaxAllocationNeedAvailableWorkFinish

ABABABABAB

pl：11001111

p2：110011

Request[l]=(l,O),

安全，分配。

銀行家算法的保守性

例子：R={A,B},申請(qǐng)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)致死鎖)

銀行家算法的缺點(diǎn)：

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

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

資源量。

銀行家算法練習(xí)

R={AB&D}

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

MaxAllocationNeedAvailable

ABCDABCDABCDABCD

Pl:001200121520

p2:17501000

p3:23561354

p4:06520632

p5:06560014

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

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

3,死鎖的檢測(cè)

■資源分配圖的化簡(jiǎn):

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

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

“已化簡(jiǎn)”標(biāo)記，goto(1)；

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

可化簡(jiǎn)的，否則該資源分配圖是不可化簡(jiǎn)的。

■死鎖定理：

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

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

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

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

死鎖的檢測(cè)算法：

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

Available:arrayofinteger;

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

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

臨時(shí)變量：

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]

無(wú)死鎖