參考字串（reference string）

假設你想比較兩種不同的規則，看書桌滿時該把哪本書放回去。你不能只在抽象層次上爭論——你需要一份實際伸手去拿哪些書的真實紀錄，照順序排好，然後就能在每種規則下重播這份紀錄，單純數一數你有幾次必須從書架取書。參考字串對記憶體而言就正是這樣一份紀錄：程式所碰觸的頁號序列，依照碰觸的順序排列。

實務上我們把位址精簡到只剩頁號，因為對置換而言只有頁重要，確切的位元組並不重要。我們也把連續對同一頁的參考併成一次，因為一個已經在記憶體裡的頁，在被逐出之前不會再次發生錯誤。所以一串原始位址可能變成像 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 這樣的參考字串。要評估一個演算法，你固定一個頁框數，從左到右走過這串字串，每當被參考的頁目前不在記憶體中就記一次分頁錯誤。錯誤越少，表示該演算法在這個工作負載上越好。

為什麼重要：參考字串是分頁置換演算法的標準、誠實的量尺——它讓我們能說出「FIFO 在這裡錯了九次，但 LRU 只錯七次」這樣的話。貝雷迪異常也是這樣被發現的（用同一串字串先跑三個頁框、再跑四個，看著 FIFO 變得更糟）。一個提醒：一串參考字串只是一種工作負載；在一串字串上勝出的演算法在另一串上可能落敗，所以真正的比較會用許多份真實的軌跡，而不是單一精挑細選的例子。