algorithm - 死锁检测算法(伪代码)

Question

我正在阅读 Silberschatz G. Gagne 的操作系统概念，在关于死锁的章节中，有一个用于死锁检测的伪代码如下:

1. Let Work and Finish be vectors of length m and n, respectively. (There are n processes and m resources.)

   Initialize Work = Available. For i = 0, 1, ..., n-1, if Allocation[i] != 0, then Finish[i] = false; otherwise, Finish[i] = true.

2. Find index i such that both Finish[i] == false && Request[i] <= Work.

   If no such i exists, go to step 4.

3. Work = Work + Allocation[i]

   Finish[i] = true;

   Go to step 2.

4. If Finish[i] == false for some i, then system is deadlocked. Moreover, if Finish[i] == false, then process Pi is deadlocked.

这与银行家算法非常相似。但是，上面的粗体声明略有不同。

有人可以解释为什么如果操作系统没有为进程 i 安排任何资源，算法会立即将进程 i 的 Finish[i] 设置为真。据我所知，这绝对并不意味着它不会陷入僵局，正如第 4 步提到的那样(不确定这是否正确)。谢谢!

Answer 1

运行此算法时，它会检测当前陷入死锁的进程(如果有的话)。

一个没有资源的进程可能正在等待一个死锁进程，但它本身不会陷入死锁，并且与算法的其余部分无关(它在第 3 步中没有影响)，所以通过设置 Finish[i]=true

忽略它

请注意，该算法仍然不能完全正确地识别死锁进程。在第 4 步中标记的进程可能持有资源，并且可能在等待死锁进程时被阻塞，但可能没有需要它持有的资源的死锁进程，因此该进程不会参与死锁本身。