Additional-Reference Bits Algorithm
Basic Concept
單一 bit 只能說「有用過 / 沒用過」，無法比較兩個都用過的頁面誰比較舊。所以改用一個 8-bit shift register 來記錄「最近 8 個時間段」的使用歷史——bit pattern 越大，代表越近期被用過，越不該被踢。
How it works?
- 每個 page 維護一個 8-bit register，初始為
00000000 - OS 的 timer interrupt 定期觸發（例如每 100ms 一次）：
- 把每個 page 的 reference bit shift 進 register 最高位（MSB）
- register 右移一位，最舊的 bit 掉出去
- 再把 reference bit 清成
0
- 換頁時：找 register 數值最小的 page 踢掉（數值越小 = 越久沒用）
具體範例：
Reference string：4. 7. 0. 1. 0. 1. 2. 1. [2. 7. 1. 2]（框起來的是最近這段）
經過幾輪 shift 後，各 page 的 8-bit 歷史如下（最左位 = 最近一次的 reference bit）：
| Page | 8-bit Register | 十進位值 |
|---|---|---|
| 0 | 01100000 | 96 |
| 1 | 11100000 | 224 |
| 2 | 11000000 | 192 |
| 3 | 00000000 | 0 |
| 4 | 00100000 | 32 |
| 5 | 00000000 | 0 |
| 6 | 00000000 | 0 |
| 7 | 10100000 | 160 |
照數值由小到大排，得到近似的 LRU 順序（最該被踢的在前）：
Approximated LRU：3, 5, 6, 4, 0, 7, 2, 1
關鍵限制 Additional-Reference-Bits 的解析度受限於 timer 觸發頻率：同一個時間段內用過的頁面，register 值會一樣，無法進一步排序。時間段切越細、歷史 bit 越多，就越接近 true LRU，但 overhead 也越高。