最近最少使用 (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 能夠適應不斷變化的訪問模式。頁面驅逐中也使用了隨機化，以分散驅逐負載並避免可預測性。