银行家算法实验报告

1、 计算机科学与技术专业 0640303233 张世兵 实验二 银行家算法实验报告一、 实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。二、 实验要求设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；三、 数据结构1 可利用资源向量available ，它是一个含有m个元素的

2、数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果available（j）=k，标是系统中现有rj类资源k个。2 最大需求矩阵max，这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果max（i，j）=k，表示进程i需要rj类资源的最大数目为k。3 分配矩阵allocation，这是一个nm的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果allocation（i，j）=k，表示进程i当前已经分到rj类资源的数目为k。allocation i表示进程i的

3、分配向量，有矩阵allocation的第i行构成。4 需求矩阵need，这是一个nm的矩阵，用以表示每个进程还需要的各类资源的数目。如果need（i，j）=k，表示进程i还需要rj类资源k个，才能完成其任务。need i表示进程i的需求向量，由矩阵need的第i行构成。上述三个矩阵间存在关系：need（i，j）=max（i，j）-allocation（i，j）；四、 银行家算法参考教材p96五、 安全性算法1 设置两个向量。work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，work = available。finish：它表示系统是否有足够的资源分配

4、给进程，使之运行完成，开始finish（i）=false；当有足够资源分配给进程pi时，令finish（i）=true；2 从进程集合中找到一个能满足下述条件的进程。finish（i）= = false；need i work；如找到则执行步骤3；否则，执行步骤4；3 当进程pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行work = work + allocation i finish（i）=true；转向步骤2；4 若所有进程的finish（i）都为true，则表示系统处于安全状态；否则，系统处于不安全状态。六、流程开 始输入资源数m, 及各类资源总数，初始化avail

5、able向量输入进程数n，i=1输入进程i的最大需求向量max。inmax资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量request 调用银行家算法，及安全性算法，完成分配，或并给出提示该进程的need向量为0该进程已运行结束need矩阵为0所有进程运行都结束结 束nyynny初始化need 矩阵ny七 实验源程序#include #include #include using namespace std; #define true 1 /定义 true =1#define false 0 /定义 flase=0void bank(vector,vectorve

6、ctor ,vectorvector ,int ,int ); /声明bank（应行家算法）int safe(vector available,vectorvector need,vectorvector allocation,int n,int m);/声明safe（）安全性算法void init();/*主函数main()*/void main()init();/*初始化函数init()*/void init()int m; /m资源类数int n; /进程数cout输入资源类数m;vector available(m); /动态申请数组available可用资源向量 cout输入各类资源

7、总数:endl;/*/ /* 下面的被刚掉的为在dos下输入资源向量*/ /*未被刚掉的是从available.txt文件中读入数据*/*/*/for (int i=0;im;i+)cout输入riavailablei;/*/file *fp;fp=fopen(available.txt,r+);cout从available.txt文件中读入数据，并输出endl;for(int i=0;im;i+)fscanf(fp,%d,&availablei);coutavailableit;fclose(fp);coutn输入进程数n;vectorvector max(n, vector(m);/*/*

8、 下面的被刚掉的为在dos下输入资源向量*/*未被刚掉的是从max.txt文件中读入数据*/*/*for ( i=0;in;i+)cout输入进程i的最大需求向量;for (int j=0;jm;j+)cout 输入需要rjmaxij;while (maxijavailablej)coutjmaxij;/*/fp=fopen(max.txt,r+);cout从max.txt文件中读入数据，并输出endl;for(i=0;in;i+) for (int j=0;jm;j+)fscanf(fp,%d,&maxij);coutmaxij ;coutendl;fclose(fp);cout输入已分配的

9、allocationendl;vectorvector allocation(n, vector(m);vectorvector need(n, vector(m);/*/* 下面的被刚掉的为在dos下输入资源向量*/*未被刚掉的是从allocation.txt文件中读入数据*/*/*for ( i=0;in;i+)cout输入为进程i的分配向量;for (int j=0;jm;j+)cout 输入分配rjallocationij;while(allocationijmaxij)coutj+1allocationij;needij=maxij-allocationij;availablej =

10、availablej-allocationij;/*/fp=fopen(allocation.txt,r+);coutallocation.txt从文件中读入数据，并输出endl;for(i=0;in;i+)for (int j=0;jm;j+)fscanf(fp,%d,&allocationij);needij=maxij-allocationij; /在初始化max时，同时初始化need数组availablej =availablej-allocationij; /在初始化max时，同时修改available数组coutallocationij ;coutendl;fclose(fp);b

11、ank(available,need,allocation,n,m);/调用银行家算法bank()函数/*应行家算法bank()函数*/void bank(vector available,vectorvector need,vectorvector allocation,int n,int m)vector request(m);int all=0;/定义变量all，如果all=0，表示进程已经运行完，如果all=1，表示还有进程没有运行完for (int i=0;in;i+)for(int j=0;jm;j+)all +=needij;if (0=all)cout所有进程已经运行完，结束=

12、1，表示还有进程没有运行完/循环直至all0,即找到一个未运行完的进程cout任选一个进程作为当前进程0-n-1jc;for (int j=0;jm;j+)all += needjcj;if (0=all)cout此进程已经运行，重新输入endl;cout输入该进程的请求向量endl;for (i=0;irequesti;while(requestineedjci)cout输入错误，需要的i类资源数超过宣布的最大值,重新输入requesti;while(requestiavailablei)cout尚无足够资源满足需求,请重新输入请求requesti;/系统试探着把资源分配给该进程/for (

13、i=0;im;i+)availablei=availablei-requesti;allocationjci=allocationjci+requesti;needjci=needjci-requesti;int bb=0;bb=safe(available,need,allocation,n,m);/调用安全性算法，判断此次资源分配后，系统是否处安全状态if (1=bb)cout系统成功分配资源endl;elsecout系统未能成分配资源,收回预分配资源endl;for (i=0;im;i+)availablei=availablei+requesti;allocationjci=alloc

14、ationjci-requesti;needjci=needjci+requesti;cout您还想再次请求分配吗?是请按y/y,否请按其它键again; if(again=y|again=y) all=0;continue; break;/*安全性算法safe()函数*/int safe(vector available,vectorvector need,vectorvector allocation,int n,int m)vector work(m),finish(n);/申请工作向量work，finishwork=available;vector count(n); /记录安全序列i

15、nt len=-1; /记录安全序列的进程个数，如果len=n，即表示所有的finish【i】=true，处于安全状态for(int i=0;im;i+)finishi=false; for (i=0;in;i+) int needed=1;for (int j=0;jm;j+)if(needij=workj)needed=needed*true;else needed=needed*false;if (finishi=false)&needed=1)for (j=0;jm;j+)workj=workj+allocationij;finishi=true;len=len+1;countlen=i;i=-1;if (len=n-1)cout系统是安全的endl;cout安全序列endl;for (i=0;i=len;i+)coutcounti;if (i!=len)cout;coutendl;return true;elsecout系统是不安全的3-0-2-4,故系统此时是安全的，系统成功分配资源。继续处理进程队列，选择0号进程，并输入资源请求向量 1 0 0，经过银行家算法安全性算法得出安全序列1-3-0-2-4,故系统此时是安全的，系统成功分配资源。继续处理进程队列，选择3号进程，