algorithm - 两道工序求解算法 1

Question

下面是算法1的二过程求解:

turn = 0;
i = 0, j = 1;
do
{
    while (turn != i) ; //if not i's turn , wait indefinitely 
    // critical section

    turn = j; //after i leaves critical section, lets j in

    //remainder section
} while (1); //loop again

我理解为满足互斥。因为当 P0 在临界区时，P1 会一直等到它离开临界区。 P0 更新轮到后，P1 进入临界区。我不明白为什么这个算法的进展不令人满意。

进步是如果在临界区等待的进程没有进程应该可以不等待进入临界区。

P0 在离开临界区后更新 turn，因此在 while 循环中等待的 P1 应该能够进入临界区。你能告诉我为什么没有进展吗？

Answer 1

前进进度定义如下:

If no process is executing in its CS and there exist some processes that wish to enter their CS, then the selection of the process that will enter the CS next cannot be postponed indefinitely.

你上面写的代码在线程不平衡的情况下不满足这个，考虑下面的场景:

1. P0 已经进入临界区，完成它，将轮到 P1。
2. P1 进入该部分，完成它，将转弯设置回 P0。
3. P1 快速完成剩余部分，并希望再次进入临界区。但是，P0 仍然持有转牌。
4. P0 无限期地停滞在其剩余部分的某个位置。 P1 饿死了。

换句话说，该算法无法支持其中一个进程运行得更快的系统。它强制临界区由 P0 -> P1 -> P0 -> P1 -> .. 轮流拥有。对于前进的进展，我们希望允许一个场景，例如以下列方式拥有它 P0 -> P1 -> P1 -> ..，并在 P0 尚未准备好进入时继续 P1再次。否则 P1 可能会饿死。

Petersons' algorithm通过添加标志来指示线程何时准备好进入关键部分来修复此问题，就像您拥有的基于回合的公平性一样。这保证了没有人会因其他线程效率低下而停滞，并且除非其他人允许，否则任何人都不能连续多次进入。