临界区的进度和有限等待是什么？
What is progress and bounded waiting in critical section?
我正在阅读 Peter B. Galvin 的《操作系统概念中的临界区问题》。
根据它
1) Progress is : 如果没有进程在其临界区中执行并且某些进程希望进入其临界区，则只有那些未在其剩余部分执行的进程section 可以参与决定下一个进入它的critical section，这个选择不能无限期推迟。
和
2) 有界等待是：在一个进程发出请求后允许其他进程进入其临界区的次数存在界限或限制进入它的关键部分并在该请求被授予之前。
我不明白作者在这两种情况下想表达的意思。
能否请您举一个与此定义相关的适当示例让我理解。
谢谢。
首先，让我介绍一些术语。 临界区 (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 和休假部分。但是，其他三个部分并不排斥。
第一个条件是进度。这个条件的目的是确保某个进程当前在 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。但是谁来做这个决定呢？那些已经请求允许进入其关键部分的进程有权参与做出此决定。此外，那些 可能 希望进入其 CSs 但尚未请求这样做的权限的进程（这意味着它们正在执行第一部分）有权参与做出此决定。
and this selection cannot be postponed indefinitely.
这说明 select 进程进入其 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 时，必须 selected 才能进入 CS，它可能是也可能不是 P。假设 P 以外的进程被 selected。这种情况可能会一再发生。也就是说，其他进程有机会进入它们的 CSs 但永远不会进入 P。请注意，正在取得进展，但是由其他进程而不是 P 取得的。问题是 P 没有机会做任何事情工作。为了防止饥饿，必须保证 P 最终会进入其 CS。为此，必须限制其他进程进入 CSs 的次数。这样的话，P肯定有机会进入它的CS
我想提一下，CS 的定义可以概括为最多 N 个进程在它们的临界区中执行，其中 N 是任何正整数。还有 reader-writer 临界区的变体。
总的来说，临界区问题的解决方案必须满足三个条件：
Mutual Exclusion：每个进程对共享内存的独占访问。在任何给定时间只能有一个进程位于其临界区。
Progress：如果没有进程在其临界区，并且如果一个或多个线程想要执行它们的临界区，则这些线程中的任何一个必须被允许进入它的临界区。
Bounded Waiting: 当一个进程请求进入其临界区后，其他进程进入临界区的数量是有限制的部分，在此过程的请求被授予之前。因此在达到限制后，系统必须授予进程进入其临界区的权限。此条件的目的是确保每个进程都有机会真正进入其临界区，以便没有进程永远饿死。
互斥
在任何时间点，临界区内不能同时存在两个进程，任何时间点只能有一个进程进入临界区。
进度图片：
进度
临界区外的任何进程 运行 都不应阻止其他感兴趣的进程进入临界区，而实际上临界区是空闲的。
在此图像中，P1（在临界区之外 运行）阻止 P2 进入实际上临界区是空闲的临界区。
有界等待
任何进程都不应永远等待才能进入临界区。
获得进入关键部分的机会应该有一个界限。
如果有界等待不满足则有可能饿死。
备注
没有假设与 H/W 或处理速度有关。
判断同步解决方案正确与否的要求
1).互斥：-在任何时候，临界区内只应存在一个进程。
2).进度：- 处于临界区之外且不想进入临界区的进程，则此类进程不应阻止其他感兴趣的进程进入其临界区。如果一个进程成功停止其他感兴趣的进程，则不能保证进度，否则就可以保证。关键部分应该是免费的。
3).有界等待：-临界区外进程的等待时间应该是有限的。
4).架构中立：-没有关于硬件的假设
(简单的定义)
有界等待 :- 当每次只有一个进程轮到进入临界区时，确实其他进程也有兴趣进入临界区。
我正在阅读 Peter B. Galvin 的《操作系统概念中的临界区问题》。 根据它
1) Progress is : 如果没有进程在其临界区中执行并且某些进程希望进入其临界区，则只有那些未在其剩余部分执行的进程section 可以参与决定下一个进入它的critical section，这个选择不能无限期推迟。
和
2) 有界等待是：在一个进程发出请求后允许其他进程进入其临界区的次数存在界限或限制进入它的关键部分并在该请求被授予之前。
我不明白作者在这两种情况下想表达的意思。
能否请您举一个与此定义相关的适当示例让我理解。
谢谢。
首先，让我介绍一些术语。 临界区 (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 和休假部分。但是，其他三个部分并不排斥。
第一个条件是进度。这个条件的目的是确保某个进程当前在 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。但是谁来做这个决定呢？那些已经请求允许进入其关键部分的进程有权参与做出此决定。此外，那些 可能 希望进入其 CSs 但尚未请求这样做的权限的进程（这意味着它们正在执行第一部分）有权参与做出此决定。
and this selection cannot be postponed indefinitely.
这说明 select 进程进入其 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 时，必须 selected 才能进入 CS，它可能是也可能不是 P。假设 P 以外的进程被 selected。这种情况可能会一再发生。也就是说，其他进程有机会进入它们的 CSs 但永远不会进入 P。请注意，正在取得进展，但是由其他进程而不是 P 取得的。问题是 P 没有机会做任何事情工作。为了防止饥饿，必须保证 P 最终会进入其 CS。为此，必须限制其他进程进入 CSs 的次数。这样的话，P肯定有机会进入它的CS
我想提一下，CS 的定义可以概括为最多 N 个进程在它们的临界区中执行，其中 N 是任何正整数。还有 reader-writer 临界区的变体。
总的来说，临界区问题的解决方案必须满足三个条件：
Mutual Exclusion：每个进程对共享内存的独占访问。在任何给定时间只能有一个进程位于其临界区。
Progress：如果没有进程在其临界区，并且如果一个或多个线程想要执行它们的临界区，则这些线程中的任何一个必须被允许进入它的临界区。
Bounded Waiting: 当一个进程请求进入其临界区后，其他进程进入临界区的数量是有限制的部分，在此过程的请求被授予之前。因此在达到限制后，系统必须授予进程进入其临界区的权限。此条件的目的是确保每个进程都有机会真正进入其临界区，以便没有进程永远饿死。
互斥
在任何时间点，临界区内不能同时存在两个进程，任何时间点只能有一个进程进入临界区。
进度图片：
进度
临界区外的任何进程 运行 都不应阻止其他感兴趣的进程进入临界区，而实际上临界区是空闲的。 在此图像中，P1（在临界区之外 运行）阻止 P2 进入实际上临界区是空闲的临界区。
有界等待
任何进程都不应永远等待才能进入临界区。 获得进入关键部分的机会应该有一个界限。 如果有界等待不满足则有可能饿死。
备注
没有假设与 H/W 或处理速度有关。
判断同步解决方案正确与否的要求
1).互斥：-在任何时候，临界区内只应存在一个进程。
2).进度：- 处于临界区之外且不想进入临界区的进程，则此类进程不应阻止其他感兴趣的进程进入其临界区。如果一个进程成功停止其他感兴趣的进程，则不能保证进度，否则就可以保证。关键部分应该是免费的。
3).有界等待：-临界区外进程的等待时间应该是有限的。
4).架构中立：-没有关于硬件的假设
(简单的定义)
有界等待 :- 当每次只有一个进程轮到进入临界区时，确实其他进程也有兴趣进入临界区。