操作系统课程设计的_模拟银行家算法,绝对独一无二

湖南工业大学

课 程 设 计

资 料 袋

计算机与通信 学院（系、部） 2011 ~ 2012 学年第 2 学期 课程名称 操作系统 指导教师 左新娥 职称 讲师

学生姓名 刘 耀 澳 专业班级 计算机科学与技术 学号 09408100327 题 目 模拟银行家算法

成 绩 起止日期 2011 年 12月 19 日～ 2011 年 12月 24 日

目 录 清 单

序号 1 2 3

材 料 名 称 课程设计任务书 课程设计说明书 课程设计图纸 资料数量 备 注 1 1 张 湖南工业大学

课程设计任务书

2011 — 2012 学年第 2 学期

计算机与通信 学院（系、部） 计算机科学与技术 专业 09-3 班级 课程名称： 操作系统

设计题目： 模拟银行家算法

完成期限：自 2011 年 12 月 19 日至 2011 年 12 月 24 日共 1 周

一、课程设计目的 通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。 二、课程设计内容 编制银行家算法程序，并检测所给状态的系统安全性。 内 容 及 任 务 进 度 安 排 主 要 参 考 资 料 起止日期 工作内容 确定银行家算法所需的数据结构和算法分析 2011-12-19~2011-12-20 2011-12-20~2011-12-21 根据算法画出流程图，然后编码实现算法 2011-12-22~2011-12-24 对程序的调试、修改、改进。编写设计说明书 [1] 孟庆昌，牛欣源——编著。操作系统（第二版）。电子工业出版社。2010-10. [2] 徐虹，何嘉，张钟澎——编著。操作系统实验指导——基于Linux内核（第二版）。清华大学出版社。2009-08. 指导教师（签字）： 年 月 日 系（教研室）主任（签字）： 年 月 日

2

操作系统

课程设计说明书

模拟银行家算法

起止日期： 2011 年 12 月 19 日 至 2011 年 12 月 24日

学班学成

生姓名 级 号 绩

**** 计算机 09-3班 ***********

指导教师(签字)

计算机与通信 学院（部） 2011年 12月 24日

计算机与通信学院课程设计

一、课程设计目的

通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。

二、课程设计内容

编制银行家算法程序，并检测所给状态的系统安全性。

三、算法的原理

银行家算法是一种最有代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。 那么什么是安全序列呢？

安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i ) 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

1）对用银行家算法来避免死锁的方法有较深入的了解，给出系统的初始状态，模拟避免死锁的动态过程。

2）银行家算法中的数据结构

4

计算机与通信学院课程设计

（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj类资源K个。

（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。

（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。

（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i，j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

上述三个矩阵存在如下关系：

Need[i,j]= Max[i，j]- Allocation[i，j]

3）银行家算法

设Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

（1）如果Request[i，j]<= Need[i，j]，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request[i，j]<= Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。

（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]= Available[j]- Request[i，j]；

Allocation[i，j]= Allocation[i，j]+ Request[i，j]； Need[i，j]= Need[i，j]- Request[i，j]；

（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

4）安全性算法

系统所执行的安全性算法可描述如下：

（1）设置两个向量：①工作向量Work：它表示系统可提供给进程继续运行

5

计算机与通信学院课程设计

所需要的各类资源数目，它含有m个元素，在执行安全算发开始时，Work=Available；②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false；②Need[i，j] <= Work[j]；若找到，执行步骤（3），否则，执行

步骤（4）。

（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]= Work[i]+ Allocation[i，j]； Finish[i]=true； go to step 2；

（4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

5）银行家算法程序流程图如图3.1所示，银行家算法所用数据可参考ppt上的例子。

四、数据流程图

6

计算机与通信学院课程设计

图一、银行家算法程序流程图

五、源程序代码

源代码：

#include

using namespace std; #define F 0 #define T 1

7

计算机与通信学院课程设计

int main() {

int n,m,i,j;

n=4;m=3; //// 定义进程总数和资源类总数。 int Available[3]; ///可利用的各类的资源数。

int Max[4][3]; ////每个进程对每类资源的最大需求数。 int Allocation[4][3]; /////每个进程已分配的各类资源个数。。 int Need[4][3]; ///// 每个进程还需要每类资源的个数。 ////////////////

int Request[4][3]; ///// 每个进程对每类资源的申请的个数。 int Work[3]; //////// 在安全性算法中表示可利用的资源个数。 int Finish[4]; ////在安全性算法中每个进程的完成情况。 ///////////

int securityArithmetic(int *Work,int *Available,int *Finish,int Need[][3],int

Allocation[][3],int n,int m); ////安全性算法的子程序的声明。 ///////////下面是输入资源分配表的情况。

cout<<\"input the Available: \"<cout<<\"input the Allocation ,Max ,Need :\"</////////////////

////////下面是输入某个进程对每类资源的申请个数。。 int Request_Num=0; int thedoing;

cout<<\"读入请求分配资源的进程个数 Request_Num :\"; cin>>Request_Num; ///输入申请资源的进程个数。

for(j=0;jcout<<\"Allocation[\"<cin>>Allocation[i][j];cout<cin>>Max[i][j];cout<cin>>Need[i][j];cout<cin>>Available[j]; cout</////下面是输入各类资源的已分配的、最大需求的、现在还需要的资源个数。

8

计算机与通信学院课程设计

cout<int security=T; ///设置一个标志变量，用于判断对i号进程的

/////申请预分配后系统是否是安全的。。

int b=1; ///b也是判断标志变量，用于判断是否所有进程的Finish[i]=T. cout<<\"读入 i 进程的资源请求：\";

thedoing=i; ////输入请求资源的进程号。。 cout<cout<<\"输入第\"<cin>>i;

cin>>Request[i][j]; ///输入i进程对各类资源的申请个数。

//////////////

///进程 i 的资源预分配

int aa=1; ///控制变量aa是用于判断是否能对i进程的申请进行预分配。 for(j=0;jif(aa=1) ///如果aa=1,即所申请的<所需要的，并且所申请的<可利用的。 { ////就可进行预分配。

for(j=0;j{ ////下面是进行预分配时所要改变的相关变量参数。 Available[j]= Available[j]- Request[i][j]; { }

aa=0;

if (!(Request[i][j]<=Need[i][j] && Request[i][j]<=Available[j]))

Allocation[i][j]= Allocation[i][j]+ Request[i][j]; Need[i][j]= Need[i][j]- Request[i][j];

}

else ////如果不能进行预分配，则退出循环，结束程序。 { cout<<”警告：申请资源个数大于所需的或可利用的个数..”; return 0; }

//////////////////

/// 调用安全性算法，返回一个控制变量，表明是否存在安全序列，是否有安全状态.

////////////////////////////////// if(b==1)

}

b=securityArithmetic(Work,Available,Finish,Need,Allocation, n,m); ///////如果有安全序列，b==1，则该进程的此次请求分配可行。

9

计算机与通信学院课程设计

{ for(i=0;i///Finish[i]都置为 F .为下一个进程的申请做准备。

}

else security=F;

if(security==T) ///判断当前进程申请各类资源后系统是否安全。 {

cout<<\"进程\"<cout<<\"进程\"<Available[j]= Available[j]+ Request[i][j];

Allocation[i][j]= Allocation[i][j]- Request[i][j]; Need[i][j]= Need[i][j]+ Request[i][j]; }

///////////定义安全性算法子程序 Allocation[][3],int n,int m) {

int i,j;

for(i=0;ifor(j=0;j////////下面的 a、b、c 都是控制标志变量。 int b=1;

Work[j]=Available[j]; Finish[i]=F;

int securityArithmetic(int *Work,int *Available,int *Finish,int Need[][3],int

}

return 0; ///对每个申请资源的进程进行了银行家算法后，程序结束。。

}

Request_Num--; //申请的进程数量减一，进行下一个进程的资源预分配和系统安全性判断。

int a=1; ///标志某一进程目前还需要的各类资源<可利用的个数。

int d;

for(d=0;dfor(i=0;iint c=0; ///标志Finish[c]=T 的进程号。

10

计算机与通信学院课程设计

}

{

a=1; {

for(j=0;j//////判断i 进程的所需的所有的资源是否＜可利用的。。

if(Need[i][j]<=Work[j]) c=i; else a=0;

}

if(Finish[c]==F && a==1) ////如果所需＜可用的，且Finish==F，则进程

{ /// i 就释放其占有的资源。。 for(j=0;jWork[j]=Work[j]+Allocation[c][j]; Finish[c]=T; }

}

b=1;

for(i=0;iif(Finish[i]==T) ;///是否所有进程都能运行完成。 else b=0; } }

return b; ///返回标志目前系统是否安全的标志变量 b .

///////////分配是安全的。。。

六、程序运行结果显示

（1）、资源分配表情况 进程 0 1 2 3 资源 Allocation R0 R1 R2 1 0 0 5 1 1 2 1 1 0 0 2 Max R0 R1 R2 3 2 2 6 1 3 3 1 4 4 2 2 Need Available R0 R1 R2 R0 R1 R2 2 2 2 1 0 2 1 1 2 1 0 3 4 2 0 （2）、运行结果

1、输入可利用的资源数：Available。然后输入每个进程

的 ：Allocation的资源个数。Max的资源个数。Need的资源个数。

11

计算机与通信学院课程设计

2、 当把资源分配表的情况输入完后，再输入要请求分配资源的进程的个数，这里我输入了2，表示有两个进程请求资源。再输入请求资源的进程号，然后再输入请求的各类资源的个数，但不能超过Available 中的个数。我的输入是： 1号进程，请求各类资源数为：1、0、2 。照理论是安全的。和运行结果一样的。然后再输入：0号进程，请求各类资源数为：0、1、1 。因为这时Available已经变成：0、1、0. 所以0号进程请求后就处于不安全状态了。。

12

计算机与通信学院课程设计

七、总结

经过几天的自己动手练习，对操作系统的掌握又进了一步，收获了很多课堂上和书上未出现过的或老师未讲到的一些知识。在完成实验的过程中，进行了反复的修改和调试，这次实验，让我基本上明白了银行家算法的基本原理，加深了对课堂上知识的理解，也懂得了如何让银行家算法实现，但编程功底的原因使程序很是繁琐。 银行家算法是这样的：

1）当一个用户对资金的最大的需求量不超过银行家现有的资金时就可以接纳该用户。

2）用户可以分期贷款，但贷款的总数不能超过最大需求量。

13

计算机与通信学院课程设计

3）当银行家现有的资金不能满足用户的尚需贷款时，对用户的贷款可推迟支付，但总能使用户在有限的时间里得到贷款。

4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有资金。 我们把操作系统看作是银行家，操作系统管理的资源相当于是银行家管理的资金，则银行家算法就是：

1）当一个进程首次申请资源时，测试该进程对资源的最大的需求量，如果不超过系统现存资源时就可以按他的当前申请量为其分配资源。 否则推迟分配。 2）进程执行中继续申请资源时，测试该进程占用资源和本次申请资源总数有没有超过最大需求量。超过就不分配，没超过则再测试现存资源是否满足进程还需要的最大资源量，满足则按当前申请量分配，否则也推迟分配。

总之，银行家算法要保证分配资源时系统现存资源一定能满足至少一个进程所需的全部资源。这样就可以保证所有进程都能在有限时间内得到需要的全部资源。这就是安全状态。

参考文献

[1] 庞丽萍.《操作系统原理》[M]. 武汉：华中科技大学出版社，2008 [2] 杨树青,王欢.《Linux环境下C编程指南》[M]. 北京：清华大学出版社，2007

[3] 陈维兴,林小茶. 《C++面对对象程序设计教程》[M]. 北京：清华大学出版社，2004

[4]杨路明. 《C语言程序设计教程》[M]. 北京：北京邮电大学出版社，2005

14