操作系统课程设计银行家算法模拟实现.docx
《操作系统课程设计银行家算法模拟实现.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计银行家算法模拟实现.docx（20页珍藏版）》请在冰点文库上搜索。
操作系统课程设计银行家算法模拟实现
课程设计报告
课程设计名称：
银行家算法模拟实现
系：
学生姓名：
班级：
学号：
成绩：
指导教师：
开课时间：
学年学期
题目要求：
一．设计题目
银行家算法模拟实现
二．主要内容
设计目的
1、了解多道程序系统中，多个进程并发执行的资源分配。
2、掌握思索的产生原因、产生死锁的必要条件和处理死锁的基本方法。
3、掌握预防死锁的方法，系统安全状态的基本概念。
4、掌握银行家算法，了解资源在进程并发执行中的资源分配策略。
5、理解死锁避免在当前计算机系统不常使用的原因。
三．具体要求
设计一个n个并发进程共享m个系统资源的系统，进程可动态申请资源和释放资源，系统按各进程的申请动态的分配资源。
要求采用银行家算法实现。
四．进度安排
序号
内容
时间（天）
1
熟悉课题、分析课题
0.5
2
对系统进行模块分解，问题分析和确定解决方案
1
3
编程调试
3
4
测试和差错
1
5
书写课程设计报告
1
6
考核
1
合计
7.5
五．成绩评定
考核方法：
根据学生平时表现、测试检查、课程设计报告、运行演示和学生回答问题相结合的形式作为考核依据，考察学生的动手能力，独立分析解决问题的能力和创新精神，并根据学生的学习态度综合考评。
平时表现（占30%），课程设计报告（占40%），课程答辩（占30%）。
成绩评定：
成绩分“优秀”、“良好”、“中等”、“及格”、“不及格”五个级别。
“优秀”为100分到90分，“良好”为89分到80分，“中等”为79分到70分，“及格”为69分到60分，“不及格”为60分以下。
1.需求分析
1、始化这组进程的最大资源请求和一次申请的资源序列。
把各进程已占用和需求资源情况记录在进程控制块中。
假定进程控制块的内容包括：
进程名，状态，当前申请量，资源需求总量，已占资源量，能执行完标志。
其中，进程的状态有：
就绪，等待和完成。
当系统不能满足进程的资源请求时，进程出于等待状态。
资源需求总量表示进程运行过程中对资源的总的需求量。
已占资源量表示进程目前已经得到但还为归还的资源量。
因此，进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。
陷入每个进程的资源需求总量不应超过系统拥有的资源总量。
2、银行家算法分配资源的原则是：
当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。
若能，则让进程等待，否则，让进程的假分配变为真分配。
A）查找各进程的剩余请求，检查系统的剩余资源量是否能满足其中一进程，如果能，则转B）。
B）将资源分配给所选的进程，这样，该进程已获得资源最大请求，最终能运行完成。
标记这个进程为终止进程，并将其占有的全部资源归还给系统。
重复第A）步和B）步，直到所有进程都标记为终止进程，或知道一个死锁发生。
若所有进程都标记为终止进程，则系统的初始状态是安全的，否则为不安全的。
若安全，则正式将资源分配给它，否则，假定的分配作废，让其等待。
2.概要设计
2.1设计思想
当某个进程提出资源请求时，假定先分配资源给它，然后查找各进程的剩余请求，检查系统的剩余资源量是否由于进程的分配而导致系统死锁。
若能，则让进程等待，否则，让进程的假分配变为真分配。
2.2数据结构
假设有m个进程，则有如下数据结构:
#definew50//宏定义
#definer50//宏定义
intm;//总进程数
intall[w];//各种资源的数目总和
intmax[w][r];//m个进程最大资源需求量
intavailable[r];//系统可用资源数
intallocation[w][r];//m个进程已经得到资源的资源量
intneed[w][r];//m个进程还需要资源的资源量
intrequest[r];//请求资源个数
2.3程序流程图
3.详细设计
3.1算法思想
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。
否则拒绝分配。
3.2银行家算法
设Request[n]，是进程的请求向量，如果Request[n]=m，则表示该进程需要m个资源。
当该进程发出资源请求后，系统按下述步骤进行检查：
（1）如果Request[n]《=Need[i，n]，便转向步骤
（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。
（2）如果Request[n]>Available，则进程i进入等待资源状态，返回。
（3）假设进程i的申请已获批准，于是修改下面数据结构中的数值：
Available=Available-Request
Allocation=Allocation+Request
Need=Need-Request
（4）系统执行安全性检查，如安全，则分配成立；否则恢复原来的资源分配状态，系统恢复原状，进程等待。
程序
voidbank（）//银行家算法
{
inti=0,j=0;
charflag='Y';
while（flag=='Y'||flag=='y'）
{
i=-1;
while（i<0||i>=m）
{
cout<<"请输入需申请资源的进程号（从0到"<";
cin>>i;
if（i<0||i>=m）cout<<"该进程号不存在，请重新输入!
"<}
cout<<"请输入进程"<";
for（j=0;j<1;j++）
{
cout<<"";
cin>>request[j];
if（request[j]>need[i][j]）//若请求的资源数大于进程还需要i类资源的资源量j
{
cout<<"进程"<";
cout<<"申请不合理，请重新选择!
"<flag='1';
break;
}
else
{
if（request[j]>available[j]）//若请求的资源数大于可用资源数
{
cout<<"进程"<";
cout<<"申请不合理!
请重新选择!
"<flag='1';
break;
}
}
}
if（flag=='Y'||flag=='y'）
{
change（i）;//调用change（i）函数，改变资源数
if（chkerr（i））//若系统安全
{
rstore（i）;//调用rstore（i）函数，恢复资源数
show（）;//输出资源分配情况
}
else//若系统不安全
show（）;//输出资源分配情况
}
else//若flag=N||flag=n
show（）;
cout<cout<<"是否继续（Y/N）:
";
cin>>flag;
}
}
3.3安全性检查算法
（1）设置两个工作向量Work=Available；Finish[M]=False
（2）从进程集合中找到一个满足下述条件的进程，
Finish[i]=False
Need<=Work
如找到，执行（3）；否则，执行（4）
（3）设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+Allocation
Finish=True
GOTO2
（4）如所有的进程Finish[M]=true，则表示安全；否则系统不安全。
程序
intchkerr（ints）//检查安全性
{intwork,FInISH[w];
inti,j,k=0;
for（i=0;ifor（j=0;j<1;j++）
{
work=available[j];
i=s;
do
{
if（FInISH[i]==false&&need[i][j]<=work）
{
work=work+allocation[i][j];
FInISH[i]=true;
i=0;
}
else
{i++;
}
}while（ifor（i=0;iif（FInISH[i]==false）
{
cout<cout<<"系统不安全本次资源申请不成功"<cout<return1;
}
}
cout<cout<<"系统安全，分配成功。
"<cout<return0;
}
3.4修改数据结构中的数值
改变可用资源和已经拿到资源和还需要的资源的值
voidchange（intk）{
intj;
for（j=0;j<1;j++）
{
available[j]=available[j]-request[j];
allocation[k][j]=allocation[k][j]+request[j];
need[k][j]=need[k][j]-request[j];
}
}
3.5如果分配失败，则恢复原来的资源分配状态
恢复可用资源和已经拿到资源和还需要的资源的值
voidrstore（intk）
{intj;
available[j]=available[j]+request[j];
allocation[k][j]=allocation[k][j]-request[j];
need[k][j]=need[k][j]+request[j];
}
3.6输出显示
实现人机交互的各类资源输出显示情况。
voidshow（）//输出资源分配情况
{
inti,j;
cout<<"资源总量:
"<<"";
for（j=0;j<1;j++）cout<<""<cout<cout<<"系统目前资源可用数:
"<<"";
for（j=0;j<1;j++）cout<<""<cout<cout<<"进程名各进程还需要的资源量"<for（i=0;ifor（i=0;i{
cout<<"进程"<";
for（j=0;j<1;j++）cout<cout<}
cout<cout<<"进程名各进程已经得到的资源量"<for（i=0;i{
cout<<"进程"<";
for（j=0;j<1;j++）cout<cout<}
cout<}
voidchange（intk）//改变可用资源和已经拿到资源和还需要的资源的值
{
intj;
for（j=0;j<1;j++）
{
available[j]=available[j]-request[j];
allocation[k][j]=allocation[k][j]+request[j];
need[k][j]=need[k][j]-request[j];
}
}
3.7主函数
voidmain（）//主函数
{
inti=0,j=0,p;
cout<<"-------------银行家算法模拟-------------"<cout<<"请输入总进程数:
";
cin>>m;
cout<<"请输入总资源数:
";
for（i=0;i<1;i++）
cin>>all[i];
cout<<"依次输入各进程所需要的最大资源数量:
"<for（i=0;i{
for（j=0;j<1;j++）
{
do
{
cin>>max[i][j];
if（max[i][j]>all[j]）
cout<}
while（max[i][j]>all[j]）;
}
}
cout<<"依次输入各进程已经占据的资源数量:
"<for（i=0;i{
for（j=0;j<1;j++）
{
do
{
cin>>allocation[i][j];
if（allocation[i][j]>max[i][j]）
cout<}while（allocation[i][j]>max[i][j]）;
}
}
//初始化资源数量
for（j=0;j<1;j++）
{p=all[j];
for（i=0;i{
p=p-allocation[i][j];//减去已经被占据的资源
available[j]=p;
if（available[j]<0）
available[j]=0;
}
}
for（i=0;ifor（j=0;j<1;j++）
need[i][j]=max[i][j]-allocation[i][j];
show（）;
bank（）;
}
3.8定义全局变量
#include"string.h"
#include"iostream"
usingnamespacestd;
#definefalse0
#definetrue1
#definew50//宏定义
#definer50//宏定义
intm;//总进程数
intall[w];//各种资源的数目总和
intmax[w][r];//m个进程最大资源需求量
intavailable[r];//系统可用资源数
intallocation[w][r];//m个进程已经得到资源的资源量
intneed[w][r];//m个进程还需要资源的资源量
intrequest[r];//请求资源个数
4.调试分析
图4-1
图4-1这里为3个进程（进程0.1.2）共用10个资源，分别需要的最大资源数为3,4,3.已经占有的资源数为：
1,2,2.分配给0号进程1个资源，系统安全，分配成功
图4-2
4-2再分配给0号进程1个资源，系统安全，分配成功
图4-3
4-3分配给1号进程3个资源，因为1号资源还需要2个即达到最大需要资源数，故申请不合理，分配不成功
图4-4
图4-4重新设定2个进程（0,1）共用5个资源。
分别需要的最大资源数为4,3.已经占有的资源数为3,1。
进程1申请2个资源，大于系统可用资源数。
申请不合理，故申请失败。
图4-5
图4-5进程1申请1个资源，此时发生死锁，故申请失败。
（发生死锁后，程序出错。
）
5.总结
由于本人技术与经验的不足，在设计n类资源时出现未找到解决方法的错误，因此只把资源种类设计成只有一类。
这样程序的编写得到简化。
当然在实际实现时会出现很多类资源，这是这个程序需要改进的地方。
进程请求资源后，若产生死锁，则程序出错。
相信随着对操作系统与死锁等问题的深入了解，会更好的完善这个程序。
在上学期的数据库课程里已经初步认识了银行家算法，对它有了一定的了解。
它是避免死锁的主要方法，书上的介绍也许不够详细与完整，所以在这次课程设计中，通过查阅大量书籍资料，让我对它产生了一定的深入认识，只是由于一些个人原因，未能及时完成。
在以后的学习中，这种算法还将会有很多地方要用到的。
所以不能报着“学过就完事”的态度。
当然，以后可能还会有比这种算法更好的算法，但是核心思想与它的目的是不会变的。
所以，弄懂弄透了之后，再学习操作系统的更多知识会更容易上手。
6.参考文献
[1].汤小丹．计算机操作系统（第三版）．西安：
电子科技大学出版社；
[2].张丽芬．操作系统实验教程．清华大学出版社。
升级会员 