操作系统 银行家算法实验报告.docVIP

PAGE PAGE 7 《计算机操作系统》 课程设计 题 目 银行家算法分析 学 院 计算机与软件学院 专 业 网络工程 班 级 2012级1班 学 号 20121346001 姓 名 方锡 指导教师 岳键 起止时间 2014.5.20~2014.6.3 实验报告设计背景 1.1. 产生死锁的原因： 我们知道，多个进程在运行的时候因为争夺资源会产生死锁的情况，当进程出浴照这种情况的时候，若无外力作用，他们将处于无法再向前推进的状态，而根据课本知识可知，预知，可以通过预防死锁或者避免死锁的方法来解决这一问题，通过使产生死锁的四个必要条件的第2、3、4个条件之一不能成立来避免死锁的发生。 1.2. 产生的死锁的必要条件： 互斥条件；（2）请求和保持条件；（3）不可剥夺条件；（4）环路等待。 1.3.银行家算法介绍 通过实践可以看出，预防死锁虽然可以预防死锁的发生，但是牺牲了进程的执行效率，同时，在预防死锁的过程中需要考虑到对用户的资料的安全性，所以就需要考虑到利用一些特别的算法来避免死锁，其中最具代表性的算法就是Dijkstra的银行家算法，这是由于该算法能用于银行系统现金贷款的发放而得名的。它通过自己特有的算法，在每次分配进程系统资源时候会先试探性的假设分配资源给进程，然后通过安全性算法检测此次分配是否会导致系统进入不安全状态，如果安全则直接进行资源分配，如果不安全则暂不分配。所以本次试验报告就是要深入了解银行家算法的原理和运行过程。 银行家算法的原理 2.1 银行家算法的思路 算法会先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。 2.2 银行家算法中的数据结构 可利用资源向量 int Available[j] j为资源的种类。 最大需求矩阵 int Max[i][j] i为进程的数量。 分配矩阵 int Allocation[i][j] 需求矩阵 int need[i][j]= Max[i][j]- Allocation[i][j] 申请各类资源数量 int Request i[j] i进程申请j资源的数量 工作向量 int Work[x] int Finish[y] 2.3银行家算法 设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要k个Rj类型的资源，当Pi发出资源请求后，系统按照下述步骤进行检查： 如果Requesti[j]≤Need[j],便转向步骤（2）；否则认为出错，因为它所需要的资源数已经超过它所宣布的最大值。 如果Requesti[j]≤Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。 系统试探着将资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]:=Available[j]-Requesti[j]; Allocation[i,j]:=Allocation[i,j]+Requesti[j]; Need[i,j]:=Need[i,j]-Requesti[j]; 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 2.4安全性检查算法（safe()函数） (1)设置两个向量： 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work= Available。 Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=0；当有足够的资源分配给进程时，再令Finish[i]=1。 (2)在进程中查找符合以下条件的进程： 条件1：Finish[i]=0； 条件2：need[i][j]=Work[j] 若找到，则执行步骤(3)否则，执行步骤(4) (3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]= Work[j]+ Allocation[i][j]； Finish[i]=1； goto step 2； 如果所有的Finish[i]=1都满足，则表示系统