操作系统内存分配问答 #3

问题: 页面错误何时发生? 解释各种页面替换策略/算法。

答案: 在按需分页内存管理技术中，如果需要执行的页面在主内存中不存在，则发生页面错误。为了将需要的页面加载到主内存中，在主内存中搜索并分配一个空闲页框。如果没有空闲的页框，内存管理器必须通过将其内容交换到辅助存储器来释放一个框，从而为所需的页腾出空间。为了交换页面，使用了许多方案或策略。

各种页面置换策略/算法

最优页面替换算法 − 该算法替换最长时间不使用的页面。页面错误发生的那一刻，一些页面集在内存中。这些页面中的一个将在下一条指令中引用。直到 10,100 条或可能 1000 条指令才能引用其他页面。该信息可以与每个页面一起存储在 PMT（页面映射表）中。

P# base Offset MISC
1 10

2 NIL

3 1000

...

10 100

最优页面算法只是删除具有最多此类指令的页面，这意味着在最遥远的将来将需要它。该算法是很久以前引入的，并且难以实现，因为它需要将来了解程序行为。但是，通过使用第一次运行时收集的页面参考信息，可以在第二次运行时实现最佳页面替换。
NRU（最近未使用）页面替换算法 - 该算法要求每个页面有两个额外的状态位'R'和'M'，分别称为参考位和更改位。每当引用页面时，引用位 (R) 自动设置为 1。每当页面被修改时，更改位 (M) 设置为 1。这些位存储在 PMT 中，并在每次内存引用时更新。当发生页面错误时，内存管理器会检查所有页面并根据 R 和 M 位将它们分为 4 类。
- Class 1: (0,0) − 既没有最近使用也没有修改 - 最好的替换页面。
- Class 2: (0,1) − 最近未使用但已修改 - 页面需要在替换前写出。
- Class 3: (1,0) − 最近使用过但很干净 - 可能很快会再次使用。
- Class 4: (1,1) − 最近使用和修改 - 可能会再次使用，并且在替换之前需要写出来。
此算法从编号最小的非空类中随机删除一个页面。

优点:
- 很容易理解。
- 实施起来很高效。
FIFO（先进先出）页面替换算法 − 它是最简单的页面替换算法之一。选择并替换在内存中花费时间最长的最旧页面。该算法是在 FIFO 队列的帮助下实现的，以将页面保存在内存中。一个页面被插入到队列的后端，并在队列的前端被替换。

图中，参考字符串为 5, 4, 3, 2, 5, 4, 6, 5, 4, 3, 2, 6 有 3 帧为空。前 3 个引用 (5, 4, 3) 导致页面错误并被带入空帧。下一个引用 (2) 替换了第 5 页，因为第 5 页首先加载，依此类推。在 7 次页面错误之后，下一个引用是 5 并且 5 已经在内存中，所以这个引用没有页面错误。下一个参考 4 类似。+ 标记显示页面的传入，而圆圈显示选择要删除的页面。

优势
- FIFO 很容易理解。
- 很容易实现。
缺点
- 并不总是表现出色。它可能会替换一个活动页面以带来一个新页面，因此可能会立即导致该页面的页面错误。
- 另一个意想不到的副作用是 FIFO 异常或 Belady 异常。这个异常表示页面错误率可能会随着分配的页框数量的增加而增加。
例如下图显示了相同的页面跟踪，但内存更大。这里的页框数是 4。

这里的页面错误是 10 而不是 9。
LRU（最近最少使用）算法 − 最近最少使用 (LRU) 算法替换最长时间未使用的页面。它基于这样的观察，即长时间未使用的页面可能会在最长时间内保持未使用状态并被替换。

最初，3 个页框是空的。前 3 个引用 (7, 0, 1) 导致页面错误并被带入这些空帧。下一个引用 (2) 替换了第 7 页。由于下一个页面引用 (0) 已经在内存中，因此没有页面错误。现在，对于下一个引用 (3)，LRU 替换看到，在内存中的三个帧中，第 1 页最近最少使用，因此被替换。因此，该过程继续进行。

优势
- LRU 页面替换算法安静高效。
- 它没有受到贝拉迪异常的影响。
缺点
- 它的实现并不容易。
- 其实施可能需要大量硬件协助。