银行家算法实验报告 银行家算法报告
课程设计报告
题 目 银行家算法程序设计
课 程 名 称 操作系统课程设计 院 部 名 称 信息技术学院 专 业 计算机科学与技
术 班 级 。。。。。。。。。。。。。。。。。。。。。。。 学 生
姓 名 。。。。 学 号 。。。。。。。。。。 课程设计地
点 。。。。 课程设计学时 20 指 导 教 师 。。。
金陵科技学院教务处制
1
目 录
目录„„„„„„„„„„„„„„„„„„„„„„„„„„„I 摘要„„„„„„„„„„„„„„„„„„„„„„„„„„ II 引言 „„„„„„„„„„„„„„„„„„„„„„„„„„ 1 1、课程设计的目的和要求„„„„„„„„„„„„„„„„„„2 2、课程设计的环境„„„„„„„„„„„„„„„„„„„„„2 3、课程设计的主要
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
„„„„„„„„„„„„„„„„„„ 2 3.1、项目名称„„„„„„„„„„„„„„„„„„„„„2 3.2、项目的主要内容„„„„„„„„„„„„„„„„„„ 2 4、系统的组成及工作原理„„„„„„„„„„„„„„„„„ 3 4.1、系统主要过程的
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图„„„„„„„„„„„„„„„ 3 4.2、系统的设计方法„„„„„„„„„„„„„„„„„„ 4 5、模块划分„„„„„„„„„„„“„„„„„„„„„„„ 5 5.1各模块间的调用关系„„„„„„„„„„„„„„„„„ 6 5.2安全性算法流程图„„„„„„„„„„„„„„„„„„ 7 6.1欢迎界面„„„„„„„„„„„„„„„„„„„„„„ 8 6.2初始化界面„„„„„„„„„„„„„„„„„„„„„ 8 6.3界面显示„„„„„„„„„„„„„„„„„„„„„„11 6.4出错界面图„„„„„„„„„„„„„„„„„„„„„12 6.5程序运行结束„„„„„„„„„„„„„“„„„„„„12 7、总结„„„„„„„„„„„„„„„„„„„„„„„„„13 8、课程设计的心得体会„„„„„„„„„„„„„„„„„„14 9、参考文献
2
„„„„„„„„„„„„„„„„„„„„„„„15 附录
„„„„„„„„„„„„„„„„„„„„„„„„„„ 16
6、运行与测试结果„„„„„„„„„„„„„„„„„„„„„8
摘 要
随着时代的发展,对生活的追求越来越高,生活品质也越来越好。在学习方面的研究也越来越有成效。Dijkstra提出的银行家算法,是最具代表性的避免死锁的算法。加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。死锁的产生,必须同时满足四个条件,即一个资源每次只能由一个进程占用:第二个为等待条件,即一个进程请求资源不能满足时,它必须等待,但它仍继续保持已得到的所有其他资源:第四个为循环等待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会 产生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等。 本文对如何用银行家算法来处理操作系统给进程分配资源做了详细的
说明
关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书
,包括需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
、概要设计、详细设计、测试与分析、总结、源程序清单。 首先做了需求分析,解释了什么是银行家算法,并指出它在资源分配中的重要作用。 然
3
后给出了银行家算法的概要设计,包括算法思路、步骤,以及要用到的主要数据结构、函数模块及其之间的调用关系等。在概要设计的基础上,又给出了详细的算法设计,实现概要设计中定义的所有函数,对每个函数写出核心算法,并画出了流程图。接着对编码进行了测试与分析。最后对整个设计过程进行了总结。
关键字:死锁 安全序列 银行家算法 进程
引 言
Dijkstra (1965)提出了一种能够避免死锁的调度算法,称为银行家算法。它的模型基于一个小城镇的银行家,他向一群客户分别承诺了一定的贷款额度,每个客户都有一个贷款额度,银行家知道不可能所有客户同时都需要最大贷款额,所以他只保留一定单位的资金来为客户服务,而不是满足所有客户贷款需求的最大单位。这里将客户比作进程,贷款比作设备,银行家比作系统。客户们各自做自己的生意,在某些时刻需要贷款。在某一时刻,客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的,其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请,希望得到最大贷款额,而银行家无法满足其中任何一个的要求,则
4
发生死锁。不安全状态并不一定导致死锁,因为客户未必需要其最大贷款额度,但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查,检查如果满足它是否会导致不安全状态。若是,则不满足该请求;否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以,则这笔投资认为是能够收回的,然后接着检查下一个距最大需求最近的客户,如此反复下去。如果所有投资最终都被收回,则该状态是安全的,最初的请求可以批准。
在预防死锁的几种方法之中,都施加了较强的限制条件;而在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态,便可避免死锁的发生。而最具代表性的避免死锁的算法,便是Dijkstra的银行家算法。
利用银行家算法,我们可以来检测CPU为进程分配资源的情况,决定CPU是否响应某进程的的请求并为其分配资源,从而很好避免了死锁
1、课程设计的目的和要求
目的:
银行家算法是避免死锁的一种重要方法,本设计要求用C语言(或高级语言)编写和调试一个简单的银行家算法程序。
5
加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。通过对这个算法的设计,让学生能够对
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
本知识有更深的理解,在操作和其它方面有更高的提升,同时对程序设计的水平也有所提高。
要求:
设计一个n个并发进程共享m个系统资源的程序实现银行家算法。要求包含: 1)、简单的选择界面。
2)、前系统资源的占用和剩余情况。
3)、为进程分配资源,如果进程要求的资源大于系统剩余的资源,不与分配并且提示分配不成功。
4)、撤销作业,释放资源。
2、课程设计的环境
奔腾以上计算机,装有Turbo C 2.0软件
3、课程设计的主要内容
3.1 项目名称
银行家算法程序设计
3.2 项目的主要内容
(1)设计银行家算法,能够检测系统某一时刻是否安全,输出安全序列。 (2)实现安全性检测算法。即在某一进程在某时刻提出Request时,检测系统是否能够满足该进程的请求,并得到一个安全序列,若能够得到一个安全序列,则系统能够满足它的请求,同意分配资源。若不能够满足,则
6
回到请求前状态。
(3)对于此次课程设计通过需求分析、概要设计、详细设计、测试与分析、总结、源程序清单等模块进行全面分析,以加深对死锁概念的理解,以及银行家算法避免死锁的过程。能够利用银行家算法,有效避免死锁的发生,或检测死锁的存在。
4、系统的组成及工作原理
4.1系统主要过程流程图
4.1.1初始化算法流程图
图4.1初始化算法流程图
4.1.2 银行家算法流程图
图4.2银行家算法流程图
4.2 系统的设计方法
根据设计任务书的要求,画出程序设计流程图,确定程序的功能,把整个程序根据功能要求分解为各个子程序,利用TC语言分编写程序代码,然后进行上机调试、修改、进行
7
连接,测试,写出设计总结报告。主要函数的核心代码:
1. 进行初始化输入的函数 2. 打印输出的函数
3. 利用安全性算法进行检测的函数 4. 进行资源分配的函数 5. 利用行家算法进行判定的函数
void mainenter()//主要的输入部分代码 {
printf(
printf(
printf(
for(i=1;ifor(j=1;jprintf(
5、模块划分
第一部分:银行家算法(扫描)
1(如果Request(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的
各类资源数目)
(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False
2.若Finish[i]=False&&Need4. 若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!
5.1各模块间的调用关系:
主函数void main()
8
要调用: printFrame(),print(),Safty(),mainenter() 安全性检测函数Safty()
要调用:print()
银行家算法函数mainenter()
要调用print()、Safty()、和mainenter()本身 void main() { int k,h=1; while(h)
{ system(
printf(
switch(k) {
case 1:mainenter(); break; case 2:mainrequest();
break; case 3:mainprint(); break; case 4:h=0;
break; }
printf(
system(
printf(
printf(
5.2安全性算法流程图
图5.1安全性算法流程图
6运行与测试结果
6.1运行程序成功之后的欢迎界面
9
图6.1欢迎界面
6.2初始化程序
图6.2初始化界面
图6.3输入数据
图6.4申请进程1
图6.5申请进程2
图6.6申请进程3
图6.7申请进程5
6.3界面显示
图6.8界面显示
6.4出错界面图
10
图6.9出错界面
6.5程序运行结束
图6.10程序结束画面
7、总结
在本程序代码中,银行家算法用数组函数来实现。首先,输入欲申请资源的进程以及其所申请的资源数,存放在Request数组中。然后,判断进程请求的资源数是否大于其所需的资源数,若大于则报错并返回,若不大于则继续判断它是否大于系统在此时刻可利用的资源数,同样,如果大于则报错并反回,如果不大于则调用函数来进行预分配,之后再调用安全型算法safty检查。
最后,无论此次分配是否成功,我们都可以选择继续分配或者退出系统。 在银行家算法这个系统之中,所采用的数据结构应是最基本的部分。银行家算法的数据结构我们采用了一维数组与二维数组来存储,比如最大需求量Max[][]、已分配资源数Allocation[][]、仍需求资源数Need[][]、以及系统可利用的资源数、申请各类资源等数组。数据结构虽然重要但却只是基础,而最主要的用以实现系统功能的应该有
11
两个部分,一是用银行家算法来判断,二是用安全性算法来检测系统的安全性。除此之外,在程序当中,我们也得强调一下对输入的合法性的判断。比如,我们输入的欲申请资源的进程号没有在系统已存在的进程当中,或者进程号定义为整型,但是却错输成字母等情况,我们需要对这些情况进行判断,让程序报错返回而并非因错误而中断。
这样的情况处理起来比较麻烦,相当于对每次输入针对各种不同的情况都得做判断。我也没有涵盖全部的输入,仅仅只是对输入的进程号不在已存在进程当中、以及输入的操作选择不存在两种情况分别作了判断,并且针对第二种情况设定了五次输入错误的话系统关闭的功能。而因为对于某些——比如进程号——本来设定就是整型,因此对输入的是字母的判别因比较复杂而未能加上。
通过对本次银行家算法的程序进行修改对其结构更加明确。
8、课程设计的心得体会
操作系统的基本特征就是并发和共享,系统允许多个进程并发执行,并且共享系统的软、硬件资源。为了最大限度的利用计算机资源,操作系统应采用动态分配的策略,但是这样就容易因资源不足、分配不当而引起“死锁”。本次课程设计就是用银行家算法来避免“死锁”。
12
该算法就是一在程序进行编写之前,先对程序的要求进行分析,弄清楚程序所需要的功能,然后将每个功能分成一个功能模块即调用函数来实现,无需过多的画蛇添足。编写这个简易的银行家算法让我知道了在资源一定的条件下为了让多个进程都能使用资源完成任务,
避免死锁的产生可以从一开始就对系统进行安全性检查来判断是否将资源分配给正在请求的进程。但是银行家算法会加大系统的开销。在资源分配过程,使分配序列不会产生死锁。此算法的中心思想就是,每次分配后总存在着一个进程,如果让它单独的运行下去,一周的操作系统课程设计,我学到了很多课本上没有的知识。想要完成模拟银行家算法的C语言程序,首先就是要彻底熟悉算法,了解算法的基本原理,才能开始着手程序设计在程序设计设计过程中,遇到了一些困难,通过向同学询问,翻阅资料等问题被一一解决了。首先就是在知识层面上了解了银行家算法这种进程调度和避免死锁的算法,并用C语言程序真正模拟出安全性检查和银行家算法过程,复习了之前所学C语言和数据结构的知识;在编程过程中虽然遇到很多困难,解决问题的过程中,同时也锻炼了我不怕困难,勇于迎接挑战的精神,为以后的工作打下了坚实的基础。
9、参考文献
[1]汤小丹等,《计算机操作系统第三版》,西安电子科技大
13
学出版社,2007年 [2]塔嫩鲍姆等,《操作系统设计与实现》,电子工业出版社,2007 [3]罗宇等,《操作系统课程设计》,
机械工业出版社,2005 [4]郑扣根著,《操作系统概念》,高
等教育出版社,2010
[5]严蔚敏,吴伟明著,《数据结构》,北京 清华大学出版
社,2006 [6]斯托林肯著,《操作系统:精髓与设计原理》,
机械工业出版社,2010
附录
#include #include #include
int Available[10]; //可使用资源向量 int Max[10][10]; //最大需求矩阵 int Allocation[10][10]={0}; //分配矩阵 int Need[10][10]={0}; //需求矩阵 int Work[10];
//工作向量 int Finish[10]; //状态标志
int Request[10][10]; //进程申请资源向量 int Pause[10]; int List[10]; int i,j;
int n; //系统资源总数 int m;
//总的进程数
int a; //当前申请的进程号 int l,e; //计数器 int b=0,c=0,f=0,g;
//计数器 void mainenter()//主要的输入部分代码 {
14
printf(
printf(
printf(
for(i=1;ifor(j=1;jprintf(
void mainrequest() //进程提出新申请的代码部分 {
printf(
scanf(
printf(
printf(
Available[i]=Available[i]-Request[a][i];
Allocation[a][i]=Allocation[a][i]+Request[a][i];
Need[a][i]=Need[a][i]-Request[a][i]; Work[i]=Available[i]; }
for(i=1;iPause[i]=Available[i];//Pause[i]只是一个暂时寄存
的中间变量,为防止在下面 //安全性检查时修改到Available[i]而代替的一维数组
Finish[i]=false; }
for(g=1;gfor(i=1;ib=0; //计数器初始化
for(j=1;jif(Need[i][j]b=b+1; }
if(Finish[i]==false&&b==n) {
for(l=1;lPause[l]=Pause[l]+Allocation[i][l]; }
Finish[i]=true;
printf(
15
printf(
for(i=1;i{
if(Finish[i]==true) f=f+1;//统计Finish[i],,true的个数
}
if (f==m)
{
printf(
f=0;//将计数器f重新初始化,为下一次提出新的进程申请做准备 }
else
{
printf(
for(i=1;i{
Available[i]=Available[i]+Request[a][i];
Allocation[a][i]=Allocation[a][i]-Request[a][i];
Need[a][i]=Need[a][i]+Request[a][i];
}
}
}
void mainprint()
{
printf(
16
printf(
for(j=1;j{
printf(
}
for(i=1;i{
printf(
for(j=1;j{
printf(
}
for(j=1;j{
printf(
}
for(j=1;j{
printf(
}
}
printf(
for(i=1;i{
printf(
}
printf(
}
17
void main()
{ int k,h=1;
while(h)
{ system(
{
printf(
printf(
scanf(
}
switch(k)
{
case 1:mainenter(); break;
case 2:mainrequest(); break;
case 3:mainprint(); break;
case 4:h=0; break;
}
printf(
system(
}
system(
printf(
printf(
18
}
百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网92to.com,您的在线图书馆
19