【操作系统课程设计】银行家算法的设计与实现.docx

内蒙古工业大学操作系统课程设计学校代码： 10128学 号： 200810205004课程设计题 目：银行家算法的设计与实现 学生姓名：朱见涛 学 院：信息工程学院系 别：计算机系 专 业：软件工程 班 级：软08-1指导教师：秦俊平 讲师马志强 讲师20011年1月18日 15内蒙古工业大学课程设计任务书（二）学院（系）：信息学院计算机系 课程名称：操作系统课程设计 指导教师（签名）： 专业班级： 软件工程 081 学生姓名： 朱见涛 学号： 200810205004 一、课程设计题目银行家算法的设计与实现二、课程设计的目的通过银行家算法设计与实现，可以加深学生对死锁的理解，掌握死锁的预防、避免、检测和解除的基本原理，重点掌握死锁的避免方法银行家算法。使学生初步具有研究、设计、编制和调试操作系统模块的能力。 三、课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求等） 技术参数： Windows XP系统，VC+6.0开发工具。设计要求： 1 设计银行家算法的核心数据结构、安全性检查算法；2 画出银行家算法流程图；3 编程实现算法功能；4 编写课程设计说明书。 工作量要求：完成以上设计要求中的所有算法功能。四、工作进度安排 周一：布置、讲解题目，收集资料；周二：系统分析，算法设计；周三：编制、调试程序；周四：测试系统，形成设计结论，编写课设报告；周五：系统及材料验收，课设答辩。五、主要参考文献1 张尧学编计算机操作系统教程（第三版）习题解答与实验指导北京:清华大学出版社，20062 汤子瀛主编计算机操作系统（第三版）西安:西安电子科技大学出版社，2001 3 张坤等编操作系统实验教程北京:清华大学出版社，2008审核批准意见系（教研室）主任（签字） 目 录第一章设计内容111 设计目的112 设计要求113 程序设计思想1第二章 数据结构、算法和算法流程图221 数据结构222 程序功能图223 程序流程图3第三章 程序运行结果及分析631 程序运行结果632 程序分析7第四章 心得体会8参考文献9附录 程序清单10第一章 设计内容11 设计目的通过银行家算法设计与实现，可以加深学生对死锁的理解，掌握死锁的预防、避免、检测和解除的基本原理，重点掌握死锁的避免方法银行家算法。使学生初步具有研究、设计、编制和调试操作系统模块的能力。12 设计要求1.问题描述银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态的申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当与用户向银行家贷款。操作系统按照银行家指定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足他的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。2.基本要求1）分析设计内容，给出解决方案（要说明设计实现的原理，采用的数据结构）。2）画出程序的基本结构框图和流程图。3）对程序的每一部分要有详细的设计分析说明。4）源代码格式要规范。5）设计合适的测试用例，队得到的运行结果要有分析。6）设计中遇到的问题，设计的心得体会。7）按期提交完整的程序代码，可执行程序和课程设计报告。1.3 程序设计思想1.设计思想输入当前进程资源的使用情况以及整个系统的资源使用情况，并进行初始化安全性检查；如果是不安全状态，重新初始化系统；否则，从等待队列中提取一个等待进程，使用银行家算法进行检测，输出当前系统的状态和安全序列；如果是安全状态，系统继续从等待队列中提取等待进程进行检查；如果是不安全状态，进程回到等待队列，系统从等待队列中提取等待进程进行检查。系统中申请资源的进程全部进入等待队列等候处理。第二章 数据结构、算法和算法流程图21 数据结构银行家算法中用到的主要数据结构可用资源向量 int AVAILABLEi /j为资源的种类最大需求矩阵 int MAXij /i为进城的数量分配矩阵 int ALLOCATIONij 需求矩阵 int NEEDij=MAXij-ALLOCATIONij申请各类资源数量 int REQUESTij /i申请j资源的数量工作向量 int Worki int FINISHi安全序列 int pi22 程序功能图银行家算法系统显示分配资源状态资源分配安全性检查初始化资源银行家算法实现资源分配显示安全序列图2.1文件系统提供的文件操作有建立文件(mkfile)、复制文件(copy)、显示文件所有内容(type)、删除文件(delfile)。可以通过键盘输入命令来模拟文件的操作。23 程序流程图（1）主程序流程图：图2.1第三章 程序运行结果及分析31 程序运行结果（1）初始化界面图3.1（2）检测系统资源分配是否安全（若安全，输入安全序列）图3.2图3.332 程序分析本程序依靠键盘输入初始化系统资源数量及种类，有银行家算法检验系统资源是否安全，输出安全序列。提出请求REQUESTi，同意分配，则进行安全性算法Safe（），否则输出提示：请求被拒绝。直到所有进程FINISH=true，安全且输出安全序列，安全算法Safe（）结束。第四章 心得体会通过本次的课程设计，使我能够正确运用操作系统课程中所学的基本理论和知识。操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死锁”。银行家算法是一个分配资源的过程，是分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。本次程序就是按照上面的思路展开的。但是因为时间上的仓促，本课程设计存在以下不足：一、不能实现并发操作，即当总资源同时满足几个进程所需要的资源数时，这些进程不能同时进行，只能一一按进程顺序执行。二、扫描进程顺序单一，只能按进程到来的顺序来扫描，从而产生的安全序列只能是在这个顺序的基础上产生的，而其实安全序列是有多个的。三、对进程数和资源数进行的数量进行了限制，都只能最多有十个。四、运行程序后，界面较差，进程数，所需要资源数，已分配资源数，能用资源数，不能一目了然。设计一个软件，先要做好需求分析，这一点很重要，如果没有分析好需求，到软件设计的最后，发现所做的功能不符合要求，那么一切都得重做。还有比较重要的是，画好程流程图。在编程和调试的过程中，经常会出现意想不到的问题，并非每个问题都可以从相关资料中找到解决方法，有些问题是无法预料到的，这就需要通过自己理性的分析得出问题的解决方案。在设计过程中，查询了不少相关资料，不断的发现问题、提出问题、解决问题。总的来说通过这次的设计的学习使我学到了很多在平时的学习中学不到的很多东西，通过这次课程设计，使我学到了很多的实用性知识。除了更深的了解这个算法，而且对C语言进行了复习，而且其过程中有很多的知识点都不记得了，所以在此感谢在此过程中帮助过我的老师和同学。参考文献1 张尧学编计算机操作系统教程（第三版）习题解答与实验指导北京:清华大学出版社，20062 汤子瀛主编计算机操作系统（第三版）西安:西安电子科技大学出版社，2001 3 CSDN论坛4 张丽芬等编操作系统实验教程北京:清华大学出版社，2006附录 程序清单#include using namespace std;#define MAXPROCESS 10 /*最大进程数*/#define MAXRESOURCE 10 /*最大资源数*/int AVAILABLEMAXRESOURCE; /*可用资源数组*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩阵*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩阵*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩阵*/int REQUESTMAXPROCESSMAXRESOURCE; /*进程申请资源数*/bool FINISHMAXPROCESS; /*系统是否有足够的资源分配*/int pMAXPROCESS; /*记录序列*/int m,n; /*m个进程,n个资源*/void Init();bool Safe();void Bank();int main() Init(); Safe(); Bank();void Init() /*初始化算法*/ int i,j; printf(请输入进程的数目:); scanf(%d,&m); printf(请输入资源的种类:); scanf(%d,&n); printf(请输入每个进程最多所需的各资源数,按照%dx%d矩阵输入n,m,n); for(i=0;im;i+) for(j=0;jn;j+) scanf(%d,&MAXij); printf(请输入每个进程已分配的各资源数,也按照%dx%d矩阵输入n,m,n); for(i=0;im;i+) for(j=0;jn;j+) scanf(%d,&ALLOCATIONij); NEEDij=MAXij-ALLOCATIONij; if(NEEDij0) printf(您输入的第%d个进程所拥有的第%d个资源数错误,请重新输入:n,i+1,j+1); j-; continue; printf(请输入各个资源现有的数目:n); for(i=0;in;i+) scanf(%d,&AVAILABLEi); void Bank() /*银行家算法*/ int i,cusneed; char again; while(1) printf(请输入要申请资源的进程号(注:第1个进程号为0,依次类推)n); scanf(%d,&cusneed); printf(请输入进程所请求的各资源的数量n); for(i=0;in;i+) scanf(%d,&REQUESTcusneedi); for(i=0;iNEEDcusneedi) printf(您输入的请求数超过进程的需求量!请重新输入!n); continue; if(REQUESTcusneediAVAILABLEi) printf(您输入的请求数超过系统有的资源数!请重新输入!n); continue; for(i=0;in;i+) AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() printf(同意分配请求!n); else printf(您的请求被拒绝!n); for(i=0;in;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;im;i+) FINISHi=false; printf(您还想再次请求分配吗?是请按y/Y,否请按其它键n); scanf(%d,&again); if(again=y|again=Y) continue; break; bool Safe() /*安全性算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作数组*/ for(i=0;in;i+) Worki=AVAILABLEi; for(i=0;im;i+) FI