【面试题】银行家算法

admin 发表于 2013-5-23 15:36:05

本人比较白痴，很多问题不明觉厉，听到有筒子说实习面试中遇到[银行家算法]，感觉很拉风的样子，遂搜索之，并与大家分享，一起学习。@admin
static/image/hrline/5.gif

URL: http://zh.wikipedia.org/wiki/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95
(维基有个不错的例子，一看就懂，建议看一下，)
银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死結產生的演算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
背景在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
安全和不安全的状态
如果所有过程有可能完成执行（终止），则一个状态（如上述范例）被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下，这是一个合理的假设，因为系统不是特别关注每个进程运行了多久（至少不是从避免死锁的角度）。此外，如果一个进程终止前没有获取其它能获取的最多的资源，它只是让系统更容易处理。基于这一假设，该算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想集合，来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
static/image/hrline/line6.png
static/image/hrline/line6.png

一、实验目的银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法二、实验要求根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效地防止和避免死锁的发生。设计思想说明:设计银行家算法是为了避免死锁三、实验方法内容1. 算法设计思路银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待 2. 算法中用到的数据结构数据结构的说明1.可利用资源向量AVAILABLE。这是一个含有M个元素的数组，其中的每一个元素代表一类可利用的资源数目，其3初始值是系统中所配置的该类全部可哦那个资源的数目，其数值随该类资源的分配和回收而动态的改变。2.最大需求矩阵MAX。这是一个M*N的矩阵，它定义了系统中N个进程中的每一个进程对M类资源的最大需求。3.分配矩阵ALLOCATION。这也是一个M*N的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。4.需求矩阵NEED。这也是一个M*N的矩阵，用以表示每一个进程尚需的各类资源数。5.NEED=MAX-ALLOCATION 3. 主要的常量变量#define W 10 //最大进程数W=10#define R 20 //最大资源总数R=20 int AVAILABLE; //可利用资源向量int MAX; //最大需求矩阵int ALLOCATION; //分配矩阵int NEED; //需求矩阵int Request; //进程请求向量void changdata(int k);//进程请求资源数据改变intchksec(int s); //系统安全性的检测4. 主要模块 void inputdata()void showdata()void changdata(int k)void restoredata(int k) int chksec(int s)int chkmax(int s) 四、实验代码#include <string.h>#include <iostream.h>#define FALSE 0#define TRUE 1#define W 10 //最大进程数W=10#define R 20 //最大资源总数R=20int M ; int N ; int ALL_RESOURCE; int AVAILABLE; //可利用资源向量int MAX; //最大需求矩阵int ALLOCATION; //分配矩阵int NEED; //需求矩阵int Request; //进程请求向量void inputdata(); //数据输入 void showdata(); //数据显示 void changdata(int k);//进程请求资源数据改变void restoredata(int k); //数据恢复intchksec(int s); //系统安全性的检测intchkmax(int s); //检测最大需求 void bank(); //检测分配的资源是否合理 void main(){int i,j; inputdata(); for(i=0;i<M;i++) { j=chksec(i); if (j==0) break; } if (i>=M)cout<<"错误提示：经安全性检查发现，系统的初始状态不安全！！！\n"<<endl; else {cout<<"提示：经安全性检查发现，系统的初始状态安全！"<<endl; bank(); }}void inputdata(){ int i=0,j=0,p; cout<<"请输入总进程数:"<<endl; do{ cin>>M; if (M>W) cout<<endl<<"总进程数超过了程序允许的最大进程数，请重新输入:"<<endl; }while (M>W); cout<<endl; cout<<"请输入资源的种类数:"<<endl; do {cin>>N; if (N>R) cout<<endl<<"资源的种类数超过了程序允许的最大资源种类数，请重新输入:"<<endl; }while (N>R); cout<<endl; cout<<"请依次输入各类资源的总数量，即设置向量all_resource:"<<endl; for(i=0;i<N;i++) cin>>ALL_RESOURCE; cout<<endl; cout<<"请依次输入各进程所需要的最大资源数量，即设置矩阵max:"<<endl; for (i=0;i<M;i++) { for (j=0;j<N;j++) { do {cin>>MAX; if (MAX>ALL_RESOURCE) cout<<endl<<"该最大资源数量超过了声明的该资源总数,请重新输入:"<<endl; }while (MAX>ALL_RESOURCE); } } cout<<endl; cout<<"请依次输入各进程已经占据的各类资源数量，即设置矩阵allocation:"<<endl; for (i=0;i<M;i++) { for (j=0;j<N;j++) { do{cin>>ALLOCATION; if (ALLOCATION>MAX) cout<<endl<<"已占有的资源数量超过了声明的最大资源数量,请重新输入:"<<endl; }while (ALLOCATION>MAX); } } cout<<endl; for (i=0;i<M;i++) for(j=0;j<N;j++) NEED=MAX-ALLOCATION; for (j=0;j<N;j++) { p=ALL_RESOURCE; for (i=0;i<M;i++) { p=p-ALLOCATION; AVAILABLE=p; if(AVAILABLE<0) AVAILABLE=0; } }}void showdata(){int i,j; cout<<"各种资源的总数量，即向量all_resource为:"<<endl; cout<<" "; for (j=0;j<N;j++) cout<<" 资源"<<j<<": "<<ALL_RESOURCE; cout<<endl<<endl; cout<<"当前系统中各类资源的可用数量，即向量available为:"<<endl; cout<<" "; for (j=0;j<N;j++) cout<<" 资源"<<j<<": "<<AVAILABLE; cout<<endl<<endl; cout<<"各进程还需要的资源数量，即矩阵need为:"<<endl<<endl; for (i=0;i<M;i++) { cout<<"进程P"<<i<<": "; for (j=0;j<N;j++) cout<<NEED<<" "; cout<<endl; } cout<<endl; cout<<"各进程已经得到的资源量，即矩阵allocation为: "<<endl<<endl; for (i=0;i<M;i++) { cout<<"进程P"<<i<<": "; for (j=0;j<N;j++) cout<<ALLOCATION<<" "; cout<<endl; } cout<<endl;}void changdata(int k){ int j; for (j=0;j<N;j++) { AVAILABLE=AVAILABLE-Request; ALLOCATION=ALLOCATION+Request; NEED=NEED-Request; }} void restoredata(int k) { int j; for (j=0;j<N;j++) { AVAILABLE=AVAILABLE+Request; ALLOCATION=ALLOCATION-Request; NEED=NEED+Request; }} int chksec(int s){ int WORK,FINISH; int i,j,k=0; for(i=0;i<M;i++) FINISH=FALSE; for(j=0;j<N;j++) { WORK=AVAILABLE; i=s; do { if(FINISH==FALSE&&NEED<=WORK) { WORK=WORK+ALLOCATION; FINISH=TRUE; i=0; }else { i++; } }while(i<M); for(i=0;i<M;i++) if(FINISH==FALSE) { return 1; } }return 0; }int chkmax(int s) { int j,flag=0; for(j=0;j<N;j++) { if (MAX==ALLOCATION) { flag=1; AVAILABLE=AVAILABLE+MAX; MAX=0; } } return flag;} c { int i=0,j=0; char flag='Y'; while(flag=='Y'||flag=='y') { i=-1; while(i<0||i>=M) { cout<<"请输入需申请资源的进程号（从P0到P"<<M-1<<"，否则重新输入!）:"; cout<<"p"; cin>>i; if(i<0||i>=M) cout<<"输入的进程号不存在，重新输入!"<<endl; } cout<<"请输入进程P"<<i<<"申请的资源数:"<<endl; for (j=0;j<N;j++) { cout<<"资源"<<j<<": "; cin>>Request; if(Request>NEED) {cout<<"进程P"<<i<<"申请的资源数大于进程P"<<i<<"还需要"<<j<<"类资源的资源量!"; cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; flag='N'; break; } else { if(Request>AVAILABLE) {cout<<"进程P"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!"; cout<<"申请不合理，出错!请重新选择!"<<endl<<endl; flag='N'; break; } } } if(flag=='Y'||flag=='y') { changdata(i); if(chksec(i)) { cout<<endl; cout<<"该分配会导致系统不安全!!! 本次资源申请不成功，不予分配!!!"<<endl; cout<<endl; restoredata(i); } else { cout<<endl; cout<<"经安全性检查，系统安全，本次分配成功，且资源分配状况如下所示："<<endl; cout<<endl; showdata(); if(chkmax(i)) {cout<<"在资源分配成功之后，由于该进程所需的某些资源的最大需求量已经满足，"<<endl; cout<<"因此在进程结束后系统将回收这些资源！"<<endl;cout<<"在资源收回之后，各进程的资源需求和分配情况如下所示："<<endl; showdata(); } } } cout<<endl; cout<<" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: "; cin>>flag; }} 五、实验结果结果分析银行家算法就是当接收到一个系统资源的分配后找到一个安全序列，使得进程间不会发生死锁，若发生死锁则让进程等待。六、实验总结通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。实验中遇到点问题，通过查阅资料、询问老师顺利解决。通过这次的实践，使我的理论知识更加的牢固。

hslx111 发表于 2013-5-23 17:22:01

面试的时候让手写这么长的代码那我就直接pass了= =

xywhere 发表于 2013-5-23 17:38:50

还真没玩过银行家算法代码呢 ...

vo_ 发表于 2013-5-23 17:46:05

哎似曾相识的回忆。。。又不太相熟。。。{:6_208:}

明月生寒 发表于 2013-5-23 18:13:00

银行家算法最坏情况下的时间复杂度是O(n^3)，所以实际中用的比较少。。

admin 发表于 2013-5-23 18:32:45

明月生寒发表于 2013-5-23 18:13
银行家算法最坏情况下的时间复杂度是O(n^3)，所以实际中用的比较少。。

不明觉厉，学习了，能说明下怎么算出来的吗

世俗的程序员 发表于 2013-5-23 21:47:29

哇，居然能有代码写出银行家算法，真牛、、{:5_120:}

jijunjie 发表于 2013-5-24 22:55:59

只懂理论，代码不会。。。

页: [1]

软院网 RuanYuan.Net's Archiver

【面试题】银行家算法