Least Recently Used (LRU) Page Replacement
Basic Concept
和 optimal page replacement 相反，LRU 踢掉「最久沒被用到」的頁面——基於 locality 假設，最近沒用的東西，近期也不太可能會用。
Implementation
1. Counter Implementation
每個 page table entry 裡存一個 counter，每次 page 被存取就把當前 clock 值寫進去。
- 換頁時：掃描所有 entry，找 counter 最小（最久沒用）的踢掉
- 缺點：每次換頁都要 search through table，O(n)
2. Stack Implementation
用一個 doubly linked list 維護所有在記憶體裡的 page：
- Page 被存取：把它從目前位置移到 stack top（最近使用）
- 需要改 6 個 pointer（doubly linked list 的 remove + insert）
- Stack bottom 永遠是 LRU victim，換頁時直接取用 → no search needed
- 缺點：每次 reference 都要更新 pointer，update 代價高
top → [最近用的]
[...]
[...]
bottom → [最久沒用的] ← 換頁時踢這個
硬體支援問題 不管 Counter 還是 Stack，每次 memory reference 都要更新（clock 或 pointer），硬體負擔很重。真實系統很少完整實作 true LRU。
LRU-Approximation
既然 true LRU 太貴，大多數系統改用近似版本，透過 reference bit 來低成本地追蹤使用情況。
Reference bit 機制：
- 硬體在 page 被 refer 時自動把 reference bit 設成
1 - OS 定期把所有 reference bit 清成
0 - 可以知道「某頁在上一個時間段內有沒有被用」，但不知道順序
變體一：Additional-Reference-Bits Algorithm
D-OS-Ch10eca-Additional-Reference-Bits_Algorithm
變體二：Second-Chance Algorithm（Clock Algorithm）
D-OS-Ch10ecb-Second-Chance_Algorithm