学习啦>学习电脑>操作系统>操作系统基础知识>

操作系统死锁银行家算法

佳洲分享

  操作系统中死锁是可以通过银行家算法避免的。下面由学习啦小编为大家整理了操作系统的死锁银行家算法的相关知识,希望对大家有帮助!

  操作系统死锁银行家算法详解

  死锁既然不好,我们就可以利用银行家算法避免死锁。

  1.银行家算法中的数据结构

  (1) 可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。

  (2) 最大需求矩阵Max。这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。

  (3) 分配矩阵Allocation。这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得R j类资源的数目为K。

  (4) 需求矩阵Need。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要R j类资源K个,方能完成其任务。

  上述三个矩阵间存在下述关系:

  Need[i, j]=Max[i, j]-Allocation[i, j]

  2.银行家算法

  设Request i是进程Pi的请求向量,如果Request i[j]=K,表示进程P i需要K个R j类型的资源。当P i发出资源请求后,系统按下述步骤进行检查:

  (1) 如果Request i[j]≤Need[i,j],便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

  (2) 如果Request i[j]≤Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi须等待。

  (3) 系统试探着把资源分配给进程P i,并修改下面数据结构中的数值:

  Available[j]:= Available[j]-Request i[j];

  Allocation[i,j]:= Allocation[i,j]+Request i[j];

  Need[i,j]:= Need[i,j]-Request i[j];

  (4) 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

  3.安全性算法

  系统所执行的安全性算法可描述如下:

  (1) 设置两个向量:

  ① 工作向量Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work:=Available。

  ② Finish,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时,再令Finish[i]:=true。

  (2) 从进程集合中找到一个能满足下述条件的进程:

  ① Finish[i]=false;

  ② Need[i,j]≤Work[j];若找到,执行步骤(3),否则,执行步骤(4)。

  (3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

  Work[j]:= Work[j]+Allocation[i,j];

  Finish[i]:=true;

  go to step (2);

  (4) 如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

    3626639