银行家算法设计报告

1绪论基于银行家算法的研究摘要1．研究的目的和意义加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.2．研究的内容及方法银行家算法是最有代表性的避免死锁的算法，由于该算法能用于银行系统现金贷款的发放而得名。其实现思想是：允许进程动态地申请资源，系统在每次实施资源分配之前，先计算资源分配的安全性，若此次资源分配安全（即资源分配后，系统能按某种顺序来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利地完成），便将资源分配给进程，否则不分配资源，让进程等待。关键词：银行家算法安全死锁1绪论目录摘要………………………………………………………………i1绪论……………………………………………………………11.1前言…………………………………………………………………11.2本文主要研究内容……………………………………………………12需求分析………………………………………………………22.1死锁的概念……………………………………………………………22.2关于死锁的一些概念…………………………………………………22.3资源分类………………………………………………………………22.4产生死锁的必要条件…………………………………………………22.5死锁预防………………………………………………………………32.6银行家算法……………………………………………………………33概要设计………………………………………………………43.1设计思路………………………………………………………………43.2数据结构………………………………………………………………43.3主要函数说明…………………………………………………………54详细设计…………………………………………………………64.1算法描述…………………………………………………………………64.1.1银行家算法……………………………………………………………64.1.2安全性检查算法………………………………………………………74.2函数的实现过程…………………………………………………………74.3程序流程图………………………………………………………………95测试结果…………………………………………………………106结果分析…………………………………………………………127总结……………………………………………………………13源程序清单…………………………………………………………141绪论1绪论1.1前言银行家算法是避免死锁的一种重要方法。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法确实能保证系统时时刻刻都处于安全状态，但它要不断检测每个进程对各类资源的占用和申请情况，需花费较多的时间。现在的大部分系统都没有采用这个算法，也没有任何关于死锁的检查。1.2本文主要研究内容（1）设计银行家算法，能够检测系统某一时刻是否安全，输出安全序列。（2）实现安全性检测算法。即在某一进程在某时刻提出Request时，检测系统是否能够满足该进程的请求，并得到一个安全序列，若能够得到一个安全序列，则系统能够满足它的请求，同意分配资源。若不能够满足，则回到请求前状态。（3）对于此次课程设计通过需求分析、概要设计、详细设计、测试与分析、总结、源程序清单等模块进行全面分析，以加深对死锁概念的理解，以及银行家算法避免死锁的过程。能够利用银行家算法，有效避免死锁的发生，或检测死锁的存在。2需求分析2需求分析2.1死锁的概念所谓死锁:是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。2.2关于死锁的一些结论1)参与死锁的进程最少是两个（两个以上进程才会出现死锁）2)参与死锁的进程至少有两个已经占有资源3)参与死锁的所有进程都在等待资源4)参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。2.3资源分类1)可剥夺资源2)不可剥夺资源2.4产生死锁的必要条件1、互斥条件（Mutualexclusion）一个资源每次只能被一个进程使用。2、请求与保持条件（占有等待）（Holdandwait）一个进程因请求资源而阻塞时，对已获得的资源保持不放。3、不剥夺条件（不可抢占）（Nopre-emption）进程已获得的资源，在未使用完之前，不能强行剥夺。4、循环等待条件（Circularwait）若干进程之间形成一种头尾相接的循环等待资源关系。3概要设计这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。2.5死锁预防理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。因此，对资源的分配要给予合理的规划。2.6银行家算法我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。3概要设计3概要设计3.1设计思路第一部分:银行家算法(扫描)1．如果Request=Need,则转向2;否则,出错2．如果Request=Available,则转向3,否则等待3．系统试探分配请求的资源给进程4．系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finish[i]=False&&Need=Work,则执行3;否则执行4(I为资源类别)3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:Work=Work+Allocation;Finish[i]=true;转24.若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!3.2数据结构1．可利用资源向量矩阵AVAILABLE。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果AVAILABLE[j]=K，则表示系统中现有R类资源K个操作系统课程设计2．最大需求矩阵MAX。这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果MAX[i,j]=K，则表示进程i需要R类资源的数目为K。3．分配矩阵ALLOCATION。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果ALLOCATION[i,j]=K，则表示进程i当前已分得R类资源的数目为K。4．需求矩阵NEED。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果NEED[i,j]=K，则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系：NEED[i,j]=MAX[i,j]﹣ALLOCATION[i,j]3.3主要函数说明a:voidxx(intshu[][10],inti,intm)//输出各数组资源b:voidinput(intmax[][10],intallocation[][10],intneed[][10],intavailable[],intn,intm)//输出资源分配情况c:intsec(intwork[],intneed[][10],intallocation[][10],intn,intm)//安全性算法,检查系统是否处于安全状态d:voidmain()//主函数4详细设计4详细设计4.1算法描述4.1.1银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程cusneed提出请求REQUEST[i]，则银行家算法按如下规则进行判断。(1)如果REQUEST[cusneed][i]=NEED[cusneed][i]，则转(2)；否则，出错。(2)如果REQUEST[cusneed][i]=AVAILABLE[cusneed][i]，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。操作系统课程设计4.1.2安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH(2)从进程集合中找到一个满足下述条件的进程，FINISH==false;NEED=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;GOTO2(4)如所有的进程Finish=true，则表示安全；否则系统不安全4.2函数的实现过程1．主函数(main)的实现：输入已知条件，利用安全检测函数检测已知的进程分配情况是否为安全状况。如果为安全，则输入需请求资源的进程号和所需资源数，否则结束主函数。reqi为进程i的请求向量。进行银行家算法：(1):如果reqi[j]need[i][j]则认为出错，输出请求的资源数超过它所需的最大数;否则执行(2);(2):如果reqi[j]available[i][j]则输出尚无足够的资源;否则执行(3)(3):系统试探着把资源分配给进程i，并修改下面数据结构中的数值：available[j]:=