计算机操作系统第三章处理机调度与死锁详解.ppt

银行家算法的资源分配思想 为实现银行家算法，每个进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应该超过系统所拥有的资源总量。 当进程请求一组资源时，系统必须先确定是否有足够的资源分配给该进程。若有，再进一步就算在将这些资源分配给进程后，是否会使系统进入不安全状态。如果不会，才将资源分配给它，否则让进程等待。 2.银行家算法 (一). 银行家算法中的数据结构 （1）可利用资源向量Available：这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。 Available[j]=k,表示系统中现有Rj类资源k个。 （2）最大需求矩阵Max：这是一个n × m的矩阵，它定义了n个进程中每一个进程对m类资源的最大需求。Max[i,j]=K，表示进程i需要Rj类资源的最大数目为K。 （3）分配矩阵Allocation。这是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。Allocation［i,j]=K，表示进程i当前已分得Rj类资源的数目为K。 （4）需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。Need[i,j]=K，表示进程Pi还需要Rj类资源K个，方能完成其任务。 Need[i,j]＝Max[i,j]一Allocation[i,j] (二)．银行家算法 设Requesti，是进程Pi的请求向量，当Pi发出资源请求后，系统按下述步骤进行检查： （1）如果Requesti[j]≤Need[i,j],便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所声明的最大值。 （2）如果Requesti[j]≤Available[j]，便转向步骤（3）；否则，表示尚无足够资源，Pi须阻塞等待。 （3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]：＝ Available[j] - Requesti[j]； Allocation[i,j] : ＝ Allocation[i,j] ＋ Requesti[j]; Need[i,j]: =Need[i,j] - Requesti[j]； （4）系统执行安全性算法，检查此次资源分配 后，系统是否处于安全状态。 若安全，才正式将资源分配给进程Pi，以完成本次分配； 否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 开始 Requesti[j]≤Need[i,j], 出错 N Requesti[j]≤Available[j] Pi进程等待 Available[j]：＝Available[j]一Requesti[j]； Allocation[i,j]：＝Allocation[i,j]＋Requesti[j]; Need[i,j]: =Need[i,j]一Requesti[j]； 系统安全性检查 N 安全 不分配资源 分配资源 N Y (三)．安全性算法 系统所执行的安全性算法可描述如下： （1）设置两个向量： ①工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，初始值Work:＝Available. ②设置数组Finish[n]： 它表示系统是否有足够的资源分配给进程，使之运行完成。初始值Finish[i]:=false； 当Finish[i]:=true时，进程pi可获得其所需的全部资源，从而顺利执行完成。 （2）从进程集合中找到一个能满足下述条件的进程： ①Finish[i]=false； ②Need[i,j]≤work； 若找到，执行步骤（3),否则，执行步骤（4）。 （3）当进程pi获得资源后，顺利执行直至完成，并释放出分配给它的资源，故应执行： Work：= Work+Allocation[i,j]； Finish[i] ：=true; go to step 2； （4）如果所有进程的Finish[i]＝true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 Work:=Available Finish[I]:=false 从进程集合中找能满足下述条件的进程： ①Finish[i]=false, ②Need[i,j]≤work； Work[j]:= Work+Allocation[i,j]; Finish[i] ：=true; 所有进程都满足: Finish[i]＝true 系统不安全 系统安全 安全检查开始 安全检查结束 N y N