页面置换算法

在虚拟内存管理中，当作业运行时，访问的页面可能不在主存中。此时，需要将该页面从外存（如磁盘）加载到主存中。如果主存已满，系统需要选择一个已在内存中的页面将其调出，以为新页面腾出空间。这一过程称为“页面置换”。选择要被替换的页面的算法就是页面置换算法。

抖动现象

抖动（或称颠簸）指的是当页面在主存和外存之间频繁地交换，导致系统大部分时间都花费在页面调度上，而实际的计算工作非常少，系统性能急剧下降。这通常是因为页面置换算法不够高效，或者分配的内存不合理。

一个好的页面置换算法应该尽量减少抖动现象，确保页面调度次数较少，系统运行流畅。

页面走向是指程序运行时访问的页面的顺序。在分析页面置换时，我们通常仅关心页面的访问顺序，而不关注具体的内存地址。通过简化页面的走向，可以帮助评估页面置换算法的效率。

示例：

假设一个程序的地址序列是：

0100, 0432, 0101, 0612, 0102, 0103, 0104, 
0101, 0611, 0102, 0103, 0104, 0101, 0610, 
0102, 0103, 0104, 0101, 0609, 0102, 0105

假设每页大小为100字节，那么页面走向可以简化为

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

如何实现？

为了简化页面走向，首先需要根据给定的地址序列和页面大小，将每个地址转换为对应的页面号。假设每页大小为100字节，地址序列给定的是以字节为单位的地址值。接下来，通过对每个地址进行“除以100”（也就是取页号），就可以得到对应的页面号。页面走向就是这些页面号的序列。

地址序列：

0100, 0432, 0101, 0612, 0102, 0103, 0104, 
0101, 0611, 0102, 0103, 0104, 0101, 0610, 
0102, 0103, 0104, 0101, 0609, 0102, 0105

步骤 1：计算每个地址的页面号

我们知道每页大小是100字节。因此，可以通过将每个地址除以100来确定其页面号。每次访问某个地址时，我们只关心其页号，不关心具体的地址。

步骤 2：简化页面走向

将每个地址对应的页面号列出并简化重复访问的页面。连续访问同一个页面时，我们只保留第一次访问。

根据以上计算，原始页面号序列为：

1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1

去掉重复的访问后，简化后的页面走向序列为：

1, 4, 6, 1, 6, 1, 6, 1

这意味着页面访问序列中，页面 1 和 6 经常被访问，而页面 4 和 7 只在某些特定时刻出现。

最佳页面置换算法是理想化的算法，它假设可以预知未来的页面访问情况。根据这个算法，当需要替换页面时，应选择在未来最久未被访问的页面进行替换。

FIFO（First-In-First-Out）是最简单的页面置换算法。它假设最先进入主存的页面最不可能在未来被访问，因此选择最早进入内存的页面进行替换。

LRU（Least Recently Used）页面置换算法选择最近一段时间内最久未被访问的页面进行替换。

时钟页面置换算法是LRU的一种近似算法。它使用一个环形队列和一个指针（时钟指针）来模拟最近最少使用的情况，避免了LRU算法的复杂性。

实现：为每个页面增加一个引用位，指针指向当前页面。当页面被访问时，引用位置为1；当发生缺页中断时，指针逐一检查页面，如果某页面的引用位为0，则淘汰该页面；如果引用位为1，则将引用位清零，并移动指针继续检查下一个页面。
优点：实现较为简单，效率高。
缺点：可能无法完美模拟LRU的行为。

LFU（Least Frequently Used）页面置换算法选择在过去一段时间内访问次数最少的页面进行替换。

缺页中断率（Page Fault Rate）是衡量页面置换算法效率的一个重要指标。它表示在一定时间内，发生缺页中断的次数占总访问次数的比例。优化页面置换算法的目标之一就是减少缺页中断率。

影响缺页中断率的因素：

缺页中断率公式：

\[ f = \frac{F}{A} \]

其中：