进程死锁——银行家算法

时间:2024-04-03 21:59:14

死锁概念

  一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到该资源,这种现象称为进程死锁(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 已不能满足任何进程的需要,不能分配