Belady的页面替换算法异常

先决条件–

页面替换算法

在操作系统中, 过程数据以固定大小的块加载, 每个块称为页面。处理器将这些页面加载到固定大小的称为帧的内存块中。通常, 每页的大小始终等于框架大小。

当在内存中找不到页面并且需要从磁盘加载页面时, 就会发生页面错误。如果发生页面故障并且已经分配了所有内存帧, 则需要在新页面的请求下更换内存中的页面。这称为需求分页。由页面替换算法指定要替换哪个页面的选择。常用的页面替换算法是FIFO, LRU, 最佳页面替换算法等。

通常, 随着增加进程虚拟内存的帧数, 页面错误发生的次数就会减少, 其执行速度也会更快。有时会发生相反的情况, 即, 当更多帧分配给一个进程时, 会发生更多的页面错误。这个最出乎意料的结果称为Belady的异常.

Belady的异常是一种现象的名称, 其中对于给定的内存访问模式, 增加页面帧数会导致页面错误数增加。

在以下页面替换算法中通常会遇到这种现象：

1. 先进先出(FIFO)
2. 二次机会算法
3. 随机页面替换算法

Belady异常的原因-

其他两种常用的页面替换算法是Optimal和LRU, 但是Belady的Anamoly永远不会出现在这些参考字符串的算法中, 因为它们属于基于堆栈的页面替换算法。

一种基于堆栈的算法是一个可以证明内存中的页面集的对象ñ框架始终是内存中的页面集的子集N + 1框架。对于LRU更换, 内存中的页面集将是ñ最近引用的页面。如果帧数增加, 则这些ñ页面仍将是最近引用的页面, 因此仍将保留在内存中。在FIFO中时, 如果页面名为b在进入页面之前进入物理内存–一种然后优先更换b大于一种, 但这并不取决于页面帧的数量, 因此, FIFO不遵循堆栈页面替换策略, 因此会遭受Belady的异常。

例子：考虑下图以了解基于堆栈的页面替换算法的行为

该图说明, 给定页面集(即3帧内存中的{0, 1, 2})不是内存中页面的子集– {0, 1, 4, 5}具有4帧, 这在内存中是违反的基于堆栈的算法的属性。这种情况在FIFO算法中很常见。

Belady的FIFO异常-

假设系统没有将页面加载到内存中, 并且使用FIFO页面替换算法。考虑以下参考字符串：

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

情况1：如果系统有3帧, 则使用FIFO页面替换算法的给定参考字符串将产生总共9个页面错误。下图说明了示例中发生的页面错误的模式。

情况2：如果系统有4帧, 则使用FIFO页面替换算法的给定参考字符串将产生总共10个页面错误。下图说明了示例中发生的页面错误的模式。

从上面的示例可以看出, 在使用FIFO页面替换算法时增加帧数时, 页面错误增加从9到10。

注意 -不必每个字符串引用模式都导致FIFO中Belady异常, 但是某些类型的字符串引用会在增加帧数时恶化FIFO性能。

为什么基于堆栈的算法不会出现异常现象–

所有基于堆栈的算法都不会遭受Belady Anomaly的困扰, 因为这些类型的算法为页面(用于替换)分配的优先级与页面帧数无关。此类策略的示例为Optimal, LRU和LFU。另外, 这些算法还具有用于仿真的良好特性, 即, 可以通过单次通过参考字符串来计算任意数量的页面帧的未命中率。

在LRU算法中, 每次引用页面时, 页面都会移到堆栈的顶部, 因此, 顶部ñ堆栈的页面是ñ最近使用的页面。即使帧数增加到n + 1, 堆栈顶部将有n + 1最近使用过的页面。

在LRU算法中, 可以使用类似的示例来计算页面错误的数量。假设系统没有在内存中加载任何页面, 并且使用LRU页面替换算法。考虑以下参考字符串：

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

情况1：如果系统有3帧, 则使用LRU页面替换算法时给定的参考字符串将产生总共10个页面错误。下图说明了示例中发生的页面错误的模式。

情况2：如果系统有4帧, 则使用LRU页面替换算法的给定参考字符串, 则总共发生8个页面错误。该图显示了示例中的页面错误模式。

结论–

各种因素会严重影响页面错误的数量, 例如参考字符串长度和可用的空闲页面框架的数量。由于较小的高速缓存大小以及高速缓存内容的鲁ck变化率, 也会发生异常。同样, 即使在增加帧数之后, 固定页面错误数的情况也可以视为异常。经常喜欢的算法

随机页面替换算法

也容易受到Belady异常的影响, 因为

表现得像先进先出(FIFO)

页面替换算法。但是基于堆栈的算法通常不受所有此类情况的影响, 因为当帧增加时, 可以保证它们提供更好的页面命中率。

GATE CS Corner问题–

练习以下问题将帮助你测试知识。在前几年的GATE或GATE模拟测试中, 所有问题都已提出。强烈建议你练习它们。

1. GATE-CS-2001 |问题21
2. GATE-CS-2009 |问题8
3. ISRO CS 2011 |第73章
4. GATE-CS-2016(Set 2)|问题30
5. ISRO CS 2016 |第48章
6. GATE CS Mock 2018年|第63章

---