最近最少使用 (NRU) 页面置换算法

---

操作系统使用最近最少使用 (NRU) 页面置换算法作为基本的页面置换策略来管理内存。其主要目标是找到并移除内存中长时间未被访问的页面。

在本文中，我们将讨论 NRU 页面置换算法，其中的类别，涉及的步骤，用例以及它的优点。

NRU 算法的类别

基于其使用情况或引用位，NRU 算法将页面分为四类：

0 类 - 自加载到内存以来，页面既未被引用（访问）也未被修改（写入）。

1 类 - 加载到内存后被修改过，但未被引用的页面。

2 类 - 被引用但未被修改的页面。

3 类 - 被修改并被引用的页面。

NRU 方法通常使用时钟或计时器设备定期重置每个页面的引用位。该方法在每次时钟滴答或计时器中断时，都会分析内存中的每个页面，然后选择一个页面进行驱逐，并根据其引用位和修改位对每个页面进行分类。

在 NRU 中，选择过程包括查找编号最低的非空类，并从该类中随机驱逐一个页面。该方法通过选择编号最低的类来优先驱逐最近未被使用的页面，从而增加驱逐不太重要或不太常用页面的可能性。

当由于实现限制（尤其是在资源有限的系统中）而难以使用更复杂的算法（如最近最少使用 (LRU)）时，NRU 是一种相当简单有效的页面置换机制。需要注意的是，NRU 不考虑页面的引用次数，其随机驱逐策略可能并不总是产生最佳性能。

NRU 算法的步骤

以下步骤构成了 NRU（最近最少使用）页面置换机制的工作原理：

• 内存中的每个页面都分配一个引用位 (R) 和一个修改位 (M)。通常，每个页面的页表条目都包含这些位。

• 算法定期或响应特定事件（例如时钟滴答或计时器中断）启动 NRU 选择过程。

• 根据它们的 R 位和 M 位，算法将内存中的所有页面分为以下四类：

  0 类 - 页面的 R 位和 M 位都为 0。

  1 类 - 页面的 R 位为 0，M 位为 1。

  2 类 - 页面的 R 位为 1，M 位为 0。

  3 类 - 页面的 R 位和 M 位都为 1。

• 页面分类后，算法选择一个页面进行驱逐。它首先查找编号最低的非空类。如果有多个类包含页面，算法会优先选择编号较小的类。例如，如果 0 类和 1 类都包含页面，则会选择 0 类。

• 程序从指定的类中随机选择一个页面进行驱逐。这可以通过迭代该类中的所有页面并随机选择一个页面来完成，也可以使用随机数生成器来完成。

• 如果需要，可以选择页面从内存中移除后，可以加载替换页面。对相关的页表条目进行相应的修改。

• 最后，为了准备下一次选择周期，内存中所有剩余页面的引用位 (R) 被清除（设置为 0）。

NRU 通过定期扫描和驱逐尚未使用的页面（即引用位为 0 的页面）来尝试删除不太可能在近期内被需要的页面。NRU 没有考虑页面引用的频率，这在某些情况下可能导致性能不理想。

以下是 NRU 算法的流程图：

NRU 页面置换算法的用例

让我们探讨一下操作系统中非连续分配的一些用例。

• 可变大小的进程 - 在处理大小不同的进程时，非连续分配特别有用。它允许内存分散在多个区域中，从而实现对可用内存的有效利用。

• 动态内存管理 - 非连续分配允许动态内存管理，允许根据进程的启动或终止来分配和释放内存。这种灵活性在进程的内存需求不断变化的环境中至关重要。

• 有效的内存利用率 - 非连续分配通过根据进程的实际需求分配内存块来确保有效的内存利用率。它通过仅为每个进程分配必要的内存量来防止浪费内存。

• 碎片管理 - 虽然非连续分配可能会增加外部碎片，但它有助于减少内部碎片。内部碎片是指已分配的内存块中存在空闲或部分利用的空间。通过根据进程的特定需求分配内存块，可以最大限度地减少内部碎片。

• 处理大型数据集 - 在处理无法放入单个连续内存块的大型数据集时，非连续分配非常有用。能够在多个非连续块中分配内存，允许进程处理大量数据而不会耗尽可用的内存资源。

• 虚拟内存系统 - 非连续分配是虚拟内存系统中使用的基本技术。它允许操作系统以灵活的方式将逻辑地址映射到物理地址，从而使进程能够以非连续的方式访问内存。

• 多编程环境 - 在多个进程同时运行的多编程环境中，非连续分配有助于有效地将内存块分配给不同的进程。可以根据每个进程的特定需求分配内存，从而实现最佳内存使用率。

• 实时系统 - 非连续分配在具有严格时间要求的实时系统中可能很有用。它允许动态分配和释放内存，使进程能够在满足严格的时间约束的同时有效地管理其内存资源。

  通过使用非连续分配，操作系统可以满足进程的多样化内存需求，提高内存利用率，并提供处理不同工作负载和数据大小所需的灵活性。

NRU 页面置换算法的优点

在某些情况下，NRU（最近最少使用）页面置换机制具有一些优点。以下是 NRU 算法的一些优点：

简单性 - NRU 是一种相对易于实现的页面置换方法。例如，NRU 的简单性可能有助于嵌入式系统或具有内存限制的旧硬件。

优先驱逐很少访问的页面 - NRU 优先驱逐很少访问的页面。在一个特定应用程序或数据集使用频率低但需要大量内存的系统上，NRU 可以帮助确保首先移除不太常用的页面，从而为更活跃使用的页面腾出空间。

快速适应不断变化的访问模式 - NRU 提供了一种简单的方法来快速适应不断变化的访问模式。这使得算法能够（尽管粗略地）根据最新的访问模式来调整其驱逐决策。

随机驱逐 - NRU 使用随机选择技术来选择要从每个类中驱逐的页面。此外，它可以使驱逐更不可预测，从而使恶意软件更难以利用特定的驱逐模式。

结论

最近最少使用 (NRU) 页面置换技术简单直接，开销小，并允许优先驱逐很少使用的页面。它是一种简单的算法，适用于资源有限的系统或更复杂的算法不切实际的情况。通过定期重置引用位，NRU 能够适应不断变化的访问模式。页面驱逐中也使用了随机化，以分散驱逐负载并避免可预测性。