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

问题：页面错误何时发生？解释各种页面置换策略/算法。

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

各种页面置换策略/算法

1. 最佳页面置换算法 − 该算法替换最长时间内不会被使用的页面。页面错误发生时，内存中会有一组页面。其中一个页面将在下一条指令中被引用。其他页面可能要到 10、100 或甚至 1000 条指令后才会被引用。此信息可以与 PMT（页面映射表）中的每个页面一起存储。

   P#	基地址	偏移量	其他信息
   1			10
   2			空
   3			1000
   ...
   10			100

   最佳页面算法简单地删除指令数最多的页面，这意味着它将在最远的将来被需要。该算法很久以前就被提出，并且难以实现，因为它需要对程序行为的未来知识。但是，可以通过使用在第一次运行时收集的页面引用信息，在第二次运行时实现最佳页面替换。

2. NRU（最近未使用）页面置换算法 - 该算法要求每个页面有两个额外的状态位 'R' 和 'M'，分别称为引用位和修改位。每当引用页面时，引用位 (R) 会自动设置为 1。每当修改页面时，修改位 (M) 会设置为 1。这些位存储在 PMT 中，并在每次内存引用时更新。当发生页面错误时，内存管理器会检查所有页面，并根据 R 和 M 位将它们划分为 4 类。

   • 类 1：(0,0) − 最近未使用且未修改 - 最佳替换页面。

   • 类 2：(0,1) − 最近未使用但已修改 - 替换前需要将页面写出。

   • 类 3：(1,0) − 最近使用但干净 - 可能很快会被再次使用。

   • 类 4：(1,1) − 最近使用且已修改 - 可能很快会被再次使用，并且替换前需要写出。

   该算法从编号最低的非空类中随机删除一个页面。

   优点

   • 易于理解。

   • 易于实现。

3. 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。

4. LRU（最近最少使用）算法 − 最近最少使用 (LRU) 算法替换最长时间未使用过的页面。它基于这样的观察结果：长时间未使用过的页面可能在最长时间内保持未使用，并且应该被替换。

   

   最初，3 个页面帧是空的。前 3 次引用（7、0、1）导致页面错误，并被带入这些空闲帧。下一次引用（2）替换页面 7。由于下一次页面引用（0）已经在内存中，因此没有页面错误。现在，对于下一次引用（3），LRU 替换发现，在内存中的三个帧中，页面 1 最近最少使用，因此被替换。依此类推。

   优点

   • LRU 页面置换算法非常有效。

   • 它不受 Belady 异常的影响。

   缺点

   • 它的实现并不容易。

   • 它的实现可能需要大量的硬件辅助。