操作系统课程设计银行家算法

操作系统-课程设计报告银行家算法姓 名： 学 号： 专 业： 指导老师： 目录一、设计目的1二、设计要求1三、设计内容和步骤1四、算法描述4五、实验结果11六、实验心得1212一、设计目的银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。二、设计要求在了解和掌握银行家算法的基础上，能熟练的处理课本例题中所给状态的安全性问题，能编制银行家算法通用程序，将调试结果显示在计算机屏幕上。具体程序的功能要求：1设定进程对各类资源最大申请表示及初值确定。2设定系统提供资源初始状况（已分配资源、可用资源）。3设定每次某个进程对各类资源的申请表示。4编制程序，依据银行家算法，决定其申请是否得到满足。三、设计内容和步骤设计内容 银行家算法的思路：先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。设计步骤1、为实现银行家算法，系统中需要设置若干数据结构，用来表示系统中各进程的资源分配及需求情况。假定系统中有M个进程，N类资源。进程数和资源数由程序中直接定义 #define M 5 /总进程数#define N 3 /总资源数银行家算法中使用的数据结构如下： （1）可利用资源Available。这是一个含有m个元素的数组，其中的每一个元素代表一类资源的空闲资源数目，其初值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Availablej=k，表示系统中Rj类资源有k个。 （2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中每一个进程对各类资源的最大需求数目。如果Maxi，j=k，表示进程Pi对Rj类资源的最大需求数为k个。 （3）分配矩阵Allocation。这是一个n*m的矩阵，它定义了系统中当前已分配给每一个进程的各类资源。如果Allocationi,jk, 表示进程Pi当前已分到 Rj类资源有k个。 （4）需求矩阵Need。这是一个n*m的矩阵，它定义了系统中每一个进程还需要的各类资源的数目。如果Need i，j=k，表示进程Pi需要Rj类资源有k个，才能完成任务。int Max53=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/每个进程对每类资源的最大需求int Allocation53=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2;/系统已分配资源int Avaliable3=3,3,2; /系统可利用资源int Need53=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1;/还需要资源int Request3;2、实现过程主函数void main()/主函数 int choice;showdata();safeAlgorithm(); do printf(n输入接下来你要进行的操作 1：分配资源 2:显示资源 否则按任意键退出); scanf(%d,&choice); switch(choice) case 1: bankerAlgorithm(); break; case 2: showdata(); break; default: break; while(choice=1)|(choice=2);其中用到的函数操作有三个showdata();/显示资源矩阵safeAlgorithm();/安全性检测算法bankerAlgorithm();/利用银行家算法对申请资源对进行判定3、安全性检查程序中安全性算法的描述如下：（1） 设置如下两个工作向量：Work：表示系统可提供给进程继续运行的各类资源的空闲资源数目，它含有m个元素，执行安全性算法开始时，WorkAvailable。Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finishifalse；当有足够的资源分配给进程Pi时，令Finishitrue。（2） 从进程集合中找到一个能满足下列条件的进程：Finishifalse；Need i= Work；，如果找到了就执行步骤（3），否则执行步骤（4）。（3） 当进程Pi获得资源后，可执行直到完成，并释放出分配给它的资源，故应执行Work = Work + Allocation;Finishifalse；然后转向第（2）步骤。（4） 若所有进程中的Finishi都是true，则表示系统处于安全状态；否则，系统处于不安全状态。 此过程由一个安全性检测函数实现：safeAlgorithm();/安全性检测算法4、对进程申请资源的处理 当某一进程提出资源申请时，系统须做出判断，能否将所申请资源分配给该进程。设request为进程i的请求向量，如果requestj=K，表示进程i需要K个j资源。当系统发出请求后，系统按下述步骤开始检查： （1） 如果requestj=needij,转向步骤2；否则报告出错，申请的资源大于它需要的最大值。 （2） 如果requestj=availablej,转向步骤3；否则报告出错，尚无足够的资源。 （3）系统试探着把资源分配给pi，并修改下列数据结构中的值： availablej=availablej-requestj allocationij=allocationij+requestj needij=needij-requestj （4）系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程i；否则，恢复原来的资源分配状态，让进程i等待。整个过程由银行家算法实现：bankerAlgorithm()/利用银行家算法对申请资源对进行判定四、算法描述#include#include#define M 5 /定义进程数 #define N 3 /定义资源数 s#define False 0#define True 1int Max53=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3; /每个进程对每类资源的最大需求int Allocation53=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2;/系统已分配资源int Avaliable3=3,3,2; /系统可利用资源int Need53=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1;/还需要资源int Request3;void showdata()/显示资源矩阵 int i,j; printf(系统目前可利用的资源数量:n A,B,Cn); printf(resouce: ); for (j=0;jN;j+) printf(%d,Avaliablej);/输出分配资源 printf(n); printf(各进程的资源需求:n); for (i=0;iM;i+) printf(pr%d: ,i); for (j=0;jN;j+) printf(%d,Maxij);/输出最大需求资源数 printf(n); printf(各进程得到资源:n); for (i=0;iM;i+) printf(pr%d: ,i); for(j=0;jN;j+) printf(%d,Allocationij);/输出已分配资源数 printf(n); printf(各进程还需求资源:n); for (i=0;iM;i+) printf(pr%d: ,i); for(j=0;jN;j+) printf(%d,Needij);/输出还需要资源数 printf(n); void release(int i)/判断是否安全，若不安全则释放第j类资源 int j; for (j=0;jN;j+) Avaliablej=Avaliablej+Requestj; Allocationij=Allocationij-Requestj; Needij=Needij+Requestj; void distribute(int i)/若符合条件则对第j类资源进行分配 int j; for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj; void safeAlgorithm()/安全性算法int Work3,FinishM=0,resultM,run;/* work：表示系统可提供给进程继续运行的所需的各类资源数目 finish： 表示系统是否有足够的资源分配给进程 result用来存放依次执行成功的线程 */ int i,j,k=0,m,demand; for(i=0;i3;i+) Worki=Avaliablei; /开始的时候work=available for(i=0;iM;i+) demand=0;for(j=0;jN;j+)if (Finishi=False&Needij=Workj) demand+;if(demand=3)/只有ABC三类资源都满足才把相应的线程记入数组result中for(m=0;mN;m+)Workm=Workm+Allocationim;/重新分配第i类线程的当前可利用资源Finishi=True; resultk=i;i=-1; k+; else if(Finishi=False) if(i=M-1) printf(系统不安全n);/如果不成功，输出系统不安全 run=False; break; printf(系统资源分配成功!);/如果安全，输出成功 printf(分配的序列:n); for(i=0;iM;i+)/输出运行进程数组 printf(pr%d ,resulti); void bankerAlgorithm()/利用银行家算法对申请资源对进行判定int i,j,OK=1,run=True;printf(n请输入第一个要求分配的资源进程号从(0 to 4):); scanf(%d,&i);/输入须申请的资源号 printf(请输入进程 %d 申请的资源:n,i);for(j=0;j3;j+)printf(第 %d 个资源:,j+1);scanf(%d,&Requestj);/输入需要申请的资源for (j=0;jNeedij)/判断申请是否大于需求，若大于则出错 printf(进程 %d 申请的资源大于它需要的资源,i); printf( error!n);OK=0; break;else if(RequestjAvaliablej)/判断申请是否大于当前资源，若大于则出错 printf(进程 %d 申请的资源大于当前可利用资源,i); printf( error!n);OK=0;break;if(OK=1)/若都符合条件，则进行分配distribute(i);/根据进程请求分配资源showdata();/显示变换后的资源 safeAlgorithm();/通过安全算法判断该序列是否安全if(run=False)/若不安全，则进行释放第I类资源release(i);void main()/主函数 int choice;showdata();safeAlgorithm(); do printf(n输入接下来你要进行的操作 1：分配资源 2:显示资源 否则按任意键退出); scanf(%d,&choice); switch(choice) case 1: bankerAlgorithm(); break; case 2: showdata(); break; default: break;