algorithm - Dijkstra 的银行家算法

Question

有人可以提供使用银行家算法解决以下问题的分步方法吗？如何确定是否存在“安全状态”？进程可以“运行至完成”是什么意思？

在这个例子中，我有四个进程和同一资源的 10 个实例。

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

Answer 1

根据 Wikipedia ,

A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resources, it only makes it easier on the system.

当一个进程在它自己和系统之间所需的每种资源的数量可用时，它就可以运行到完成。如果一个进程需要 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 个单元以供进一步工作。由于我们可以选择允许所有进程运行的进程顺序，因此该状态被认为是“安全的”。