什么是关键部分的进展和有限等待？

Question

我正在阅读Peter B. Galvin的"操作系统概念中的关键部分问题".根据它

1)进度是:如果没有进程在其关键部分执行,并且某些进程希望进入其关键部分,那么只有那些未在其余部分中执行的进程才能参与决定哪个进程将在下一个进入其关键部分,选择不能无限期推迟.

和

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和休假部分.但是,其他三个部分并不是唯一的.

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

进度:如果在其关键部分没有执行任何进程,并且某些进程希望进入其关键部分,那么只有那些未在其余部分中执行的进程才能参与决定哪个进程接下来将进入其关键部分,并且此选择不能是无限期推迟.

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

如果在其关键部分中没有执行任何进程

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

一些流程希望进入他们的关键部分

如果没有进程想要进入他们的关键部分,那么就没有更多的工作要做了.否则,如果至少有一个进程希望进入其关键部分......

那么只有那些没有在其余部分执行的进程

这意味着我们正在讨论在前两个部分中执行的那些进程(请记住,没有进程在其关键部分或离开部分执行)...

可以参与决定哪个会进入下一个关键部分,

由于至少有一个进程希望进入其CS,因此我们必须选择其中一个进入其CS.但是谁会做出这个决定呢？已经请求获得进入其关键部分许可的流程有权参与做出此决定.此外,那些可能希望进入其CS但尚未请求许可的进程(这意味着它们在第一部分中执行)也有权参与做出此决定.

而这个选择不能无限期推迟.

这表明选择进入其CS的流程将花费有限的时间.特别是,不会发生死锁或活锁.因此,在这个有限的时间之后,一个过程将进入其CS并做一些工作,从而取得进展.

现在我将解释最后一个条件,即有限等待.这个条件的目的是确保每个进程都有机会实际进入其临界区,这样任何进程都不会永远饿死.但请注意,这种情况和进展都不能保证公平.CS的实施不一定是公平的.

有界等待:在进程请求进入其临界区并且在该请求被授予之前,允许其他进程进入其关键部分的次数存在约束或限制.

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

在一个进程请求进入其关键部分之后并且在该请求被授予之前.

换句话说,如果有一个进程已请求进入其CS但尚未进入该进程.我们称这个过程为P.

允许其他进程进入其关键部分的次数存在限制或限制

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

我想提一下CS的定义可以推广,以便最多N个进程在其关键部分执行,其中N是任何正整数.还有读写器关键部分的变体.

Answer 2

相互排斥

在任何时间点,临界区内不能同时存在两个过程,在任何时间点只有一个过程可以进入临界区.

进展图片:

进展

在临界区之外运行的任何进程都不应阻止其他感兴趣的进程进入其临界区,而实际上临界区是免费的.

有限的等待

任何流程都不应该永远等待进入关键部分.在获得进入关键部分的机会方面应该存在边界.如果不满足有限等待,那么就有可能出现饥饿.

注意
没有假设与H/W或处理速度有关.

Answer 3

总的来说，临界区问题的解决方案必须满足三个条件：

1. 互斥：每个进程对共享内存的独占访问。在任何给定时间，只有一个进程可以处于其临界区。

2. 进度：如果没有进程处于其临界区，并且一个或多个线程想要执行其临界区，则必须允许这些线程中的任何一个进入其临界区。

3. 有界等待：在进程请求进入其临界区后，在该进程的请求被批准之前，有多少其他进程可以进入其临界区。因此，在达到限制后，系统必须授予进程进入其临界区的权限。此条件的目的是确保每个进程都有机会真正进入其临界区，以便没有进程永远处于饥饿状态。