为什么这个 Mutex 解决方案不正确？

Question

有2个进程P1和P2可以进入临界区

互斥解决方案要求：

互斥区 -（临界区）最多只能容纳一个进程。

无相互阻塞 - 临界区外的进程不能阻塞临界区内的进程。

No Starvation - 有兴趣进入临界区的进程不必永远等待。

无争用成功 - 如果没有其他进程感兴趣，则有兴趣进入临界区的进程必须成功。

为什么下面的代码是互斥问题的错误解决方案？

即不满足哪个要求？

C1和C2初始化为1。

P1:  LOOP
        Non-Critical Section
        LOOP UNTIL C2 = 1 END_LOOP;
        C1 := 0;
        Critical Section
        C1 := 1;
END

P2:  LOOP
        Non-Critical Section
        LOOP UNTIL C1 = 1 END_LOOP;
        C2 := 0;
        Critical Section
        C2 := 1;
END

Answer 1

为了最好地解释这个问题，我不得不假设每次读取或写入都被认为是原子的且有序的。那就更有意义了。

你这里的问题是每个进程中的内循环可以独立完成。这些循环是互斥锁的 "wait for my turn" 部分。

但是，该循环的终止和随后的赋值（这将阻止 other 循环终止）不是原子的。因此，我们有以下可能的情况：

P1: exit wait loop because C2 is 1

P2: exit wait loop because C1 is 1
P2: set C2 to 0
P2: enter critical section

P1: set C1 to 0
P1: enter critical section

以上违反了拥有互斥区的第一个要求。导致此类违规的条件通常称为 竞争条件。

您还可以预期一个进程会耗尽另一个进程。有可能 P2 总是会执行它的临界区并在 P1（正在等待锁）获得 CPU 时间片之前再次获取锁。因此，控制变量 C2 将始终为 P1 所见的 0。或者至少，对于不成比例的切片数量可能是这样。

P2: exit wait loop because C1 is 1
P2: set C2 to 0

P1: spin on C2 != 1 for entire time slice

P2: enter critical section
P2: set C2 to 1
P2: exit wait loop because C1 is 1
P2: set C2 to 0

P1: spin on C2 != 1 for entire time slice

P2: enter critical section
P2: set C2 to 1
P2: exit wait loop because C1 is 1
P2: set C2 to 0

P1: spin on C2 != 1 for entire time slice

...

除非在某些环境中，P1 不太可能永远挨饿。但由于 P1 已断言它正在等待，因此不应期望 P2 在轮到之前在临界区获得多个裂缝。

这也可能违反了无竞争成功的要求，但这真的很难争论。但我建议，如果 P2 不再是运行，那么请考虑 C2 可能处于何种状态，以及为什么 P1 需要完全了解 P2。

为什么这个 Mutex 解决方案不正确？

Why is this Mutex solution incorrect?

mutex

mutual-exclusion