死锁避免算法设计报告

操作系统课程设计报告漳州师范学院操作系统课程设计死锁避免算法设计姓名：学号：系别：专业：年级：指导教师：一、课程设计题目介绍（含设计目的）操作系统课程设计报告死锁避免算法设计是通过模拟实现银行家算法实现死锁避免目的：1、了解进程产生死锁的原因，了解为什么要进行死锁的避免。2、掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。3、通过运用Dijkstra的银行家算法来避免多个进程运行中因争夺资源而造成僵局，即死锁要求：本课程设计可以实现教材3.6.3节中所描述的银行家避免死锁算法。可自定义进程数目、资源类型和每种类型资源的数目；可输入每个进程对每种资源的最大需求、已经获得的数量；当某进程发起某种资源请求时，计算系统状态是否安全。思想：操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配，从而达到死锁的避免。操作系统课程设计报告二、总体设计（含系统的结构、原理框图或模块介绍等）1.系统的结构2.原理框图从主函数开始进入银行家算法系统，先调用初始化函数chushihua()分别输入Allocation[i][j]，Max[i][j]，All[y]并判断是否符合条件，在调用函数show(),输出当前状态Available，Max[i][j]，Allocation[i][j]，Need[i][j]。然后调用安全性算法函数safe()判断在该时刻是否处于安全状态，并输出安全序列。然后调用银行家算法函数bank()进行试分配后再调用安全性算法函数判断在该时刻是否处于安全状态，若不安全，则恢复试分配时改变的值。进入银行家算法演示初始化资源矩阵尝试资源分配检测系统的安全性退出操作系统课程设计报告三、详细设计（含主要的数据结构、程序流程图等）1.数据结构资源的总数量All[i]：是个含有i个元素的数组，其中的每一个元素代表一类资源的总数量。如果All[i]=K，则表示系统中现有i类资源总数为K个。可利用资源向量Available[i]：是个含有i个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[i]=K，则表示系统中现有i类资源K个。最大需求矩阵Max[i][j]：这是一个i×j的矩阵，它定义了系统中i个进程的每一个进程对j类资源的最大需求。如果Max[i][j]=K，则表示进程i需要j类资源的最大数目为K。分配矩阵Allocation[i][j]：这也是一个i×j的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i][j]=K，则表示进程i当前已分得j类资源的数目为K。进入银行家算法演示调用银行家算法bank()调用显示当前状态函数show()调用初始化函数chushihua()调用安全性检查算法safe()lnNYY拒绝申请操作系统课程设计报告需求矩阵Need[i][j]：这也是一个i×j的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i][j]=K，则表示进程i还需要j类资源K个，方能完成其任务。上述三个矩阵间存在关系：Need[i][j]=Max[i][j]-Available[i]2.程序流程图2.1初始化函数chushihua()输入进程的数量n和资源种类数m。使用for循环在二维数Allocation[i][j]中输入各进程当前已分配的资源数量。使用for循环在二维数组Max[i][j]中输入各进程对各类资源的最大需求，并求出对应的二维数组Need[i][j]用来记录尚需分配的资源。使用for循环在一维数组All[]中输入各种资源的总数量，并求出各类资源尚可利用的数量Available[j]。图1初始化函数chushihua()流程图输入n、mfor循环输Allocationfor循环输入Max，求出Needfor循环输入All，求出Available操作系统课程设计报告2.2显示当前状态函数show()用于输出当前各种数组的情况。2.3银行家算法bank()a、先输入申请资源的进程k，判断是否kn-1。再输入该进程申请各类资源的数量，没输入一个要申请的资源数都要用do……while循环判断申请输入的情况。判断申请是否大于需求量，如果（Request[j]Need[k][j]）则出错，提示重新输入。否则继续判断申请是否大于可利用量，如果(Request[j]Available[j])则出错，本次申请不成功，进程等待。否则进行试分配。试分配后调用安全性检查算法safe()检测此时系统是否处于安全状态如果安全继续运行，如果不安全将试分配的数据恢复。b、进程i发出请求申请k个j资源，Requesti[j]=k(1)检查申请量是否不大于需求量：Requesti[j]=need[i,j],若条件不符重新输入，不允许申请大于需求量。(2)检查申请量是否小于系统中的可利用资源数量：Requesti[j]=available[i,j]，若条件不符就申请失败，阻塞该进程，用goto语句跳转到重新申请资源。(3)若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Available[i,j]=Available[i,j]-Requesti[j]；详细设计Allocation[i][j]=Allocation[i][j]+Requesti[j]；need[i][j]=need[i][j]-Requesti[j]；(4)试分配后，执行安全性检查，调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(5)用do{…}while循环语句实现输入字符y/n判断是否继续进行资源申请。输入申请资源的进程kkn-1输入申请数量Request[j]for(j=0;jm;j++)RjAjRjNj试分配安全调用safe()输出安全序列阻塞恢复YYNNYNYYN图2银行家算法bank()流程图2.4安全性检查算法safe()a、令全局变量l=0，l用来记录有几个进程是Finish[i]=1的，当l=n是说明系统状态是安全的。使用for循环逐个查找Finish[i]==0的进程，设置记数器counter用来记录满足条件Work[j]=Need[i][j]的资源类数，如果满足则给counter加一，如果counter==m，则表示i进程的每类资源都符合Work[j]=Need[i][j]，把此时进程i的值存入存储安全序列p[l]中，使Finish[i]=0，表示i进程标志为可分配。释放资源使Work[j]=Work[j]+Allocation[i][j]，给l加一详细设计图3安全性检查算法safe()流程图b、检查过程：(1)设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work=Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=0；当有足够的资源分配给进程时，再令Finish[i]=1。l=0for(j=0;jm;j++)Fi=0Counter=0for(i=0;in;i++)Wj=NjCounter+1Counter=mp[l]=i,Fi=1,Wj=Wj+Aj,l=l+1YYNNNYYYY不安全操作系统课程设计报告(2)在进程中查找符合以下条件的进程：条件1：Finish[i]=0；条件2：need[i][j]=Work[j]若找到，则执行步骤(3)否则，执行步骤(4)(3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work[j]=Work[j]+Allocation[i][j]；Finish[i]=1；gotostep2；(3)如果所有的Finish[i]=1都满足，则表示系统处于安全状态，否则，处于不安全状态。操作系统课程设计报告四、运行结果（含测试和用户使用说明书）1.测试与分析（1）初始化：输入进程的数量n，资源种类数m，已分配的资源数Allocation[i][j]，各进程对各类资源的最大需求数Max[i][j]，各种资源的总数量All[]。（2）显示当前状态：输出各类资源尚可利用的数量Available，各进程对各类资源的最大需求数Max[i][j]，已分配的资源数Allocation[i][j]，尚需分配的资源数Need[i][j]，以及安全序列。操作系统课程设计报告（3）输入申请资源数Request[j]：输入申请资源数Request[1]=（1,0,2），并逐个判断是否满足条件：Requesti[j]=need[i,j]；Requesti[j]=available[i,j].如果满足条件，申请资源成功。输出安全序列以及各类资源尚可利用的数量Available，各进程对各类资源的最大需求数Max[i][j]，已分配的资源数Allocation[i][j]，尚需分配的资源数Need[i][j]，的值操作系统课程设计报告输入申请资源数Request[4]=（3,3,0），进程4申请资源0的数量：3小于进程4的尚需资源4，但是它大于可利用资源2，所以没有那么多资源，本次申请不成功，应该阻塞等待。（4）输入申请资源数Request[0]=（0,2,0）：虽然Request[0]=（0,2,0）满足条件：Requesti[j]=need[i,j]；Requesti[j]=available[i,j]，但是试分配后，状态不安全，所以恢复原状态。显示各类资源尚可利用的数量Available，各进程对各类资源的最大需求数Max[i][j]，已分配的资源数Allocation[i][j]，尚需分配的资源数Need[i][j]，的值。操作系统课程设计报告2.用户说明书程序开始运行后，首先进行初始化数据，提示输入进程的数量n，资源种类数m，已分配的资源数Allocation[i][j]，之后按屏幕显示的提示操作。五、课程设计小结与心得体会设计开始的时候,由于整体对银行家算法还没有完全理解透,再加上没认真预习、思考不够认真、对书本的知识不够扎实,所以一脸惘然,不知道从哪里开始着手.才发现这次课程设计没我想得那么简单,回寝室后,连忙查看相关的书,以及通过上网查找相关的资料,最终对银行家算思想有了彻底的了解，银行家分配算法原则是:当进程申请资源时，如果系统中现存资源数能满足进程的当前资源申请量以及申请的资源数要小于需要的资源数(request[j]=need[i][j]||操作系统课程设计报告request[j]=available[j])并且还要验证是否有安全,只有在安全情况下才能将资源分配给它,也即银行家算法能避免死锁的发生。接下来的任务就是开始编写程序,刚开始由于这学期对c++知识没有学习好,所以刚编写时有很大的难度,把一些本来可以用很少话解决的问题很多都复杂化了,这时我才发现我有那么多的不足,只好重新拿出以前的书,把不懂的大概都看了一遍,脑子里总算有了理解.通过这次实践,我相信，只要自己在每一次实践中都能仔细思考，课程设计其实都不会很难,关键在于自己能不能认真思考,能不能亲自动手做实验，而不是想着其他人的劳动果实,其次你还要多操作,只有多操作才能从中发现问题,才能及时向老师和同学请教,解决问题,从而更好的掌握书本中知识。还有通过这次实践也让我懂得了,要认真对待每一次设计,通过这次设计对课本上知识有了更深刻的认识,得到了很多从书本中得不到的经验。操作系统课程设计报告六