緩存機制中，當發生頁衝突時，操作系統將會調用頁面置換演算法進行淘汰，而我們這篇文章中重點介紹隨機訪問情況下效率較高的兩種演算法。

LRU：Least Recently Used

NRU：Not Recently Used

LRU

LRU淘汰的是最早被使用的Cache，演算法可以分為兩種實現：

A.時間戳

硬體記錄最近一次訪問時間，每次淘汰遍歷求最早訪問的Cache。

B.鏈表

Algorithm 4th：著名的前移編碼策略，假設最近訪問過的元素很有可能再次訪問,因此可以用於緩存、數據壓縮等許多場景。

這裡將所有可能被淘汰的Cache用一張線性鏈表存儲，當查詢時，每次被查詢到的Cache節點將會被移除出鏈表並且插入表頭。如此一來，鏈表頭將會是最新被訪問的數據，而鏈表尾則會被淘汰。

這樣一來，淘汰最早訪問的Cache則非常方便，代價則是需要鏈表的結構是可修改的。

在硬體層，這兩種實現都具有巨大的開銷，因此難以用於實踐。

NRU

考慮到LRU實現困難，Clock 頁面置換演算法（NRU）應運而生。

記錄誰最早被使用很難，那麼換一種思路，把時間分成一個個週期，如果最近一個週期都沒有被使用，那就乾脆當做一直沒有被使用。

本質上這可以說是一種逆向思維：不一定要最早被使用的被淘汰，只要不是最近被使用的被淘汰就好了。而統計誰最近被使用則成本低廉，只需要在某個時間段清空訪問狀態，是否新被訪問就很容易判斷。

如同時鐘一般，Clock將所有可能被淘汰的Cache entry用一張環形鏈表存儲，並由頁表維護reference bit，時鐘的柄（clock hand）作為入口（如果是固定入口的話，會導致靠近入口的entry更容易被淘汰，因此不可取）。

被Cache的頁表是物理內存，而非虛擬內存，而MMU負責管理的reference bit在虛擬內存頁上。因此實際查找的不僅是一個頁，更是一個頁鏈表（一個物理頁對應多個虛擬頁），只要鏈表其中有一個ref bit為1，那麼整個物理頁就被視為新被訪問。而置0操作代表將物理頁對應的所有虛擬內存頁的ref bit置0。

當進行查詢時：

Hit：

將虛擬內存頁的reference bit設置為1（新被訪問）

Miss：

從clock hand開始查找物理頁Reference bit為0 的entry

如果物理頁Reference bit為1，將物理頁對應的所有虛擬內存頁的ref bit置0（注意，這裡的前移會導致入口變化），指針前移，直到找到為0的entry為止。（清空訪問狀態）

如果物理頁Reference bit 為0， 將數據放入該entry，並將虛擬內存頁Reference bit置1。（沒有新被訪問，所以被淘汰），指針前移，終止。

由於鏈表環形，因此即使第一圈掃描沒有找到Ref bit為0的entry，但由於已經清空了所有對應虛擬內存頁Ref bit，因此下一圈依然能夠輕易地找到沒有新被訪問的entry。

從性能上來講，NRU和LRU差距不大，因此可以作為替代品。

Clock?

pages.cs.wisc.edu

而最主要的是，這種環形鏈表本身的結構是穩定的，不同於LRU裏的節點的反覆插入，這裡變動的只是頁表上存儲的Ref Bit，使得其被硬體實現的可能性遠遠增強。

這使我想起以前上選修課的時候聽過的一個例子，在計算機圖形學中，反射公式本身運用大量積分計算，這是科研界的職責；而工業界則把這些複雜公式近似成計算效率高但是差距又不大的簡單公式，這樣才能在配置落後的PC上運行。

對於Cache來說，能找到最早訪問的固然好，但是寬容一點，不是最早，但是也很早被訪問的被淘汰問題也不大，只要不淘汰最近被訪問的破壞locality就好了。而這種近似，是必然存在的對現實的妥協，也是工業界必不可少的生存智慧。


推薦閱讀：
相關文章