试验 银行家算法

题目：死锁避免算法的模拟实现——银行家算法班级：软件三班学号：2012551521姓名：王振宇1.实验目的银行家算法是由Dijkstra设计的最具有代表性的避免死锁的算法。本实验要求用高级语言编写一个银行家的模拟算法。通过本次实验加深对预防死锁和银行家算法的认识。2.实验预备内容银行家算法是避免死锁发生的有效算法，预习银行家算法的步骤，算法中包含的数据结构。VC环境，C语言程序设计技术3设计内容（原理图以及相关说明、调试过程、结果）设requesti为进程p[i]的请求向量，如果requesti[j]=K，表示进程p[i]需要K个Rj资源。当系统发出请求后，系统按下述步骤开始检查：（1）、如果requesti[j]=need[i][j],转向步骤2；否则报告出错，申请的资源已经大于它需要的最大值。（2）、如果requesti[j]=available[j],转向步骤3；否则报告出错，尚无足够的资源。（3）、系统试探着把资源分配给p[i]，并修改下列数据结构中的值：available[j]=available[j]-request[j]allocation[i][j]=allocation[i][j]+request[j]need[i][j]=need[i][j]-request[j]（4）、系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程p[i]；否则，恢复原来的资源分配状态，让进程p[i]等待。安全性算法（略）1.为实现银行家算法，系统中需要设置若干数据结构，用来表示系统中各进程的资源分配及需求情况。假定系统中有m个进程，n类资源进程数和资源数由程序中直接定义，#definem5//总进程数#definen4//总资源数对于不同规模的进程和资源数，在程序中直接修改m和n值即可。2.银行家算法中使用的数据结构如下：（1）可利用资源Available.这是一个含有m个元素的数组，其中的每一个元素代表一类资源的空闲资源数目，其初值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=k，表示系统中Rj类资源有k个。（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中每一个进程对各类资源的最大需求数目。如果Max[i，j]=k，表示进程Pi需要Rj类资源有k个。（3）分配矩阵Allocation。这是一个n*m的矩阵，它定义了系统中当前已分配给每一个进程的各类资源。如果Allocation[i,j]＝k,表示进程Pi当前已分到Rj类资源有k个。Allocationi表示进程Pi的分配向量，由矩阵Allocation的第i行构成。（4）需求矩阵Need。这是一个n*m的矩阵，它定义了系统中每一个进程还需要的各类资源的数目。如果Need[i，j]=k，表示进程Pi需要Rj类资源有k个，才能完成任务。Needi表示进程Pi的需求量，由矩阵Need的第i行构成。因为数据结构中涉及变量太多，为方便起见，可以定义一个结构体，将这些矩阵都放在一起。structbank//定义结构体{intAvailable[n];//可利用资源向量intMax[m][n];//最大需求矩阵intAllocation[m][n];//分配矩阵intNeed[m][n];//需求矩阵};这样在后面的安全性检查操作中，只需要带入一个bank型变量即可，比较方便。3.实现过程主函数voidmain(void){bankcurrent;//定义变量Initilize(current);//初始化Safe_test(current);//检查安全性while(1)//循环执行进程申请资源和系统对申请的处理{Resoure_allocate(current);}}其中用到的函数操作有三个voidInitilize(bank&);//初始化intSafe_test(bank);//检查安全性voidResoure_allocate(bank&);//系统对进程资源申请的处理Initilize函数是初始化变量的，即设置相关矩阵参数，由用户输入。Safe_test函数是检查当前系统安全性的，安全则返回1，不安全返回0。Resoure_allocate函数里的操作包括：a.进程申请资源b.假设系统可以响应该请求，将分配资源给该进程，修改相关数据c.检查系统是否安全，若安全在，则可以分配资源，若不安全，不能分配资源，并收回分配的资源。4.安全性检查程序中安全性算法的描述如下：（1）设置如下两个工作向量：Work：表示系统可提供给进程继续运行的各类资源的空闲资源数目，它含有m个元素，执行安全性算法开始时，Work＝Available。Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finish（i）＝false；当有足够的资源分配给进程Pi时，令Finish（i）＝true。（2）从进程集合中找到一个能满足下列条件的进程：Finish（i）＝false；Needi=Work；，如果找到了就执行步骤（3），否则执行步骤（4）。（3）当进程Pi获得资源后，可执行直到完成，并释放出分配给它的资源，故应执行Work=Allocationi＋Work;Finish（i）＝false；然后转向第（2）步骤。（4）若所有进程中的Finish（i）都是true，则表示系统处于安全状态；否则，系统处于不安全状态。此过程由一个安全性检查函数实现intSafe_test(bankx){inti,j;intsafeprocess[m];//安全序列向量intwork[n];//空闲资源矩阵intFinish[m];//进程完成标志矩阵for(i=0;in;i++)//开始时可利用资源向量就是空闲资源矩阵work[i]=x.Available[i];for(i=0;im;i++)//初始化标志矩阵为falseFinish[i]=false;intk=0;//安全序列排列号for(i=0;im;i++)//每次都从第一个进程开始做循环{if(Finish[i]==false){for(j=0;jn;j++){if(x.Need[i][j]work[j])//判断当前进程需求矩阵能否得到满足break;//不满足则跳出}if(j==n)//第i个进程满足执行条件{safeprocess[k++]=i;//将进程号存入安全序列向量for(intq=0;qn;q++)//修改空闲资源矩阵work[q]+=x.Allocation[i][q];Finish[i]=true;//标志该进程可完成i=-1;//下次检查从第一个进程重新查起}}}for(i=0;im;i++)//检查标志数组，若有一个为false则找不到安全序列if(!Finish[i]){cout找不到安全序列,系统处于不安全状态!\n;return0;}cout找到安全序列:;//找到安全序列并显示该序列for(i=0;im;i++)cout进程safeprocess[i]+1;cout\n系统处于安全状态.\n;return1;}5.对进程申请资源的处理当某一进程提出资源申请时，系统须做出判断，能否将所申请资源分配给该进程。设Requesti是进程Pi的请求向量，Requesti（j）＝k表示进程Pi请求分配Rj类资源有k个。当Pi发出资源请求后，系统按照下述步骤进行检查：（1）如果Requesti=Needi,则转向第二步；否则出错，因为进程所需要的资源数已超过它所宣布的最大值；（2）如果Requesti=Available，则转向步骤（3）；否则，表示系统中尚无足够的资源满足进程Pi的申请，让进程Pi等待。（3）假设系统把申请的资源分配给进程Pi，则对应下面的数据结构进行修改：Available=Available－Requesti;Allocationi=Allocationi＋Requesti;Needi=Needi－Requesti;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，就将资源分配给Pi，满足其资源申请要求；否则，让进程等待，并恢复原来的资源分配状态。整个过程由一个函数实现voidResoure_allocate(bank&x){banktemp=x;//临时变量存储x的初值intRequest[n];//请求向量intnumber;//进程号inti;cout请输入要申请资源的进程序号:\n;cinnumber;cout请输入请求向量:\n;for(i=0;in;i++)cinRequest[i];//输入请求向量for(i=0;in;i++){if(Request[i]x.Need[number-1][i])//所需资源数大于需求量{cout进程所需要的资源数已超过它所宣布的最大值，系统不予分配资源!\n;return;}if(Request[i]x.Available[i])//所需资源数大于可利用资源{cout系统中无足够的资源满足进程的申请，系统不予分配资源!\n;return;}}for(i=0;in;i++)//假设系统将申请资源数分配给该进程，对数据进行相关修改{x.Available[i]-=Request[i];x.Need[number-1][i]-=Request[i];x.Allocation[number-1][i]+=Request[i];}if(Safe_test(x))//安全性检查结果为安全{cout系统可以为该进程分配资源.\n;return;}else//安全性检查结果为不安全{cout系统不为该进程分配资源\n;x=temp;//将相关矩阵修改过来，表示资源不分配资源return;}}实验小结（问题、收获和体会）在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。银行家算法是死锁避免算法中的一种，银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。源程序：#includeiostream.h/***********************************************************************数据定义与函数原型说明***********************************************************************/#definem5//总进程数#definen4//总资源数structbank//定义结构体{intAvailable[n];//可利用资源向量intMax[m][n];//最大需求矩阵intAllocation[m][n];//分配矩阵intNeed[m][n];//需求矩阵};voidInitilize(bank&);//初始化intSafe_test(bank);//检查安全性voidResoure_allocate(bank&);//系统对进程资源申请的处理/***********************************************************************主函数***********************************************************************/voidmain(void){bankcurrent;//定义变量Initilize(current);//初始化Safe_test(current);//检查安全性while(1)//循环执行进程申请资源和系统对申请的处理{Resoure_allocate(current);}}/********************