常見的頁面替換演算法

在多工作業系統中，當系統需要載入新的頁面到主記憶體（main memory）時，如果所有記憶體框架（frames）都已被佔用，就必須選擇一個現有的頁面將其換出，這個被選中的頁面稱為「受害者頁面」（victim page）。為了盡可能降低頁面置換的頻率，也就是減少 Page Fault 的發生，作業系統會採用不同的頁面替換演算法來決定哪個頁面應該被換出。

FIFO（First-In-First-Out，先進先出）

FIFO 演算法的概念非常直觀：最早被載入到記憶體中的頁面，也最先被替換。它使用一個佇列（Queue）結構來管理頁面的順序，隊伍頭的頁面是等待最久的，因此在發生 Page Fault 時，會優先被換出。

優點： 實作簡單，只需要記錄頁面進入記憶體的順序。
缺點：

• 沒有考慮頁面的實際使用頻率。即使是經常被存取的頁面，只要它進入記憶體的時間最早，也可能被淘汰。
• 可能產生 Belady's Anomaly（貝拉迪異常）：在某些情況下，增加可用的記憶體框架數量，反而會導致 Page Fault 次數增加。

範例：
Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Frame: 3
Page Fault 次數可能比 Frame=4 還低（違反直覺）。

OPT（Optimal Page Replacement，最佳演算法）

OPT 演算法是理論上的最佳選擇。它會檢視未來所有頁面的存取需求，然後選擇在未來最久不會被使用的頁面來替換。這種預測性的選擇策略可以確保 Page Fault 的發生次數達到理論上的最小值。

優點： 能夠達成最低的 Page Fault 率，常用於評估其他演算法的效能。
缺點： 由於需要「預知」未來的存取行為，在實際的作業系統中無法實現。

LRU（Least Recently Used，最久未使用）

LRU 演算法是 OPT 的一種實際近似。它基於時間局部性（Temporal Locality）原則：如果一個頁面在近期被頻繁使用，那麼在不久的將來也很可能再次被使用。因此，它會選擇最久沒有被使用過的頁面來替換。

優點： 表現良好，Page Fault 率接近理想值，能有效利用程式的局部性原則。
缺點： 實作複雜且開銷大，因為它需要額外的硬體或軟體來追蹤每個頁面的「最近使用時間」。常見的實作方式有：

• 計數器法（Counter）： 每個頁面都有一個計數器或時間戳記，每次存取時更新。替換時，選擇計數器值最小的頁面。
• 堆疊法（Stack）： 每次存取頁面時，將其從堆疊中移除並放到頂端，因此堆疊底部的頁面就是最久未使用的。

LRU Approximation

由於完整 LRU 的實作開銷過大，實務上常採用其近似演算法來取得效能與開銷的平衡。

1. 參考位元法 (Reference Bit)

這是一種最簡單的近似。每個頁面都有一個由硬體提供的參考位元（Reference Bit），當頁面被存取（讀或寫）時，硬體會自動將其設為 1。作業系統會定期將所有位元清為 0。

優點： 實作簡單，開銷小。
缺點： 只能判斷頁面是否被使用過，無法得知其具體的使用順序或時間間隔。

2. 額外參考位元演算法 (Additional-Reference-Bits Algorithm)

此方法在參考位元的基礎上加入了時間的概念。每個頁面除了參考位元，還配備一個 8 位元的暫存器。作業系統會定期（例如每 100 毫秒）執行以下動作：

• 將每個頁面的參考位元（第 8 位）左移並加到該頁面的暫存器中。
• 將該頁面的參考位元清為 0。

這樣一來，這個 8 位元暫存器會記錄頁面在過去一段時間內的使用頻率和時間序列。數值越小，代表該頁面越久沒有被使用，也就越適合被替換。

3. 二次機會演算法 (Second-Chance Algorithm, Clock Algorithm)

此演算法結合了 FIFO 的簡單性和參考位元的概念。它將所有頁面組織成一個環狀佇列，並使用一個指標（類似時鐘的指針）指向下一個要檢查的頁面。

• 當發生 Page Fault 時，指針從當前位置開始檢查頁面。
• 如果指針指向的頁面參考位元為 0，則該頁面被替換。
• 如果指針指向的頁面參考位元為 1，則給它「第二次機會」：將其參考位元清為 0，並將指針移到下一個頁面繼續檢查。

這種機制讓經常被使用的頁面有機會留在記憶體中，避免了 FIFO 的主要問題，同時又比完整 LRU 的實作成本低。

Frame Allocation（框架分配）

在虛擬記憶體系統中，框架（Frame）是實體記憶體的最小分配單位。一個程式的頁面（Page）必須載入到框架中才能被執行。當有多個程式競爭有限的框架資源時，作業系統需要採取一套策略來進行分配。

框架分配的考量因素

在分配框架給各個程式前，作業系統會先將部分框架保留給自己使用，以存放核心程式碼（kernel code）、系統資料結構以及 I/O 緩衝區等。剩餘的框架才會被分配給使用者程式。這個分配過程主要考量以下幾點：

1. 最小框架數量（Minimum Number of Frames）： 每個程式必須至少被分配一定數量的框架，才能保證其正常執行。這個最小數量取決於電腦的指令集架構，例如，一個指令可能需要同時存取指令本身、操作數和間接參考，這就至少需要 3 個框架。如果分配的框架少於這個數量，將導致指令在執行中途就發生 Page Fault，引發無意義的頻繁頁面置換。
2. 程式特性： 不同的程式大小和類型也應被考慮。例如，一個大型程式可能需要更多的框架以減少 Page Fault，而一個高優先權的程式也可能被分配更多的框架以加速其執行。
3. 系統公平性與效能： 分配策略必須在保證公平性的同時，盡可能降低整體 Page Fault 率，提高系統的吞吐量。

常見的框架分配方法

在確定了最小框架數量後，作業系統通常會採用以下幾種策略來分配其餘的框架：

1. 固定分配（Fixed Allocation）

此方法在程式載入時，就為其分配一個固定的框架數量。此後，這個數量不會再改變。

• 均等分配（Equal Allocation）： 將可用的框架數量平均分配給每個執行中的程式。
  • 優點： 實作簡單，能保證每個程式得到公平的資源。
  • 缺點： 缺乏彈性。沒有考慮到不同程式對記憶體的需求差異，可能會導致大型程式頻繁發生 Page Fault，而小型程式卻有閒置的框架。
• 比例分配（Proportional Allocation）： 根據每個程式的大小按比例分配框架。程式佔用的頁面數越多，分配到的框架也越多。
  • 優點： 比均等分配更合理，能更好地滿足不同程式的記憶體需求。
  • 缺點： 依然是固定分配，無法應對程式在執行過程中記憶體需求的變化。

2. 動態分配（Dynamic Allocation）

動態分配允許程式在執行過程中，根據其 Page Fault 的頻率來動態調整所分配的框架數量。

舉例：系統有 128 個 Frame，OS 使用 35 個 → 剩下 93 個 Frame 給使用者程式。

例子：
某 CPU 架構執行一條指令可能需要同時存取：

• 1 個 Frame → 存放指令本身。
• 1 個 Frame → 存放操作數（operand）。
• 1 個 Frame → 存放間接參考（indirect addressing）。
  → 每個程式至少需要 3 個 Frame，否則可能在指令執行中途就發生 Page Fault。

Thrashing（抖動）

在虛擬記憶體系統中，抖動（Thrashing）是一種嚴重的效能問題，它發生在系統將大部分時間花在頁面置換（paging）上，而不是執行程式的真正指令。當系統的記憶體資源無法滿足正在運行的程式的需求時，就會發生這種現象。

當作業系統為一個程式分配的實體記憶體框架（Frame）數量太少，無法容納其**局部性（Locality）**所需的頁面時，抖動就可能發生。局部性指的是程式在某個時間點內，其存取行為會集中在少數幾個頁面上。如果這些重要的頁面無法同時被載入到記憶體中，會發生以下惡性循環：

1. 高頻率的頁面錯誤（Page Fault）： 程式嘗試存取一個不在記憶體中的頁面，觸發 Page Fault。
2. 頁面置換頻繁： 為了載入新的頁面，作業系統必須將一個舊頁面換出。然而，由於分配的框架太少，這個被換出的頁面很可能在短時間內又會被程式需要，再次觸發 Page Fault。
3. IO 佔用大量時間： 頻繁的頁面置換需要大量的磁碟 I/O 操作（將頁面從硬碟讀入或寫出），這會導致程式大部分時間都在等待 I/O 完成，而無法執行。

系統錯誤的應對機制

問題的根源往往在於作業系統的多工處理排程策略。當系統偵測到 CPU 使用率下降時，它通常會誤認為是因為沒有足夠的程式可以執行，因此會嘗試增加新的程式來提高 CPU 利用率。然而，在抖動的狀態下，CPU 的空閒並非因為缺乏工作，而是因為所有程式都在等待 I/O 操作完成（即等待頁面置換）。當新的程式被加入時，它會從本來就不足的記憶體框架池中分走一部分資源，使得現有程式和新程式都因為缺乏足夠的記憶體而產生更頻繁的 Page Fault。這導致所有程式的效能都急劇下降，最終使系統陷入崩潰狀態。

工作集模型 (Working-Set Model)

工作集指的是程式在一個固定的時間視窗（
Delta）內最常存取的頁面集合。此模型的核心思想是：作業系統會追蹤每個程式的工作集，並確保其擁有足夠的框架來容納整個工作集。

• 如果所有程式的工作集總大小超過可用的實體記憶體，作業系統就會暫時掛起（suspend）部分程式，減少多工處理的程度，以防止抖動。
• 此策略能有效地為程式提供其執行所需的最小記憶體，同時也避免了抖動。

頁面錯誤頻率法 (Page-Fault Frequency, PFF)

PFF 是一種更直接的動態框架分配策略。它不計算複雜的工作集，而是直接監控每個程式的 Page Fault 發生率，並根據這個比率來調整其框架分配。

• 作業系統會為每個程式設定一個 Page Fault 頻率的上限（Upper Bound）和下限（Lower Bound）。
• 當程式的 Page Fault 率高於上限時，表示它缺乏足夠的框架，作業系統會為其增加框架數量。
• 當程式的 Page Fault 率低於下限時，表示它可能有閒置的框架，作業系統會減少其框架數量。

PFF 策略能即時反應程式的記憶體需求變化，並有效地調整框架分配，從而防止抖動的發生。這兩種策略雖然實作上各有挑戰，但它們都體現了現代作業系統在記憶體管理中，平衡資源分配與效能的核心思想。

Memory Compression（記憶體壓縮）

在現代作業系統中，記憶體壓縮（Memory Compression）是一種先進的技術，用來應對記憶體壓力。它的核心思想是在實體記憶體（RAM）即將用盡時，不急於將頁面寫入速度緩慢的硬碟（Swap Out），而是將一些不常用頁面的內容壓縮後，繼續保存在 RAM 中。這樣做能釋放出額外的實體記憶體空間，同時避免了昂貴且耗時的磁碟 I/O 操作。

傳統分頁與記憶體壓縮的比較

傳統的虛擬記憶體管理依賴於分頁（Paging），當記憶體不足時，作業系統會將不常用的頁面從 RAM 移動到硬碟上的交換區（Swap Space）。

硬碟的存取速度比 RAM 慢了數萬倍。頻繁的頁面換出（Swap Out）和頁面換入（Swap In）會造成嚴重的系統延遲，甚至導致抖動（Thrashing），讓系統幾乎無法運作。

記憶體壓縮則提供了一種更為聰明的解決方案：利用 CPU 的計算能力來換取 I/O 效能的提升。因為執行壓縮與解壓縮演算法的成本，遠低於從磁碟讀寫資料的成本，所以整體系統的反應速度會顯著加快。

運作原理：

1. 偵測記憶體壓力： 作業系統持續監控可用的實體記憶體框架數量。當這個數量低於一個預設的閾值時，會觸發壓縮機制。
2. 選擇頁面： 系統會選擇一些不常使用的頁面作為壓縮的對象，這些頁面通常是那些最久未被存取的頁面。
3. 執行壓縮： 被選中的頁面內容會被送往一個內核模組進行壓縮。常見的壓縮演算法包括 LZO、LZ4 或 WKdm 等，這些演算法的特點是速度快、開銷低。
4. 儲存壓縮頁面： 壓縮後的頁面通常體積會變小，作業系統可以將多個壓縮頁面打包並儲存在一個或多個實體記憶體框架中。這樣一來，原本每個獨立頁面佔用的框架就能被釋放出來，供其他程式使用。
5. 需要時解壓縮： 當一個被壓縮的頁面再次被程式需要時，作業系統無需從磁碟讀取，而是直接從 RAM 中的壓縮區域讀取，並進行解壓縮。解壓縮的速度非常快，能迅速將頁面恢復到其原始狀態，然後放回一個獨立的框架中，讓程式可以繼續存取。

Prepaging（預先載入）

預先載入（Prepaging）是一種用於優化虛擬記憶體系統效能的技術。它旨在解決需求分頁（Demand Paging）在程式啟動或從暫停狀態恢復時，可能導致的大量頁面錯誤（Page Fault）問題。在傳統的需求分頁模型中，程式的頁面只會在被需要時才被載入記憶體。這導致程式剛啟動時，由於沒有任何頁面在記憶體中，每條指令或資料存取都可能觸發 Page Fault，形成一個「Page Fault 洪峰」，嚴重影響程式啟動速度。預先載入則是一種主動式的策略。它透過預測程式在不久的將來會需要哪些頁面，並在程式實際發出請求之前，就將這些頁面一次性地載入到記憶體中。

運作機制

1. 預測： 當作業系統決定載入一個程式或將其從掛起狀態恢復時，它會分析程式的特性，並預測哪些頁面最有可能被立即使用。這個預測通常基於局部性原則（Locality Principle），例如，作業系統會假設緊鄰的頁面（即連續的虛擬位址）也會被使用。
2. 一次性載入： 作業系統會將預測到的多個頁面集中起來，透過一次或少量幾次的磁碟 I/O 操作，將它們載入到記憶體中。
   30 效能提升： 程式開始執行後，由於其所需的初始頁面已經存在於記憶體中，可以避免大量的 Page Fault，從而顯著加快程式的啟動速度和響應時間。

成本 vs 效益分析：
假設系統預先載入 s 頁：有 α 比例頁面最終被真正使用。
則：
* 成本 (Cost) = 載入沒使用的頁面數量 = s × (1 – α)
* 效益 (Benefit) = 避免的 Page Fault 次數 = s × α
* 當 α → 1（預測準確） → 預載效益高。
* 當 α → 0（預測失誤） → 浪費記憶體與 I/O。

優點：減少程式啟動時的 Page Fault 洪峰。也加快系統回應時間，特別是大型程式或頻繁暫停/恢復的程式。
缺點：若預測錯誤，會浪費 I/O 與記憶體空間。且難以百分之百準確預測，實務多採取保守策略（僅預載鄰近頁面）

Page Size（頁面大小）

在虛擬記憶體系統中，頁面大小（Page Size）是一個基礎且關鍵的設計參數。它決定了虛擬記憶體和實體記憶體被劃分的單位大小。這個看似簡單的選擇，會對整個系統的效能產生廣泛而深遠的影響。在虛擬記憶體系統中，頁面大小（Page Size）是一個基礎且關鍵的設計參數。它決定了虛擬記憶體和實體記憶體被劃分的單位大小。這個看似簡單的選擇，會對整個系統的效能產生廣泛而深遠的影響。

Page Table 大小

Page Table 是用來存放虛擬位址與實體位址對應關係的資料結構。

• 小頁面： 虛擬位址空間被劃分為更多頁面。這導致 Page Table 中需要更多條目來記錄映射關係，從而讓 Page Table 本身變得更大，佔用更多實體記憶體。
• 大頁面： 虛擬位址空間被劃分為更少頁面。Page Table 條目數減少，使其體積縮小，節省了寶貴的實體記憶體空間。

內部碎裂 (Internal Fragmentation)

內部碎裂指的是頁面中未被使用的空間。當程式的資料大小不是頁面大小的整數倍時，最後一頁會產生未使用的浪費空間。

• 小頁面： 頁面尺寸小，即使有浪費，浪費的空間也相對較少。因此，內部碎裂程度較低，記憶體利用率更高。
• 大頁面： 頁面尺寸大，最後一頁的閒置空間可能非常可觀。這會導致嚴重的內部碎裂，浪費更多記憶體空間。

I/O 傳輸效率

當發生 Page Fault 時，需要將整個頁面從磁碟讀入記憶體。

• 小頁面： 一次 I/O 只能傳輸少量資料，需要多次 I/O 才能載入足夠的頁面。這增加了 I/O 開銷，降低了傳輸效率。
• 大頁面： 一次 I/O 就能傳輸大量資料，效率更高。這對於處理大型連續資料塊的應用程式（如影片播放或科學計算）特別有利。

局部性 (Locality) 精準度

局部性原則是虛擬記憶體系統運作的基礎。它假設程式在一段時間內會集中存取某些頁面。

• 小頁面： 由於頁面較小，可以更精確地只載入程式真正需要的資料，而不會載入不必要的資訊。這提升了局部性精準度。
• 大頁面： 頁面尺寸大，可能將大量程式用不到的資料一併載入。這降低了局部性精準度，並可能浪費記憶體空間。

Page Fault 次數

Page Fault 次數與每次載入頁面的資料量有關。

• 小頁面： 載入的資料量少，程式在執行過程中需要更頻繁地從磁碟載入新頁面，導致 Page Fault 次數增加。
• 大頁面： 每次載入的資料量多，程式未來會需要的資料很可能已經被預先載入，從而減少了 Page Fault 的發生次數。