计算机课件补2死锁

补充2

死锁

提纲

■2.1死锁的概念

■2.2死锁的排除方法

2.1死锁的概念

■1,死锁的定义

□所谓死锁，是指各并发进程彼此互相等待对方

所拥有的资源，且这些并发进程在得到对方的

资源之前不会释放自己所拥有的资源。从而造

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

发进程不能继续向前推进的状态。

例1:

一系统有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：哲学家就餐

当每个哲学家均拿起左手的叉子时,都在等待右手叉子，陷入死锁。

■死锁的形式定义：

有并发进程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),从而造成资源的互相占有和

互相等待。

在没有外力驱动的情况下，该组并发进程停止往

前推进，陷入永久等待状态。

2.产生死锁的必要条件

■⑴互斥条件(Mutualexclusion)o并发进程所要求和占

有的资源是不能同时被两个以上进程使用或操作的，进程

对它所需要的资源进行排他性控制。

■(2)不剥夺条件(Nopreemption)。进程所获得的资源在

未使用完毕之前，不能被其他进程强行剥夺，而只能由获

得该资源的进程自己释放。

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

的一部分资源，在等待新资源的同时继续占用已分配到的

资源。

■(4)环路条件(Circularwait)。存在一种进程循环链，

链中每一个进程已获得的资源同时被下一个进程所请求。

显然，只要使上述4个必要条件中的某一个不满足，则死锁

就可以排除。

资源分配图

顶点集：V；边集E

V两种类型：

P={P1,P2,…，Pn},系统包含的所有进程集合.

R={R1,R2,Rm},系统包含的所有资源集合.

请求边：PifRj

分配边：Rj-Pi

%

资源分配图示例含有死锁的资源分配图示例

基本结论：

如果资源分配图不含环路n没有死锁

如果资源分配图含有环路n

—如果每类资源中包含1个资源，

则死锁。

—如果每类资源中包含多个资源,

则可能死锁。

含有环路，但没有死锁的资源分配图

2.2死锁的排除方法

■一般方法

□预防

□避免

口检测与恢复

■有的系统(UNIX,Windows)

对死锁采取忽略的策略，以减少系统开销。

1.死锁预防(DeadlockPrevention)

■采用某种策略，使得死锁的必要条件在系统执行的

任何时间都不满足。

■主要方法：

□(1)打破资源的互斥和不可剥夺两个必要条件

□(2)打破资源的部分分配必要条件。

□(3)打破死锁的环路必要条件

(1)打破资源的互斥和不可剥夺两个必要条件

■例如：允许进程同时访问某些资源等。

■缺陷：不能解决访问那些不允许被同时访问的资源

时所带来的死锁问题。

■通常是不可取的。

(2)打破资源的部分分配必要条件

■预先静态分配法：

□预先分配各并发进程所需要的全部资源。

□如某个进程的资源得不到满足时等待。

■缺点：

□(1)进程在执行之前需提出它所需要的全部资源

□(2)进程只有在所有要求资源都得到满足后才开始执行

□(3)资源利用率低

□(4)降低了进程的并发性

(3)打破死锁的环路必要条件

把资源分类按顺序排列，使进程在申请、保持资源时不形成

环路。

有序资源使用法：

如有m种资源，则列出<口2

若进程Pi提出申请资源Ri,则它今后只能申请比Ri级别更高的

资源Rj(Ri<Rj)。

释放资源时必须是Rj先于Ri被释放，从而避免环路的产生。

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

如果一个进程一旦申请了磁盘驱动器，则不能再申请磁带机。

缺点：限制了进程对资源的请求。

证明：

假设系统存在环路：P1F2F3,…Pn

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

・・・F(Ri)<F(凡);

即产生矛盾结果，所以系统不会存在环路。

思考：对哲学家就餐问题，分别用以上两种方法预防死

锁如何实现。

2.死锁避免(DeadlockAvoidance)

■系统在分配资源时，根据资源的使用情况提前做出

预测，从而避免死锁的发生。

设并发进程pLp2….pn(nN1)共享不同类型的资源R1,

R2,…，Rm(m>1),每一Ri有固定的单元数目Ci

(1<i<n)o

安全八亦_,

------k分酉己

可满足请求检测

不安全,不分配

系统处于安全状态:存在安全进程序列<pl,p2，…,pn>

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

例：设某系统共有3个进程(PLP2、P3),共享12台磁

带机，系统在某时刻的状态为：

进程最大需求已分配还需

P11055

P2422

P3927

系统可用的磁带机：3

问题：

(1)此时系统是否安全？

(2)P3申请一台磁带机，能否满足?

(3)P1申请一台磁带机，能否满足?

银行家算法（ContJ

Bankersalgorithm,E.W.Dijkstra.

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

系统：对每个可满足的资源申请命令进行安全性检查。

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

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

银行家算法（ContJ

数据结构：

Available：array[l..m]ofinteger;〃系统可用资源

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

设X,Y为下标L.m的一维数组：

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

-----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),

不安全，不分配

(分配不导致死锁)

银行家算法的缺点：

(1)死锁避免需要占去系统较大的开销。

(2)银行家算法需要用户给出各进程需要的最大

资源量。

银行家算法练习

R={AB&D}

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

MaxAllocationNeedAvailable

ABCDABCDABCDABCD

Pl:001200121520

p2:17501000

p3:23561354

p4:06520632

p5:06560014

(1)此时，系统是否安全？如果安全，给出安全序列。

(2)若此时p2请求:Request[2]=(0,4,2,0),系统能否马上满足?

3,死锁的检测

■资源分配图的化简:

(1)找一进程Pi,其请求边均能满足，找不到转(3)

(2)删去与进程Pi相关的所有请求边、分配边，对Pi作

“已化简”标记，goto(1)；

(3)若所有进程均“已化简”，则称该资源分配图是

可化简的，否则该资源分配图是不可化简的。

■死锁定理：

当且仅当状态S对应的资源分配图是不可化简的,

则S处于死锁状态，不可化简的进程是死锁进程。

反之，系统处于安全状态。

资源分配图示例含有死锁的资源分配图示例

死锁的检测算法：

数据结构：

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]

无死锁