银行家算法课程设计

1、信息与计算科学信息与计算科学操作系统原理操作系统原理课程设计报告课程设计报告题目： 银行家算法程序设计班级： 姓名：专业： 银行家算法程序设计第 页1银行家算法程序设计目录1.1.绪论绪论.22.2.需求分析需求分析.22.1 功能需求.22.2 数据需求.23.3. 总体设计总体设计.23.1 功能模块设.23.2 系统设计方案.33.3 开发工具.44.4. 详细设计详细设计.44.1 银行家算法中的数据结构.44.2 银行家算法.54.3 安全性算法.65.5. 调试与测试调试与测试.86.6. 结论结论.8结束语结束语.8参考文献参考文献.9附录附录 1 1用户手册用户手册.10附录附

2、录 2 2源程序清单源程序清单.12银行家算法程序设计第 页21.1.绪论绪论20 世纪末，随着计算机科学的发展，c 语言的应用越来越广泛，很多程序都需要使用 c 语言来编写。c 语言使用方便快捷，它已经成为计算机编程中不可缺少的一部分，而且它也被用于各个方面。例如：政府部门，银行，学校等等。银行家算法是判断系统是否安全，并且允许其它进程来申请这里的资源，任何一个进程来申请资源时，必须先登记该进程对资源的申请要求然后由系统检查当前资源的状况，并用银行家算法和安全性算法来检查是否允许分配资源给进程。通过课程设计，加深我们对利用银行家算法避免死锁的理解。在设计中主要的难点是用语言编写银行家算法和安

3、全性算法，使系统资源分配能安全进行，避免系统死锁。2.2.需求分析需求分析2.12.1 功能需求功能需求1.添加进程的可用资源，最大资源，已分配资源；2.判断系统是否安全；3.申请资源；4.申请资源后如何分配；5.进行安全检查。2.22.2 数据需求数据需求主要数据包括：可用资源，最大资源，已分配资源，申请资源数。3.3. 总体设计总体设计3.13.1 功能模块设功能模块设银行家算法程序设计第 页3对资源进行分配银行家算法判断是否安全输出安全序列图 1 功能模块图3.23.2 系统设计方案系统设计方案在程序中设计五个进程，分别为 p0,p1,p2,p3,p4。共享三类资源。在这个资源管理系统中

4、对进程的所需最大资源(max)、已分配给当前进程资源(allocation)和系统可用资源(available)分别进行了初始化了值。进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列，若分配不安全，则释放分配的资源，防止使系统进入不安全状态。显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。程序还可以实现对系统的修改。如果修改系统可用资源(available)，和进程分配资源。程序具体的设计是：函数 void showdata()用来显示资源矩阵，包括系统可用资源数目，进程对资源最大需求数，系

5、统已分配给进程的资源数，进程还需求资源。通过以上显示，很直观的观察到资源分配和修改的过程。函数 share()用来利用银行家算法对某个进程申请资源对进行判定。函数 int setdata(int k)用来实现资源试探分配。主要执行银行家算法程序设计第 页4的步骤是 vailablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj;函数 panduan()用来实现安全性算法，对分配后的资源进行计算，若分配资源后，系统是安全的，则资源完成本次分配。若不安全将本次的试探分配作废，调用 b

6、ackdata()函数恢复原来的资源分配状态。3.33.3 开发工具开发工具该程序是采用 c 程序设计完成的，vc6.0 的编译环境。4.4. 详细设计详细设计4.14.1 银行家算法中的数据结构银行家算法中的数据结构1.可利用资源向量 available是个含有 3 个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果availablej=k，则表示系统中现有 rj 类资源 k 个。 2.最大需求矩阵 max这是一个 53 的矩阵，它定义了系统中 5 个进程中的每一个进程对 3 类资源的最大需求。如果 maxi,j=k，则表示进程 i 需要 rj 类资源的最大数目为 k。3.分配矩阵

7、 allocation这也是一个 53 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 allocationi,j=k，则表示进程 i 当前已分得 rj 类资源的数目为 k。4.需求矩阵 need这也是一个 53 的矩阵，用以表示每一个进程尚需的各类资源数。如果needi,j=k，则表示进程 i 还需要 rj 类资源 k 个，方能完成其任务。 needi,j=maxi,j-allocationi,j银行家算法程序设计第 页5初始化函数showdata()开始输入各可用资源输入已分配资源输入每个进程最多所需资源初始化函数showdata()结束图 2 赋值4.24.2 银行家

8、算法银行家算法设 requesti 是进程 pi 的请求向量，如果 requestij=k，表示进程 pi 需要 k 个rj 类型的资源。当 pi 发出资源请求后，系统按下述步骤进行检查：如果 requestijneedi,j ，便转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。1.如果 requestijavailablej ，便转向步骤(3)；否则， 表示尚无足够资源，pi 须等待。 银行家算法程序设计第 页62.系统试探着把资源分配给进程 pi，并修改下面数据结构中的数值： availablej=availablej-requestij; allocationi,j

9、=allocationi,j+requestij; needi,j=needi,j-requestij;3.系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程 pi 等待。4.34.3 安全性算法安全性算法1.设置两个向量：工作向量 work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m个元素，在执行安全算法开始时，work=available; 工作向量 finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 finishi=

10、false; 当有足够资源分配给进程时， 再令 finishi=true。 2.从进程集合中找到一个能满足下述条件的进程： finishi=false; needi,jworkj ；若找到，执行 (3)，否则，执行 (4)3.当进程 pi 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：workj=worki+allocationi,j;finishi=true;go to step 2; 4.如果所有进程的 finishi=true 都满足， 则表示系统处于安全状态；否则，系统处于不安全状态银行家算法程序设计第 页7开始初始化showdata()判断needijworkj

11、？tempi=truetempi=false是否workj=workj+allocationij;5个进程是否判断完毕？否输出安全序列显示分配结束是不安全图 3 安全性判断银行家算法程序设计第 页85.5. 调试调试与测试与测试1.在执行程序时，有时分配空间能够造成死锁也会分配资源。通过细心地查找发现了其中的逻辑错误，并加以改正。2.在使用循环语句：while 时由于循环条件的值没有改变，所以形成了死循环。通过耐心的检查发现了这一错误，然后将其改正。3.在执行程序时，有时分配资源数大于总资源数时仍能分配。通过调试找到其中的错误并改正。4.在使用选择语句 if 时，经常出现逻辑错误。通过老师的指

12、导，改正了错误。6.6. 结论结论这次操作系统实验基本上已经达到了预期的目的：能够实现银行家算法。虽然程序已经可以使用了，但是它还是有一些需要改进的地方。例如：不能同时对 2 个进程进行分配，不能自行输入进程数量和进程种类。实验主要是银行家算法部分：1.如果 request=need,便转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。2.如果 request=available,便转向步骤 3；否则，表示尚无足够资源，需要等待。3.系统试探分配请求的资源进程。4.系统执行安全性算法。结束语结束语近两周的操作系统实验结束了，从开始选择题目到作品的完成，再到设计报告的完成，

13、每一步对我来说都是新的尝试与挑战，在老师的细心指导和严格要求下我顺利的完成的任务，做出了理想的程序。虽然这是我第三次做课设，但是我对操作系统的实验还是不了解。通过老师的耐心指导我的 c 语言水平有所提高，并且完全明白了银行家算法。虽然课程设计占用了我大量的时间，但是却让我复习了一下过去所学到的知识，我认为银行家算法程序设计第 页9还是值得的。在做这次课程设计过程中不但使我学到了很多 c 语言方面的知识，而且我也领悟到了一些真理。我感到不论做什么事只有真正用心去做，才能克服种种困难，其实有些时候困难本身并不可怕，真正可怕的是面对困难我们缺少的决心和信心。光学不做是没有意义的，只有实践才能学好，要

14、想学好一门科目就要经常做一些练习。希望这次的经历能让我在今后的学习. 工作和生活中不断成长与进步。参考文献参考文献1谭浩强.c 程序设计（第三版）. 北京：清华大学版社，20052汤子灜.哲凤屏. 汤小丹.计算机操作系统（第三版）. 西安：电子科技大学出版社，2007银行家算法程序设计第 页10附录附录 1 1用户手册用户手册1.输入可利用资源：2.输入需要申请资源的进程号：系统不安全银行家算法程序设计第 页113.输入需要申请资源的进程号：系统安全并输出安全序列4.输入申请资源错误银行家算法程序设计第 页12附录附录 2 2源程序清单源程序清单#include int available3,

15、allocation53,max100100;/已有资源量 int need100100,work50,finish5,work53;/需求int request3=0,0,0; int i,j,n,m,l=0,flag=0,temp5=0,1,2,3,4;void showdata() int i,j; for(i=1;i5;i+) for(j=0;j3;j+) worktemp0j=availablej; worktempij=worktempi-1j+allocationtempi-1j; cout 系统可用的资源数为:endlendl; cout 资源: a: available0;

16、cout b: available1; cout c: available2; coutendlendl; cout work need allocation work+allocationendl; cout资源 a b c a b c a b c a b cendl; for (i=0;i5;i+) cout进程 ptempi:; for (j=0;j3;j+)cout worktempij; coutt; for (j=0;j3;j+)cout needtempij; coutt; for (j=0;j3;j+)cout allocationtempij; coutt; for (j=0

17、;j3;j+)cout worktempij+allocationtempij; coutendl; cout-endlendl; void setdata(int k) int j; 银行家算法程序设计第 页13 for (j=0;j3;j+) availablej=availablej-requestj; allocationkj=allocationkj+requestj; needkj=needkj-requestj; void backdata(int k) int j; for (j=0;j3;j+) availablej=availablej+requestj; allocati

18、onkj=allocationkj-requestj; needkj=needkj+requestj; int panduan(int t) int h=0; int i=t; while(i5)flag=0; if (finishi=0) for (j=0; j=needij) flag=flag+1; if(flag=m) finishi=1; for (j=0; jm;j+) workj=workj+allocationij; l=l+1;temph=i;h+; i=0;银行家算法程序设计第 页14elsei+;return l; void main() int k=0,r=0; cout输入各种资源可利用的数量 available3: endl; for (j=0; javailablej; workj=availablej; coutn 请输入各进程当前已分配的资源数量 allocation53: endl; coutn 请严格按照(53)的距阵输入:endl; for (i=0; i5; i+) for (j=0; jallocationij; finishi=0; coutn 输入各进程对各类资源的