概述：

? 作為一個學計算機的一定聽過緩存（注意這里是緩存，不是緩沖）。比如我們在登錄網頁時，網頁就可以緩存一些用戶信息；比如我們在寫界面代碼的時候，可能就會遇到界面的繪制是基于一些緩存算法的。所以，了解一下緩存算法的原理還是有必要的。

本文鏈接：http://blog.csdn.net/lemon_tree12138/article/details/50463365 --Coding-Naga
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?--轉載請注明出處

基本分析：

? 首先我們要做的事情是，我們知道最好的置換或者說緩存算法是，我們可以把那些最不可能會使用的資源或是作業從內存移到外存，以確保盡可能少地進行置換操作。可是，我們又要如何知道后面有哪些資源正在排隊呢，或者說即將被使用呢？這里你是不是要問，我們操作系統不是有一個就緒和阻塞的進程隊列么？遍歷這個列表不就可以知道后面哪些資源最沒可能被訪問了么？是的，不可否認。如果可以這樣的確還不錯。可是，這個隊列一定是一個動態的隊列。比如，在PC上，用戶想使用哪個軟件都有可能，這個我們不能事先定義好。

? 既然不能預知，那么這種最佳的轉換算法就不能實現。因為我們不能預知，所以我們就要想辦法來預測。預測哪些哪些資源可能在近期不會被使用，就換出該資源。

具體算法策略：

1.先進先出(FIFO)頁面置換算法

? 最簡單的算法莫過于FIFO了，正是因為這個算法的簡單，所以在效果上就并不那么讓人滿意了。下面是原理圖：

圖-1 FIFO算法原理圖

? 在FIFO的原理圖中，如果隊列還未滿時，我們可以隨意加入，當隊列緩存的數據滿了的時候，我們也只是簡單地從隊列的尾部加入，從隊列的頭部移除。某一個資源的使用對于資源的移除不產生任何影響。所以，圖中就沒有展示。代碼的編寫也很簡單，如下：

public class FIFO implements Cacheable {private int maxLength = 0;private Queue<Object> mQueue = null;public FIFO(int _maxLength) {... ...}@Overridepublic void offer(Object object) {if (mQueue == null) {throw new NullPointerException("策略隊列對象為空");}// check is need swap or notif (mQueue.size() == maxLength) {clean();}mQueue.offer(object);}@Overridepublic void visitting(Object object) {System.out.println("Visited " + object);}private void clean() {mQueue.poll();} }

2.最近最久未使用(LRU)置換算法

圖-2 LRU算法原理圖

? 對比FIFO原理圖和LRU原理圖，可以很明顯地看到只是在被使用的資源部分有一些小的改動。在一般地使用過程中，和FIFO一樣，如果隊列還未滿時，我們可以隨意加入，當隊列緩存的數據滿了的時候，我們一樣地從隊列的尾部加入，從隊列的頭部移除了。當我們要訪問一個資源的時候，就把這個資源移動到隊列的尾部，讓這個資源看上去就像最新添加的一樣。這個就是我們LRU算法的核心了。

? 下面提供部分關鍵代碼，完整代碼參見文章最下方的源碼下載。

public class LRU implements Cacheable {private int maxLength = 0;private Queue<Object> mQueue = null;public LRU(int _maxLength) {... ...}@Overridepublic void offer(Object object) {if (mQueue == null) {throw new NullPointerException("策略隊列對象為空");}// check is need swap or notif (mQueue.size() == maxLength) {clean();}mQueue.offer(object);}@Overridepublic void visitting(Object object) {if (mQueue == null || mQueue.isEmpty()) {throw new NullPointerException("訪問對象不存在");}System.out.println("Visited " + object);displace(object);}// remove the longer no visitprivate void clean() {mQueue.poll();}// cache core codeprivate void displace(Object object) {for (Object tmp : mQueue) {if (object.equals(tmp)) {mQueue.remove(tmp);break;}}mQueue.offer(object);} }

3.Clock置換算法

? 這里有一點需要糾正一下，當你看到“Clock”的時候，請不要把它理解成Clock算法是基于時間片之類的一種算法。Clock算法是把資源隊列看成是一個類似Clock一樣的，可以循環訪問的這么一個特性。

圖-3 Clock算法原理圖

? 在Clock頁面置換算法中，我們對對象進行了一個二次封裝。在封裝類中，額外加入了一個新的元素：Flag。這是一個boolean的標志位，用于指示，當前的資源或是進程是否可以被換出。當這個標志位為false的時候，就把這個標志打成true，用于下次遍歷到此元素的時候，可以移除它；當這個標志位為true的時候，就把這個元素從隊列中移除。當我們要訪問某一個對象的時候，就把檢查指針指向這個元素的下一個元素，這樣下次檢查的時候，可以跳過這個元素，確保了當前元素的安全性。代碼過程如下（這里省略了一部分輕量級的代碼，因為它相對于算法本身本言并不重要，詳細代碼參見最下方的GitHub源碼下載鏈接）：

public class Clock implements Cacheable {private int maxLength = 0;private List<ClockBean> list = null;private int index = 0;public Clock(int _maxLength) {... ...}@Overridepublic void offer(Object object) {if (list == null) {throw new NullPointerException("策略隊列對象為空");}if (list.size() == maxLength) {clean();} else {index = (index + 1 + maxLength) % maxLength;}list.add((ClockBean) object);}@Overridepublic void visitting(Object object) {if (object instanceof ClockBean) {ClockBean bean = (ClockBean) object;for (int i = 0; i < list.size(); i++) {if (bean == list.get(i)) {list.get(i).setCleanFlag(false);index = (i + 1 + maxLength) % maxLength;}}} else {System.err.println("Error Type");}}// 移除待置換的對象private void clean() {ClockBean bean = list.get(index);if (bean == null) {throw new NullPointerException();}if (bean.isCleanFlag()) {list.remove(index);return;}bean.setCleanFlag(true);clean();} }

Ref：

《計算機操作系統》

http://flychao88.iteye.com/blog/1977653

GitHub源碼下載：

https://github.com/William-Hai/LRU-Cache

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的操作系统：基于页面置换算法的缓存原理详解（上）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。