实验二(银行家算法)

实验二死锁的防止――银行家算法实验目的掌握死锁产生的原因。掌握银行家算法。能使用高级语言模拟实现银行家算法。相关数据结构可利用资源向量Available，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=k，标是系统中现有j类资源k个。最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i][j]=k，表示进程i需要j类资源的最大数目为k。分配矩阵Allocation，这是一个n×m的矩阵，它定义了系统中的每类资源当前分配到每一个进程的资源数。如果Allocation[i][j]=k，表示进程i当前已经分到j类资源的数目为k个。Allocation[i]表示进程i的分配向量。需求矩阵Need，这是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need[i][j]=k，表示进程i还需要j类资源k个，才能完成其任务。Need[i]表示进程i的需求向量。上述三个矩阵间存在关系：Need[i][j]=Max[i][j]-Allocation[i][j]；银行家算法Request是进程i的请求向量。Request[j]=k表示进程i请求分配j类资源k个。当进程i发出资源请求后，系统按下述步骤进行检查：如果Request≤Need[i]，那么转向步骤2；否那么，认为出错，因为它所请求的资源数已超过它当前的最大需求量。如果Request≤Available，那么转向步骤3；否那么，表示系统中尚无足够的资源满足进程i的申请，进程i必须等待。系统试探性地把资源分配给进程i，并修改下面数据结构中的数值：Available=Available-RequestAllocation[i]=Allocation[i]+RequestNeed[i]=Need[i]-Request系统执行平安性算法，检查此次资源分配后，系统是否处于平安状态。如果平安才正式将资源分配给进程i，以完本钱次分配；否那么，将试探分配作废，恢复原来的资源分配状态，让进程i等待。平安性算法设置两个向量。Work：它表示系统可提供应进程继续运行的各类资源数目，它包含m个元素，开始执行平安性算法时，Work=Available。Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始Finish[i]=false；当有足够资源分配给进程i时，令Finish[i]=true；从进程集合中找到一个能满足下述条件的进程。Finish[i]==false；Need[i]≤work；如找到那么执行步骤3；否那么，执行步骤4；当进程i获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行Work=work+Allocation[i]Finish[i]=true；转向步骤2；假设所有进程的Finish[i]都为true，那么表示系统处于平安状态；否那么，系统处于不平安状态。实验内容设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；程序框架已经给出〔见附件〕，要求将平安性测试算法补充完整。当前资源状态图总的资源向量E=〔1057〕空闲的资源向量C=(357)已分配尚需ABCABCP0010743P1200122P2302600P3211011P40024312．补充完整的平安性算法//平安性检测//返回值：0：未通过平安性测试；1：通过平安性测试intTest_Safty(){//〔请写出平安性测试算法的代码〕 cout<<endl<<"进入平安性检测！"<<endl; inti,j; intWork[MAX_RESOURCE];//定义工作向量 for(i=0;i<RESOURCE_NUM;i++) { Work[i]=Available[i]; } boolFinish[MAX_PROCESS];//定义布尔向量 for(i=0;i<PROCESS_NUM;i++) Finish[i]=false; intsafe[MAX_RESOURCE];//用于保存平安序列 boolfound=false;//判断在一轮查找中是否找到符合条件的进程 intFinishCount=0;//找到满足跳进的进程IDE数目while(FinishCount<5){ for(i=0;i<PROCESS_NUM;i++){if(Finish[i]==true)//检查是否满足条件Finish[i]==falsecontinue; boolHasResource=true; for(j=0;j<RESOURCE_NUM;j++)//检查是否满足条件Need[i]<=Work if(Need[i][j]>Work[j]) HasResource=false; if(HasResource) { for(j=0;j<RESOURCE_NUM;j++) Work[j]=Work[j]+Allocation[i][j]; Finish[i]=true; safe[FinishCount]=i; FinishCount++; found=true; } } if(found) { found=false;}elsebreak;}for(i=0;i<PROCESS_NUM;i++)//判断是否所有进程满足Finish[i]==true{ if(Finish[i]==true) continue; else { cout<<"未通过平安性测试，不分配"<<endl; return0;}}cout<<'\n'<<"找到一个平安序列:";for(i=0;i<PROCESS_NUM;i++)//打印平安序列??{ cout<<"P"<<safe[i]; if(i!=PROCESS_NUM-1) cout<<"--->";}cout<<'\n'<<"已通过平安性测试!"<<endl;return1;}3：截图4：体会：本次实验银行家算法是对死锁的防止很好表达，充分说明了能否设计一个好的资源分派算法是从源头上防止死锁的发生的重要之处。