“critical section算法”中的“进展”和“有界等待”是什么意思？

Question

考虑以下代码：

  //proces i:                             //proces j:

  flag[i] = true;                         flag[j] = true;
  turn = j;                               turn = i;
  while(flag[j] == true && turn==j);       while(flag[i] == true && turn == i);

  <critical section>                      <critical section>

  flag[i] = false;                        flag[j] = false;

  <remainder section                      <remainder section>

我确信上述代码能够满足“互斥”属性，但对于以下问题仍有疑问：

1. “进展”（progress）指的具体是什么？上述代码是否满足该属性？上述代码要求临界区在严格交替中执行。这被认为是“进展”吗？

2. 从我所看到的，上述代码并没有维护任何有关进入临界区次数的信息，那么这是否意味着上述代码不满足“有界等待”（bounded waiting）属性？

- vikkyhacks

Answer 1

进展意味着该过程最终将执行一些工作。一个例子是当低优先级线程可能被高优先级线程抢占并回滚时，这种情况可能不成立。一旦您的进程到达其关键部分，它们就不会被抢占，因此它们会取得进展。 有界等待意味着该进程最终将获得对处理器的控制。一个例子是当另一个进程在临界区中具有非终止循环而没有可能中断线程时，这种情况可能不成立。如果关键部分终止并且剩余部分不会重新调用该进程的关键部分，则您的代码具有有界等待（否则，一个进程可能会持续运行其关键部分，而其他进程永远无法获得处理器的控制）。

- Zim-Zam O'Pootertoot

---

你好，我在我的相关问题中链接了你的答案，但我仍然对这个主题有疑问。你能否请看一下？（很抱歉用这种方式引起你的注意，我知道这种请求帮助的方式在stackexchange上是不被鼓励的） - Mahesha999

Answer 2

1. 进程的进展意味着进程不会陷入死锁状态，因此它们的执行将继续独立进行！实际上，在任何时刻，只有进程i或进程j中的一个将执行其临界区代码，因此一致性将得到保持！因此，在给定的代码中，两个进程的进展正在成功地被讨论和满足。

2. 接下来，这段特定的代码是为了仅运行一次的进程而设计的，因此它们不会再次到达其关键部分代码。它用于单个进程的执行。

有界等待指的是，在进程请求进入其关键部分并获得批准之前，其他进程允许进入其关键部分的次数必须有一个限制。

这段特定的代码与有界等待无关，只适用于进程仅执行一次的简单情况！

- Am_I_Helpful

---

如果它们在do while循环中，互斥性是否会被违反？ - vikkyhacks

@vikkyhacks - 不，简短的回答就是不行。这仍将保留互斥性质。 - Am_I_Helpful