分頁置換與輾轉現象
計數式置換(counting-based replacement)
計數式方法不問「這個頁上次何時被用?」(新近程度),而是問「這個頁被用了多少次?」(頻率)。每個頁保有一個計數器,記錄它被參考過幾次,置換決定就根據這些計數。建立在同一個計數器上有兩種相反的版本:LFU(最不常使用)與 MFU(最常使用)。
LFU 逐出參考計數最小的頁,理由是一個很少被用的頁大概不太重要,可以走人。MFU 則相反——它逐出計數最大的頁——理由是一個被用了許多次的頁已經輪過了、很可能用完了,而一個計數小的頁大概是剛被帶進來、還需要被使用。每種策略都維護一個每頁的計數器,作業系統在每次參考時把它加一(或從參考位元估計),並在選犧牲頁時掃描最小或最大值。
為什麼重要,又為什麼很少是主要選擇:LFU 與 MFU 都很直覺,但兩者都不特別接近最佳法,在真實工作負載上也都笨拙。LFU 的經典缺陷是那個在啟動期間被猛敲的頁:它的計數高得嚇人,於是 LFU 在程式早已轉移焦點之後仍緊抓著它不放。常見的補救是讓計數老化(隨時間把它們往下移),讓舊有的人氣淡去。由於這些弱點,計數式置換在實務上並不常見——多數系統偏好像時鐘演算法這種以新近程度為基礎的近似法——但 LFU 式的頻率計數在別處確實有用,例如在快取的逐出策略中。
頁 A、B、C 的參考計數為 12、3、1。LFU 逐出 C(計數 1,最少使用)。MFU 反而逐出 A(計數 12),賭 A 已經跑完了、而低計數的頁還需要它們的回合。
LFU 丟掉最少使用的頁;MFU 丟掉最常使用的——同一個計數器,相反的賭注。
LFU 與 MFU 都不太能近似最佳法,而 LFU 惡名昭彰地會囤積一個只在啟動時忙碌過的頁。讓計數老化有幫助,但真實作業系統通常偏好以新近程度為基礎的時鐘變體,而非計數式方法。
又稱
另見