Dijkstra银行家算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Dijkstra银行家算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2613字，纯文字阅读大概需要4分钟。

内容图文

Conclusion

作为OS设计的检测死锁的一个基本算法，这个算法其实是通过破坏环路等待
这个条件来避免死锁。死锁的避免核心在于本算法的安全算法。

我想写一写关于这个算法的一些理解吧，安全算法就是在对请求资源的进程进行资源试分配后，是否可以产生一个安全序列。安全序列这个理解起来比较生涩。

想想一个很简单的情况，系统有2个资源$r_1,r_2$r1?,r2?,进程A,B必须同时需要两个资源才能完成任务，那么因为不合理的进程调度（可能发生的事情总会发生）。
A持有$r_1$r1?,B持有$r_2$r2?,这是最简单的环路等待模型。

不存在一个安全序列的意思就是在阻塞的进程中，剩下的系统资源的情况下，找不到任何一个进程作为突破口，让其运行完成并释放资源，来解开这个死结。或者换一句话说，即使将剩下的系统资源全部交给任何一个进程，都没办法让此进程脱离阻塞。

这个结论和安全序列是等价的。
比如定义一个记法:
$P_1->P_2$P1??>P2?定义为$P_1$P1?进程获得系统资源运行完成并释放使$P_2$P2?成功运行完毕，并进而也释放资源。
存在安全序列可以叙述为：
系统剩余资源全部交给某个进程$P_i$Pi?使得:
$P_i->P_j->....P_n (i,j,n \in group)$Pi??>Pj??>....Pn?(i,j,n∈group)
这里$&lt;i,j,....n&gt;$<i,j,....n>代表进程组内所有进程的一个排列。

那么不安全序列也可以推理为不存在进程$P_i$Pi?使得:
$P_i-&gt;P_j-&gt;....P_n (i,j,n \in group)$Pi??>Pj??>....Pn?(i,j,n∈group)

银行家算法简记

可用资源向量Available,记录系统可用的n类临界资源

类型	$r_1$r1?	$r_2$r2?	…	$r_n$rn?
数量	9	5	2	8

三种进程数乘资源种类的$i*j$i?j矩阵。
分别存储最大需求MAX，已分配Allocated，还需要Need

kind & process	$r_1$r1?	$r_2$r2?	…	$r_n$rn?
$p_1$p1?
$p_1$p1?
…
$p_m$pm?

假如某时刻系统处于安全状态，此时一个进程A申请临界资源，其请求向量Request[A]包含对各个资源的需求量。首先按照常识，系统对其资源进行试探分配。
并在分配后，检测此种情况下，系统是否存在安全序列。

分配算法伪码：

   /**Finish用作标识此进程在获取剩余系统资源下，能否顺利完成**/
   Boolean Secure-Check(SystemResource,Finish){
         Copy Avaliable into Work;
         for process in Queue{
              Finish[i]=false;  //假设所有进程不能顺利完成
         }
         while(CheckQForFinish!=NULL){
                 Finish[i.ProcessID]=true;
                 for j=n downto 1{
                        Work[j]=Work[j]+Allocated[i.ProcessID,j];
                  }
         }
         //检测是否集合内所有进程是否全可完成
         for Process in Queue{
               if(Finish[Process.ID]==false){
                    return false;
               }
         }
         return true; //假如没有返回false,说明存在安全序列，那么已分配资源操作不用回滚了。
    }
    /**检测是否有未在推测中顺利完成**/
    Process CheckQForFinish(){
            Process i=NULL;
            for Process in Queue{
                 if(Finish[ProcessID]==false){  //检测未可在推测中顺利完成的进程
                      boolean fit=true;
                      for j=1 to n{   //检测N种资源
                           if(Need[i,j]>Work[j]){
                                 fit=false;//只要有一种资源不满足需求设为false
                           }
                      }
                      //通过N次资源检测，还是true,进程可完成，交付给调用者
                      if(fit==true){
                           i=Process;
                           return i;
                     }
                }
            }
            return i;  //此时未能找到符合条件的进程，返回空。
    }

内容总结

以上是互联网集市为您收集整理的Dijkstra银行家算法全部内容，希望文章能够帮你解决Dijkstra银行家算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---