頁面置換算法 LRU & LFU 算法
頁面置換算法介紹
評價一個頁面替換算法好壞的標準主要有兩個，一是命中率要高，二是算法要容易實現。要提高一個頁面替換算法的命中率，首先要使這種算法能正確反映程序的局部性，其次是這種算法要能夠充分利用主存中頁面調度情況的歷史信息，或者能夠預測主存中將要發生的頁面調度情況。
頁面替換算法主要用于如下幾個地方：
(1) 虛擬存儲器中，主存頁面（或程序段）的替換。
(2) Cache中的塊替換。
(3) 虛擬存儲器的快慢表中，快表的替換。
(4) 虛擬存儲器中，用戶基地址寄存器的替換。
LFU算法
近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然，這是一種非常合理的算法，因為到目前為止最少使用的頁面，很可能也是將來最少訪問的頁面。該算法既充分利用了主存中頁面調度情況的歷史信息，又正確反映了程序的局部性。但是，這種算法實現起來非常困難，它要為每個頁面設置一個很長的計數器，并且要選擇一個固定的時鐘為每個計數器定時計數。在選擇被替換頁面時，要從所有計數器中找出一個計數值最大的計數器。因此，通常采用如下一種相對比較簡單的方法。
核心思想：如果一個數據在最近一段時間內使用次數很少，那么在將來一段時間內被使用的可能性也很小“
傳統實現:
1. 新加入數據插入到隊列尾部（因為引用計數為1）；
2. 隊列中的數據被訪問后，引用計數增加，隊列重新排序；
3. 當需要淘汰數據時，將已經排序的列表最后的數據塊(訪問次 數最少的塊)刪除。
實現方式：
可用一個小頂堆+hashmap,來實現；
小頂堆對訪問次數排序
hashmap對每個緩存節點訪問次數來更新
改良版算法：Window-LFU（置換指定時間內，按照LFU規則排序淘汰數量）
1）記錄了過去W個訪問記錄；
2）需要淘汰時，將W個訪問記錄按照LFU規則排序淘汰
舉例如下：
假設歷史訪問記錄長度設為9，緩存大小為3，圖中不同顏色代表針對不同數據塊的訪問，同一顏色代表 針 對同一數據的多次訪問。
樣例1：黃色訪問3次，藍色和橘色都是兩次，橘色更新，因此緩存黃色、橘色、藍色三個數據塊
樣例2：綠色訪問3次，藍色兩次，暗紅兩次，藍色更新，因此緩存綠色、藍色、暗紅三個數據塊
需要維護一個隊列，記錄數據的訪問流歷史；需要排序。
Window-LFU只記錄一部分的訪問歷史記錄，不需要記錄所有的數據訪問歷史，因此內存消耗和排序消耗都 比LFU要低。
LRU算法
最久沒有使用算法，即LRU算法（Least Recently Used algorithm）。這種算法把近期最久沒有被訪問過的頁面作為被替換的頁面。它把LFU算法中要記錄數量上的"多"與"少"簡化成判斷"有"與"無"，因此，實現起來比較容易。
核心思想：如果在一段時間內長時間不訪問的頁面將來也不會訪問
傳統實現原理：
假設 序列為 4 3 4 2 3 1 4 2
物理塊有3個 則
首輪 4調入內存 4
次輪 3調入內存 3 4
之后 4調入內存 4 3
之后 2調入內存 2 4 3
之后 3調入內存 3 2 4
之后 1調入內存 1 3 2（因為最少使用的是4，所以丟棄4）
之后 4調入內存 4 1 3（原理同上）
最后 2調入內存 2 4 1
LRU算法擴展，可以看我的另一篇博文：
http://my.oschina.net/manmao/blog/601698