进程死锁——银行家算法
死锁概念
一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到该资源,这种现象称为进程死锁(Deadlock),这一组进程就称为死锁进程。
1、死锁产生的原因
- 竞争资源引起进程死锁(资源分配策略)(可剥夺和非剥夺资源)
- 进程推进顺序不当引起死锁
PS:关于死锁的一些结论:
- 参与死锁的进程最少是两个(两个以上进程才会出现死锁)
- 参与死锁的进程至少两个已经占有资源
- 参与死锁的所有进程都在等待资源
- 参与死锁的进程是当前系统中所有进程的子集
- 如果死锁发生,会浪费大量的系统资源,甚至导致系统崩溃
2、死锁的四个必要条件
- 互斥条件:设计的资源是非共享的
- 不可抢占条件:不能强行剥夺进程拥有的资源
- 请求和保持条件:进程在等待一新资源时继续占有已分配的资源
- 环路条件:存在一种进程的循环链,链中的每一个进程已获得的资源同时被下一个进程所请求
3、处理死锁的方法
- 预防死锁:通过设置某些限制条件,去破坏死锁四个必要条件中的一个或多个,来防止死锁。
- 避免死锁:不事先设置限制条件去破坏产生死锁的条件,而是在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免死锁的发生。
- 检测死锁:允许死锁发生,但可通过检测机构及时检测出死锁的发生,并精确确定与死锁有关的进程和资源,然后采取适当措施,将系统中已发生的死锁清除掉。
- 解除死锁:与检测死锁相配套,用于将进程从死锁状态解脱出来。常用的方法是撤消或挂起一些进程。以回收一些资源,再将它们分配给处于阻塞状态的进程,使之转为就绪状态
4、避免死锁——银行家算法
- 可利用资源向量Available。它是一个含有 m个元素的数组,其中每个元素代表一类 可利用资源的数目。
- 最大需求矩阵Max。n*m矩阵,表示n个进程的每一个对m类资源的最大需求。
- 分配矩阵Allocation 。n*m矩阵,表示每个进程已分配的每类资源的数目。
- 需求矩阵Need 。n*m矩阵,表示每个进程还需要各类资源数。
银行家算法步骤:
当进程Pi提出资源申请时,执行下列步骤:
(1)若Requesti[j]≤Need[i,j],转(2);否则错误返回
(2)若Requesti[j] ≤Available[j],
转(3);否则进程等待
(3)假设系统分配了资源,则有:
Available [j] :=Available [j] -Requesti[j];
Allocation[i,j]:=Allocation[i,j]+Requesti[j];
Need[i,j]:=Need[i,j]-Requesti[j]
(4)执行安全性算法。
若系统新状态是安全的,则完成分配;
若系统新状态是不安全的,则恢复原状态,进程等待
安全性算法步骤:
(1) Work[j]:=Available[j];
Finish[i]:=false;(2) 寻找满足下列条件的i:
a). Finish[i]=false;
b). Need[i,j]≤Work[j];
如果不存在,则转(4)
(3) Work[j] :=Work[j]+Allocation[i,j];
Finish[i]:=true;
转(2)
(4) 若对所有i,Finish[i]=true,则系统处于安全状态,否则处于不安全状态
可得: Need[i,j]= Max[i,j]- Allocation[i,j]
例:
设系统有五个进程和三类资源,每类资源分别有10、5、7。在T0时刻资源分配情况如下:
T0时刻可以找到一个安全序列<P1, P3, P4, P2, P0>,系统是安全的。
P1发出请求Request(1,0,2),执行银行家算法
可以找到一个安全序列{P1,P3,P4,P0,P2},系统是安全的,可以将P1请求资源分配给它。
若是:P4发出请求Request(3,3,0), 执行银行家算法
Available=(2 3 0)
不能通过算法第2步( Requesti[j]≤Available[j] ),所以P4等待。
例:如下:若P0发出请求Request(0,2,0),执行银行家算法
Available{2,1,0}已不能满足任何进程需要,所以系统进入不安全状态,P0的请求不能分配。
练习题:有三类资源A(17)、B(5)、C(20)。有5个进程P1~P5。T0时刻系统状态如下:
问:
(1)、T0时刻是否为安全状态,给出安全系列。
(2)、T0时刻,P2: Request(0,3,4),能否分配,为什么?
(3)、在(2)的基础上P4:Request(2,0,1),能否分配,为什么?
(4)、 在(3)的基础上P1:Request(0,2,0),能否分配,为什么?
解:(1) T0时刻的出安全系列
先求出Need和Work
(2) P2: Request(0,3,4)
因(Available =2 3 3)< Request(0,3,4) 所以不能分配。
(3) P4:Request(2,0,1) Available =2 3 3
有安全序列P4 P5 P3 P2 P1 可以分配
(4) P1:Request(0,2,0)
0 1 2 已不能满足任何进程的需要,不能分配