银行家算法的模拟实现（课程设计）

课程设计报告银行家算法的模拟实现专业计算机科学与技术学生姓名徐静班级B计073学号0710604325指导教师李先锋完成日期2011年1月信息工程学院目录TOC\o"1-3"\f\h\z一、设计目的 2二、设计内容 2〔1〕概述 2〔2〕设计原理 2〔3〕详细设计及编码 3〔4〕运行结果分析 7〔5〕设计小结 9〔6〕参考文献 9题目：银行家算法的模拟实现一、设计目的TC"一、设计目的"\fC本课程设计是学习完“操作系统原理〞课程后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统根底理论和重要算法的理解，加强学生的动手能力。二、设计内容TC"二、设计内容"\fC〔1〕概述TC"〔1〕概述"\fC我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规那么为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量那么按当前的申请量分配资源，否那么就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。假设超过那么拒绝分配资源，假设没有超过那么再测试系统现存的资源能否满足该进程尚需的最大资源量，假设能满足那么按当前的申请量分配资源，否那么也要推迟分配。〔2〕设计原理TC"〔2〕设计原理"\fC1、银行家算法

〔1〕如果Requesti＜或=Need,那么转向步骤2；否那么，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

〔2〕如果Request＜或=Available,那么转向步骤〔3〕；否那么，表示系统中尚无足够的资源，P1必须等待。

〔3〕系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：

Available:=Available-Requesti;

Allocation:=Allocationi+Request;

Needi:=Needi-request;

(4)系统执行平安性算法，检查此次资源分配后，系统是否处于平安状态。

2、平安性算法

系统所执行的平安性算法可描述如下：

〔1〕设置两个向量

①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，它含有m个元素，执行平安算法开始时，Work:=Allocation;

②Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]:=false;当有足够资源分配给进程时，令Finish[i]:=true。

〔2〕从进程集合中找到一个能满足下述条件的进程：

①Finish[i]:=false

②Need</=Work

如找到，执行步骤〔3〕；否那么，执行步骤〔4〕。

〔3〕当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work：=Work+Allocation;

Finish[i]：=true;

Gotostep2;

〔4〕如果所有进程的Finish[i]=true,那么表示系统处于平安状态；否那么，系统处于不平安状态〔3〕详细设计及编码TC"〔3〕详细设计及编码"\fC流程图：银行家算法的具体实现程序：#include<stdio.h>#defineR10#defineP10intSafeCheck(intn,intm,intMax[P][R],intAllocation[P][R],intAvailable[R],intNeed[P][R]){ intp,i,j,safeque[P],Work[R],Finish[P]={0},t=0,flag; printf("当前的工作向量为："); for(j=0;j<m;j++){ Work[j]=Available[j];printf("%d,",Work[j]); }//设置Work向量 while(t<n){ //开始寻找可分配的进程 for(i=0;i<n;i++){ if(Finish[i]==1)flag=0;//跳过已分配结束的进程 elseflag=1; if(flag){ p=i; for(j=0;j<m;j++) if(Need[p][j]>Work[j]){p=-1;break;} } if(p==i) {printf("找到一个可分配的进程P%d!\n",p);break;} }//顺序循环查找可分配资源的进程 if(p!=-1){ safeque[t++]=p;//入栈保护 Finish[p]=1;//标志该进程结束 printf("当前的工作向量为："); for(j=0;j<m;j++){ Work[j]+=Allocation[p][j]; printf("%d,",Work[j]); } p=-1;//清空当前进程号，以便下一次寻找出新的进程 }//找到可分配资源的进程，并重设Work向量 else{printf("找不到一个可分配的进程！终止检查！");break;} } if(t==n){ printf("系统存在一个平安序列:"); for(t=0;t<n;t++) printf("P%d->",safeque[t]); printf("\n"); return1; } else{printf("系统不平安！会产生死锁！\n");return0;}}voidmain(){ intAvailable[R],Max[P][R],Allocation[P][R],Need[P][R]; inti,n,m,j,p,Request[R]; intsafe1,safe2;//设置第一次检查与第二次检查正确与否的观察变量 printf("输入进程总数:"); scanf("%d",&n); printf("输入资源类数:"); scanf("%d",&m); printf("系统中R0--R%d类资源可利用数〔空格隔开〕:",m-1); for(i=0;i<m;i++){ scanf("%d",&Available[i]); } for(i=0;i<n;i++){ printf("P%d进程的每类资源的分配情况如下:\n",i); printf("\tR0--R%d类资源最大数〔空格隔开〕:",m-1); for(j=0;j<m;j++){ scanf("%d",&Max[i][j]); } printf("\tR0--R%d类资源已分配〔空格隔开〕:",m-1); for(j=0;j<m;j++){ scanf("%d",&Allocation[i][j]); Need[i][j]=Max[i][j]-Allocation[i][j]; } printf("\tR0--R%d类资源需求数〔空格隔开〕:",m-1); for(j=0;j<m;j++){ printf("%d",Need[i][j]); } printf("\n"); }//初始化进程的资源分配表 printf("——————-第一次平安性检查——————\n"); safe1=SafeCheck(n,m,Max,Allocation,Available,Need); if(safe1){ printf("输入请求请求进程P的进程号:"); scanf("%d",&p); printf("输入请求的R0--R%d各类资源数〔空格隔开〕:",m-1); for(j=0;j<m;j++){ scanf("%d",&Request[j]); if(Request[j]>Need[p][j]){ printf("所请求的该资源数大于该进程所需求的最大值！终止请求！"); safe1=0;break; } if(Request[j]>Available[j]){ printf("所请求的该资源数大于系统中所拥有的最大值！终止请求！"); safe1=0;break; } } }//第一次平安检查系统平安后判断请求向量的正确性 if(safe1){ printf("——————-第二次平安性检查——————\n"); for(j=0;j<m;j++){ Allocation[p][j]+=Request[j]; Need[p][j]=Max[p][j]-Allocation[p][j]; Available[j]-=Request[j]; }//第二次平安检查前试探分配资源给请求资源 safe2=SafeCheck(n,m,Max,Allocation,Available,Need); if(safe2==0) for(j=0;j<m;j++){ Allocation[p][j]-=Request[j]; Need[p][j]=Max[p][j]-Allocation[p][j]; Available[j]+=Request[j]; }//平安检查失败后重新收回分配给请求进程的资源 }〔4〕运行结果分析TC"〔4〕运行结果分析"\fC开始运行截图：结果运行截图：输入输出数据说明：主函数模块功能：用于程序与用户的交互操作，由用户选择模拟实验的算法，并执行相应的算法。数据输入模块功能：系统由此输入数据，并检测输入的数据是否超过了系统最大的进程数或最大数据种类。数据显示模块功能：显示系统运行过程中数据的变化，并显示出系统所需数据。平安检查模块功能：检测系统的运行过程中系统是否平安。资源检测模块功能：检测系统分配的资源是否合理结果分析：分析：该程序找到的平安序列：第一次检查{p1,p0,p2,p3}第二次检查{p1,p0,p2,p3}银行家算法就是当接收到一个系统资源的分配后找到一个平安序列，使得进程间不会发生死锁，假设发生死锁那么让进程等待。〔5〕设计小结TC"〔5〕设计小结"\fC一周的操作系统课程设计终于结束了，感觉收获还是蛮大的。唤回了我对操作系统的重新的认识，在编写程序不断出现错误和改正的过程序中加深了我对银行家算法的理解。这个系统的功能根本能满足要求，完成了对资源的修改还有用银行家算法和平安性算法来检查是否允许分配资源给进程。设计主要由两局部组成。第一局部:银行家算法(扫描)，第二局部平安性算法首先在网上收集了一些关于银行家的资料，加深了对它的理解，首先需要初始化系统资源，其次，平安性检查，再者，试分配，最后是试分配后的平安性检查。在程序测试中出现了很多问题，例如，死循环，逻辑关系的设计不当，通过查阅书本，对算法细节重新建立正确的认识后。在通过单步调试后。最终解决。还有