Belady’s Anomaly

Concept

直覺上來說我們的 frame 數量越多，越不容易發生 page fault，然而反直覺的是在某些 page replacement algorithm 下這不一定成立

Example: FIFO Page Replacement

對於存取序列：1 2 3 4 1 2 5 1 2 3 4 5

Frames	Page Faults
3	9
4	10 (更多！)

When Occurs?

在一個 place replacement algorithm 中，如果它用來決定 victim 的性質不是獨立於 frame 數量的話，那麼就會發生 Belady’s Anomaly

像是 FIFO 用來決定 victim 的性質是「該 page 何時被載入」，但這個性質取決於「這個 page 上一次在何時被踢出」，而這件事和 frame 數量是相關的

LRU 紀錄的則是在任意時間點 $t$ 「最近使用過的 page」這個集合，這個集合是被 reference string 本身決定的，frame 數量並不會對其產生影響