操作系统实验-银行家算法.doc

实验三　　银行家算法
一、 实验内容简要描述
1． 实验目标:
加深了解有关资源申请、避免死锁等概念,并体会与了解死锁与避免死锁得具体实施方法.
要求编写与调试一个系统动态分配资源得简单模拟程序，观察死锁产生得条件，并采用银行家算法，有效得防止与避免死锁得发生。
2． 实验要求:
银行家算法就是避免死锁得一种重要方法,本实验要求用高级语言编写与调试一个简单得银行家算法程序。
用银行家算法实现资源分配.
设计五个进程｛ｐ0，p１，ｐ２，ｐ3,p4｝共享三类资源{Ａ，B,C｝得系统，例如，{A，B,C}得资源数量分别为1０，５，７.进程可动态地申请资源与释放资源，系统按进程得申请动态地分配资源，要求程序具有显示与打印各进程得某一个时刻得资源分配表与安全序列;显示与打印各进程依次要求申请得资源号以及为某进程分配资源后得有关资源数据.
二、 报告主要内容
1． 设计思路
A、 设计进程对各在资源最大申请表示及初值确定。
B、 设定系统提供资源初始状态。
C、 设定每次某个进程对各类资源得申请表示。
D、 编制程序,依据银行家算法,决定其申请就是否得到满足。
2． 主要数据结构
假设有M个进程N类资源，则有如下数据结构：
ＭAＸ[M＊N］ M个进程对N类资源得最大需求量
AVAILＡBLＥ［Ｎ］　系统可用资源数
ALLＯCATIOＮ[M*N] M个进程已经得到N类资源得资源量
NEED[Ｍ*N］ Ｍ个进程还需要N类资源得资源量
银行家算法:
设进程I提出请求Reqｕest[N],则银行家算法按如下规则进行判断。
(１）如果Ｒｅquｅst［N］〈=ＮEED［Ｉ，N］,则转(2)；否则，出错。
(2）如果Ｒequeｓt［N］<=AＶAILABLＥ,则转(3）;否则,出错。
（3）系统试探分配资源，修改相关数据:
ＡVＡIＬAＢLE=AＶAILAＢLE—REQUＥＳＴ
ALＬＯCATIＯN=AＬLＯＣATION+RＥQUEＳT
ＮEED=NEＥD－RＥＱUEST
(4) 系统执行安全性检查，如安全,则分配成立；否则试探险性分配作废,系统恢复原状,进程等待。
安全性检查：
（１)设置两个工作向量WORK=AＶAＩLABLE；FINISH［M］＝FALSE
(2）从进程集合中找到一个满足下述条件得进程,
ＦINISＨ［i]＝FALSＥ
ＮＥED<=ＷORK
如找到,执行（3）;否则,执行（4)
（3）设进程获得资源，可顺利执行,直至完成，从而释放资源。
WORK=WORK+ALLOCAＴIOＮ
FINＩSＨ=TRUE
GO TO 2
(４）如所有得进程Ｆinish［M］=truｅ，则表示安全;否则系统不安全。
3. 主要代码
源程序：
＃iｎｃｌude 〈iｏsｔrｅaｍ＞
usinｇ nameｓpace　std;
＃ｄefiｎe MAXＰRＯCEＳS　5０　　 　　 　 ／＊最大进程数＊／
＃dｅfine MＡXRESOURＣE 100　 　 　 　 　 /＊最大资源数＊/
iｎt　AＶＡILABLE［MAＸRESOURＣE]；　 　 　 /*可用资源数组＊/
ｉnt MＡＸ［MAXPROCＥSＳ]［ＭAXRＥＳOURCE］;　 　 　　　　 /＊最大需求矩阵*/
iｎｔ　ALＬＯCATIＯN［MＡXPROCESS］［MAＸRＥSOURCE］;　 　 /*分配矩阵*/
int NＥＥD［MＡXPＲＯCESＳ][MAXREＳOURCＥ]； 　 /*需求矩阵*/
ｉｎt ＲＥQUEＳT[ＭAＸPＲＯCEＳS][MAXRESＯUＲCE]； 　　 　 ／*进程需要资源数＊／
ｂool　FINISＨ［ＭAＸPＲOCEＳS］； 　 　 　 　 　 　 　/＊系统就是否有足够得资源分配＊/
iｎt　p[MAXＰROCEＳS］； 　 　 　 /＊记录序列*／
ｉnｔ ｍ，ｎ; 　　 　 　 　 　　 　 　 /*m个进程,n个资源*/
vｏid　Init（)；
ｂoｏｌ Safe（)；
voｉd Bank(）;
int mａin（)
｛
　 Inｉt（）；
　　 Saｆe（）；
　 　 Ｂank（)；
｝
vｏid Ｉnit(） 　　 　 　 ／*初始化算法*/
{
　 int i，j；
cｏut〈<"请输入进程得数目：＂;
　 cin〉〉m；
cout〈〈"请输入资源得种类:”;
cin＞＞ｎ；
　　 cｏｕt<〈"请输入每个进程最多所需得各资源数，按照”〈〈m<＜"ｘ"<〈n〈<”矩阵输入"＜〈ｅｎdl;
fｏr（i=0；i＜m；ｉ＋+)
　　 for（j＝０;j〈n；j+＋）
cin>>MAX［i]［j]；
　cout〈＜"请输入每个进程已分配得各资源数,也按照”〈〈m〈<"ｘ”＜＜n<〈＂矩阵输入”<〈endl;
　 foｒ（i=0;i＜m；ｉ+＋)
　 ｛
　 　 for（j=0;j<ｎ；j++）
　 　 {
　 　 cin〉＞ALLＯＣATION［i］［ｊ］;
　　　 　 　 　 NEＥD[i]［j］=ＭAX[i］[j]－ALＬOCATIＯN[i］[j]；
　 　　 　ｉf（NＥED[i][j］<０）
　 　 {
　　 　　 cｏut<＜”您输入得第”〈〉AVＡILAＢLE［i］；
}
}
void Banｋ（) 　　 　 　　 　 /＊银行家算法/
{
　iｎｔ　i，cusnｅed;
　　 ｃhar ａgaiｎ；
　ｗhｉle(1)
　 ｛
　 　　　 ｃoｕt<＜＂请输入要申请资源得进程号（注：第个进程号为,依次类推）"〈〈ｅndl；
　 cin〉>cusｎｅｅｄ;
　 　 couｔ<〈＂请输入进程所请求得各资源得数量"〈 ｛
　 　if(ＲEQＵＥST[cusneed]［ｉ]>NEＥＤ［ｃusｎeed][i］）
　 　 ｛
　 　 　 　cｏｕt〈<”您输入得请求数超过进程得需求量！请重新输入！"〈＜enｄl;
　　 　 ｃoｎtｉnue;
　 　 ｝
　 　 ｉf（REＱUEＳT［cusｎeed]［i]>AＶAIＬＡBLＥ［i］）
{
　　 　 couｔ〈〈＂您输入得请求数超过系统有得资源数！请重新输入！"〈〈endｌ；
　　 　 　 　 continｕe；
　　 　 　 ｝
　 　 }
　 　　for（i＝０；ｉ同意分配请求！"<〈ｅｎｄl；
　 　 ｝
　 　 else
　 　 ｛
　 　 　cout<〈”您得请求被拒绝!"<i];
　 　 　 ｝
　 　 }
　 　 for（ｉ=0;ｉ＜m；i+＋）
　 　｛
　 　 　FＩNIＳH［i］=falsｅ;
　 　　 ｝
　 ｃouｔ〈〈"您还想再次请求分配吗?就是请按y/Y,否请按其它键＂〈＜endl；
　 ciｎ〉＞agaiｎ;
ｉf(ａgain==’ｙ'||again=='Y')
{
　 　　 ｃｏntinuｅ;
　　 ｝
　 　 brｅａk;
　 ｝
｝
bool Safe 　　 　　 　 　 　 　　 　　 ／＊安全性算法*/
｛
inｔ i，j，ｋ,l＝０；
iｎt Woｒk[MAXRＥＳOURＣＥ］; 　 　　　 　 　 /＊工作数组*/
　fｏr(i=０；i＜n;ｉ+＋）
　　 Work[i］=ＡVAＩLABＬE[i]；
　 for（i＝0；i〈m；ｉ+＋)
　ＦＩNISH［i］=falｓe;
　 　for(i=0;ｉ<ｍ;i++）
｛
　 　 　　 　if（FINISH［i］==true)
continue；
　 　 else
　 　 ｛
　　　　　 　　 fｏr（j=０;j〈n；j++）
｛　 if(NEED[i][j]>Wｏrｋ［j])
　 　 　 　 break；
ﻩ ｝
　 if（j=＝n）
　 　 ｛
　　 　 FINISH［i]＝trｕｅ；
　　 　　 　　　 　foｒ（ｋ＝０；ｋ〈n；ｋ＋＋)
　 　 Worｋ［k］＋=AＬLOCＡＴIOＮ［i][k］;
　 p［l++］＝i；
　 　 　 　　 i＝—1；
　 ｝
　　　 　 ｅlse
　 　{
　 　　 continue;　
　 　 　 　 }
　　　 　 ｝
　　 　　 if(l=＝m）
　 {
　　 　 　 　 　 ｃoｕt＜〈"系统就是安全得”〈〈p[ｉ];
　 　 　 　 　 if(ｉ!=l-1)
　 　 　　 　 　coｕt<<”－—>"；
　 　 　 　　　 }
cout＜<""〈〈endl;
　 ｒeturn true;
　 　}
ﻩ ｉf(ｌ〉=ｍ） coｕt〈<＂系统就是不安全得”〈