Question

浅析银行家算法

Answer 1

作为避免死锁的一种算法，银行家算法可以说是最为出名的了。这个名字的来源是因为该算法起初是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在操作系统中也可以用它来实现避免死锁。

首先我们要了解银行家算法的本质也即避免死锁的原理。避免死锁作为一种事先预防死锁的策略，原理是在为各个进程分配资源的过程中不允许系统进去不安全状态，以此来避免死锁的发生。所谓安全状态，是指系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成。此时称该进程推进序列为安全序列，如果无法找到这样一个安全序列，则称系统处于不安全状态。

银行家算法中的数据结构。为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源，所有进程对资源的最大需求，系统中的资源分配以及所有进程还需要多少资源的情况。

(1)可利用资源向量Available。这是一个含有m个元表的数组,其中的每一个元素代表一类可利用的资源数目。其数值随该类资源的分配和回收而动态地改变。如果 Available=K,则表示系统中现有Rj类资源K个。

    (2)最大需求矩阵Max。这是一个nxm的矩阵,它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。

    (3)分配矩阵 Allocation。这也是一个nxm的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,表示进程i当前已分得Rj类资源的数目为K。

    (4)需求矩阵Need。这也是一个nxm的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个才能完成。

当一个进程发出请求资源的请求后，如果它所请求的资源大于目前系统可利用资源则不予分配。如果小于可利用资源，则系统试探着把资源分配给该进程，并修改分配之后的资源数值。接着系统执行安全算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给该进程，以完成本次分配。否则，将本次的试探分配作废，恢复原来的资源分配状态，让该进程等待。