实验二-银行家算法

实验二银行家算法一、实验目的1．理解死锁避免相关内容；2．掌握银行家算法主要流程；3．掌握安全性检查流程。操作系统中的死锁避免部分的理论进行实验。要求实验者设计一个程序，该程序可对每一次资源申请采用银行家算法进行分配。二、实验设备PC机、windows2000操作系统、TurboC2.0三、实验要求本实验要求4学时完成。1．设计多个资源（≥3）；2．设计多个进程（≥3）；3．设计银行家算法相关的数据结构；4．动态进行资源申请、分配、安全性检测并给出分配结果。5．撰写实验报告，并在实验报告中画出银行家和安全性检查函数流程图；四、预备知识死锁避免定义：在系统运行过程中，对进程发出的每一个资源申请进行动态检查，并根据检查结果决定是否分配资源：若分配后系统可能发生死锁，则不予分配，否则予以分配。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的全安性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。1系统安全状态1）安全状态所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2…Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的。并非所有的不安全状态都会转为死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。所以避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态。2）安全状态之例假设系统有三个进程，共有12台磁带机。各进程的最大需求和T0时刻已分配情况如下表：进程最大需求已分配可用P1P2P310495223问：T0时刻是否安全？答：T0时刻是安全的，因为存在安全序列：P2P1P3不安全序列：P1…P3…P2P3P13）由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。2利用银行家算法避免死锁1）银行家算法中的数据结构①可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。②最大需求矩阵Max。最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。③分配矩阵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）银行家算法设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要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；结束否是申请失败。以上分配作废，恢复原来的分配状态：Available[j]=Available[j]+Request[i][j]Allocation[i][j]=Allocation[i][j]－Request[i][j]Need[i][j]=Need[i][j]+Request[i][j]NYNYRequest[i][j]Need[i][j]出错返回：return(error)Request[i][j]Available[j]出错返回：(进程阻塞)return(error)Available[j]=Available[j]–Request[i][j]Allocation[i][j]=Allocation[i][j]+Request[i][j]Need[i][j]=Need[i][j]–Request[i][j]假定分配：输入初始参数（资源分配及请求情况）开始假定分配之后，系统安全吗？申请成功。输出各种数据的变化图银行家算法流程图②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;gotostep（2）；(4)如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。安全性算法的参考流程图如下：Y所有finish都为true？输出安全序列NYN存在Finish[i]=false&&Need[i][j]Available[j]初始化Work和FinishFinish[i]=true，Work[j]=Work[j]+Allocation[j]所有进程都找完了？Y开始图安全性算法流程图#includestdio.h#includeconio.h#includestdlib.h#defineRESOURCE_MAXNUM3//资源数#defineTHREAD_MAXNUM3//进程数//定义可利用资源向量structAvailable{intavailable[RESOURCE_MAXNUM];}res_ava;//最大需求矩阵structMax{intmax[THREAD_MAXNUM][RESOURCE_MAXNUM];}res_max;//已分配矩阵structAllocation{intallocation[THREAD_MAXNUM][RESOURCE_MAXNUM];}res_all;//需求矩阵structNeed{intneed[THREAD_MAXNUM][RESOURCE_MAXNUM];}res_nee;//临时进程的资源分配序列inttmpSequence[THREAD_MAXNUM];//可能的一个安全序列intsecSequence[THREAD_MAXNUM];//找到一个安全执行序列的标志intisFindSecQue=0;//定义一系操作方法//进行显式地初始化操作voidinit();//打印操作voidprintInfo();//输入操作voidinput();//检测条件Need=Max-Allocationintcheck();//测试可得到的资源能否江足要求intcheck(intthreadID,intneed[THREAD_MAXNUM]);//当前待分配的进程需求voidcurThreadNeed();//更新操作voidupdate(intthredID,intneed[THREAD_MAXNUM]);//释放操作voidrelease(intthreadID);//安全性算法intsecurity(intsequence[THREAD_MAXNUM]);//回溯得到进程执行序列，并执行安全性算法voidbacktrack();//交换数组中指定的两个值voidswapArray(intarr[THREAD_MAXNUM],intpos1,intpos2);//拷贝数组voidcopyArray(intarr1[THREAD_MAXNUM],intarr2[THREAD_MAXNUM]);intmain(){init();input();intcheckres=check();if(checkres==0){printf(输入有问题，确认后重新输入/n);exit(-1);}printInfo();curThreadNeed();printInfo();printf(执行安全性算法/nENTER键继续.../n/n);getch();backtrack();if(isFindSecQue==0)printf(未找到一个安全的进程执行序列/n);return0;}voidinit(){inti,j;for(i=0;iTHREAD_MAXNUM;++i){for(j=0;jRESOURCE_MAXNUM;++j){res_all.allocation[i][j]=0;res_max.max[i][j]=0;res_nee.need[i][j]=0;}tmpSequence[i]=i;secSequence[i]=i;}for(j=0;jRESOURCE_MAXNUM;++j){res_ava.available[j]=0;}}voidprintInfo(){inti,j;printf(**********************当前资源分配**********************\n);printf(最大需求矩阵\t\t|分配矩阵\t\t|需求矩阵\n);for(i=0;iTHREAD_MAXNUM;++i){for(j=0;jRESOURCE_MAXNUM;++j){printf(%d\t,res_max.max[i][j]);}for(j=0;jRESOURCE_MAXNUM;++j){printf(%d\t,res_all.allocation[i][j]);}for(j=0;jRESOURCE_MAXNUM;++j){printf(%d\t,res_nee.need[i][j]);}printf(\n);}printf(\n);printf(可利用资源向量\t\n);for(j=0;jRESOURCE_MAXNUM;++j){printf(%d\t,res_ava.available[j]);}printf(\n);}voidinput(){inti,j;printf(输入当前可利用资源\n);for(j=0;jRESOURCE_MAXNUM;++j){scanf(%d,&res_ava.available[j]);}printf(输入分配矩