操作系统中的 Belady 异常

Belady 异常在页面置换算法中的应用

在 LRU 和最优页面置换算法的情况下，可以看到增加帧的数量会减少缺页中断的次数。然而，Balady 发现，在 FIFO 页面置换算法中，增加帧的数量会导致缺页中断次数的增加。

这是 FIFO 算法在某些情况下表现出的奇怪行为。这种异常被称为 Belady 异常。

Belady 异常是一种在操作系统中发生的现象，其中增加内存中的页面帧数量会导致某些页面置换算法的缺页中断次数增加。通常情况下，随着页面帧数量的增加，操作系统可以更灵活地将必要的页面保留在内存中，这应该会减少缺页中断的次数。

这种现象在以下页面置换算法中很常见：

• 先进先出（FIFO）
• 二度机会算法
• 随机页面置换算法

当页面不在内存中，需要从磁盘加载时，就会发生页面错误。如果发生页面错误，并且所有内存帧都已被分配，那么在请求新页面时就需要替换内存中的页面。这被称为请求分页。选择替换哪个页面由页面置换算法指定。常用的页面置换算法有 FIFO、LRU、最优页面置换算法等。

什么是页面错误？

页面错误是一种在计算机操作系统中发生的中断或异常，当程序尝试访问物理 RAM（随机存取存储器）中当前未加载的内存页面时发生。相反，该页面存储在磁盘上的称为页面文件或交换空间的位置。

通常，在为进程的虚拟内存增加帧数时，由于缺页中断次数减少，其执行速度会加快。有时反之亦然，即为进程分配更多帧时会发生更多缺页中断。这种最出乎意料的结果被称为Belady 异常。

Belady 异常的原因

Belady 异常发生是因为像 FIFO 这样的算法根据页面的到达顺序替换页面，而不考虑它们将被使用多久或多久。增加更多帧会改变替换顺序，导致频繁使用的页面被提前淘汰，从而增加缺页中断。这是由于缺乏对未来页面引用的了解以及此类算法的非最优性。

像 Optimal 和 LRU（最近最少使用）这样的算法可以避免 Belady 异常，因为：

它们会考虑页面未来的或过去的用法。

它们使用基于堆栈的结构，确保在较小帧设置中的页面也存在于较大的设置中，从而避免异常。

另外两个常用的页面置换算法是 Optimal 和 LRU，但在任何引用字符串上，Belady 异常都不会发生在这些算法中，因为它们属于一类基于堆栈的页面置换算法。

堆栈式算法是指可以证明在拥有 N 帧的情况下内存中的页面集合始终是拥有 N + 1 帧的情况下内存中的页面集合的子集。对于 LRU 置换，内存中的页面集合将是最近引用的 n 个页面。如果帧的数量增加，那么这 n 个页面仍然是最近引用的页面，因此仍然在内存中。而在 FIFO 中，如果一个名为 b 的页面比页面 a 先进入物理内存，那么 b 的替换优先级就比 a 高，但这与页面帧的数量无关，因此 FIFO 不遵循堆栈页面置换策略，因此会发生 Belady 异常。

使用基于堆栈的页面置换算法的一个重要好处是它们可以防止 Belady 异常，即增加页面帧数导致缺页中断次数增加的现象。这些算法固有的设计和工作逻辑使它们能够抵抗这种异常。

优先考虑最近使用的页面

最近最少使用 (LRU) 和其他基于堆栈的算法通过维护一个页面堆栈来跟踪页面的访问顺序。最近访问的页面被推到堆栈顶部，而访问频率较低的页面则向下移动。为了将最有可能再次使用的页面保留在内存中，当需要替换页面时，算法会选择堆栈底部的页面。无论有多少可用帧，这种方法都会自动降低缺页中断的可能性。

一致的替换策略

这些算法以独立于页面帧数量的一致方式替换页面。无论系统有多少帧，算法总是优先保留最近使用的页面。这种一致性有助于避免 Belady 异常，方法是确保随着更多帧的可用，缺页中断的数量不会突然增加。

利用时间局部性

基于堆栈的算法利用了时间局部性原理，该原理认为最近访问过的页面很可能很快会再次被访问。这些算法之所以能免疫 Belady 异常，部分原因在于它们通过保持这些页面的可访问性来最大程度地减少了缺页中断的可能性。

不依赖于帧分配

与可能根据分配的帧数采取不同行动的其他算法不同，基于堆栈的算法在做出决策时仅考虑页面访问历史。它们还通过独立于帧分配来避免产生 Belady 异常的情况。

示例：考虑以下图表来理解基于堆栈的页面置换算法的行为

该图说明了在内存的 3 个帧中页面集合 {0, 1, 2} 并不是在 4 个帧的内存中的页面集合 {0, 1, 4, 5} 的子集，这是堆栈式算法属性的违背。这种情况在 FIFO 算法中很常见。

让我们来分析一个这样的例子

引用的字符串是 0 1 5 3 0 1 4 0 1 5 3 4。让我们分析两种情况下 FIFO 算法的行为。

情况 1：帧数 = 3

缺页中断次数 = 9

情况 2：帧数 = 4

缺页中断次数 = 10

因此，在此示例中，通过增加帧数，缺页中断次数在增加，因此这会受到 Belady 异常的影响。

FIFO 中的 Belady 异常

在 FIFO 页面置换中，人们期望当我们增加帧数时，缺页中断次数会更少。但有时，即使在增加帧数后，缺页中断次数也增加了，“Belady 异常”就发生了。

如何消除 Belady 异常？

可以使用基于堆栈的方法来消除 Belady 异常。这些是此类算法的一些示例：

• 最优页面置换算法
• 最近最少使用算法 (LRU)

这些算法基于这样一个理念：如果一个页面长时间不活动，那么它就不经常被使用。因此，最好忘记这个页面。这可以改进内存管理并消除 Belady 异常。

Belady 异常的特点

缺页中断率：缺页中断率是在进程执行期间发生的缺页中断次数。当分配给进程的页面帧数量增加时，缺页中断率增加，就发生了 Belady 异常。

页面置换算法：先进先出 (FIFO) 和二度机会算法是两种特别受 Belady 异常影响的页面置换算法示例。

系统负载：当系统负载变化时，Belady 异常可能会显现。随着工作负载的页面引用量增加，它可能会发生。

页面帧分配：当为进程分配更多页面帧而系统总页面帧数保持不变时，可能会发生 Belady 异常。这是因为分配了更多页面帧的进程最初会经历更少的缺页中断，但是随着工作负载的增加，进程可能会更频繁地将其工作集中的页面淘汰，从而导致更多的缺页中断。

性能影响：由于 Belady 异常可能导致更多的缺页中断和较差的整体系统性能，因此它可能对系统性能产生重大影响。因此，为过程选择最佳页面帧数量也可能变得困难。

优点

• 对算法行为的更好洞察：Belady 异常可以洞察页面置换算法的工作原理以及它在不同场景下的行为。这有助于为特定用例设计和优化算法。
• 改进算法性能：在某些情况下，即使增加了分配给进程的帧数导致缺页中断次数增加，也可以提高算法性能。这是因为拥有更多帧可以减少页面替换的频率，从而提高整体性能。

缺点

Belady 异常可能导致不准确的性能和系统不稳定，这使得预测算法在不同帧和页面配置下的行为变得困难。

• 开销增加：为进程分配的页面帧数量的增加有时会导致更高的开销和资源消耗，从而可能损害系统性能。
• 直观行为：当进程获得更多帧时，如果缺页中断次数增加，Belady 异常可能会使用户和系统管理员感到困惑。
• 优化挑战：由于 Belady 异常，页面置换算法可能表现出不可预测和不一致的行为，使得针对特定用例进行优化变得困难。

常见问题

Q1. Belady 异常 为什么会发生？

当页面置换算法未能利用基于堆栈的属性时，就会发生 Belady 异常。即使页面不在主内存中，基于堆栈的属性也可以通过创建优先级列表轻松检索最常用的页面。当 FIFO 中先添加的页面首先被换出时，Belady 异常就会发生，因为它们将在内存中停留最长时间。

Q2. 如何解决 Belady 异常？

使用基于堆栈算法的算法可以消除 Belady 异常。基于堆栈的算法的特点之一是它为最常用的页面创建一个子集，并将它们视为堆栈的顶部。这些页面被放在优先级列表中，方便需要时进行检索。

Q3. 哪个页面置换算法的缺页中断率最低？

最优页面置换算法的缺页中断率最低。在这种情况下，长时间未使用的页面会被换出，以替换我们需要的页面。

Q4. 如何处理缺页中断？

操作系统内核可以管理缺页中断。它控制计算机硬件并查找错误的位置。