2

这是两个过程的解决方案算法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 在离开临界区后更新，所以在 while 循环中等待的 P1 应该能够进入临界区。你能告诉我为什么没有进展吗？

4

3 回答 3

3

前进进度定义如下：

如果没有进程在其CS中执行，并且存在一些希望进入其CS的进程，则不能无限期地推迟选择下一个将进入CS的进程。

在线程不平衡的情况下，您上面编写的代码不满足这一点，请考虑以下情况：

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

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

Petersons 的算法通过添加标志来指示线程何时准备好进入临界区来解决这个问题，就像您拥有的基于回合的公平性之上。这保证了没有人因另一个线程的低效率而停滞不前，并且除非对方允许，否则没有人可以连续多次进入。

于 2013-11-02T18:44:59.423 回答
1

您无法确定两个进程中的代码运行的顺序。当第一个 P1 运行并试图进入临界区时，它是不允许的，因为它是轮到 P0 的。因此，即使 P1 中没有其他进程，P1 也无法进入临界区。因此，进展没有实现。

于 2013-11-02T14:44:06.670 回答
0

这里的问题是这完全取决于较低级别的进程调度。操作系统通常需要一点时间来唤醒一个睡眠进程，这是在当前运行在 CPU 上的进程通过执行一些阻塞系统调用自愿放弃控制权时完成的，或者在时间量到期时超时中断。在完整的 SMP 系统上，这也需要一些重要的内核同步和信令。

这意味着进程 0 可以循环离开并再次进入临界区，而进程 1 没有机会运行。

另外，我希望您也不要依赖裸整数变量来进行互斥。这些可能由编译器缓存在寄存器中，如果没有，处理器缓存就会发挥作用。这应该通过特殊的 CPU 指令（如 test-and-set）来完成。

于 2013-11-02T14:50:29.800 回答