LRU是Least Recently Used的縮寫(xiě)德迹，即最近最久未使用知染，常用于頁(yè)面置換算法烈掠，是為虛擬頁(yè)式存儲(chǔ)管理服務(wù)的。

LRU算法的提出来候，是基于這樣一個(gè)事實(shí)：在前面幾條指令中使用頻繁的頁(yè)面很可能在后面的幾條指令中頻繁使用跷叉。反過(guò)來(lái)說(shuō)，已經(jīng)很久沒(méi)有使用的頁(yè)面很可能在未來(lái)較長(zhǎng)的一段時(shí)間內(nèi)不會(huì)被用到。

設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)最近最少使用（LRU）緩存的數(shù)據(jù)結(jié)構(gòu)云挟，它應(yīng)該支持以下操作：get和set梆砸。
get(key)——如果鍵存在于緩存中，則獲得鍵值（總是正數(shù)）园欣，否則返回-1帖世。
set(key, value)——如果鍵不存在，則設(shè)置或插入值俊庇。當(dāng)緩存達(dá)到其容量時(shí)，應(yīng)在插入新項(xiàng)之前使最近最少使用的項(xiàng)無(wú)效鸡挠。

分析：LRU緩存可使用一個(gè)HashMap和雙向鏈表實(shí)現(xiàn)辉饱。HashMap，使得get的時(shí)間是O（1）拣展；雙向鏈表使節(jié)點(diǎn)添加/刪除操作O（1）彭沼。

定義雙向鏈表的節(jié)點(diǎn)：

class Node{
    int key;
    int value;
    Node pre;
    Node next;
 
    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    int capacity;
    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    Node head=null;
    Node end=null;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
 
    public int get(int key) {
        if(map.containsKey(key)){
            Node n = map.get(key);
            remove(n);
            setHead(n);
            return n.value;
        }
 
        return -1;
    }
 
    public void remove(Node n){
        if(n.pre!=null){
            n.pre.next = n.next;
        }else{
            head = n.next;
        }
 
        if(n.next!=null){
            n.next.pre = n.pre;
        }else{
            end = n.pre;
        }
 
    }
 
    public void setHead(Node n){
        n.next = head;
        n.pre = null;
 
        if(head!=null)
            head.pre = n;
 
        head = n;
 
        if(end ==null)
            end = head;
    }
 
    public void set(int key, int value) {
        if(map.containsKey(key)){
            Node old = map.get(key);
            old.value = value;
            remove(old);
            setHead(old);
        }else{
            Node created = new Node(key, value);
            if(map.size()>=capacity){
                map.remove(end.key);
                remove(end);
                setHead(created);
 
            }else{
                setHead(created);
            }    
 
            map.put(key, created);
        }
    }
}

關(guān)于操作系統(tǒng)的內(nèi)存管理，如何節(jié)省利用容量不大的內(nèi)存為最多的進(jìn)程提供資源备埃，一直是研究的重要方向姓惑。而內(nèi)存的虛擬存儲(chǔ)管理，是現(xiàn)在最通用按脚，最成功的方式—— 在內(nèi)存有限的情況下于毙，擴(kuò)展一部分外存作為虛擬內(nèi)存，真正的內(nèi)存只存儲(chǔ)當(dāng)前運(yùn)行時(shí)所用得到信息辅搬。這無(wú)疑極大地?cái)U(kuò)充了內(nèi)存的功能唯沮，極大地提高了計(jì)算機(jī)的并發(fā)度。虛擬頁(yè)式存儲(chǔ)管理堪遂，則是將進(jìn)程所需空間劃分為多個(gè)頁(yè)面介蛉，內(nèi)存中只存放當(dāng)前所需頁(yè)面，其余頁(yè)面放入外存的管理方式溶褪。

有利就有弊币旧，虛擬頁(yè)式存儲(chǔ)管理增加了進(jìn)程所需的內(nèi)存空間，卻也帶來(lái)了運(yùn)行時(shí)間變長(zhǎng)這一缺點(diǎn)：進(jìn)程運(yùn)行過(guò)程中猿妈，不可避免地要把在外存中存放的一些信息和內(nèi)存中已有的進(jìn)行交換吹菱，由于外存的低速，這一步驟所花費(fèi)的時(shí)間不可忽略彭则。因而毁葱，采取盡量好的算法以減少讀取外存的次數(shù)，也是相當(dāng)有意義的事情贰剥。