银行家算法-实验报告

银行家算法

一、 课题内容和要求

内容：

银行家算法是操作系统中一种最有代表性的用来避免死锁的算法。该算法在资源分配前进行安全性检测，保证系统处于安全状态，从而避免死锁。

此次课程设计的主要内容是实现算法模拟银行家算法，模拟实现动态资源分配，编写和调试一个系统动态资源的简单模拟银行家算法程序程序，观察死锁产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。从而，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 要求：

 模拟一个银行家算法；

 了解算法中用的各种数据结构；  系统的初始状态信息从文本文件读取；

 判断是否存在安全序列，输出任意一个安全序列即可；  判断系统是否可以满足进程的请求。

二、需求分析

银行家算法在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。 本次课程设计的目的是通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁地发生。 总体要求如下：

①了解算法中用的各种数据结构；②系统的初始状态信息从文本文件读取；③判断是否存在安全序列，输出任意一个安全序列即可；④判断系统是否可以满足进程的请求。

Nanjing University of Posts and Telecommunications

- 1 -

课程设计I -----银行家算法

【要了解银行家算法，必须先了解操作系统安全状态和不安全状态。

安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。】

三、概要设计

 银行家算法的原理

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全，银行家规定：

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；

(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；

(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。  银行家算法中用到的主要数据结构： 1.可利用资源向量Available

int Available[j] //如果Available[j]=K，则表示系统中现有Rj类资源K个。 2.最大需求矩阵Max

int Max[i][j] //如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

Nanjing University of Posts and Telecommunications

- 2 -

课程设计I -----银行家算法

3.分配矩阵Allocation

int Allocation[i][j] //如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。 4.需求矩阵Need

int need[i][j]= Max[i][j]- Allocation[i][j] //如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

5.申请各类资源数量 int Request i[j] //i进程申请j资源的数量 6.工作向量 int Work[x] int Finish[y]  银行家算法的实现：  初始化

由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。  银行家算法

在避免死锁的方法中，所施加的条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转（3)；否则，出错。

(3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i]; NEED[cusneed][i]-=REQUEST[cusneed][i];

Nanjing University of Posts and Telecommunications

- 3 -

课程设计I -----银行家算法

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

(5)用do{…}while 循环语句实现输入字符y/n判断是否继续进行资源申请。  安全性检查算法 safe（）函数

(1)设置两个工作向量Work=AVAILABLE;FINISH

(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED<=Work;如找到，执行（3)；否则，执行（4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO 2

(4)如所有的进程Finish= true，则表示安全；否则系统不安全。

 算法流程图：

初始化函数init()结束Nanjing University of Posts and Telecommunications - 4 - 初始化函数init()Init()开始 输入进程的数目m n 输入资源的种类 输入资源的种类输入进程的数目m n 输入每个进程最多所需的各资源数 输入每个进程已分配的各资源数 true 输入各个资源现有的数目 输出提示：输入有误，请重新输入 课程设计I -----银行家算法

输出请求向量无法 满足 N 银行家算法bank() 选一个进程作为当前进程 输入该进程的请求向量 Request[i]<=Need[jc][i]||Request[i]<=All[i] 调用safe（） 输出系统未能成分配资源, 收回预分配资源 Y 系统试探着把资源分配给该进程 银行家算法bank()结束 您还想再次请求分配吗?是请按y/Y,否请按其它键 输出系统成功分配资源 All[i]=All[i]+Request[i];Allocation[jc][i]=Allocation[jc][i]-Request[i];Need[jc][i]=Need[jc][i]+Request[i]; Nanjing University of Posts and Telecommunications

- 5 -

课程设计I -----银行家算法

安全性算法safe()函数

安全性算法safe（）结束 输出安全序列 Finish[i]=TRUE; Finish[i]==FALSE)Work=All; Finish[i]=FALSE; N &&needed==1 Y Work[j]=Work[j]+Allocation[i][j]; 输出系统是不安全的 N Y 输出系统是安全的 Nanjing University of Posts and Telecommunications

- 6 -

课程设计I -----银行家算法

四．详细设计

 程序结构

程序共有以下几个部分：  主程序main()

逐个调用初始化、显示状态、安全性检查、银行家算法函数，使程序有序的进行。  初始化init()

用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。  银行家算法bank()

进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程。  当前安全性检查safe()

用于判断当前状态安全性，根据不同地方的调用提示处理不同。  函数声明

void init(); //系统初始化函数 void safe(); //安全性算法函数 void bank(); //银行家算法函数 void main(); //主函数

 数据结构

程序使用的一些变量：

int m; //m资源种类数 int n; //进程数

int Available[x]; //各种资源可利用的数量

int Allocation[y][y]; //各进程当前已分配的资源数量 int Max[y][y]; //各进程对各类资源的最大需求数 int Need[y][y]; //还需求矩阵 int Request[x]; //申请各类资源的数量

int Work[x]; //工作向量，表系统可提供给进程运行所需各类资源数量 int Finish[y]; //表系统是否有足够的资源分配给进程，0为否，1为是 int p[y]; //存储安全序列

int i,j; //全局变量，主要用于循环语句中 int jc; //任选一个进程

int all=0; //定义变量all，如果all==0，表示进程已经运行完，如果all>=1，表示还有进程没有运行完

const int x=10，y=10； //定义常量

Nanjing University of Posts and Telecommunications

- 7 -

课程设计I -----银行家算法

 源代码

#include //标准的输入输出流头文件 #include //实际上是引用c library #include //它是I/O流控制头文 using namespace std; //定义标识符

#define TRUE 1 //定义 TRUE =1 #define FALSE 0 //定义 FLASE=0

void bank(vector,vector >,vector >,int ,int ); //声明银行家算法bank

int safe(vector All,vector > Need,vector > Allocation,int n,int m);//声明safe（）安全性算法 void init(); //声明初始化函数

/*************************************主函数

main()**************************************************************/ void main() { init(); //设定初值 int safe(vector All,vector > Need,vector > Allocation,int n,int m); }

/**************************************初始化函数

init()*********************************************************/ void init() { int m; //m资源类数 int n; //进程数 cout<<\"输入资源类数\"<>m; vector All(m); //动态申请数组All可用资源向量 cout<<\"输入各类资源总数:\"<>n; Nanjing University of Posts and Telecommunications

- 8 -

课程设计I -----银行家算法

vector > Max(n, vector(m)); /***********************************************************************************************************/ fp=fopen(\"Max.txt\ cout<<\"从Max.txt文件中读入数据，并输出\"< > Allocation(n, vector(m)); vector > Need(n, vector(m)); /************************************************************************************************/ fp=fopen(\"Allocation.txt\ cout<<\"Allocation.txt从文件中读入数据，并输出\"< All,vector > Need,vector > Allocation,int n,int m); cout<<\"此状态安全!\"<Nanjing University of Posts and Telecommunications

- 9 -

课程设计I -----银行家算法

/*******************************************银行家算法bank()函数******************************************************/

void bank(vector All,vector > Need,vector > Allocation,int n,int m) { vector Request(m); int all=0; //定义变量all，如果all==0，表示进程已经运行完，如果all>=1，表示还有进程没有运行完 for (int i=0;i=1，表示还有进程没有运行完 //循环直至all>0,即找到一个未运行完的进程 cout<<\"任选一个进程作为当前进程0--\"<>jc; for (int j=0;j>Request[i]; while(Request[i]>Need[jc][i]||Request[i]>All[i]) Nanjing University of Posts and Telecommunications

- 10 -

课程设计I -----银行家算法

{ cout<<\"请求向量无法满足\"<>again;

if(again=='y'||again=='Y') {

all=0; continue; }

break; } }

Nanjing University of Posts and Telecommunications

- 11 -

课程设计I -----银行家算法

/**************************************安全性算法safe()函数*********************************************************/

int safe(vector All,vector > Need,vector > Allocation,int n,int m) { vector Work(m),Finish(n),count(n); //申请工作向量work，finish,安全序列数组count[n] Work=All; //Work代表 可用资源数, 把总资源数ALL当做可用资源数Available int len=-1; //记录安全序列的进程个数，如果len==n，即表示所有的finish[i]=true，处于安全状态 for(int i=0;i- 12 -

课程设计I -----银行家算法

}

cout<\"; } } cout<五、测试数据及其结果分析

1. 初始化结果

Nanjing University of Posts and Telecommunications

- 13 -

课程设计I -----银行家算法

2. 检测系统资源分配是否安全结果：

Nanjing University of Posts and Telecommunications

- 14 -

课程设计I -----银行家算法

3. 结果分析 ：结果正确，符合本次课程设计要求

六、调试过程中的问题

第一次完成编程后，运行时候只能手动输入相应矩阵，这样如果遇见很大的矩阵会增加很长的输入时间。经过查阅资料，进行调试之后，实现了从文件中读入数据，这样大大减少了工作量。设计程序时候要考虑到方便用户的操纵控制并减少用户的记忆负担。在友好度方面，进行了不断的改进，以确保用户能清晰地看清程序的运行结果，运行过程。但是我并没有去美化界面设计，不过操作起来还算是简单清晰。

在调试程序时候，还出现了一些死循环，导致程序无法运行。本程序涉及的模块较多，一定要要注意实参的调用以及返回值的控制，不然在运行时极容易出错。仔细分析原来是程序少了system(\"pause\")的语句。

注意：有些指令C里可以用，但C++不能运用。所以平时要注意积累。 在设计程序中遇见不懂得问题，一定要请教老师或者查阅资料，往往一个错误会导致一连串的错误。我在开始做的时候，就没有把握好程序模块之间调用的先后，一度导致了程序难以运行。后来我画出了程序实现的流程图，清晰明了地掌握了程序的脉络，编写起来也轻松多了。

个人认为此次设计的代码还是可以优化的，但是由于知识有限，希望可以通过将来的学习，继续完善本段代码。

七、参考文献和查阅的资料

 参考文献：

[1] 《操作系统教程》[M]. 黄刚、徐小龙、段卫华 人民邮电出版社，2009 [2] 《Linux环境下C编程指南》[M].杨树青,王欢. 清华大学出版社，2007 [3] 《C++面对对象程序设计教程》[M]. 陈维兴,林小茶. 清华大学出版社，2004 [4] 《C语言程序设计教程》[M]. 杨路明. 北京：北京邮电大学出版社，2005 [5] 《数据结构--使用C++语言描述》第二版 陈慧南主编 人民邮电出版社，2008 [6] 百度

Nanjing University of Posts and Telecommunications

- 15 -

课程设计I -----银行家算法

八、程序设计总结

银行家算法是一种能有效避免死锁的算法，是一个分配资源的过程，使分配的序列不会产生死锁。其基本原理已经在《操作系统教程》这门课学过并且基本掌握。但是用编程算法来实现，还是第一次，所以一开始没啥头绪。后来又重新研究了一下书本上的银行家算法，并上网查了一些资料。经过仔细的分析，初步确定使用C++实现这个程序的功能。确定了基本模块的使用以及各个模块之间的调用关系，逐渐地构建好了程序的框架。

自己的编程能力还是不够的，平时没有主动去自己做一些编程，本次课程设计使用C++程序来模拟操作系统上的常用算法。在本次课程设计之前，对于操作系统我还是有很多不了解的地方，对于银行家算法也只是肤浅的了解吧。但是通过本次课程设计，经过与老师、同学沟通，图书馆、网上查阅资料，我很快地详细地了解了银行家算法的具体知识，并对数据结构、C++等知识进行了充分的复习。

编程时经验的积累是很重要的，尤其是基础性知识也是要经常巩固的，温故才能知新嘛。我还认为特别重要的是编程的思想，银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。掌握编程的思想不仅仅是解决一个题目，而是对整体思维的锻炼和知识的提升。当然了，只有自己亲自动手做才能从中获益。

本次课程设计在老师和同学的帮助下顺利完成，个人的力量是很重要，但是团队的力量更加强大高效，在此感谢敬爱的老师和我可爱的组员们！

课程设计已经结束，但是从中学到的知识、总结的经验都会影响我对编程的热爱和学习。希望以后能有机会多多接触此类的课程设计。

Nanjing University of Posts and Telecommunications

- 16 -