操作系统实验报告银行家算法.docx
《操作系统实验报告银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统实验报告银行家算法.docx（21页珍藏版）》请在冰点文库上搜索。
操作系统实验报告银行家算法
操作系统实验报告
----银行家算法
班级：
______计算机03（7）班______________
姓名：
_________李君益__________________
学号：
______________（61号）___
提交日期：
____06.7.11___________________
****______林穗____________________
一、设计题目
加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。
要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用银行家算法，有效的防止和避免死锁的发生。
二、设计要求
内容：
编制银行家算法通用程序，并检测思考题中所给状态的安全性。
要求：
（1）下列状态是否安全？
（三个进程共享12个同类资源）
进程已分配资源数最大需求数
114（状态a）
244
358
114
246（状态b）
368
（2）考虑下列系统状态
分配矩阵最大需求矩阵可用资源矩阵
001200121520
10001750
13542356
06320652
00140656
问系统是否安全？
若安全就给出所有的安全序列。
若进程2请求（0420），可否立即分配？
三、设计分析
一．关于操作系统的死锁
1．死锁的产生
计算机系统中有许多独占资源，他们在任一时刻只能被一个进程使用，如磁带机，绘图仪等独占型外围设备，或进程表，临界区等软件资源。
两个进程同时向一台打印机输出将导致一片混乱，两个进程同时进入临界区将导致数据库错误乃至程序崩溃。
正因为这些原因，所有操作系统都具有授权一个进程独立访问某一辞源的能力。
一个进程需要使用独占型资源必须通过以下的次序：
●申请资源
●使用资源
●归还资源
若申请施资源不可用，则申请进程进入等待状态。
对于不同的独占资源，进程等待的方式是有差别的，如申请打印机资源、临界区资源时，申请失败将一位这阻塞申请进程；而申请打开文件文件资源时，申请失败将返回一个错误码，由申请进程等待一段时间之后重试。
只得指出的是，不同的操作系统对于同一种资源采取的等待方式也是有差异的。
在许多应用中，一个进程需要独占访问多个资源，而操作系统允许多个进程并发执行共享系统资源时，此时可能会出现进程永远被阻塞的现象。
这种现象称为“死锁”。
2.死锁的定义
一组进程处于死锁状态是指：
如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的时间，则称一组进程或系统此时发生了死锁。
3．死锁的防止
a.死锁产生的条件：
●互斥条件
●占有和等待条件
●不剥夺条件
●循环等待条件
以上三个条件是死锁存在的必要条件，胆不是充分条件。
第四个条件是钱唢呐个条件同时存在时产生的结果，所以，这些条件并不完全独立。
但单独考虑每个条件是有用的，只要能破坏这四个必要条件之一，死锁就可以防止。
b.实用死锁防止方法
●静态分配策略
●层次分配策略
4．死锁的避免
破坏死锁的四个条件之一能防止系统发生死锁，但这会导致低效率的进程运行和资源使用率。
死锁的避免则相反，他允许系统中同时存在三个必要条件，如果能掌握并发进程中与每个进程有关的资源动态申请情况，做出明智和合理的选择，仍然可以避免死锁的发生。
每当在为申请者分配资源前先测试系统状态，若把资源分配个申请者会产生死锁的话，则拒绝分配，否则接受申请，为它分配资源。
死锁避免不是通过队进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能安全的分配。
问题是：
是否存在一种算法总能做出正确的选择从而避免死锁？
二．单种资源的银行家算法
Dijkstra（1965）提出了一种能够避免死锁的调度方法，称为一银行家算法。
它的模型基于一个小城镇的银行家，现将该算法描述如下：
假定一个银行家拥有资金，数量为∑，被N个客户共享。
银行家对客户提出下列约束条件：
●每个客户必须预先说明自己所要求的最大资金量；
●每个客户每次提出部分资金量申请和获得分配；
●如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内归还银行。
只要每个客户遵守上述约束，银行家将保证做到：
若一个客户所要求的最大资金量不超过∑，则银行一定接纳该客户，并可处理他的资金需求；银行在受到一个客户的资金申请是，可能因资金不足而让客户等待，但保证在有限时间内让客户获得现金。
在银行家算法中，客户可看作进程，资金可看作资源，银行家可看作操作系统
Andy
1
6
Barbara
2
5
Marvin
2
4
Suzanne
4
7
Andy
1
6
Barbara
1
5
Marvin
2
4
Suzanne
4
7
名字已使用最大名字已使用最大名字已使用最大
Andy
0
6
Barbara
0
5
Marvin
0
4
Suzanne
0
7
可用：
10可用：
2可用：
1
安全安全不安全
银行家算法就是对每一个请求进行检查，检查这次资源申请是否会导致不安全状态，若是，则不满足该请求，否则便满足。
检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。
如果所有投资都最终被收回，则该状态是安全的，最初的请求可以批准。
三．多种资源的银行家算法
银行家算法可以被推广用来处理系统中有任意数目的进程，任意种类的资源，并且每种资源有多个实例的情况。
下图示出了其工作原理：
进程磁带机绘图仪打印机cd－rom进程磁带机绘图仪打印机cd－rom
A
3
0
1
1
B
0
1
0
0
C
1
1
1
0
D
1
1
0
1
E
0
0
0
0
A
1
1
0
0
B
0
1
1
2
C
3
1
0
0
D
0
0
1
0
E
2
1
1
0
已分配的资源仍需要的资源
检查一个状态是否安全的步骤如下：
（1）查找右边矩阵是否有一行，其未被满足的设备数均小于或等于向量A。
如果找不到，则系统将死锁，因为任何进程都无法运行结束。
（2）若找到这样一行，则可以假设它获得所需的资源并运行结束，将该进程标记为结束，并将资源加到向量A上。
（3）重复以上两步，知道所有的进程都标记为结束。
若达到所有进程结束，则状态示安全的，否则将发生死锁。
如果在第一步中同时存在若干进程均符合条件，则不管挑选哪一个运行都没有关系，因为，可用资源或者将增多，或者在最坏的情况下保持不变。
图中所示的状态示安全的，进程B现在再申请一台打印机，可以满足它的请求，而且保持系统状态仍然示安全的（进程D可以结束，然后是A或E，剩下的进程最后结束）。
假设进程B获得一台打印机后，E试图获得最后的一台打印机，若分配给E，可用资源向量将减到1000，这时将导致死锁，显然E的请求不能立即满足，必须延迟一段时间。
该算法最早由Dijkstra于1965年发表。
从那以后几乎每本操作系统的专著都详细的描述它，许多论文的内容也围绕该算法讨论，其主要优点是不需要死锁预防中加上的种种限制，如资源剥夺或重新运行进程。
但很少由作者指出该算法缺乏实用价值。
因为，进程很难在运行前就知道其所需资源的最大量；而且系统中的进程必须是无关的，相互之间没有同步要求；进程的个数和分配的资源数目应该是固定的。
这些要求往往事先难以满足。
1.实现原理
1．数据结构
假设有n个进程m类资源，则有如下数据结构：
MAX[n*m]n个进程对m类资源的最大需求量
AVAILABLE[m]系统可用资源数
ALLOCATION[n*m]n个进程已经得到m类资源的资源量
NEED[n*m]n个进程还需要m类资源的资源量
2．银行家算法
设进程I提出请求Request[m]，则银行家算法按如下规则进行判断。
（1）如果Request[m]<=NEED[I，m]，则转
（2）；否则，出错。
（2）如果Request[m]<=AVAILABLE，则转（3）；否则，出错。
（3）系统试探分配资源，修改相关数据：
AVAILABLE=AVAILABLE-REQUEST
ALLOCATION=ALLOCATION+REQUEST
NEED=NEED-REQUEST
（4）系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
3．安全性检查
（1）设置两个工作向量WORK=AVAILABLE；FINISH[n]=FALSE
（2）从进程集合中找到一个满足下述条件的进程，
FINISH[i]=FALSE
NEED<=WORK
如找到，执行（3）；否则，执行（4）
（3）设进程获得资源，可顺利执行，直至完成，从而释放资源。
WORK=WORK+ALLOCATION
FINISH=TRUE
GOTO2
（4）如所有的进程Finish[n]=true，则表示安全；否则系统不安全。
2、程序执行过程
四、程序代码
设计思路
A、设计进程对各在资源最大申请表示及初值确定。
B、设定系统提供资源初始状态。
C、设定每次某个进程对各类资源的申请表示。
D、编制程序，依据银行家算法，决定其申请是否得到满足。
主要数据结构
假设有M个进程N类资源，则有如下数据结构：
MAX[M*N]M个进程对N类资源的最大需求量
AVAILABLE[N]系统可用资源数
ALLOCATION[M*N]M个进程已经得到N类资源的资源量
NEED[M*N]M个进程还需要N类资源的资源量
主要代码结构
voidmain（）
voidinit（）
intfenpei（）
intshq（）
源程序
#include
#include
#include
typedefstructMax1
{
intm_a;
intm_b;
intm_c;
intm_d;
}Max;
typedefstructAllocation1
{
inta_a;
inta_b;
inta_c;
inta_d;
}Allocation;
typedefstructNeed1
{
intn_a;
intn_b;
intn_c;
intn_d;
}Need;
structAvailable1
{
intav_a;
intav_b;
intav_c;
intav_d;
}q;
structpr
{
charname;
Maxmax;
Allocationallocation;
Needneed;
intfinishflag;
}p[5];
charna[5];
//*****************************
voidinit（）//读入
{
printf（"各进程的NEED：
\n"）;
FILE*fp;
fp=fopen（"","r+"）;
for（inti=0;i<5;i++）
{
fscanf（fp,"%c,%d,%d,%d,%d,%d,%d,%d,%d\n",&p[i].name,&p[i].max.m_a,&p[i].max.m_b,&p[i].max.m_c,&p[i].max.m_d,&p[i].allocation.a_a,&p[i].allocation.a_b,&p[i].allocation.a_c,&p[i].allocation.a_d）;
p[i].need.n_a=p[i].max.m_a-p[i].allocation.a_a;
p[i].need.n_b=p[i].max.m_b-p[i].allocation.a_b;
p[i].need.n_c=p[i].max.m_c-p[i].allocation.a_c;
p[i].need.n_d=p[i].max.m_d-p[i].allocation.a_d;
printf（"%c:
%d,%d,%d,%d\n",p[i].name,p[i].need.n_a,p[i].need.n_b,p[i].need.n_c,p[i].need.n_d）;
}
fclose（fp）;
}
//*****************************
intfenpei（）//分配
{
printf（"Available:
\n"）;
printf（"%d,%d,%d,%d\n",q.av_a,q.av_b,q.av_c,q.av_d）;
intfinishcnt=0,k=0,count=0;
for（intj=0;j<5;j++）
p[j].finishflag=0;
while（finishcnt<5）
{
for（inti=0;i<5;i++）
{
if（p[i].finishflag==0&&q.av_a>=p[i].need.n_a&&q.av_b>=p[i].need.n_b&&q.av_c>=p[i].need.n_c&&q.av_d>=p[i].need.n_d）
{
q.av_a+=p[i].allocation.a_a;
q.av_b+=p[i].allocation.a_b;
q.av_c+=p[i].allocation.a_c;
q.av_d+=p[i].allocation.a_d;
p[i].finishflag=1;
finishcnt++;
na[k++]=p[i].name;
break;
}
}
count++;//禁止循环过多
if（count>5）return0;
}
return1;
}
//*****************************
intshq（）
{
intm,i,j,k,l;
printf（"请输入进程号和请求资源！
例如:
题目要求：
10420（进程号和资源之间3个空格）\n"）;
scanf（"%d%d%d%d%d",&m,&i,&j,&k,&l）;
if（i<=p[m].need.n_a&&j<=p[m].need.n_b&&k<=p[m].need.n_c&&l<=p[m].need.n_d）
{
if（i<=q.av_a&&j<=q.av_b&&k<=q.av_c&&l<=q.av_d）
{
p[m].allocation.a_a+=i;
p[m].allocation.a_b+=j;
p[m].allocation.a_c+=k;
p[m].allocation.a_d+=l;
p[m].need.n_a=p[m].max.m_a-p[m].allocation.a_a;
p[m].need.n_b=p[m].max.m_b-p[m].allocation.a_b;
p[m].need.n_c=p[m].max.m_c-p[m].allocation.a_c;
p[m].need.n_d=p[m].max.m_d-p[m].allocation.a_d;
printf（"各进程的NEED:
\n"）;
for（intw=0;w<5;w++）
printf（"%c:
%d,%d,%d,%d\n",p[w].name,p[w].need.n_a,p[w].need.n_b,p[w].need.n_c,p[w].need.n_d）;
return1;
}
else
printf（"Request>Available\n让%c等待......\n",p[m].name）;
}
elseprintf（"Request>Need\n让%c等待......\n",p[m].name）;
return0;
}
//*****************************
voidmain（）
{
intflag;
charc;
cout<<"\n\n\n\n\n\n\n\n\n\t";
for（inti=0;i<30;i++）
cout<<"*";
cout<cout<cout<李君益\n"<cout<\n"<cout<06.7.11\n"<printf（"\t"）;
for（i=0;i<30;i++）
printf（"*"）;
printf（"\n\n\n\n\n"）;
getch（）;
printf（"\t请确认已经在\"\"中正确输入各进程的有关信息\n"）;
getch（）;
init（）;
q.av_a=3;
q.av_b=14;
q.av_c=12;
q.av_d=12;
while（flag）
{
for（i=0;i<5;i++）
{
q.av_a-=p[i].allocation.a_a;
q.av_b-=p[i].allocation.a_b;
q.av_c-=p[i].allocation.a_c;
q.av_d-=p[i].allocation.a_d;
}
if（fenpei（））
{
printf（"\n这样配置资源是安全的\n"）;
printf（"其安全序列是：
"）;
for（intl=0;l<5;l++）
printf（"-->%c",na[l]）;
printf（"\n"）;
printf（"有进程发出Request请求向量吗（EnteryorY）\n"）;
c=getch（）;
if（c=='y'||c=='Y'）
{
if（shq（））continue;
elsebreak;
}elseflag=0;
}
else{flag=0;printf（"不安全\n"）;}
}
}
五、执行结果和结果分析
1.程序运行还是介面如下:
2单资源状态a情况
下列状态是否安全？
（三个进程共享12个同类资源）
进程已分配资源数最大需求数
114（状态a）
244
358
在文件里面输入以上内容,点击单资源状态a.exe运行,显示如下:
经过验证状态a情况是安全的
3单资源状态b情况
下列状态是否安全？
（三个进程共享12个同类资源）
114
246（状态b）
368
在文件里面输入以上内容,点击单资源状态b.exe运行,显示如下:
经过验证状态b情况是不安全的
4考虑下列系统状态
分配矩阵最大需求矩阵可用资源矩阵
001200121520
10001750
13542356
06320652
00140656
问系统是否安全？
若安全就给出所有的安全序列。
若进程2请求（0420），可否立即分配？
在文件里面输入以上内容,点击多资源状态.exe运行,显示如下:
按题目要求进程2申请资源0420,于是输入:
10420（进程号和资源之间3个空格）
程序显示结果进程2申请资源0420,是安全的,于是程序把资源分配给进程2,询问是否继续发出请求,
按个人需要继续进行……
六、心得体会
银行家算法不是很难，书上已经通过实例生动的说明了算法的思想，应用已掌握的c＋＋知识写出了此模拟程序。
思考的过程不是很难，主要是在c＋＋语言的应用上面倒是碰到了不少困难，在查阅了相关c＋＋资料后，才勉勉强强的完成此次课程设计。
用时两天，完成初版，后陆续修改几处bug，并稍加修饰界面。
通过此次程序设计，让我深刻的理解了银行家算法的核心，了解了它是怎么样避免系统的死锁的，也了解了银行家算法的种种弊端，比如在实际应用中存在很大困难，因为程序最大资源值p_max[NO][NUM]很难预测，而且银行家算法必须循环检测各项进程，对系统资源也是一种极大的剥夺。
课程设计已经完成，对于我来说，收获是非常大的。
一方面加强和巩固了从c＋＋语言知识，另一方面加深了我对操作系统这门课程的理解。
升级会员 