银行家算法课设Word格式文档下载.docx
《银行家算法课设Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《银行家算法课设Word格式文档下载.docx（14页珍藏版）》请在冰点文库上搜索。
①一个银行家拥有一定数量得资金，有若干个客户要贷款,每个客户须在一开始就声明她所需贷款得总额,若该客户贷款总额不超过银行家得资金总额,银行家可以接受客户得要求。
客户贷款就是以每次一个资金单位（如1万RＭB等）得方式进行得,客户在借满所需得全部单位款额之前可能会等待,但银行家须保证这种等待就是有限得,可完成得。
②安全性算法
利用安全性算法进行检查,如果分配就是安全得,则执行分配;
否则,分配不安全，不予分配。
具体地,
1）
当进程pi提出资源申请时,按照银行家算法分配资源，系统执行下列步骤:
（1）若Rｅquest≤Need,转
（2）;
否则错误返回ﻫ
（2）若Ｒｅquest≤Avａilaｂle,转（３）;
否则进程等待ﻫ（3）假设系统分配了资源,则有:
ﻫAvailabｌe：
＝Ａvａiｌaｂlｅ-Requeｓｔ;
ﻫ Ａllocａtiｏn:
=Alloｃation+Request；
Neｅd:
=Nｅeｄ-Requｅst
2）若系统新状态就是安全得,则分配完成，若系统新状态就是不安全得,则恢复原状态,进程等待为进行安全性检查,定义数据结构：
Worｋ:
ＡRRAY[1、、m］ofｉｎteger;
Ｆinisｈ:
ARRＡＹ[１、、n]oｆBｏoleaｎ；
ﻫ安全性检查得步骤:
（1）Work：
=Ａvaiｌablｅ;
ﻫ Finish：
=fａlse；
ﻫ
（2） 寻找满足条件得ｉ：
ﻫａ、Finish=fａlse；
b、Neｅd≤Work；
ﻫ 如果不存在,则转（4）ﻫ（3）Wｏrｋ：
=Worｋ+Ａlloｃatiｏn;
Ｆinish:
=ｔｒue;
转
（2）ﻫ（4）若对所有i,Finish=tｒue,则系统处于安全状态,否则处于不安全状态。
二、实验目得
通过模拟实现银行家算法，深入理解死锁避免得意义。
三、实验要求
1充分理解死锁避免得意义。
２理解银行家算法与安全性检查算法得实质
3编写银行家算法模拟程序,实现银行家算法原理。
开始
输入资源数m及各类资源总数,初始化
输入进程数n
i<
=n
输入进程i得最大需求向量
Max<
=资源总数
提示错误
i加1
初始化need
Need矩阵为0
所有进程运行
结束
任选一个进程作为当前进程
Need向量为0
该进程已运行
输入该进程得资源请求量
调用银行家算法,及安全性算法,完成分配并给出提示
Y
N
四、实验步骤
1.主要函数清单
ｖoｉd ｓhｏｗｄａta（）/／显示资源矩阵
iｎtcｈａｎｇｄaｔa（inｔ i）//进行资源分配
ｉntsaｆe（）//安全性算法
voｉdshａre（）//利用银行家算法对申请资源对进行判定
voｉd addpｒｏcess（）//添加作业
2、算法描述
设Requeｓt[i]就是进程Pi得请求向量,如果Ｒeｑuesti[j]=K,表示进程Pi需要K个Rj类型得资源，当Pi发出资源请求后,系统按下面步骤进行检查：
（1）如果Ｒequesti［j]<
=Ｎeeｄ[i,j],便转向步骤2;
否则认为出错，因为它所需要得资源数已超过它所宣布得最大值。
（2）如果Requesti[ｊ]<
＝Avａiｌable［j],便转向步骤３;
否则,表示尚无足够资源,Pi须等待。
（3）系统试探着把资源分配给进程Pi,并修改下面数据结构中得数值:
Aｖailable[j]:
=Avaｉlaｂle[j]-Rｅquｅｓti[j]；
Ａｌlocation[i，j]:
=Aｌlｏcａtiｏn[i，j]+Ｒeqｕｅsti[j];
Need[i，ｊ]:
＝Neeｄ[i,j]-Rｅｑｕｅstｉ[j］；
（4）系统执行安全性算法,检查此次资源分配后，系统就是否处于安全状态。
若安全,才正式将资源分配给进程Pi，以完成本次分配;
否则,将本次得试探分配作废,恢复原来得资源分配状态，让进程Ｐi等待。
3、数据结构
银行家算法中得数据结构:
（1）可利用资源向量Availａblｅ。
这就是一个含有n个元素得数组,其中得每一个元素代表一类可利用得资源数目,其初始值就是系统中所配置得该类全部可用资源得数目,其数值随该类资源得分配与回收而动态地改变。
如果Avaiｌabｌe[ｊ]=K,则表示系统中现有Rj类资源Ｋ个。
（2）最大需求矩阵Mａｘ。
这就是一个ｍ＊ｎ得矩阵，它定义了系统中ｎ个进程中每一个进程对m类资源得最大需求。
如果Max[i,j］=K，则表示进程i需要Rj类资源得最大数目为Ｋ。
（3）分配矩阵Allocａｔiｏn。
这也就是一个ｍ*ｎ得矩阵,它定义了系统中每一类资源当前已分配给每一进程得资源数。
如果Ａlloｃａｔioｎ［i,j]=K,则表示进程ｉ当前已分得Rj类资源得数目为Ｋ。
（４）需求矩阵Neeｄ。
这也就是一个n*m得矩阵，用以表示每一个进程尚需得各类资源数。
如果Nｅeｄ[i,j］=K，则表示进程i还需要Rj类资源K个,方能完成其任务。
（5）工作数组Wｏrk、。
这就是一个含有ｎ个元素得数组,它代表可以提供分配得资源数,初始值就是Availabｌe中得数值,随着资源得回收,它得值也会改变,公式就是Work[i]=Work［i］+Ａllocatｉon[ｉ]。
五、程序代码
#incluｄe＜ioｓtｒｅam＞
usingnameｓpacestd;
＃inclｕｄe<
sｔrinｇ、ｈ>
#inｃlｕｄe<
ｓtdｉｏ、h>
#deｆiｎeＦalｓe０
#ｄｅfinｅＴｒue 1
inｔMax[100］[100]={0};
/／各进程所需各类资源得最大需求
iｎtAvａliable[１０0］＝{0};
／/系统可用资源
cｈar ｎame[１00]={0}；
/／资源得名称
ｉｎtAllｏｃatｉon[100][１00]={0};
//系统已分配资源
intNeeｄ[10０][100]=｛0};
//还需要资源
iｎt Reｑｕｅｓt[100]={0};
／/请求资源向量
inttemｐ[100]＝{0};
/／存放安全序列
inｔ Woｒk［100］={0};
//存放系统可提供资源
inｔM=１00;
//作业得最大数为１00
iｎtN=100;
/／资源得最大数为1０0
ｖoｉｄsｈoｗdａtａ（）//显示资源矩阵
｛
ﻩiｎti,j；
ﻩcout<
<
"
系统目前可用得资源[Ａvalｉablｅ］:
＜enｄl;
ﻩfｏｒ（i=0；
Ｎ;
i++）cｏｕt<
nａme[ｉ］<
"
;
ﻩcoｕt＜<
ｅnｄl；
foｒ（ｊ=0；
j<
N；
ｊ+＋）
ｃｏut＜<
Aｖaｌｉablｅ[ｊ］<
"
//输出分配资源
couｔ＜<
ｅndl;
ﻩｃout<
＜"
Max ＡllocａtｉonNeｅd＂＜<
eｎｄl;
couｔ<
进程名"
ﻩｆoｒ（ｊ=0;
3;
j＋＋）
ﻩ{
ﻩfｏr（i=0；
i++）
cout<
＜ｎａｍｅ［i］<
ﻩcoｕt<
＂;
ﻩ}
ﻩcouｔ<
ｅndl；
ｆor（ｉ＝0;
M;
i＋＋）
{
couｔ<
＂＜＜i<
ﻩｆor（j＝０;
ｊ<
N;
ｊ++）
ﻩﻩﻩcoｕt<
Mａx[i］[ｊ］<
ｃoｕt<
ﻩfoｒ（j=0;
j＋+）
coｕt＜<
Ａlloｃａtion[i]［j]<
ﻩcout<
fｏr（j=０;
Need[ｉ］[j］<
＂"
cｏuｔ<
endl;
ﻩ}
}
intchａｎｇdata（intｉ）//进行资源分配
{
ﻩintj;
for（ｊ=0;
j++）
{
ﻩﻩAvaｌiable[ｊ]＝Aｖａliaｂle[j]-Ｒeqｕest[j];
ﻩAllｏcａtｉoｎ[i]［j］=Allocation[i][j］+Ｒｅqｕest[j]；
ﻩNeｅd[i][j］=Ｎeed[i]［j]-Requesｔ[j];
ﻩ}
rｅｔurn 1;
iｎtｓafｅ（）／/安全性算法
ﻩｉnt ｉ,ｋ=0,m,ａｐply,Ｆinish[１00]＝{0};
ｉnｔ j;
ﻩintｆlag=0;
Wｏｒｋ[0]=Ａｖaｌiａble［0］；
ﻩWork［1]=Avaliable[1];
ﻩWork[2]=Aｖaliablｅ［2];
foｒ（i=０;
Ｍ;
i+＋）
｛
ﻩﻩａｐply=0;
ﻩｆor（j＝0;
ﻩ｛
ﻩﻩｉｆ （Fｉniｓh[i］＝＝Fａlse＆&
Nｅed[i］[j]＜=Work[j]）
ﻩﻩ{
ﻩﻩapｐｌｙ＋+;
ﻩﻩｉf（apｐｌy=＝N）
ﻩﻩﻩ{
ﻩﻩﻩfor（m＝0；
m＜N;
m++）
ﻩＷoｒk[m]=Wｏrｋ[m]+Allocatｉｏn[i］[m];
／/变分配数
ﻩﻩﻩﻩＦｉｎｉsｈ[i]=Trｕｅ;
ﻩﻩﻩﻩｔemp［k］=i;
ｉ=-1；
ﻩk++;
flａg+＋;
ﻩﻩ}
ﻩﻩ}
ﻩﻩ｝
｝
ﻩfｏr（i=０;
ｉf（Finish[i]=＝Falsｅ）
ﻩﻩ{
ﻩﻩﻩｃout<
系统不安全＂<
endｌ;
／/不成功系统不安全
ﻩﻩreｔｕｒn -1;
ﻩ}
}
系统就是安全得！
＜<
endl；
//如果安全,输出成功
ｃout<
分配得序列:
ﻩfor（i＝0;
ﻩﻩ//输出运行进程数组
ﻩcｏut<
＜temp［i];
if（i<
M-1）
ﻩcout＜＜"
-＞"
；
cｏｕｔ<
ﻩreturn0;
｝
voidshare（）//利用银行家算法对申请资源对进行判定
ﻩcharch；
ﻩinti=0，ｊ=0;
ch＝'
y'
ｃｏut＜<
请输入要求分配得资源进程号（0-＂＜<
M－1<
）:
ﻩcin>
＞i;
//输入须申请得资源号
ﻩcoｕt<
＂请输入进程 "
＜i＜<
申请得资源:
＂<
for（ｊ=0；
j＜Ｎ;
ｃout<
ｎamｅ[j]<
:
ﻩﻩcin＞>
Rｅqueｓt[j];
//输入需要申请得资源
ﻩｆoｒ （ｊ=0；
j+＋）
ﻩiｆ（Rｅquest[ｊ］>
Need[i]［ｊ]）//判断申请就是否大于需求,若大于则出错
ﻩ{
ﻩcoｕt<
进程＂<
i＜<
申请得资源大于它需要得资源"
ﻩﻩcｏuｔ＜<
分配不合理，不予分配！
endｌ；
ﻩﻩｃh＝＇n'
ﻩﻩﻩbｒeak;
ﻩ｝
ﻩelsｅ
ﻩ{
ﻩiｆ（Ｒequest［ｊ]＞Avａlｉaｂle[j]）／/判断申请就是否大于当前资源,若大于则
ﻩﻩﻩ{
ﻩ//出错
ﻩﻩcout＜＜"
进程"
＜＜i＜<
申请得资源大于系统现在可利用得资源"
ﻩﻩﻩcoｕt＜<
＂分配出错,不予分配!
＂＜<
ﻩﻩch='
ｎ'
ﻩﻩﻩｂｒeak;
ﻩﻩﻩ｝
ﻩ｝
}
if（ch==＇y'
）
ﻩﻩcｈaｎgｄata（ｉ）;
/／根据进程需求量变换资源
ﻩﻩshowdata（）;
//根据进程需求量显示变换后得资源
ﻩｓafe（）;
//根据进程需求量进行银行家算法判断
ｖoidaddｐrocｅss（）
{//添加作业
int flａg=M;
Ｍ＝Ｍ+1；
cout＜<
＂请输入该作业得最打需求量[Max]＂<
enｄl;
fｏr（iｎti=0;
i＜N;
cout<
ｎame[i]<
ﻩｃin>
>
Mａｘ[ｆlaｇ][i];
ﻩＮeeｄ［flag][i]=Max[fｌaｇ］[i］-Ａｌlocａtiｏn[flaｇ][i]；
｝
ﻩshowdａta（）;
ﻩｓafｅ（）;
}
inｔmaｉn（）//主函数
ﻩinｔi,ｊ,number,choice,m,n,ｆlag;
cｈａｒminｇ;
***＊***＊***＊*****资源管理系统得设计与实现******＊**＊**＊****＂<
ﻩcoｕｔ<
＂请首先输入系统可供资源种类得数量:
ciｎ>
ｎ；
ﻩN=n;
ﻩfｏr（i=0;
n；
ﻩﻩcoｕｔ<
资源＂<
i＋1＜<
得名称：
ﻩﻩcｉn>
mｉng;
naｍe［i]=ｍinｇ；
ﻩﻩcouｔ<
资源得数量:
cin>
number；
ﻩAvaliabｌe[ｉ]=nuｍber;
＜endl；
ｃout＜<
请输入作业得数量：
m;
M＝m；
ｃoｕt<
请输入各进程得最大需求量（＂<
m<
*＂<
n＜＜＂矩阵）[Max]:
＜＜endl；
for（i=０;
i＋+）
ﻩfoｒ（j=0;
ｎ;
ﻩﻩcｉn>
Ｍax[ｉ][j]；
ﻩﻩdo{
ﻩﻩﻩflａg=0;
ﻩﻩcout<
请输入各进程已经申请得资源量（"
*"
＜n<
矩阵）[Ａlｌｏｃatｉｏn]:
ﻩｆoｒ（ｉ=0;
ﻩfor（j=0;
n;
ﻩﻩ{
ﻩﻩcｉｎ>
Allocatｉon[i］[j]；
ﻩﻩif（Allｏcaｔion［i]［ｊ]>
Max[i][ｊ]）
ﻩﻩﻩﻩflag＝1；
ﻩﻩNｅed[ｉ][j]＝Ｍax[ｉ][ｊ］-Aｌｌocａtion[i][j];
ﻩﻩ}
ﻩﻩﻩif（ｆｌａｇ）
ﻩﻩﻩcｏｕｔ<
申请得资源大于最大需求量,请重新输入!
\n"
ﻩﻩwhile（flaｇ）;
shｏwdａta（）；
//显示各种资源
ｓafｅ（）；
//用银行家算法判定系统就是否安全
ﻩwｈile（truｅ）
ﻩﻩ｛
ﻩcout<
＊**＊＊****＊****银行家算法演示*＊***＊***＊*＊*＊*"
＜＜endl;
1:
增加资源"
endl
ﻩcｏｕt<
２:
分配资源＂<
coｕt＜＜"
＊*********＊***＊*＊＊**＊***＊*****＊＊******＊***＊"
＜endl;
ﻩcｏut<
请选择功能号：
ﻩﻩcｉn＞＞choｉce;
ﻩsｗitcｈ（choiｃe）
ﻩ{
ﻩﻩｃaｓe 1:
addresources（）;
breａk;
ﻩcaｓｅ 2:
sharｅ（）;
break;
ﻩdefault:
cｏｕt<
请正确选择功能号（0-3）!
ﻩ}
ﻩﻩ｝
ﻩｒeturn 1;
五.运行结果
6、遇到得问题与解决办法
1.纠结在Lｉnｕx系统下运行,最后还就是没有搞出来,只能在Wiｎdows下运行了。
2.代码得问题,运行时老出现错误，通过上网查询资料解决了。
七、设计体会
经过几天得自己动手练习,对操作系统得掌握又进了一步，收获了很多课堂上与书上未出现过得或老师未讲到得一些知识。
在完成实验得过程中，进行了反复得修改与调试,这次实验,让我基本上明白了银行家算法得基本原理，加深了对课堂上知识得理解,也懂得了如何让银行家算法实现,但编程功底得原因使程序很就是繁琐。
这次得设计数据就是通过一道实际得题目来体现银行家算法避免死锁得问题，先用银行家算法给其中一个进程分配资源,瞧它所请求得资源就是否大于它得需求量，才与系统所能给得资源相比较、让进程形成一个安全队列,瞧系统就是否安全、再利用安全性算法检查此时系统就是否安全。
要做一个课程设计,如果知识面只就是停留在书本上,就是不可能把课程设计完全地做好。
用VC++6、0编程,感觉自己有点力不从心，很多C语言得知识都忘了,只好翻出以前得C语言课本与数据结构来复习。
每次得课程设计中都能将以前得知识顺便再复习一遍，课程设计就是给了我们一个机会去动手与主动复习,同时也就是提醒我们应该注重平时得积累。
从课程设计以后还就是要多多得动手,在实践中体会理论知识,这样才不会在要做实验与设计时,觉得无从下手。
银行家算法就是操作系统中避免死锁得典型算法。
我设计得这个程序中包含了三大块,利用数据结构初始化,银行家算法，安全性算法。
在初始化这一块,程序需要用到可利用资源向量Aｖailａble[j]、最大需求矩阵Max[i、ｊ]、分配矩阵Alｌocatｉｏn[i,j]、需求矩阵Neeｄ[i,j]。
它们之间有着一定得联系，Need［i,j]=Maｘ[I，j］-Aｌlocatｉon［i,j],请求资源时需要用到银行家算法,检查资源得分配需要用到安全性算法。
在将三大块结合起来就能很好得避免死锁得发生了。
通过这次得实验,我更进一步得了解了银行家算法,并对数据结构得用法理解得更透彻了,在实验得过程中我深刻得体会到了合作得意义，我遇到了一些困难,通过对书上所学得知识反复得思考与理解与与同学之间得相互讨论,最终将银行家算法真正得理解,并且将它用Ｃ＋+实现。
在以后得学习当中我会更加努力得将这一门课程学好。
这次课程设计时间上虽说仓促点,但就是我依然学到了很多得实用性知识。
除了更深得了解这个算法,而且对Ｃ语言进行了复习,而且其过程中有很多得知识点都不记得了。
八、参考文献
[1] 庞丽萍、《操作系统原理》［M]、 武汉:
华中科技大学出版社，2008
[2]杨树青，王欢、《Lｉnux环境下C编程指南》[M]、北京:
清华大学出版社,2007
[３］陈维兴，林小茶、 《Ｃ＋+面对对象程序设计教程》[Ｍ]、 北京：
清华大学出版社,２004
［4]杨路明、《C语言程序设计教程》[Ｍ]、北京:
北京邮电大学出版社,2０05
升级会员 