第一篇：操作系统课程设计(银行家算法的模拟实现)
操作系统课程设计
（银行家算法的模拟实现）
一、设计目的
1、进一步了解进程的并发执行。
2、加强对进程死锁的理解。
3、用银行家算法完成死锁检测。
二、设计内容
给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝（银行家算法）模拟该进程组的执行情况。
三、设计要求
1、初始状态没有进程启动。
2、计算每次进程申请是否分配，如：计算出预分配后的状态情况（安全状态、不安全状态），如果是安全状态，输出安全序列。
3、每次进程申请被允许后，输出资源分配矩阵A和可用资源向量V。
4、每次申请情况应可单步查看，如：输入一个空格，继续下个申请。
四、算法原理
1、银行家算法中的数据结构(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、银行家算法应用
模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成：一是银行家算法（扫描）；二是安全性算法。
（1）银行家算法（扫描）
设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
①如果Requesti[j]<=Need[i,j]，便转向步骤②；否则认为出错，因为它所需的资源数已经超过了它所宣布的最大值。
②如果Requesti[j]<=Allocation[i,j]，便转向步骤③；否则表示尚无足够资源，Pi需等待。
③系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值。
Available[j]=Available-Requesti[j]；
Allocation[i,j]=Allocation[i,j]+Requesti[j]；
Need[i,j]=Need[i,j]-Requesti[j]；
④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，已完成本次分配；否则，将本次的试探分配作废，恢复原来资源的分配状态，让进程Pi等待。
（2）安全性算法
系统所执行的安全性算法可描述如下：
①设置两个向量：一个是工作向量Work；它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，在执行安全性算法开始时，work=Available；另一个是Finish；它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true；
②从进程集合中找到能满足下述条件的进程：
一是Finish[i]==false；二是Need[i,j]<=Work[j]；若找到，执行步骤③，否则，执行步骤④；
③当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j]=Work[j]+Allocation[i,j]；
Finish[i]=true；
go to step②；
④如果所有进程的 Finish[i]==true都满足，则表示系统处于安全状态，否则系统处于不安全状态。
五、设计思路
1、进程一开始向系统提出最大需求量；
2、进程每次提出新的需求（分期贷款）都统计是否超出它事先提出的最大需求量；
3、若正常，则判断该进程所需剩余量（包括本次申请）是否超出系统所掌握的剩余资源量，若不超出，则分配，否则等待。
六、程序运行调试结果
1、程序初始化
2、检测系统资源分配是否安全结果
七、小结
“银行家算法的模拟实现”是本学期操作系统课程的课程设计。在设计此程序的过程中我们遇到过许多问题也学到了很多东西。通过这周的课程设计，我加深了对银行家算法的理解，掌握了银行家算法避免死锁的过程和方法，理解了死锁产生的原因和条件以及避免死锁的方法。所编写程序基本实现了银行家算法的功能，并在其基础上考虑了输出显示格式的美观性，使界面尽可能友好。并且在编程时将主要的操作都封装在函数中，这样使程序可读性增强，使程序更加清晰明了。在算法的数据结构设计上考虑了很长时间。在程序设计中先后参考了很多网络资料也参考了一些别人写的的程序综合这些算法思想和自己的思路对程序做了很好的设计方式对一些算法的优越性等也作了一些考虑。当然，在编写和调试过程中我遇到了许多的问题，通过网上查询资料、翻阅课本、向同学请教、多次调试等方法逐渐解决了大部分问题。让我收获很多，相信在今后的生活中也有一定帮助。
附：程序源代码：
#include
int no1;//进程数 int no2;//资源数 int r;int allocation[m][m],need[m][m],available[m],max[m][m];char name1[m],name2[m];//定义全局变量 void main(){ void check();void print();int i,j,p=0,q=0;char c;int request[m],allocation1[m][m],need1[m][m],available1[m];printf(“**********************************************n”);printf(“* 银行家算法的设计与实现 *n”);printf(“**********************************************n”);printf(“请输入进程总数:n”);scanf(“%d”,&no1);printf(“请输入资源种类数:n”);scanf(“%d”,&no2);printf(“请输入Max矩阵:n”);for(i=0;i for(j=0;j scanf(“%d”,&max[i][j]);//输入已知进程最大资源需求量 printf(“请输入Allocation矩阵:n”);for(i=0;i for(j=0;j scanf(“%d”,&allocation[i][j]);//输入已知的进程已分配的资源数 for(i=0;i for(j=0;j need[i][j]=max[i][j]-allocation[i][j];//根据输入的两个数组计算出need矩阵的值 printf(“请输入Available矩阵n”);for(i=0;i scanf(“%d”,&available[i]);//输入已知的可用资源数 print();//输出已知条件 check();//检测T0时刻已知条件的安全状态 if(r==1)//如果安全则执行以下代码 { do{ q=0;p=0;printf(“n请输入请求资源的进程号(0~4)：n”); for(j=0;j<=10;j++) { scanf(“%d”,&i); if(i>=no1) { printf(“输入错误，请重新输入：n”); continue; } else break; } printf(“n请输入该进程所请求的资源数request[j]:n”); for(j=0;j scanf(“%d”,&request[j]); else //请求满足条件 { for(j=0;j { available1[j]=available[j]; allocation1[i][j]=allocation[i][j]; need1[i][j]=need[i][j]; //保存原已分配的资源数，仍需要的资源数和可用的资源数 available[j]=available[j]-request[j]; allocation[i][j]+=request[j]; need[i][j]=need[i][j]-request[j];//系统尝试把资源分配给请求的进程 } print(); check();//检测分配后的安全性 if(r==0)//如果分配后系统不安全 { for(j=0;j { available[j]=available1[j]; allocation[i][j]=allocation1[i][j]; need[i][j]=need1[i][j];//还原已分配的资源数，仍需要的资源数和可用的资源数 } printf(“返回分配前资源数n”); print(); } } }printf(“n你还要继续分配吗？Y or N ?n”); //判断是否继续进行资源分配 for(j=0;j if(p) printf(“请求资源超过该进程资源需求量，请求失败！n”);else { for(j=0;j if(request[j]>available[j])q=1;//判断请求是否超过可用资源数 if(q) printf(“没有做够的资源分配，请求失败！n”); c=getche(); }while(c=='y'||c=='Y');} } void check()//安全算法函数 { int k,f,v=0,i,j;int work[m],a[m];bool finish[m];r=1;for(i=0;i finish[i]=false;// 初始化进程均没得到足够资源数并完成for(i=0;i k=no1;do{ for(i=0;i { if(finish[i]==false) { f=1; for(j=0;j if(need[i][j]>work[j]) f=0; if(f==1)//找到还没有完成且需求数小于可提供进程继续运行的资源数的进程 { finish[i]=true; a[v++]=i;//记录安全序列号 for(j=0;j work[j]+=allocation[i][j];//释放该进程已分配的资源 } } } k--;//每完成一个进程分配，未完成的进程数就减1 }while(k>0);f=1;for(i=0;i if(finish[i]==false) { f=0; break; } } if(f==0)//若有进程没完成，则为不安全状态 { printf(“系统处在不安全状态！”); r=0;} else { printf(“n系统当前为安全状态，安全序列为：n”); for(i=0;i printf(“p%d ”,a[i]);//输出安全序列 } } void print()//输出函数 { int i,j;printf(“n”);printf(“*************此时刻资源分配情况*********************n”);printf(“进程名/号 | Max | Allocation | Need |n”);for(i = 0;i < no1;i++) { printf(“ p%d/%d ”,i,i); for(j = 0;j < no2;j++){printf(“%d ”,max[i][j]);} for(j = 0;j < no2;j++) {printf(“ %d ”,allocation[i][j]);} for(j = 0;j < no2;j++) {printf(“ %d ”,need[i][j]);} printf(“n”); } printf(“n”); printf(“各类资源可利用的资源数为:”); for(j = 0;j < no2;j++) {printf(“ %d”,available[j]);} } printf(“n”); （程序结束） 操作系统 课程设计报告 专业 计算机科学与技术 学生姓名 班级 学号 指导教师 完成日期 信息工程学院 题目： 银行家算法的模拟实现 一、设计目的本课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练，通过课程设计，更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 二、设计内容 1）概述 用C或C++语言编制银行家算法通用程序，并检测所给状态的系统安全性。 1.算法介绍：数据结构： 1） 可利用资源向量 Available； 2） 最大需求矩阵Max； 3） 分配矩阵Allocation； 4） 需求矩阵Need 2.功能介绍 模拟实现Dijkstra的银行家算法以避免死锁的出现，分两部分组成： 第一部分：银行家算法（扫描）； 第二部分：安全性算法。 2）设计原理 一．银行家算法的基本概念 1、死锁概念。 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 2、关于死锁的一些结论： Ø 参与死锁的进程最少是两个 Ø （两个以上进程才会出现死锁） Ø 参与死锁的进程至少有两个已经占有资源 Ø 参与死锁的所有进程都在等待资源 Ø 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 3、资源分类。 永久性资源： 可以被多个进程多次使用（可再用资源） l 可抢占资源 l 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请--分配--使用--释放”模式 4、产生死锁的四个必要条件：互斥使用（资源独占）、不可强占（不可剥夺）、请求和保持（部分分配，占有申请）、循环等待。 1) 互斥使用（资源独占） 一个资源每次只能给一个进程使用。 2) 不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放。 3) 请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）。 4) 循环等待 存在一个进程等待队列 {P1,P2,…,Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。 5、死锁预防: 定义:在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 ①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请 ②破坏“请求和保持”条件。 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 ③破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 6．安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，…Pn，则系统处于安全状态。一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i)当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的) 不安全状态:不存在一个安全序列，不安全状态一定导致死锁。 二．银行家算法 1、银行家算法中的数据结构 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、银行家算法 设Requesti是进程Pi的请求向量。如果Requesti[j]＝k，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 1）如果 Requesti[j]<=Need[i,j]，则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 2）如果Requesti[j]<=Available[j]，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待。 3）系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]:=Available[j]-Requesti[j]; Allocation[i,j]:=Allocation[i,j]+Requesti[j]; Need[i,j]:=Need[i,j]-Requesti[j]; 4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 3、安全性算法 系统所执行的安全性算法可描述如下： 1）设置两个向量 ①、工作向量Work。它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work = Available。 ②、Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]:=false ；当有足够资源分配给进程时，令 Finish[i]:=true。 2）从进程集合中找到一个能满足下述条件的进程： ①、Finish[i]=false; ②、Need[i,j]<=Work[j];如找到，执行步骤（3）；否则，执行步骤（4）。 3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]:=Work[i]+Allocation[i,j]; Finish[i]:=true; goto step 2； 4）如果所有进程的Finish[i]:=true，则表示系统处于安全状态；否则，系统处于不安全状态。 三．银行家算法之例 假定系统中有五个进程：{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7,在T0时刻的资源分配情况如图1所示。 资源情况 进程 Max Allocation Need Available A B C A B C A B C A B C P0 0 0 (2 0) P1 0 0 (3 0 2) (0 0) P2 0 0 0 0 P3 0 P4 0 0 图1 T0时刻的资源分配表 (1)T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图2)可知，在T0时刻存在着一个安全序列｛P1，P3，P4，P2，P0｝，故系统是安全的。 资源情况 进程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P1 0 0 true true true true true P3 0 P4 0 0 P2 0 0 0 P0 0 0 图2 T0时刻的安全序列 (2)P1请求资源：P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查： ①Request1(1,0,2)<=Need1(1,2,2) ②Request1(1,0,2)<=Available1(3,3,2) ③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成资源变化情况如图1中的圆括号所示。 ④再利用安全性算法检查此时系统是否安全。如图3所示。 资源情况 进程 Work Need Allocation Work+Allocation Finish A B C A B C A B C A B C P1 0 0 0 0 true true true true true P3 0 P4 0 0 P0 0 0 P2 0 0 0 图3 P1申请资源时的安全性检查 由所进行的安全性检查得知，可以找到一个安全序列｛P1,P3,P4,P2,P0｝。因此系统是安全的，可以立即将P1所申请的资源分配给它。 (3)P4请求资源：P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查： ①Request4(3,3,0)≤Need4(4,3,1); ②Request4(3,3,0)不小于等于Available(2,3,0),让P4等待。 (4)P0请求资源：P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查。 ①Request0(0,2,0) ≤Need0(7,4,3); ②Request0(0,2,0) ≤Available(2,3,0); ③系统暂时先假定可为P0分配资源，并修改有关数据，如图4所示。 资源情况 进程 Allocation Need Available A B C A B C A B C P0 0 0 0 P1 0 0 0 P2 0 0 0 P3 0 P4 0 0 图4 为P0分配资源后的有关资源数据 (5)进行安全性检查：可用资源Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。 3）详细设计及编码 1）银行家算法流程图 2）程序源代码 #include #include #include #include //定义全局变量 const int x=20,y=20; //常量，便于修改 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 chushihua(); //初始化函数 void safe(); //安全性算法 void show(); //函数show,输出当前状态 void bank(); //银行家算法 //void jieshu(); //结束函数 void chushihua() { cout<<“输入进程的数量: “;//从此开始输入有关数据 cin>>n; cout<<“输入资源种类数: “; cin>>m; cout< 种): “< for (j=0; j j++) { cout<<“输入资源 “< 可利用的数量Available[“< “; cin>>Available[j]; //输入数字的过程...Work[j]=Available[j]; //初始化Work[j]，它的初始值就是当前可用的资源数 } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 输入进程 “< 当前已分配的资源 “< 数量: “; cin>>Allocation[i][j]; } cout< Finish[i]=0;//初始化Finish[i] } cout< “< for (i=0; i i++) { for (j=0; j j++) { cout<<“ 输入进程 “< 对资源 “< “; cin>>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< } cout< } //安全性算法函数 void safe() { l=0; for (i=0; i { //i++ if (Finish[i]==0) { //逐个查找Finish[i]==0的进程 条件一 counter=0; //记数器 for (j=0; j j++) { if (Work[j]>=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 Work[j]=Work[j]+Allocation[i][j]; //释放资源 l=l+1; //记数,现在有L个进程是安全的，当L=N时说明满足安全序列 i= -1; //从第一个进程开始继续寻找满足条件一二的进程 } } } } //显示当前状态函数 void show() //函数show,输出当前资源分配情况 { int i,j; //局部变量 int All[y]; //各种资源的总数量 cout<<“当前的状态为：“< cout<<“各种资源的总数量:“< for (j=0;j { cout<<“ 资源“< “; All[j]=Available[j]; //总数量=可用的+已分配的for (i=0;i All[j]+=Allocation[i][j]; cout< “; } cout< for (j=0;j cout<<“ 资源“< “< “; cout< “< for (j=0;j cout<<＇＼t＇<<“资源“< cout< for(i=0;i { cout<<“进程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } cout< for (j=0;j cout<<＇＼t＇<<“资源“< cout< for(i=0;i { cout<<“进程“< for (j=0;j cout<<＇＼t＇<<“ “< cout< } } //银行家算法函数 void bank() { cout< int k=0; //用于输入进程编号 bool r=false; // 初值为假，输入Y继续申请则置为真 do{//输入请求 cout<<“输入申请资源的进程(0-“< “; cin>>k; cout< while(k>n-1) //输入错误处理 { cout< cout< “; cin>>k; cout< } cout< “< for (j=0; j j++) { do{ //do……while 循环判断申请输入的情况 cout<<“进程 “< 申请资源[“< cin>>Request[j]; cout< if(Request[j]>Need[k][j]) { //申请大于需求量时出错，提示重新输入（贷款数目不允许超过需求数目） cout<<“申请大于需要量!“< cout<<“申请的资源“< 进程“< cout<<“重新输入!“< } else //先判断是否申请大于需求量，再判断是否申请大于可利用量 if(Request[j]>Available[j]) { //申请大于可利用量，应该阻塞等待？…… ？？？ cout<<“＼n没有那么多资源，目前可利用资源“< Finish[k]=0; //该进程等待 goto ppp; //goto语句 跳转，结束本次申请 } }while(Request[j]>Need[k][j]); //Request[j]>Available[j]|| } //改变Avilable、Allocation、Need的值 for (j=0; j j++) { Available[j] = Available[j]-Request[j]; Allocation[k][j] = Allocation[k][j]+Request[j]; Need[k][j] = Need[k][j]-Request[j]; Work[j] = Available[j]; } //判断当前状态的安全性 safe(); //调用安全性算法函数 if (l { l=0; cout<<“＼n试分配后，状态不安全,所以不予分配!恢复原状态“< //恢复数据 for (j=0; j j++) { Available[j] = Available[j]+Request[j]; Allocation[k][j] = Allocation[k][j]-Request[j]; Need[k][j] = Need[k][j]+Request[j]; Work[j] = Available[j]; } for (i=0; i i++) Finish[i]=0; //进程置为未分配状态 } else { l=0; cout<<“＼n申请资源成功！!“< for(j=0;j { if(Need[k][j]==0); else { //有一种资源还没全部申请到，则该进程不可执行，不能释放拥有的资源 l=1; //置l为1，作为判断标志 break; } } if(l!=1) { //进程可以执行，则释放该进程的所有资源 for (j=0;j { Available[j]=Available[j]+Allocation[k][j]; Allocation[k][j]=0; } cout<<“该进程已得到所有需求资源，执行后将释放其所有拥有资源！“< } l=0; //归零 cout<<“＼n安全的状态!“< cout<<“安全序列为: “; cout< Finish[0]=0; for (i=1; i i++) { cout<<“==>>“<<“进程“<<“(“< Finish[i]=0; //所有进程置为未分配状态 } cout< } show(); //显示当前状态 ppp: //申请大于可利用量，应该阻塞等待,结束本次资源申请，GOTO 语句跳转至此 cout< ?“; char* b=new char; //输入y/n，判断是否继续申请 < cin>>b; cout< cout<<“-------------------------------------------“< cout< if(*b==＇y＇||*b==＇Y＇) r=true; else //{ r=false; //输入非 Y 则令 R =false // jieshu(); //调用结束函数 //} } while (r==true); } //结束函数 //void jieshu() //{ // cout< // cout<<“＼t＼t 演示计算完毕“< // cout< //} //主函数 int main() { cout< chushihua(); //初始化函数调用 cout< show(); //输出当前状态 safe(); //判断当前状态的安全性 if (l //l在safe中是用来记录安全的进程的个数的{ cout<<“＼n当前状态不安全，拒绝申请！“< cout< return 0; } else { int i; //局部变量 l=0; cout< cout<<“进程“<<“(“< //输出安全序列 for (i=1; i i++) cout<<“->>“<<“进程“<<“(“< for (i=0; i i++) Finish[i]=0; //所有进程置为未分配状态 cout< } bank(); //调用银行家算法函数 cout<<“＼t＼t 演示计算完毕“< return 0; } 4）运行结果分析 1．示例数据 进程数量：5 资源种类3 资源情况 进程 Max Allocation Need Available A B C A B C A B C A B C P0 0 0 (2 0) P1 0 0 (3 0 2) (0 0) P2 0 0 0 0 P3 0 P4 0 0 2.测试结果（以上表中数据为列） 截图如下： 5）设计小结 这次我做的课题是“银行家算法的模拟实现”，通过这次的课程设计，我不仅拓宽了自己的知识面，还在实践过程中巩固和加深了自己所学的理论知识，使自己的技术素质和实践能力有了进一步的提高，同时我的专业水平也有了很大的进步。 同时，在软件开发方面也累积了不少经验，对操作系统的知识重要性的认识更深了。通过设计过程的锻炼，自己分析问题和解决问题的能力都得到了锻炼和提高，完善了自己的知识结构，加深了对所学知识的理解。 通过几天努力，这次课程设计圆满的结束了，在这个过程中，我学到了很多的知识，在以后的学习中，我会更加努力的学好专业知识，并将所学知识用于实践当中去，以便牢固掌握知识。 6）参考文献 [1]计算机操作系统(第3版)，汤小丹，西安电子科技大学出版社，2007年7月 [2]Visual C++面向对象编程教程（第二版），王育坚，清华大学出版社，2007年10月） 课程设计报告书 课程名称： 操作系统原理 题 目： 编程序模拟银行家算法 系 名： 信息工程系 专业班级： 软件 姓 名： 学 号： 指导教师: 2013年 X 月 X 日 学院信息工程系 课 程 设 计 任 务 书 课程名称： 操作系统原理课程设计 指导教师： 班级名称： 软件 开课系、教研室： 软件与信息安全 一、课程设计目的与任务 操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练，加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。 学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。 二、课程设计的内容与基本要求 1、课程设计题目 编程序模拟银行家算法 2、课程设计内容 本课程设计要求在Linux操作系统，GCC编译环境下开发。 银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。 3、设计报告撰写格式要求： 1设计题目与要求 设计思想 3系统结构 数据结构的说明和模块的算法流程图 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况） 自我评价与总结 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 三、课程设计步骤及时间进度和场地安排 本课程设计将安排在第15周,教育技术中心。具体安排如下： 第一天 下发任务书，学生查阅资料 第二天 系统设计和原型开发 第三，四天 系统功能实现 第五天 系统调试 测试 打包和验收 四、课程设计考核及评分标准 课程设计考核将综合考虑学生考勤和参与度，系统设计方案正确性，系统设计和开发效果以及课程设计报告书的质量。具体评分标准如下： 设置六个评分点 （1）设计方案正确，具有可行性、创新性； 25分 （2）系统开发效果较好； 25分 （3）态度认真、刻苦钻研、遵守纪律； 10分 （4）设计报告规范、课程设计报告质量高、参考文献充分 20分 （5）课程设计答辩概念清晰，内容正确 10分 （6）课程设计期间的课堂考勤、答疑与统筹考虑。 10分 按上述六项分别记分后求和，总分按五级记分法记载最后成绩。 优秀（100～90分），良好（80～89分），中等（70～79分），及格（60～69分），不及格（0～59分） 1.题目要求与实验目的1.1 实验目的： 1.1.1进一步理解利用银行家算法避免死锁的问题； 1.1.2在了解和掌握银行家算法。 1.1.3理解和掌握安全序列、安全性算法 1.2 设计题目: 编程序模拟银行家算法 1.3 要求 ： 本实验要求用用 c/c语言在Linux 操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 1.4 实验内容 ： 1.4.1编写安全性算法； 1.4.2编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。 设计思想 将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。 用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。 3.需求分析 3.1问题描述：利用银行家算法模拟计算机系统分配资源的过程。 3.2要求： 3.2.11、以课本例题中数据为例，模拟资源分配过程。 3.2.2、系统中资源种类，各类资源数目，进程申请资源数目可任意输入，模拟资源分配过程。 4.系统结构 初始化函数init（）开始 输入进程的数目m 输入资源种类n 输入每个进程最多所需的各种资源数 输入每个进程分配的资源数 输入各个资源现有数目 初始化函数init（）结束 输入提示： 输入有误重新输入 图 5.数据结构的说明和模块的算法流程图 5.1 数据结构： ①可利用资源向量 Available 是个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果 AvailablejK，则表示系统中现有 Rj 类资源 K 个。 ②最大需求矩阵 Max 这是一个 n×m的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 MaxijK，则表示进程 i 需要 Rj 类资源的最大数目为 K。 ③分配矩阵 Allocation 这也是一个 n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 AllocationijK，则表示进程 i 当前已分得 Rj 类资源的数目为 K。 ④需求矩阵 Need。 这也是一个 n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果NeedijK，则表示进程 i 还需要 Rj 类资源 K 个，才可以完成其任务。 5．2 程序流程图： ①、系统主要过程流程 预分配 安全？ 实际分配打印输出 退出系统 Request[i]>Available[i]? Request[i]>need[i]? 提出申请 打印输出此时刻资源分配情况 进入系统 输入： 1.继续分配 2.退出 进入初始化 ②、安全性算法流程图 调用safty()函数 Work[]=Available[],Finish[]=False Need[]<=work[]且Finsh[]=Falsse? Work[]=work[]+Alloccation[],Finish[]=Ture 所有进程的Finsh[]=Ture? 实际分配输出安全序列并打印出 输出提示系统不安全 调用结束 用户手册 6.1 首先在终端中使用 vi 编辑器建立 c的源文件 6.2 然后使用 gcc 编辑器编译生成可执行文件 6.3 使用命令./当前名字，来执行 7.运行结果和结果分析 7．1 运行结果： 申请成功如图 2，申请失败如图 3： 图 申请金额在需求范围之内同意 图 申请金额在需求范围之外拒绝 7.2 结果分析 首先是自己定义 个用户所需的金额数，银行可以给用户贷款的总金额数是100，用户 Id 号的范围是在0 到 4，超过 之后的id 请求贷款，会显示拒绝提示信息，每个客户的贷款数量必须是在之前定义的范围之内，如果超出，也会出现错误提示，只有在规定的用户 id 和在客户所要求金额的范围之内请求，才会给予贷款，并且输出安全序列号。 8.自我评价与总结 一周的课程设计结束了。在这一周里，我收获很多，以前都是在自己的教室由我们自己的老师进行讲课，这次学校没有这样做，而是请的校外的老师给我们做课程设计，让我们体会一下真正的公司是怎样做业务的。在这一周里我做一个模拟银行家算法。我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的书写。 课程设计这几天学到的东西还真不少。以前不清楚的现在都暴露出来了。以前认为学了没用的东西现在也用到了。这次的课程设计使我进一步了解了调度与死锁的问题。以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。 经过本周的课程设计，我对操作系统的掌握又进了一步，收获了很多知识。，终于我了由于对 c 语言不够熟练，在试验过程中，进行了反复的修改和调试，解银行家算法的基本原理，并且在此次的课程设计中我又复习了一下 c 语言，加深了对它的了解，而且在课程设计的过程中我们同样学会了如何简单的操作与使用 Linux 操作系统，学习到了许多 Linux 操作系统中常用的一些密令。 这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列看系统是否安全.再利用安全性算法检查此时系统是否安全。 操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。 通过这次实验，我体会到银行家算法的重要性，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我来学习借鉴。 附录： 主要源程序 参考文献 [1] 张尧学主编．计算机操作系统教程（第三版）．北京:清华大学出版社，2006 [2] 张尧学编．计算机操作系统教程（第三版）习题解答与实验指导．北京:清华大学出版社，2006 [3] 汤子瀛主编．计算机操作系统（第三版）．西安:西安电子科技大学出版社，2001 [4] 张坤等编．操作系统实验教程．北京:清华大学出版社，2008 [5] 张丽芬等编．操作系统实验教程．北京:清华大学出版社，2006 [6] 屠祁等编.操作系统基础（第三版）．北京:清华大学出版社，2000 [7] 冯耀霖等编.操作系统.西安:西安电子科技大学出版社，2001 [8] 左万历．计算机操作系统教程（第二版）．北京：高等教育出版社，2004 [9]谭浩强.《C语言程序设计》.北京：清华大学出版社2003 [8] 庞丽华.《操作系统原理》（第四版）.北京.华中科技大学出版社 2002 设计过程中质疑（或答辩）记载： 1.银行家算法的主要思想是什么？ 答：一个进程进入系统时分配资源之前,判断系统是否是安全的，即看它所请求的资源是否大于它的最大需求量，若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的剩余资源量,若不超出,则分配,否则等待。 2.银行家算法的主要问题是什么？ 答：要求每个进程必须事先知道资源的最大需求量，而且，在系统运行过程中，考查每个进程对各类资源的申请需花费较多的时间。 3.在银行家算法中各个资源存在什么关系？ 答：该进程所需要的资源数NEED[m][n]=MAX[m][n](该进程所需要的最多的资源数)-----ALLOCATION[m][n](该进程所占有的资源数) 指导教师评语： 签名： ****年**月**日 《操作系统》课程设计报告 课题： 银行家算法 专业 计算机科学与技术 学生姓名 班级 计算机 学号 指导教师 信息工程学院 一、实验要求和实验目的实验目的：本课程设计是学生学习完《操作系统原理》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 实验要求：从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：两人一组，每组从所给题目中任选一个（如自拟题目，需经指导教师同意），每个学生必须独立完成课程设计，不能相互抄袭，同组者文档不能相同；设计完成后，将所完成的工作交由指导教师检查；要求写出一份详细的设计报告。 二、设计内容： 课题一、编制银行家算法通用程序，并检测所给状态的系统安全性。 1）银行家算法中的数据结构： 可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj 类资源K个。 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。 1.分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资料当前已分配给没一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 上述三个矩阵存在如下关系： Need[i,j]= Max[i，j]- Allocation[i，j] 2）银行家算法 设Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Request[i，j]<= Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 三、设计思路 设计思路A、设计进程对各在资源最大申请表示及初值确定。B、设定系统提供资源初始状态。C、设定每次某个进程对各类资源的申请表示。D、编制程序，依据银行家算法，决定其申请是否得到满足。 四、详细设计 1、初始化：由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。 2、银行家算法：在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。 银行家算法的数据结构 假设有M个进程N类资源，则有如下数据结构: #define W #define R int M ; //总进程数 int N ; //资源种类 int ALL_RESOURCE[W]; //各种资源的数目总和 int MAX[W][R]; //M个进程对N类资源最大资源需求量 int AVAILABLE[R]; //系统可用资源数 int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量 int NEED[W][R]; //M个进程还需要N类资源的资源量 int Request[R]; //请求资源个数 3.“安全性检测“算法 1)先定义两个变量,用来表示推算过程的数据.F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.J[n]=False表示推算过程中各进程是否假设“已完成“ 系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i]; ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];、NEED[cusneed][i]-=REQUEST[cusneed][i]; 4、安全性检查算法 1)设置两个工作向量Work=AVAILABLE;FINISH 2)从进程集合中找到一个满足下述条件的进程，FINISH==false; NEED<=Work; 如找到，执行(3)；否则，执行(4) 3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION; Finish=true; GOTO 4)如所有的进程Finish= true，则表示安全；否则系统不安全。 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j 最大需求 尚需 P1 P2 P3 4 2 在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.银行家算法的数据结构.五、代码清单 #include #include #include #include #include #include const int MAX_P=20; const int MAXA=10; //定义A类资源的数量 const int MAXB=5; const int MAXC=7; typedef struct node{ int a; int b; int c; int remain_a; int remain_b; int remain_c; }bank; typedef struct node1{ char name[20]; int a; int b; int c; int need_a; int need_b; int need_c; }process; bank banker; process processes[MAX_P]; int quantity; //初始化函数 void initial() { int i; banker.a=MAXA; banker.b=MAXB; banker.c=MAXC; banker.remain_a=MAXA; banker.remain_b=MAXB; banker.remain_c=MAXC; for(i=0;i strcpy(processes[i].name,““); processes[i].a=0; processes[i].b=0; processes[i].c=0; processes[i].need_a=0; processes[i].need_b=0; processes[i].need_c=0; } } //新加作业 void add() { char name[20]; int flag=0; int t; int need_a,need_b,need_c; int i; cout< cout<<“新加作业“< cout<<“请输入新加作业名:“; cin>>name; for(i=0;i if(!strcmp(processes[i].name,name)){ flag=1; break; } } if(flag){ cout<<“错误,作业已存在“< } else{ cout<<“本作业所需A类资源:“; cin>>need_a; cout<<“本作业所需B类资源:“; cin>>need_b; cout<<“本作业所需C类资源:“; cin>>need_c; t=1; cout<第二篇：操作系统课程设计银行家算法的模拟实现
第三篇：操作系统课程设计编程序模拟银行家算法
第四篇：银行家算法《操作系统》课程设计报告