操作系统课程设计银行家算法.docx

操作系统课程设计银行家算法.docx

《操作系统课程设计银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计银行家算法.docx（24页珍藏版）》请在冰点文库上搜索。

操作系统课程设计银行家算法

操作系统课程设计报告

题目：

银行家算法

院（系）：

专业：

班级：

学生：

学号：

指导教师：

2010年12月

操作系统课程设计报告

题目：

银行家算法

院（系）：

专业：

班级：

学生：

学号：

指导教师：

2010年12月

银行家算法

摘要

本次的课程设计内容是银行家算法，在操作系统当中，由于竞争非剥夺性资源和进程推进的不当，对系统的安全造成威胁，所以，银行家算法就是为了避免对系统产生死锁而存在的。

银行家算法包括对请求资源的试分配和对安全性的考量，当系统的安全性不能够满足的时候，则对系统进行保护。

在编写银行家算法的时候需要定义Need（需求矩阵），Allocation（分配矩阵），Max（最大需求矩阵）以及Available（可利用资源量）。

在实现一系列的功能的时候使用的数组的结构，便于进行矩阵的加减运算，可以提高程序的运行效率。

通过编写可以基本上实现银行家算法所要达到的基本目的，在输入正确的情况下能够输出正确的安全序列，在不安全的情况下可以做出提醒，并且恢复原有输入数据。

关键字：

银行家算法最大需求矩阵分配矩阵需求矩阵可利用资源量

摘要…………………………………………………………….…（i）

1绪论………………………………………………………………

（1）

2需求分析………………………………………………………...…

（2）

2.1问题描述…………………………………………………...…

（2）

2.2产生条件…………………………………………………...…

（2）

2.3运行环境…………………………………………………...…

（2）

2.4程序功能…………………………………………………...…

（2）

3概要设计………………………………………………………..…（3）

3.1程序模块………………………………………………….........（3）

3.2模块调用关系………………………………………………......（3）

3.3数据结构…………………………………………………...…..（3）

3.4算法细想………………………………………………….........（4）

4详细设计………………………………………………………...…（5）

4.1模块划分……………………………………………………….（5）

4.2数据判断……………………………………………………….（5）

4.3函数调用…………………………………………………...…..（5）

4.4程序流程图…………………………………………………...…（6）

5测试与分析……………………………………………………….（8）

5.1程序调试………………………………………………………..（8）

5.2程序测试…………………………………………………...…..（8）

6实验心得………………………………………………………….（9）

7参考文献………………………………………………………….（10）

附录：

源程序清单……………………………………………………（11）

1绪论

银行家算法是操作系统当中为避免锁死的算法，并且是最具有代表性的避免锁死的算法，能够有效的在资源分配的过程中，对系统的安全性进行检测。

整个算法的计算步骤为对输入的数据进行试分配，并对安全性进行检测，当系统为安全的时，依照安全序列执行程序，如果不安全则进入阻塞状态。

银行家算法的来源是在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。

银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。

在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

在避免死锁的方法中，所施加的简直条件比在预防死锁的方法中限制条件要弱，有可能获得令人满意的系统性能。

在该方法中，把系统的状态分为安全状态和不安全状态，只要能使系统都处于安全状态，就可避免死锁的发生。

所谓安全状态与不安全状态是指如果所有过程有可能完成执行（终止），则一个状态被认为是安全的。

由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。

2需求分析

2.1问题描述：

在多道程序系统中，虽然能够借助于多个进程的并发执行，来改善系统资源的利用率，提高系统的吞吐量，但是依然有风险存在，那就是——锁死。

所谓锁死是指，多个进程在运行中因争夺资源而造成的一种僵局，当进程的这种僵持状态时，若无外力作用，它们将无法再向前推进。

一组程序中，每个进程都无限等待被该组进程中的另一进程所占有的资源，因而永远无法得到资源，这种现象就叫做进程死锁。

2.2产生条件：

1、进程间竞争非剥夺性资源

2、

2.3运行环境

VisualC++6.0

2.4程序功能

在该程序中应该具有以下功能：

1、从外界输入进程数，资源数以及完成银行家算法的所需的各类资源数。

2、当输入越界或者非法输入时能够提示错误。

3、当进程推进处于不安全状态时要能够进行提示处于不安全状态，并且能够恢复数据到初始状态。

当请求资源量大于可利用资源数时要能够进行提醒，并且重新输入。

4、当数据完成初始化时，要能够输出数据所对应的矩阵。

3概要设计

3.1程序模块

本程序包括了四个基本模块：

主函数、试分配、安全性测试、数据的输入与输出。

3.1.1主函数

主函数用于输出系统的主要操作界面，以及调用其他的函数，完成银行家算法。

3.1.2试分配：

对输入的进程的Max、Available、Allocation以及Request进行分配，判断是否可以正常分配。

3.1.3安全性测试：

当试分配完成时，通过安全性测试来对系统的安全性进行检测，安全时输出安全序列，不安全时进行提醒，并且恢复到初始化时输入的数据。

3.2模块之间关系

主函数可以调用系统的所有函数，以及输出功能界面，将试分配函数，安全性测试函数和输入输出函数定义在主函数当中，在需要时通过相应的选项进行调用。

而试分配与安全性测试是并列的两个函数，存在执行试分配后需对安全序列进行判断。

输入输出函数，确定数值，并将相对应的数据输入到对应的模块，来进行计算。

3.3数据结构

程序当中需要四种数据结构。

1、可利用资源矩阵（Available），当Available[]=k时，这表示系统中有该类资源k个。

2、最大需求矩阵（Max），当Max[][]=k时，则表示进程需要的资源为k个。

3、分配矩阵（Allocation），当Allocation[][]=k时，则表示进程当前已被分得k个资源。

4、需求矩阵（Need），当Need[][]=k时，则表示进程还需要k个资源才能够完成。

3.4算法思想

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。

当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。

若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

4详细设计

4.1程序模块划分：

4.1.1数据的初始化：

根据提示输入最大需求矩阵（Max），可利用资源量（Available），分配矩阵（Allocation）所需的数据。

4.1.2输出所对应的矩阵：

根据输入的数据输出对应的矩阵，并且计算出需求矩阵（Need），将完整的算法需要的数据呈现给操作者。

4.1.3试分配：

根据操作者所输入的进程号已经请求，对系统进行时分配。

4.1.4安全测试

当试分配完成时可进行安全性测试，当进程间是安全的时候则可以输出相应的安全序列。

如果错误，则可以回到数据的初始化状态。

4.2数据判断

当输入的数据不符合规定时，可以对该数据进行判断，不符合条件重新输入，例如：

if（!

（0<=in&&in<=t-1）），在程序中，用于判断所输入的进程号是否满足要求，如果不满足要求通过该语句输出“cout<<"该进程不存在,重新输入"<

4.3函数调用

通过switch语句对所调用的函数进行判断。

switch（choice）

{

case1:

Input（）;break;//输入相关数据函数

case2:

Print（）;break;//打印输出相关数据表函数

case3:

cout<<"请输入有请求的进程号:

"break；

case4:

checksafe（in）;break;//安全性检查

case5:

refenpei（in）;break;//恢复数据

}

4.4程序流程图

4.4.1数据初始化流程图

4.4.2安全性流程图

5测试与分析

5.1程序调试:

1、在数据初始化当中要考虑到输入进程数是否为负数，是否为字符。

2、在安全性算法当中要考虑到当不安全时，数据能否恢复，是否可以重新进行分配。

当输入的Request大于Need或者大于Available的情况，当大于是需要重新输入。

5.2程序测试:

5.2.1输入初始化：

5.2.2矩阵输出

5.2.3安全序列输出

5.2.4进程不安全时

6实验心得

操作系统是计算系组成当中最为重要的系统软件，只有操作系统的存在在能够使得计算机能够有正常有序的进行工作，操作系统对于计算机来说是各项活动的组织者和指挥者。

而银行家算法的存在则是为了保证这个系统能够正常的安全的进行工作的保证。

我们可以把操作系统看成是银行，而银行家算法则可以看成是银行的管理者，而各类资源则可以看成时银行的资金，而进程则是客户。

作为管理者的银行家算法则需要使得在银行的资金，即操作系统的资源进行正常有序的分配，以保证操作系统能够正常运转。

并保证在进程有足够的资源进行运转。

操作系统按照银行家制定的规则进行资源分配，当进程首次申请资源是，要测试进程对最远的最大需求是多少，如果系统现有的资源能够满足，则最该进程分配资源，否则推迟分配。

当进程在执行过程，依然要求分配资源时，则先测试该进程已占用的资源数与需求数是否超过了该进程的最大需求。

若超过，应该拒绝分配资源。

银行家算法作为系统资源的保障，起着举足轻重的作用，所以多银行家算法必须有深入的了解，从而认识操作系统的工作过程。

7参考文献

[1]计算机操作系统（第三版）汤小丹梁红兵哲凤屏汤子瀛编著西安电子科技大学出版社

[2]软件工程王长元李晋惠等编著西安地图出版社

[3]操作系统原理孟庆昌等编著机械工业出版社

附录：

源程序清单：

#include

#defineM10//资源类数

#defineN50//进程数

voidInput（）;//用于输入的函数

voidPrint（）;//用于打印输出表格的函数

voidtryfenpei（inti）;//试分配函数

voidchecksafe（intx）;//安全检测函数

voidrefenpei（inti）;//恢复数据函数

//定义初始化数组

intAvailable[M],

Max[N][M],

Allocation[N][M],

Need[N][M],

Request[M];

intc,t;//资源进程

intin;//用户选择的进程号

/*----------------------------------------------------------------*/

voidmain（）

{

intchoice;

charch='Y';

cout<<"输入资源数：

";

cin>>c;

cout<<"输入进程数：

";

cin>>t;

do

{

if（ch=='Y'||ch=='y'）

{

cout<<"银行家算法"<

cout<<"1:

输入所需数据"<

cout<<"2:

显示矩阵"<

cout<<"3:

试分配"<

cout<<"4:

检查安全性"<

cout<<"5:

恢复数据到初始状态"<

cout<<"**********************"<

cout<<"请选择操作序号：

";

cin>>choice;

switch（choice）

{

case1:

Input（）;//输入相关数据函数

break;

case2:

Print（）;//打印输出相关数据表函数

break;

case3:

cout<<"请输入有请求的进程号:

";

while（cin>>in）

{

if（!

（0<=in&&in<=t-1））

{

cout<<"该进程不存在,重新输入"<

}

elsebreak;

}

tryfenpei（in）;//试分配

break;

case4:

checksafe（in）;//安全性检查

break;

case5:

refenpei（in）;//恢复数据

break;

default:

cout<<"请（1-5）中选择正确的操作序号!

"<

break;

}

cout<<"要继续进行吗?

（y-是n否）";

}

elseif（ch=='N'||ch=='n'）

{

cout<<"正在退出..."<

break;

}

else

{

cout<<"输入无效!

重新输入..."<

}

}while（cin>>ch）;

}/*---------------------main函数结束----------------------------------*/

/*--------------------------输入函数----------------------------------*/

voidInput（）

{

intj,n,m;

cout<<"输入可利用资源:

"<

for（j=0;j

{

//cout<<"请输入Available["<

";

while（cin>>Available[j]）

{

if（Available[j]<0）

cout<<"输入数字无效，请重新输入"<

elsebreak;

};

}

cout<<"输入最大需求:

"<

for（n=0;n

{

for（m=0;m

{

while（cin>>Max[n][m]）

{

if（Max[n][m]<0）

cout<<"输入数字无效，请重新输入"<

elsebreak;

};

}

}

cout<<"输入占有资源:

"<

for（n=0;n

{

for（m=0;m

{

while（cin>>Allocation[n][m]）

if（Allocation[n][m]<0）

cout<<"输入数字无效，请重新输入"<

elsebreak;

Need[n][m]=Max[n][m]-Allocation[n][m];

}

}

cout<<"初始化完成!

..."<

}/*-------------------------输入函数结束----------------------------------*/

/*-------------------------输出函数----------------------------------*/

voidPrint（）

{

inti,j;

cout<<"|*****|*************|*************|**********|*************|"<

cout<<"|*****|||||"<

cout<<"|进程|Max|Allocation|Need|Available|"<

cout<<"|*****|*************|*************|**********|*************|"<

for（i=0;i

{

cout<<"|p"<

for（j=0;j

{

cout<

}

cout<<"|";

for（j=0;j

{

cout<

}

cout<<"|";

for（j=0;j

{

cout<

}

cout<<"|";

if（i==0）

{

for（j=0;j

{

cout<

}

cout<<"|";

}

if（i>0）

{

cout<<"|";

}

cout<

}

cout<<"|*****|*************|*************|**********|*************|"<

}/*-------------------------输出函数结束--------------------------------*/

/*-------------------------试分配函数----------------------------------*/

voidtryfenpei（intn）

{

inti;

cout<<"您输入的是"<<"p["<

cout<<"该进程需求量为：

";

for（i=0;i

cout<

cout<

cout<<"请输入请求资源的数目:

";

for（i=0;i

{

while（cin>>Request[i]）

{

if（Request[i]<0）

{

cout<<"!

!

输入的数字无效."<

}

elseif（Request[i]>Need[n][i]）

{

cout<<"!

!

超出进程需求量"<

}

elseif（Request[i]>Available[i]）

{

cout<<"!

!

系统没有足够的可用资源量满足进程需要"<

}

elsebreak;

}

}

cout<<"输入成功，输入的是：

";

for（intf=0;f

cout<

cout<

cout<<"执行银行家算法，进行试分配..."<

for（f=0;f

{

Available[f]=Available[f]-Request[f];

Allocation[n][f]=Allocation[n][f]+Request[f];

Need[n][f]=Need[n][f]-Request[f];

}

cout<<"试分配完成!

"<

}/*-------------------------试分配函数结束----------------------------------*/

/*-------------------------安全检测函数----------------------------------*/

voidchecksafe（intx）

{

cout<<"进入安全性检测..."<

inti,m,apply,j,k=0,flag=0;

intWork[M],temp[N];

boolFinish[N];//t为进程数

for（i=0;i

{

Work[i]=Available[i];

}

for（i=0;i

{

Finish[i]=false;

}

for（i=0;i

{

apply=0;

for（j=0;j

{

if（false==Finish[i]&&Need[i][j]<=Work[j]）

{

apply++;//标记是否所需的资源都得到满足

if（apply==c）

{

for（m=0;m

{

Work[m]=Work[m]+Allocation[i][m];//变分配数w=w+a

}

Finish[i]=true;

temp[k++]=i;//将满足的进程号存入temp[]数组中

i=-1;//若有进程满足条件则从头开始寻找

}

}

}

}

for（i=0;i

{

if（Finish[i]==false）

{

cout<<"试分配后系统不安全本次资源申请不成功"<

cout<<"等待恢复原来的数据..."<

refenpei（in）;

return;

}

}

cout<