一張圖一個題幫你迅速理解LRU演算法
- 2019 年 10 月 21 日
- 筆記
對於LRU演算法，相信剛開始有很多人和我一樣都不是很明白，但是它的應用卻非常的廣泛，下面我就通過一個簡單的例子來幫助理解一下。
下面是某年的軟考題：
| 某進程頁面訪問序列為4，2，3，1，2，4，5，3，1，2，3，5，且開始執行時記憶體中沒有頁面，分配給該進程的物理塊數是3，則採用RLU頁面置換演算法時的缺頁率是多少？ |
對於這個問題的求解，你可以直接根據這個序列寫出頁面置換的過程，如下表所示，
那麼這個表格是怎麼快速寫出來的呢。其是你只需要根據這個序列每3個元素寫一次就行了，如下圖所示，
與上面的表格進行比較，你是不是也發現了這個很簡單的規律呢。只要按照箭頭上面的數字去寫就可以得到那個表格了，然後就只要判斷是否缺頁就行了，最後就寫出了頁面置換過程。
我們可以看出最後缺頁次數為10，訪問的頁面數為12次，所以最後的缺頁率為：
整個的求解過程還是比較簡單的。
