operating-system - 临界区的进度和有界等待是什么？

Question

我正在阅读 Peter B. Galvin 的操作系统概念中的临界区问题。
根据它

1) 进度 is :如果没有进程在其临界区中执行，而某些进程希望进入其临界区，则只有那些未在其剩余部分中执行的进程才能参与决定下一个将进入其临界区的进程，并且此选择不能无限期推迟。

和

2)有界等待是 :在一个进程请求进入其临界区之后，在该请求被批准之前，允许其他进程进入其临界区的次数存在界限或限制。

我不明白作者想在这两种情况下说什么。

您能否通过给出与此定义相关的适当示例来让我理解。

谢谢你。

Answer 1

首先，让我介绍一些术语。临界区 (CS) 是一系列指令，最多可以同时由一个进程执行。使用临界区时，代码可以分解为以下部分:

// Some arbitrary code (such as initialization).

EnterCriticalSection(cs);

// The code that constitutes the CS.
// Only one process can be executing this code at the same time. 

LeaveCriticalSection(cs);

// Some arbitrary code. This is called the remainder section.

第一部分包含一些代码，例如初始化代码。我们没有该部分的名称。第二部分是尝试进入 CS 的代码。第三部分是 CS 本身。第四部分是离开临界区的代码。第五个也是最后一个部分称为剩余部分，可以包含任何代码。请注意，CS 本身在进程之间可能不同(例如，考虑一个从客户端接收请求并将它们插入队列的进程和另一个处理这些请求的进程)。

为了确保关键部分的实现正常工作，必须满足三个条件。你提到了其中的两个(我将在下面解释)。三是互斥，这显然是至关重要的。值得注意的是，互斥仅适用于 CS 和 leave 部分。但是，其他三个部分并不是唯一的。

第一个条件是进步。此条件的目的是确保某个进程当前在 CS 中并在执行某些工作，或者，如果至少有一个进程想要进入 CS，它将然后执行某些工作。在这两种情况下，一些工作正在完成，因此所有流程总体上都在取得进展。

Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

让我们逐句理解这个定义。

If no process is executing in its critical section

如果有一个进程在其临界区执行(即使没有明确说明，这也包括离开部分)，那么这意味着一些工作正在完成。所以我们正在取得进展。否则，如果不是这样的话……

and some processes wish to enter their critical sections

如果没有进程想要进入它们的临界区，那么就没有更多的工作要做。否则，如果至少有一个进程希望进入其临界区...

then only those processes that are not executing in their remainder section

这意味着我们谈论的是在前两个部分中的任何一个中执行的进程(请记住，没有进程在其临界区或离开部分中执行)......

can participate in deciding which will enter its critical section next,

由于至少有一个进程希望进入它的 CS，所以我们必须以某种方式选择其中一个进程进入它的 CS。但是谁来做这个决定呢？那些已经请求允许进入其关键部分的流程有权参与做出此决定。另外，那些进程 5 月 希望进入其 CS 但尚未请求许可(这意味着他们正在执行第一部分)也有权参与做出此决定。

and this selection cannot be postponed indefinitely.

这表明选择一个进程以进入其 CS 将花费有限的时间。特别是，没有 deadlock or livelock会发生。所以在这段有限的时间之后，一个进程将进入它的 CS 并做一些工作，从而取得进展。

现在我将解释最后一个条件，即有界等待。此条件的目的是确保每个进程都有机会真正进入其临界区，以便没有进程 starves forever .但是，请注意，此条件和进度均不保证公平性。 CS 的实现不一定是公平的。

Bounded waiting: There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

让我们从最后一个开始逐句理解这个定义。

after a process has made request to enter its critical section and before that request is granted.

换句话说，如果有一个进程已经请求进入它的 CS 但还没有进入它。我们称这个过程为 P。

There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections

当 P 正在等待进入其 CS 时，其他进程可能也在等待，并且某些进程正在其 CS 中执行。当它离开它的 CS 时，必须选择一些其他进程进入 CS，它可能是也可能不是 P。假设选择了 P 以外的进程。这种情况可能会一次又一次地发生。也就是说，其他进程有机会进入他们的 CS，但从来没有 P。请注意，正在取得进展，但由其他进程，而不是 P。问题是 P 没有机会做任何工作。为了防止饥饿，必须保证 P 最终会进入它的 CS。为此，必须限制其他进程进入其 CS 的次数。在这种情况下，P肯定有机会进入它的CS。

我想提一下，CS 的定义可以泛化，因此至多 N 个进程在其临界区中执行，其中 N 是任何正整数。还有读写器临界区的变体。