什么是临界区的进展和有界等待?

70
我正在阅读Peter B. Galvin的《操作系统概念》中的“临界区问题”章节。根据书中所述: 1)进展是指:如果没有任何进程在其临界区执行,同时一些进程希望进入其临界区,则只有那些没有在其余部分执行的进程可以参与决定下一个将进入其临界区的进程,并且这个选择不能无限期地推迟。 并且 2)有界等待是:存在一个上限,或者说限制,即当一个进程请求进入其临界区之后,在该请求被允许之前,其他进程被允许进入其临界区的次数是有限制的。
我不理解作者在这两种情况下想要表达什么意思。能否给我提供一个相关定义的恰当例子来帮助我理解?
谢谢。
5个回答

158

首先,让我介绍一些术语。临界区(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但还没有进入它。 让我们称这个进程为P。

在其他进程被允许进入其关键部分的次数上存在一个限制或限制。

当P等待进入其临界区时,其他进程也可能在等待,某些进程正在其临界区中执行。当它离开其临界区时,必须选择另一个进程进入临界区,这个进程可能是P,也可能不是P。假设选择了除P以外的进程。这种情况可能一次又一次地发生。也就是说,其他进程有机会进入其临界区,但从未是P。请注意,正在取得进展,但是由其他进程而非P完成。问题在于P没有获得任何工作机会。为防止饥饿,必须保证P最终将进入其临界区。为此,必须限制其他进程进入其临界区的次数。在这种情况下,P肯定会有机会进入其临界区。
我想提到,可以将临界区的定义概括为最多N个进程正在执行其临界区,其中N是任何正整数。还有读写器临界区的变体。

13
精彩的逐行解释 - Subomi
4
你很棒。解释得非常好! - void
3
如果没有饥饿现象,我们能否说我们有有界等待(bounded waiting)? - Radha Gogia
4
是的。一般而言,饥饿和无限等待是相同的概念。但是,某些特定的教科书或论文可能会对这些术语给出更精确的定义。 - Hadi Brais
1
你能回答这个问题吗?https://cs.stackexchange.com/questions/100269/should-every-process-in-the-system-have-same-bound-to-fulfill-bounded-waiting - Mr. Sigma.

31

互斥

任何时候都不能同时存在两个进程在临界区内,只有一个进程可以进入临界区。

进度

在临界区外运行的进程不应该阻塞其他感兴趣的进程进入临界区,当且仅当临界区空闲时,其他进程应能够进入临界区。在该图像中,P1(在临界区之外运行)正在阻塞P2进入临界区,而实际上临界区是空闲的。

有界等待

没有进程应该永远等待进入临界区,获取进入临界区的机会应该有一定的限制。如果无法满足有界等待,则可能会发生饥饿现象。

注意事项
没有与 H/W 或处理速度相关的假设。

Progress 的图像:

Progress


8

总的来说,解决关键段问题的方案必须满足三个条件:

  1. 互斥性:每个进程对共享内存的访问是互斥的。在任何时刻只能有一个进程处于其关键段。

  2. 进展性:如果没有进程处于其关键段,并且有一个或多个线程想要执行其关键段,则这些线程中的任何一个都必须被允许进入其关键段。

  3. 有界等待:在进程请求进入其关键段后,有一定数量的其他进程可以进入其关键段之前,该进程的请求将被授予。因此,在达到限制后,系统必须授予进程权限进入其关键段。这个条件的目的是确保每个进程都有机会进入其关键段,以便没有进程永远挨饿。


3

如何判断同步解决方案是否正确

1). 互斥性:在任意时间点,临界区域内只能有一个进程。

2). 进度:如果一个进程不想进入临界区域,则它不应该阻止其他进程进入其临界区域。如果一个进程成功地阻止了其他有兴趣的进程,则不能保证进度;否则,可以保证进度。临界区域应该是空闲的。

3). 有界等待:在临界区域外等待的进程应该有限制的等待时间。

4). 架构中立:不对硬件做任何假设。


0

(简单定义)

有界等待:每次只有一个进程获得进入临界区的机会,而其他进程也有兴趣进入临界区。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接