c - 这个互斥伪代码是如何工作的？

Question

bool flag[2] = {false, false}
process p(i):   // i in { 0, 1 }
while (flag[1-i]) {
    // do nothing
}
flag[i] = true
while (flag[1-i]) {
    // do nothing
}
<critical section>
flag[i] = false

这段代码让我抓狂。它是为解决两个程序 (0 , 1) 之间的互斥问题而构建的代码。 有人可以解释一下，当放入代码中时，每个程序 0 和 1 的标志如何变化。

Answer 1

2 个 bool 值的数组 flag 必须位于共享内存中才能有机会工作。对于流程来说，这是至关重要的；如果这些是线程，则不需要共享内存。

最初，进程 0 或 1 都没有将其 flag 值设置为 true。

假设进程i = 0尝试访问临界区。第一个繁忙循环(while 循环)等待，直到 flag[1] 为 false(目前为 false)；然后代码设置flag[0] = true。代码现在进入第二个繁忙循环； flag[1] 仍然是 false，因此它会继续安全地进入临界区，因为知道其他进程也不在临界区中。

假设当进程 0 位于临界区时，进程 1 也尝试进入临界区。它在第一个繁忙循环中被阻塞，因为 flag[0] 为 true。它会一直保持这种状态，直到进程 0 离开并将 flag[0] 设置回 false。当进程0离开时，进程1将flag[1]设置为true，进入第二个繁忙循环，然后由于flag[0]为false而离开；它现在处于关键部分。

为什么有两个繁忙循环？因为可能会出现两个进程同时在多个核心上运行的情况，并且都可能同时进入第一个繁忙循环。他们都会看到对方的标志为假，退出循环并将自己的标志设置为真，然后重新检查对方的标志是否仍然为假。大多数时候，其中一个会发现另一个是假的，并会进入临界区。有时，他们可能都发现对方的说法是正确的(因为他们的工作步调一致)，然后双方都会进入第二个忙循环，并且都不会退出——死锁。

所以，我不相信该代码是一种万无一失的互斥机制，尽管它需要运气不好才能陷入僵局。然而，如果尝试足够多，运气就会发生——长时间运行的流程无法承受这种风险。