作業系統中的起源

快取檔案置換機制

現代語言的很多特性都可以在作業系統中找到最初的原型，LRU我們最早也可以在作業系統中找到當初的設計，

“高速快取是計算機科學中唯一重要的思想”        -Bill Joy

我們知道，無論是記憶體還是硬碟，又或者是我們在各自應用中用到的cache，由于大小固定，因而總會面臨空間不足，而需要進行快取置換（or替換），而替換的原則被我們稱為快取檔案置換機制，

而今天聊得主題就是：最近最少未使用演算法（LRU），即最久沒有訪問的內容作為替換物件，

頁面置換演算法

作業系統中，我們可以利用覆寫或交換來擴充記憶體，當作業系統的記憶體采用基本分頁存盤管理，即作業系統采用分頁系統基礎時，作業系統可以進行請求調頁功能和頁面置換功能，從而實作虛擬存盤器的功能，選擇調出頁面的演算法就成為頁面置換演算法，LRU就是其中一種，

最近最久未使用/LRU頁面置換演算法，選擇最近最長時間未被訪問過的頁面予以淘汰，它認為過去一段時間內未訪問過的頁面，在最近的將來可能也不會被訪問，該演算法為每個頁面設定一個訪問欄位，來記錄頁面來自上次被訪問以來所經歷的時間，淘汰頁面時選擇現有頁面中值最大的予以淘汰，

如上表所示，行程第一次對頁面2進行訪問時，將最近最久未被訪問的頁面7置換出去，隨后訪問頁面3時，將最近最久未使用的頁面1換出，

LruCache演算法

前文介紹的LRU作為一種快取淘汰策略，應用在cache上即LruCache 演算法，

LruCache 演算法通過 LinkedHashMap 來實作，LinkedHashMap繼承于HashMap，它使用一個雙向鏈表來存盤 Map 中的 Entry 順序關系，對 get、put、remove 等操作，LinkedHashMap 除了要做 HashMap 做的事情，還做些調整 Entry 順序鏈表的作業，

LruCache 中將 LinkedHashMap 的順序設定為 LRU 順序來實作 LRU 快取，每次呼叫 get(也就是從記憶體快取中取圖片)，則將該物件移到鏈表的尾端， 呼叫 put 插入新的物件也是存盤在鏈表尾端，這樣當記憶體快取達到設定的最大值時，將鏈表頭部的物件（近期最少用到的）移除，

Android中的LruCache

LruCache是Android 3.1（Api12）時引入，兼容低版本實際會使用v4包進行使用，LruCache的引入讓系統在快取不足時移除佇列末尾的值，方便GC，LruCache用于記憶體快取，在避免程式發生OOM和提高執行效率有著良好表現，

看一下androidx.collection包中的LruCache：

public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;

    private int size;           //當前快取的大小
    private int maxSize;        //最大可快取的大小

    private int putCount;
    private int createCount;
    private int evictionCount;
    private int hitCount;      //命中快取的次數
    private int missCount;     //丟失快取的次數

 
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }
  
  // ...
  
  }
    

LruCache的建構式中傳入的引數maxSize為可快取的最大容量，maxSize代表了LruCache內部的LinkedHashMap可存盤的最大鍵值對數量，

 public final V put(@NonNull K key, @NonNull V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }

        trimToSize(maxSize);
        return previous;
    }

LruCache的put()方法首先判斷了LruCache的鍵或值不能為null，

在插入元素前會呼叫一次safeSizeOf()，safeSizeOf()方法呼叫sizeOf()方法，sizeOf()默認回傳1，一般會對它進行重寫：比如LruCache存盤的value是一個File，那么sizeOf回傳的就應該是當前對應該key的File的大小（所有的File大小不能超過maxSize），因為當前快取增加了，相應的size也要完成自增長，且將對應的key-value插入到鏈表中（ 這一步：previous = map.put(key, value)），

if (previous != null) {entryRemoved(false, key, previous, value);}這一步進行了二次檢查，如果該key已經存在鏈表中，此時新的value覆寫后，size要減去之前的value所占用的大小，

為了保證多執行緒場景下size的準確性，用synchronized (this)確保以上操作都是同步的，

如果是覆寫了舊的value，LruCache還對外提供了一個空方法entryRemoved，該方法會在一個值被remove或者put時被呼叫， 默認實作什么都不做，

trimToSize()方法保證了快取不溢位：

public void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                if (size <= maxSize || map.isEmpty()) {
                    break;
                }

                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

trimToSize()方法會洗掉最舊的一條鍵值對，直到快取<=最大容量，具體來說：每插入一次元素就會被呼叫該方法，方法是一個無限回圈，當當前快取大小不大于最大容量就結束回圈，否則取出LinkedHashMap的entrySet的頭部，也就是最早被插入且最近未被訪問過的鍵值對并洗掉，更新size，重復此步驟直到快取<=最大容量，LRU快取的實作利用了訪問順序的LinkedHashMap的特性完成，

取值的get()方法：

 public final V get(@NonNull K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }

        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }

get()方法key值不能為null，如果map中存在與key相對應的value，則回傳該value，并且快取命中數+1，不存在，則快取丟失數+1；如果不存在的話，會呼叫V createdValue = create(key)去嘗試根據該key創建一個value，create()方法默認回傳null，需要自己實作，

結尾

LruCache作為一個基礎的快取策略應用在很多方面，安卓從Android3.1引入，很多的開源框架比如Glide圖片快取中，也會用到LruCache，

參考

https://zh.wikipedia.org/w/index.php

https://developer.android.com/reference/android/util/LruCache