美文网首页
一句话+一张图说清楚——银行家算法

一句话+一张图说清楚——银行家算法

作者: 00d1ed2b53ae | 来源:发表于2018-12-03 13:57 被阅读15次

死锁产生的条件:
1)互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。
2)请求和保持条件:指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。
3)不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。
4)环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

一句话介绍银行家算法:
当一个进程申请使用资源的时候,银行家算法通过先 试探 分配给该进程资源,然后通过安全性算法判断分配后的系统是否处于安全状态,若不安全则试探分配作废,让该进程继续等待。

那么此时会有一个问题,如何判断系统是否处于安全状态?算法流程将用下面一张图来表示。

一张图


image.png

首先是银行家算法中的进程:
包含进程Pi的需求资源数量(也是最大需求资源数量,MAX)
已分配给该进程的资源A(Allocation)
还需要的资源数量N(Need=M-A)

Available为空闲资源数量,即资源池(注意:资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量)

假设资源P1申请资源,银行家算法先试探的分配给它(当然先要看看当前资源池中的资源数量够不够),若申请的资源数量小于等于Available,然后接着判断分配给P1后剩余的资源,能不能使进程队列的某个进程执行完毕,若没有进程可执行完毕,则系统处于不安全状态(即此时没有一个进程能够完成并释放资源,随时间推移,系统终将处于死锁状态)。

若有进程可执行完毕,则假设回收已分配给它的资源(剩余资源数量增加),把这个进程标记为可完成,并继续判断队列中的其它进程,若所有进程都可执行完毕,则系统处于安全状态,并根据可完成进程的分配顺序生成安全序列(如{P0,P3,P2,P1}表示将申请后的剩余资源Work先分配给P0–>回收(Work+已分配给P0的A0=Work)–>分配给P3–>回收(Work+A3=Work)–>分配给P2–>······满足所有进程)。

如此就可避免系统存在潜在死锁的风险。

来个例子
在银行家算法中,若出现下述资源分配情况:

注:题中共四种资源,P0的Allocation为(0,0,3,2)表示已分配给P0的第一种资源和第二种资源为0个,第三种资源3个,第四种资源2个。

(1)该状态是否安全? (2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?

(1)利用安全性算法对上面的状态进行分析(见下表),找到了一个安全序列{P0,P3,P4,P1,P2},故系统是安全的。

(2)P2发出请求向量Request(1,2,2,2),系统按银行家算法进行检查:

①Request2(1,2,2,2)<=Need2(2,3,5,6)
②Request2(1,2,2,2)<=Available(1,6,2,2)
③系统先假定可为P2分配资源,并修改Available,Allocation2和Need2向量:
Available=(0,4,0,0)
Allocation2=(2,5,7,6)
Need2=(1,1,3,4)
此时再进行安全性检查,发现 Available=(0,4,0,0) 不能满足任何一个进程,所以判定系统进入不安全状态,即不能分配给P2相应的Request(1,2,2,2)。

相关文章

  • 一句话+一张图说清楚——银行家算法

    死锁产生的条件:1)互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时...

  • 30Aug- 八月读书与笔记总结

    能用一句话说清楚地就尽量不用两句话, 能用一张图说清楚的就尽量不说话。

  • 银行家算法

    银行家算法是一种预防死锁的算法。具体算法步骤可以参考百度百科:银行家算法 例子:某系统有A、B、C、D , 4类...

  • 第二章 数据查找与资源分配算法——银行家算法

    2.4 银行家算法 银行家算法时一种资源分配算法,在操作系统理论中它是一个避免死锁的算法,是以银行借贷系统的分配策...

  • 银行家算法

    银行家算法是避免进程死锁的方法之一。那什么是银行家算法呢? 银行家,他们想的是我把钱贷出去,能不能收的回来,能不能...

  • 死锁的预防算法

    银行家算法银行家算法是一种最有代表性的避免[死锁]的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源...

  • 银行家实现C++算法网络爬虫无死锁调度!

    一、银行家算法与死锁 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在...

  • 第三章 调度算法和死锁

    银行家算法 当一个进程申请使用资源的时候,银行家算法通过先试探分配给该进程资源,然后通过安全性算法判断分配后的系统...

  • 银行家算法

    看一下 你就会了 银行家算法

  • GNSS数据处理常用软件

    一张图说明问题。

网友评论

      本文标题:一句话+一张图说清楚——银行家算法

      本文链接:https://www.haomeiwen.com/subject/aqjycqtx.html