操作系统-银行家算法期末课程设计源代码
《操作系统》课程设计
题目:银行家算法
院、 系: 计算机科学与
工程
路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理
学院 学科专业: 软件工程 姓 名:
学 号:
指导教师: 姜虹
2010年 12月 24日
绪论
操作系统是控制其他程序运行,管理系统资源并为用户提供操作界面的系统软件的集合。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行;改善人机界面;为其它应用软件提供支持等,使计算机系统所有资源最大限度地发挥作用,为用户提供方便的、有效的、友善的服务界面。
银行家算法是一种最有代表性的避死锁免的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。
安全状态是指系统能按某种顺序如
来为每个进程分配其所需资源,直到最大需求,使每个进程都可顺序完成。若系统不存在这样一个安全序列,则称系统处于不安全状态。
摘要
银行家算法是一种最有代表性的避死锁免的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。
此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并使用适当的算法,有效的防止和避免死锁的发生。
关键字:
银行家算法
安全型算法
死锁
进程
目录
1、概述..................................................................2 2、需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
...........................................................3 3、设计..................................................................4
3?1数据结构.........................................................4
3?2主要函数.........................................................4
3?3银行家算法中的数据结构..................................5
3?4银行家算法......................................................7
3?5安全性算法......................................................8 4、测试.................................................................10
4?1初始化数据.....................................................10
4?2安全序列检查..................................................10
4?3不安全序列.....................................................11 5、
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
…………………………………………….....12
6、参考文献……………………………………….....13
附录:源程序清单…………………………………...14
- 1 -
概述
1、概述
银行家算法,顾名思义是来源于银行的借贷业务,一定数量的本金要应多个客户的借贷周转,为了防止银行加资金无法周转而倒闭,对每一笔贷款,必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间内归还资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,个进程都无法继续执行下去的死锁现象。
银行家算法是一种最有代表性的避死锁免的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。要解释银行家算法,必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1?i?n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
- 2 -
需求分析
2、需求分析
此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并使用适当的算法,有效的防止和避免死锁的发生。
具体用银行家算法实现资源分配。要求如下:
(1)设计一个i个并发进程共享j类不同资源的系统,进程可动态地申请资源和释放资源,系统按进程的申请动态地分配资源。
(2)设计用银行家算法,实现资源分配的程序,应具有显示进程要求申请的资源数以及分配资源的情况。
(3)确定一组各进程依次申请资源数的序列,观察运行结果。
银行家算法是避免死锁的一种重要方法,本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。死锁的产生,必须同时满足四个条件,即一个资源每次只能由一个进程占用:第二个为等待条件,即一个进程请求资源不能满足时,它必须等待,但它仍继续保持已得到的所有其他资源:第四个为循环等待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.
- 2 -
设计
3、设计
3?1 数据结构
int n; //总进程数
int m ; //资源种类
int count; //记录某个进程安全资源的数量 int finish[] //记录进程是否安全 int Max[i][j]; //i个进程对j类资源最大资源需
求量
int Available[j]; //系统可用资源数
int Allocation[i][j]; //i个进程已经得到j类资源的资源量 int Need[i][j]; //i个进程还需要j类资源的资源量 int Request[j]; //请求资源个数
3?2 主要函数
void bank(); //银行家算法
void safe(); //安全性检查
void initialise() //初始化数据
void show(); //函数show,输出当前状态void end(); //结束函数
- 2 -
课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
3?3 、银行家算法中的数据结构
1)可利用资源向量Available是个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目。其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态的改变。如果Available,j,=K,则表示系统中现有Rj类资源K个。
2)最大需求矩阵Max这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max,i,j,=K,则表示进程i需要Rj类资源的最大数目为K。
3)分配矩阵Allocation这也是一个n×m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation,i,j,=K,则表示进程i当前已分得Rj类资源的 数目为K。
4)需求矩阵Need。这也是一个n×m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need,i,j,=K,则表示进程i还需要Rj类资源K个,方能完成其任务。
上面三个矩阵存在下面关系: Need,i,j,=Max,i,j,-Allocation,i,j,
- 2 -
课程设计报告
开始初始化数据
initalise()
输入进程数目n
输入资源种类m
false 输入每个进程对各资 输出提示:输入错误,请 源的最大需求数 重新输入
true
输入个资源已经输
入的各资源数
输入个进程现有的各资源数
初始化结束
- 3 -
课程设计报告
3?4、银行家算法 bank()
在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程pi提出请求Request i,则银行家算法按如下规则进行判断。
(1)如果Request i[j] <=Need [i][j],则转(2);否则,出错。
(2)如果Request i[j]<= Available[j],则转(3);否则,出错。
(3)系统试探分配资源,修改相关数据:
Available[j]-=Request i[j];
Allocation[i,j]+=Request i[j];
Need[i,j]-=Request i[j]。
(4)系统执行安全性检查,如安全,则分配成立;否则试探险性分配作废,系统恢复原状,进程等待。
- 2 -
课程设计报告
开始银行家算法Bank()
false
Request i[j]<=Need [i,j]; 拒绝分配 Request i[j]<=Available
true
试分配: Available[j]-=Request i[j];
Allocation[i,j]+=Request i[j];
Need[i,j]-=Request i[j]。
调用安全型算法Safe()
结束银行家算法
3?5、安全性检查算法 safe()
(1)设置两个工作向量Work=Available;Finish;
(2)从进程集合中找到一个满足下述条件的进程; Finish==false;Need<=Work;如找到,执行(3);否则,执行(4);
(3)设进程获得资源,可顺利执行,直至完成,从而释放资源。Work+=Allocation;Finish=true; go to stept2 ;
- 2 -
课程设计报告
(4)如所有的进程Finish= true,则表示安全;否则系统不
安全。
安全型算法Safe()开始
Work=Available;
Finish=False;
Need[i]<=Work&&
Finish[i]=False
Work+=Allocation[i];
Finish[i]=true;
所有进程的
false Finish=true
提示系统是
不安全的 true
输出安全序列
安全型算法Safe()结束
- 3 -
测试
4、测试 4.1 初始化数据
4.2 安全序列检查
- 2 -
课程设计报告
4.3不安全序列
- 2 -
总结
5、总结
此次课程设计是银行家算法,银行家算法是避免死锁问题最具代表性的一种,在课程设计中遇到了很多的问题,由于程序的代码不完全是自己编写的所以在修改中出现了不少问题,首先在安全性算法代码中counter的定义与使用,counter记录了比较后的Need<=Available的资源数,当counter等于符合的资源数时才能将其存储在安全序列中。还有就是安全型算法的流程,经过研究及请教,才知道开始判断了一个进程后,系统应该跳到第一个进程判断,当Finish被标记为一的时候,说明进程是安全的,开始判断下一个进程,总之,每一个进程判断完后都是跳到第一个进程,根据Finish来确定进程是否安全。最后就是对整个程序的理解,由于程序不是自己亲自编写的在修改和理解上都需要花费很大力气。虽然感觉比较复杂,但是通过自己的努力还是完成了这次的设计。
通过本次课程设计是自己能够熟练的掌握银行家算法,上机与理论相结合才能更好的对知识的运用。
- 3 -
参考资料
6、参考资料
1、汤子瀛 编:《计算机操作系统》,西安电子科技大学出版社
2、陈天华 编:《面向对象程序设计与Visual C++6.0教程》,清华大学出版社
- 2 -
附录 附录:原程序清单
#include #include #include #include
//定义全局变量
const int x=10,y=10; //常量,便于修改
int Available[x]; //各资源可利用的数量 int Allocation[y][y]; //各进程当前已分配的资源数量 int Max[y][y]; //各进程对各类资源的最大需求数 int Need[y][y]; //尚需多少资源
int Request[x]; //申请多少资源
int Work[x]; //工作向量,表示系统可提供给进程继续运行所需的各类资源数量
int Finish[y]; //表示系统是否有足够的资源分配给进程,1为是 int p[y]; //存储安全序列
int i,j; //i表示进程,j表示资源
int n,m; //n为进程i的数量,m为资源j种类数 int l=0; //l用来记录有几个进程是Finish[i]=1的,当l=n是说明系统状态是安全的
int counter=0;
//函数声明
void initialise(); //初始化函数
void safe(); //安全性算法
void show(); //函数show,输出当前状态 void bank(); //银行家算法
void end(); //结束函数
void initialise()
{
cout<<"输入进程的数量: ";//从此开始输入有关数据
cin>>n;
cout<<"输入资源种类数: ";
cin>>m;
cout<>Available[j]; //输入数字的过程...
Work[j]=Available[j]; //初始化Work[j],它的初始值就是当前可用的资源数
}
cout<>Allocation[i][j];
}
cout<>Max[i][j];
if(Max[i][j]>=Allocation[i][j]) //若最大需求大于已分配,则计算需求量
Need[i][j] = Max[i][j]-Allocation[i][j];
else
Need[i][j]=0;//Max小于已分配的时候,此类资源已足够不需再申请
}
cout<=Need[i][j]) counter=counter+1;//可用大于需求,记数
}
if(counter==m) //i进程的每类资源都符合Work[j]>=Need[i][j] 条件二
{
p[l]=i; //存储安全序列
Finish[i]=1; //i进程标志为可分配
for (j=0; j>k;
cout<n-1) //输入错误处理
{
cout<>k;
cout<>Request[j];
cout<Need[k][j]){ //申请大于需求量时出错,提示重新输入(贷款数目不允许超过需求数目)
cout<<"申请大于需要量!"<Available[j]){ //申请大于可利用量, 应该阻塞等待,…… ,,,
cout<<"\n没有那么多资源,目前可利用资源"<Need[k][j]); //Request[j]>Available[j]||
}
//改变Avilable、Allocation、Need的值
for (j=0; j>"<<"进程"<<"("<>b;
cout<>"<<"进程"<<"("<
本文档为【操作系统-银行家算法期末课程设计源代码】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。