银行家算法实验报告 mfc

XXXXXXX学院《计算机操作系统》课程设计死锁的避免——银行家算法专业班级：XXXXXXX成员：王乂、蔡乂、王xx提交时间：xxxx年xx月xx日一、问题描述1.1银行家算法银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，所谓安全状态，是指进程能按某种进程次序(pl,p2,,,pn),来为每个进程pi分配其所需资源,直至满足进程pi对资源的最需求量，使每个进程pi可顺利地完成，则此时系统处于安全状态，称序列(pl,p2,,,pn)为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态.最早由Dijkstra提出了一种能够避免死锁的调度方法，称为银行家法若分配不会导致系统进入不安全状态，则分配，否则等待。银行家算法的核心内容是判断资源试分配后系统是否处于安全状态，即是否可以找到一个进程安全序列.1.2银行家算法提出的原因在计算机系统中，安全问题一直为用户所关注。资源分配如果可以保证所用进程在有效时间得到所要资源则称其为安全。各进程在使用系统资源时，应注意系统产生的死锁问题。银行家算法是针对计算机系统上述安全问题进行的设计，可以判断新申请的进程是否为安全，避免死锁问题的发生。二、实验目的1、掌握死锁概念、死锁发生的原因、死锁产生的必要条件2、掌握死锁的预防、死锁的避免3、深刻理解死锁的避免：安全状态和银行家算法三、问题分析3.1死锁死锁问题不仅在计算机系统中存在,在日常生活中的其他领域中也广泛存在。3.1.1何谓死锁所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。3.1.2死锁发生的原因产生死锁的原因可以归结为两点：1、竞争资源，当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足进程的需要时，会引起进程对资源的竞争而产生死锁。2、进程间推进顺序非法，进程在运行过程中，请求和释放资源的顺序不当，也同样会导致进程死锁。死锁产生的必要条件1、互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，只至占有该资源的进程用毕释放。2、请求和保护条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源又被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。3、不剥夺条件：指进程已获得资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。4、环路等待条件：指在发生死锁时，必然存在一个进程一资源的环形链，即进程集合｛P0，P1，P3，„Pn｝中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。3.2死锁对多道程序系统带来的影响在多道程序设计中,多个进程可能要去竞争有限的资源。进程请求资源，如果当前这些资源不可用，因为它有可能正在被其它的进程使用着，那么该进程就必须进入等待状态。正在等待的进程可能不会再改变状态，因为它所请求的资源一直被其它进程所持有。3.3预防死锁根据产生死锁的四个必要条件，只要使其中之一不能成立，死锁就不会出现。为此，可以采用下述三种预防措施。1、防止“请求和保持”条件的出现系统要求任一进程必须预先申请它所需要的全部资源，而且仅当该进程的全部资源要求都能得到满足时。系统才给予一次性分配，然后启动该进程运行。进程在整个生存期间，不再请求新的资源。因此“请求和保持”条件不会出现，死锁也就不可能发生。该方法实际上采用的是资源的静态预分配策略,其优点是简单安全，易于实施。但太保守，资源利用率很低。2、防止“不剥夺”条件的出现在允许进程动态申请资源的前提下，规定一个进程在请求新资源不能立即得到满足而变为等待状态之前，它必须释放己占有的全部资源；若需要，再重新申请新资源和已释放的资源，从而破坏了“不剥夺”条件的出现。该策略实现起来相当困难，为了保护在自动放弃资源时的现场以及以后的恢复现场，需要付出很高的代价。特别是可能出现进程反复地申请和释放某些资源而被无限延迟执行的现象。3、防止“环路等待”条件的出现采用资源顺序使用法，其基本思想是：把系统中所有资源按类型线性排队，并按递增规则赋予每类资源以惟一的编号。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。由于在任何时刻，总有一个进程占有较高编号的资源，它继续请求资源的要求必然可获满足，因此，一定不会出现环路等待条件。这种策略的优点是，资源的申请与分配是逐步进行的，与预分配策略比较，显著提高了资源利用率。但是，实际上有些进程使用资源的顺序往往与系统规定的不一致，于是某些暂时不用的资源要先申请，先占住又暂不使用，降低了资源利用率。另外，严格地限制使用资源的顺序性，也给程序设计带来了不便。对于产生死锁的“互斥”条件，不仅不能预防，相反希望能够正确地实现互斥使用临界资源。3.4死锁的预防：什么是安全态以及如何保证多个进程在某个时刻是处于安全的3.4.1所谓安全状态，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列｛P1，P2,…，Pn)就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的状态。3.4.2一旦检测到死锁，便要立即设法解除死锁，使系统恢复。常见方法有以下几种。重新启动，最简单、最常用的方法。不过这种方法代价很大，它意味着在这之前所有的进程已经完成的计算都将付之东流。撤销进程法，这可以是撤销所有死锁进程，或者逐个撤销死锁进程。每撤销一个进程就检测死锁是否继续存在，若不再存在，就停止撤销。挂起进程法，使用挂起/激活机构挂起一些进程，剥夺它们占有的资源以解除死锁，待以后条件满足时，再激活被挂进程。问题是在挂起点激活比较困难，而要回退到挂起点之前某个状态才能重新执行，这需要保留多个现场，增加了开销。四、设计方案4.1数据结构的建立银行家算法中的数据结构设有n个进程P1、P2、……、Pn共享m类资源R1、R2、……、Rm。可利用资源向量Available=(a1、a2、、am)含有m个元素，每个元素含有某类资源可利用的单位数，初始值为系统中该类资源的全部单位数，向量随着资源的分配和回收而动态变化。最大需求矩阵MaxMax(I,j)=k;表示进程Pi总共需要j类资源K个单位。分配矩阵AllocationAllocation(I,j)=k;表示进程Pi在当前时刻占有K个单位的J类资源。需求矩阵NeedNeed(I,j)=k;表示进程Pi要完成工作还需要J类资源K个单位，即剩余资源需求。Need(I,j)=Max(I,j)-Allocation(I,j);4.2算法的设计4.2.1算法设计思路在银行家算法中，为了决定是否对当前申请资源的进程进行资源分配，将系统状态划分成安全状态和不安全状态。若当前申请资源的进程分配资源后资源进入安全状态，则正式接受当前进程请求为其分配资源，否则将拒绝资源请求。4.2.2安全性算法流程图N况如底=work&&(!Finish[i])^finishl:all]==true工作向重v/ork=Available-N况如底=work&&(!Finish[i])^finishl:all]==true工作向重v/ork=Available-ork=«llocationi]+ork1finish'i]=truefmish[i]=FALSE^系统不安全」初始化p系统安全甘4.2.3银行家算法设Request[i]是当前运行的进程Pi的请求向量，若Request[i][j]=k,表示进程Pi当前请求J类资源K个单位。当前进程Pi发出资源请求后，系统按照下述步骤进行检测：若Request[i]>Need[i]则为非法请求，进程进行相应处理，以为它需要的资源数，大于它的最大值；否则进行(2)。若Request[i]>Available，则表示系统现在的可利用资源不能满足进程的需求，阻塞进程；否则进行(3)。系统试探的把要求的资源分配给进程Pi，既不进行实际的资源分配，而只是修改相关数据结构：for(i=1;i<=j;i++)(Available[i]=Available[i]-Request[Pi][i];Allocation[Pri][i]=Allocation[Pi][i]+Request[Pi][i];Need[Pi][i]=Need[Pi][i]-Request[Pi][i];}执行安全性检测算法，检测此次资源分配后，系统是否处于安全状态。若为安全，则正式将资源分配给进程Pi,否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性检测算法设置两个工作向量Work和Finish，Work表示当前系统可利用各类资源数，初始值为Available，Finish表示各进程能否运行完成。intWork[11];for(i=0;i<11;i++)Work[i]=m_Available[i];BOOLFinish[11];for(i=0;i<11;i++)Finish[i]=FALSE;//依次寻找能获得所需资源从而完成的进程，即求安全序列for(i=1;i<=Pi_Max;i++)for(intj=1;j<=Pi_Max;j++)(if((!Finish[j])&&Compare(m_Need[j],Work))(for(intx=1;x<=Ri;x++)Work[x]=Work[x]+m_Allocation[i][x];Finish[j]=TRUE;}}for(i=1;i<=Pi_Max;i++)if(Finish[i])c++;if(c==Pi_Max)AfxMessageBox("所有程序都能运行完成\n系统处于安全状态〃)；elseAfxMessageBox("系统处于不安全状态");安全序列的生成voidCMyDlg::OnSaf()(//TODO:Addyourcontrolnotificationhandlercodehereintc=0;intm_Available[11];//可利用资源向量for(inti=0;i<11;i++)m_Available[i]=Available[i];intm_Allocation[11][11];//分配矩阵for(i=1;i<=Pi_Max;i++)for(intj=1;j<=Ri;j++)m_Allocation[i][j]=Allocation[i][j];intm_Need[11][11];//需求矩阵for(i=1;i<=Pi_Max;i++)for(intj=1;j<=Ri;j++)m_Need[i][j]=Need[i][j];for(i=1;i<=Pi_Max;i++)for(intj=1;j<=Ri;j++)m_Available[j]=m_Available[j]-Allocation[i][j];//intWork[11];for(i=0;i<11;i++)Work[i]=m_Available[i];BOOLFinish[11];for(i=0;i<11;i++)Finish[i]=FALSE;CStringCS_Safe=〃〃；charch[5];//依次寻找能获得所需资源从而完成的进程，即求安全序列for(i=1;i<=Pi_Max;i++)for(intj=1;j<=Pi_Max;j++)(if((!Finish[j])&&Compare(m_Need[j],Work))(for(intx=1;x<=Ri;x++)Work[x]=Work[x]+m_Allocation[j][x];Finish[j]=TRUE;itoa(j,ch,10);CS_Safe=CS_Safe+"P"+ch;if(i<Pi_Max)CS_Safe=CS_Safe+"->";break;}}for(i=1;i<=Pi_Max;i++)if(Finish[i])c++;if(c==Pi_Max)AfxMessageBox(CS_Safe);elseAfxMessageBox("系统死锁！〃)；4.3测试运行资源进程*****最大需求量R1R2R3R4已分配资源数R1R2R3R4总资源数R1R2R3R4P1642111119633P222212111P381112100P422111211当前进程按照P4->P2->P1->P3序列执行，系统是安全的。

输入总资源数和P1进程的最大需求和分配矩阵国银行家算法求安全态总资源数|9633查看I添加进程I进程03最大零求矩阵当前进程町三］请求资源P2进程的最大需求和分配矩阵进程03进程03最大零求矩阵P3进程的最大需求