银行家算法

简介:   银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。

  银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

  就像我们从银行贷快一样,首先银行会考虑到我们有没有偿还能力,比如说张三想通过贷款来收藏黄金,李四想搞养殖业,银行家就要考虑到黄金一直走下滑曲线,把钱贷给张三赔的话,张三十有八九赔了,直接导致张三还不起贷款,因此不能贷给张三。然而目前养殖业收益较好而且日后一定时期行情稳定,银行家就会决定把钱贷给李四。

  实例:

  

  分析:

  第一次申请是给P1进程分配6个资源,总的资源就剩余16-6=10,各进程现在需要的资源分别为:8-6=2,5,9,6。剩下的10个资源无论分配给P1,P2,P3还是P4都能使4个进程顺利完成,因此第一次申请不会是系统进入不安全状态。

  第二次申请给P2进程分配4个资源,剩余资源为16-6-4=6,各进程现在需要资源分别为:8-6=2,5-4=1,9,6。剩余的6个资源可以分配给P1,P2,P4。只要有进程结束就会释放其占有的资源,因此第二次申请也不会对系统造成威胁。

  第三次申请给P3进程分配5个资源,剩余资源为:16-6-4-5=1,各进程现在需要资源分别为:8-6=2,5-4=1,9-5=4,6。剩余的一个资源可以分配给P2,P2进程完成过就能释放5个资源供其他进程完成。所以第三次申请也不会对系统造成威胁。

  第四次申请给P4进程分配1个资源,剩余资源为:16-6-4-5-1=0,各系统现在需要资源分别为:8-6=2,5-4=1,9-4=5,6-1=5。剩余0个资源但四个进程都没得到满足,都在请求资源的同时谁都不会释放资源。所以第四次申请会使系统造成死锁。

  假如不申请第四次,直接申请第五次给P1进程分配1个资源,剩余资源为:16-6-4-5-1=0,各系统现在需要资源分别为:8-6-1=1,5-4=1,9-4=5,6。同样剩余0个资源但四个进程都没得到满足,都在请求资源的同时谁都不会释放资源。所以第五次申请也会使系统造成死锁。

  在第四次和第五次申请不成功的情况下,申请第六次给P2分配1个资源,剩余资源为:16-6-4-5=0,各系统现在需要资源分别为:8-6=2,5-4-1=0,9-4=5,6。但是P2进程这时候需要的资源已经能够得到满足,因此P2进程结束后可以释放5个资源供其他进程使用。所以第六次申请也不会对系统造成威胁。

  答案:

  

  操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源,若能满足则按当前的申请量分配资源,否则也要推迟分配。

目录
相关文章
|
6月前
|
API 调度 C语言
C++实现进程调度模拟程序——哲学家进餐问题
C++实现进程调度模拟程序——哲学家进餐问题
138 0
|
3月前
|
算法 安全 Java
银行家算法代码
银行家算法代码
23 0
|
3月前
|
Go
并发陷阱:死锁、活锁和饥饿
并发陷阱:死锁、活锁和饥饿
26 0
|
8月前
|
算法 安全 Java
银行家算法【学习算法】
银行家算法【学习算法】
63 0
|
8月前
|
安全 Linux C++
Linux线程的加锁
Linux线程的加锁
67 0
Linux线程的加锁
|
9月前
|
算法 安全
【软考学习11】死锁问题和银行家算法
【软考学习11】死锁问题和银行家算法
160 0
|
11月前
|
算法 安全
银行家算法
银行家算法
|
算法 安全
秒懂算法 | 银行家算法
最具有代表性的避免死锁的算法是Dijkstra的银行家算法,由于该算法可能用于银行现金贷款而得名。一个银行家把他的固定资金贷给若干顾客,只要不出现一个顾客借走所有资金后还不够,银行家的资金应是安全的。银行家需要一个算法保证借出去的资金在有限时间内可以收回。 假定顾客分成若干次进行贷款,并在第一次贷款时说明他的最大借款额。具体算法如下:
194 0
秒懂算法 | 银行家算法
多线程死锁的产生以及如何避免死锁
指多个线程因竞争资源而造成的一种僵局(互相等待),具体代码就是同步中嵌套了其他同步,这种现象称为死锁:比如过独木桥问题,其他锁还有可重入锁、可中断锁、公平锁和同步锁
130 0
|
算法 安全 Java
银行家算法实现代码
银行家算法Java实现
111 0