银行家算法[编辑]
银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。
背景[编辑]
在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。
进程[1][编辑]
Allocation Max Available ABCD ABCD ABCD P1 0014 0656 1520 P2 1432 1942 P3 1354 1356 P4 1000 1750
我们会看到一个资源分配表,要判断是否为安全状态,首先先找出它的Need,Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源),计算结果如下:
NEED ABCD 0642 0510 0002 0750
然后加一个全都为false的字段
FINISH false false false false
接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)
NEED Available ABCD ABCD 0642 1520 0510<- 0002 0750
P2的需求小于能用的,所以配置给他再回收
NEED Available ABCD ABCD 0642 1520 0000 +1432 0002------- 0750 2952
此时P2 FINISH的false要改成true(己完成)
FINISH false true false false
接下来继续往下找,发现P3的需求为0002,小于能用的2952,所以资源配置给他再回收
NEED Available ABCD A B C D 0642 2 9 5 2 0000 +1 3 5 4 0002---------- 0750 3 12 10 6
同样的将P3的false改成true
FINISH false true true false
依此类推,做完P4→P1,当全部的FINISH都变成true时,就是安全状态。
安全和不安全的状态[编辑]
如果所有过程有可能完成执行(终止),则一个状态(如上述范例)被认为是安全的。由于系统无法知道什么时候一个过程将终止,或者之后它需要多少资源,系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下,这是一个合理的假设,因为系统不是特别关注每个进程运行了多久(至少不是从避免死锁的角度)。此外,如果一个进程终止前没有获取其它能获取的最多的资源,它只是让系统更容易处理。
基于这一假设,该算法通过尝试寻找允许每个进程获得的最大资源并结束(把资源返还给系统)的进程请求的一个理想集合,来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
伪代码(pseudo-code)[2][编辑]
P - 进程的集合
Mp - 进程p的最大的请求数目
Cp - 进程p当前被分配的资源
A - 当前可用的资源
while (P != ∅) { found = FALSE; foreach (p ∈ P) { if (Mp − Cp ≤ A) { /* p可以獲得他所需的資源。假設他得到資源後執行;執行終止,並釋放所擁有的資源。*/ A = A + Cp ; P = P − {p}; found = TRUE; } } if (! found) return FAIL; } return OK;
相关推荐
银行家算法避免死锁 VM软件 Linux系统 C语言 成功编译 成功运行 内附完整课设报告,代码,运行cpp 附有哲学家进餐简略一题 原课设要求:死锁避免 (1)请设计一个程序演示死锁避免算法(银行家算法)。 (2)要求该...
课程设计-模拟银行家算法避免死锁.doc
这是计算机操作系统(第三版)关于利用银行家算法避免死锁的代码及程序,利用银行家算法避免死锁是最具代表性的算法(Dijkstra)
本文档是使用C#编写的银行家算法避免死锁的程序设计。里面包含数组初始化,利用递归判断输入整数,输出安全序列等函数,希望对大家有帮助。如有错误,请多多指教~
仿真模拟银行家算法对死锁的避免。 所谓安全状态是指系统能按某种进程顺序,来为每个进程pi分配所需的资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地...银行家算法就是一种最有代表性的避免死锁的算
模拟实现银行家算法避免死锁的过程。 模拟实现银行家算法避免死锁的过程。 2. 实验目的 理解银行家算法,掌握查找进程安全序列的过程,深入理解资源共享、资源分配、资源回收的概念。 实验原理 银行家算法是一种...
《操作系统》第四版汤小丹等人编著,纯C语言编写实现银行家算法,可以自行设置进程相关数据,显示安全序列,可以多次申请资源查看是否安全
本次课程设计通过编写和调试一个仿真模拟银行家算法避免死锁的程序,观察产生死锁的条件,并采用银行家算法,有效地避免死锁的发生。这是我们的操作系统课程设,用.net做的。 银行家算法避免死锁,其中有三个模块,...
这个程序主要通过模拟系统死锁避免的实现,使用银行家算法来避免死锁加深对死锁避免,系统安全状态等的理解。 (1)输入1执行算法,输入2退出程序,其他输入无效。算法要用到的资源种类有10种,每种资源的数目为1~10...
操作系统之--模拟银行家算法实现死锁避免
1)模拟一个银行家算法; (2) 初始化,为系统的各个进程分配资源; (3) 计算此时的安全序列; (4)为某进程申请资源; (5) 预分配后,系统处于安全状态,则修改系统的资源分配情况; (6) 预分配后,系统...
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系银行家算法统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待...
利用银行家算法,有效避免死锁,或检测死锁存在
银行家算法是避免死锁的一种重要方法,通过编写一个简单的银行家算法程序,加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。死锁的产生,必须同时满足四个条件,即一个资源每次...
银行家算法的实现,当输入每类资源的MAX和Allocation,计算是否存在安全序列
实验目的:通过使用银行家算法实现系统资源的分配和安全性检查模拟,深刻理解操作系统的死锁避免算法。 实验原理:银行家算法。 实验仪器:计算机一台。 实验安排:自选编程语言完成“银行家算法”,记录程序运行...
含本人实验报告,有具体流程图,实验课上写的,有更好的想法可以提出,大家一起学习,赚点积分不容易