Dijkstra的银行家算法

每 Wikipedia ,请

如果所有进程都可以完成执行(终止),则状态(如上述示例中所示)被认为是安全的。由于系统不知道进程何时将终止,或者到那时它将请求多少资源,因此系统假定所有进程最终都将尝试获取其指定的最大资源,并在不久之后终止。在大多数情况下,这是一个合理的假设,因为系统并不特别关心每个进程运行的时间(至少不是从死锁避免的角度)。此外,如果一个进程在没有获得最大资源的情况下终止,那么它只会使系统上的工作更容易。

当流程所需的每种资源的数量在其自身和系统之间可用时,流程可以运行到完成。如果一个进程需要一个给定资源的8个单元,并且已经分配了5个单元,那么如果至少还有3个单元可供分配,那么它可以运行到完成。

举个例子,系统正在管理一个资源,有10个单元可用。正在运行的进程已经分配了8(1+1+2+4)个单元,因此还有2个单元。任何过程需要完成的最大量都是它已经分配的最小值,因此在开始时,A需要5个以上(6-1),B需要4个以上(5-1),C需要2个以上(4-2),D需要3个以上(7-4)。有2个可用,因此过程C可以运行到完成,从而释放2个单元(保留4个可用)。此时,可以运行b或d(我们假定为d)。D完成后,将有8个单元可用,之后可以运行A或B(我们假设为A)。一旦A完成,将有9个单位可用,然后B可以运行,这将留下所有10个单位的进一步工作。由于我们可以选择允许所有进程运行的进程顺序,因此状态被认为是“安全的”。

  Resources Allocated | Resources Needed    claim
  Process A      1                  6            5
  Process B      1                  5            4
  Process C      2                  4            2
  Process D      4                  7            3

分配的资源总数为8 因此,尚未分配2个资源,因此分配给过程C。完成后的过程C释放4个可分配给过程B的资源,完成后的过程B释放5个分配给过程A的资源,完成后的n过程A分配2个资源给过程D。