操作系统课程设计报告—银行家算法实现.docx

银行家算法实现一、 概述 所谓死锁: 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。这就给计算机系统带来了问题，银行家算法就是一个避免死锁的算法。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则给进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量；若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。二、设计目的1、理解银行家算法；2、掌握进程安全性检查的方法及资源分配的方法；3、加深了解有关资源申请、避免死锁等概念；4、体会和了解死锁和避免死锁的具体实施方法。三、设计内容用c+语言编写并调试一个银行家算法，简单模拟动态分配，观察死锁产生的条件，学习如何有效的防止和避免死锁的发生，掌握安全性算法。四、开发环境：microsoft visual c+ 6.0五、设计思路1、银行家算法中的数据结构（1）、可利用资源向量available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果available j= k，则表示系统中现有r类资源k个（2）、最大需求矩阵max。这是一个n*m的矩阵，它定义了系统中n个进程对m类资源的最大需求。如果maxi,j=k，则表示进程i需要r类资源的数目为k。（3）、分配矩阵allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocation i,j=k，则表示进程i当前已分得r类资源的数目为k。（4）、需求矩阵need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果need i,j=k，则表示进程i还需要r类资源k个，才能完成其任务。上述矩阵存在关系：needi,j= maxi,jallocationi,j2、银行家算法设requesti是进程pi的请求向量，requesti=k表示进程pi需要k个j类资源。pi发出资源请求后，按下列步骤进行检查：（1）、如果requestijneedi,j，转向步骤（2）；否则认为错误，所需要的资源数已超过它所宣布的最大值。（2）、如果requestijavailablej，转向步骤（3）；否则，表示尚无足够资源，pi需等待。（3）、系统尝试将资源分配给进程pi，并修改下面数据结构中的数值：availablej：=availablej-requestij；allocationi,j：=allocationi,j+ requestij；needi,j：=needi,j- requestij；（4）、执行安全性算法，检查此次资源分配后，系统是否出于安全状态。若安全， 才正式将资源分配给进程pi，已完成本次分配；否则，将本次试探分配作废，恢复原来的资源分配状态，让pi等待。3、安全性检查算法（1）、设置两个向量：、工作向量work：表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时work：=available。、finish标志：表示系统是否有足够的资源分配给进程，使之运行完成。初始化finishi:=false;有足够资源分配给进程时，令finishi：=true。（2）、从进程集合中找到一个能满足下述条件的进程finishi=false; needi,jworkj;找到执行步骤（3），否则执行步骤（4）。（3）、当进程pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： workj：=worki+allocationi,j； finishi：=true； go to step ；（4）、如果所有进程的finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。六、概要设计1、主要代码：#define false 0#define true 1char name50=0;/资源名称int max5050=0;/进程所需各类资源的最大需求int allocation5050=0;/系统已分配资源int need5050=0;/进程需求资源int available50=0;/系统可用资源向量int request50=0;/进程请求资源向量int work50=0;/存放系统可提供进程继续运行所需各类资源数目int temp50=0;/存放安全序列int b50=0;/系统各类资源总数int m=50;/进程的最大数目为50int n=50;/资源的最大数目为50void display()/系统初始界面void print()/显示资源分配情况int changdata(int i)/进行资源分配int safe(int num,int m,int n)/安全性算法对系统进行分析void bank(int m,int n)/银行家算法对申请资源对进行判定2、流程图：初始化work数组，使workj=availablej; finishi=false（1）安全性算法：finishi=trueynneedijworkjynapply+;appy=nyyfinishi=trueworkm+=allocationimtempk=i;k+l=m y n不安全availablei=availablei+requesti;allocationnumi=allocationnumi-requestjneednumi=neednumi+requesti;maxnumi=allocationnumi; allocationnumi=0; availablei = availablei + allocationnumi;输出安全序列return true7（2）银行家算法：输入进程号初始化request数组requestcusneedineedcusneedi requestcusneediavailableiyn试分配changdata()nsafe()yput()输出内容3、调试结果请输入系统中资源的种类:3资源1的名称和数量:a 10资源2的名称和数量:b 5资源3的名称和数量:c 7请输入进程的数量:5请输入各进程的最大需求(5*3矩阵)max:7 5 33 2 29 0 22 2 24 3 3请输入各进程的已分配(5*3矩阵)allocation:0 1 02 0 03 0 22 1 10 0 2目前可用的资源:a b c3 3 2 max allocation need进程名 a b c a b c a b c 0 7 5 3 0 1 0 7 4 3 1 3 2 2 2 0 0 1 2 2 2 9 0 2 3 0 2 6 0 0 3 2 2 2 2 1 1 0 1 1 4 4 3 3 0 0 2 4 3 1系统是安全的!分配的序列:1-3-4-0-2请输入要求分配的资源进程号(0-4):1请输入进程 1 申请的资源:a:1b:0c:2 max allocation need进程名 a b c a b c a b c 0 7 5 3 0 1 0 7 4 3 1 3 2 2 3 0 2 0 2 0 2 9 0 2 3 0 2 6 0 0 3 2 2 2 2 1 1 0 1 1 4 4 3 3 0 0 2 4 3 1系统是安全的!分配的序列:1-3-4-0-2请输入要求分配的资源进程号(0-4):4请输入进程 4 申请的资源:a:3b:3c:0进程4申请的资源大于系统现在可利用的资源 分配出错，不予分配!请输入要求分配的资源进程号(0-4):0请输入进程 0 申请的资源:a:0b:1c:0 max allocation need进程名 a b c a b c a b c 0 7 5 3 0 2 0 7 3 3 1 3 2 2 3 0 2 0 2 0 2 9 0 2 3 0 2 6 0 0 3 2 2 2 2 1 1 0 1 1 4 4 3 3 0 0 2 4 3 1系统是安全的!分配的序列:1-3-4-0-2请输入要求分配的资源进程号(0-4):a七、详细设计（程序源代码）#include#include#define false 0#define true 1char name50=0;/资源名称int max5050=0;/进程所需各类资源的最大需求int allocation5050=0;/系统已分配资源int need5050=0;/进程需求资源int available50=0;/系统可用资源向量int request50=0;/进程请求资源向量int work50=0;/存放系统可提供进程继续运行所需各类资源数目int temp50=0;/存放安全序列int b50=0;/系统各类资源总数int m=50;/进程的最大数目为50int n=50;/资源的最大数目为50void display() int i,j,number,m,n;char ming;int a50=0;coutn;n=n;for(i=0;in;i+) cout资源i+1mingnumber;namei=ming;bi=number;coutm;m=m;cout请输入各进程的最大需求(m*n矩阵)max:endl;for(i=0;im;i+)for(j=0;jmaxij;cout请输入各进程的已分配(m*n矩阵)allocation:endl;for(i=0;im;i+)for(j=0;jallocationij;needij=maxij-allocationij;if(needij0)cout您输入的第i+1个进程所拥有的第j+1个资源数错误,请重新输入:endl;j-;continue;cout目前可用的资源:endl;for(i=0;in;i+)coutnamei ;coutendl;for (j=0;jn;j+)for(i=0;im;i+)aj+=allocationij;availablej=bj-aj;for(i=0;in;i+)coutavailablei ;/输出分配资源coutendl;void print()/显示资源分配情况int i,j;cout max allocation needendl;cout进程名 ;for(j=0;j3;j+)for(i=0;in;i+)coutnamei ;cout ;coutendl;for(i=0;im;i+)cout i ;for(j=0;jn;j+)coutmaxij ;cout ;for(j=0;jn;j+)coutallocationij ;cout ;for(j=0;jn;j+)coutneedij ;coutendl;int changdata(int i)/进行资源分配 int j;for (j=0;jm;j+) availablej=availablej-requestj; allocationij=allocationij+requestj; needij=needij-requestj;return 1;int safe(int num,int m,int n)/安全性算法对系统进行分析int i,j,k=0,m,apply,finish5=0;int flag;int flag1;for(j=0;jm;j+) workj=availablej; for(flag=0;flagm;flag+)for(i=0;im;i+)apply=0;for(j=0;jn;j+)if (finishi=false&needij=workj) apply+;if(apply=n)for(m=0;mn;m+)workm=workm+allocationim;/变分配数finishi=true;tempk=i;k+;for(i=0;im;i+)if(finishi=false)cout系统不安全endl;/不成功系统不安全for(i = 0;in;i+) availablei=availablei+requesti;allocationnumi=allocationnumi-requesti; neednumi=neednumi+requesti; return -1; cout系统是安全的!endl;/如果安全，输出成功 cout分配的序列:;for(i=0;im;i+)/输出运行进程数组couttempi;if(im-1) cout;coutendl;for(i = 0;in;i+)if(maxnumi = allocationnumi) flag1 = 1; elseflag1 = 0;break;if(flag1 = 1)for(i=0;in;i+)availablei = availablei + allocationnumi;allocationnumi = 0;return 0;void bank(int m,int n)/银行家算法对申请资源对进行判定char ch; int i=0,j=0; ch=y;cout请输入要求分配的资源进程号(0-m-1i;/输入须申请的资源号cout请输入进程 i 申请的资源:endl; for(j=0;jn;j+)coutnamejrequestj;/输入需要申请的资源for (j=0;j