存儲LRU

① 實現LRU演算法的硬體支持是什麼

寄存器、棧

實現LRU演算法的硬體支持是寄存器、棧。寄存器用於記錄某進程在內存中各頁的使用情況；棧用於保存當前使用的各個頁面的頁面號。LRU是最近最少使用，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。寄存器的功能是存儲二進制代碼，它是由具有存儲功能的觸發器組合起來構成的。一個觸發器可以存儲1位二進制代碼，故存放n位二進制代碼的寄存器，需用n個觸發器來構成。

(1)存儲LRU擴展閱讀：

大部分操作系統為最大化頁面命中率而廣泛採用的一種頁面置換演算法是LRU演算法。該演算法的思路是，發生缺頁中斷時，選擇未使用時間最長的頁面置換出去。從程序運行的原理來看，最近最少使用演算法是比較接近理想的一種頁面置換演算法，這種演算法既充分利用了內存中頁面調用的歷史信息，又正確反映了程序的局部問題。

② lru演算法是什麼呢

LRU演算法是最少使用頁面置換演算法（Least Recently Used），首先置換近期最長時間以來沒被訪問的頁面，是為虛擬頁式存儲管理服務的。

LRU演算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。

LRU原理

該思想最初用於計算機操作系統中，內存中的容量較有限，為了能更加合理的利用內存中的性能，對用戶的使用作出假設，最近最少使用的越不重要，最近使用的越有可能使用到，使得該元素更容易獲取到。

如果元素當前容量超過了內存最大容量，則需要刪除掉最近最少使用的元素。在其之後，許多緩存及許多分布式系統都採用才思想。

③ lru演算法是什麼

最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。

LRU演算法的建議基於以下事實：在前幾條指令中經常使用的頁面很可能在後幾條指令中經常使用。

相反，長時間未使用的頁面將來可能會長時間不使用。 這是眾所周知的局部性原則-緩存比內存快，它也以相同的原理運行。 因此，每次交換時，我們只需要找到使用最少的頁面來調出內存即可。

(3)存儲LRU擴展閱讀：

LRU演算法是大多數操作系統廣泛使用以最大化頁面命中率的頁面替換演算法。該演算法的思想是，當發生頁面錯誤時，將選擇並替換未使用時間最長的頁面。

從程序操作原理的觀點來看，最近最少使用的演算法是相對接近理想的頁面替換演算法。該演算法不僅充分利用了內存中頁面調用的歷史信息，而且可以正確反映程序的局部問題。

④ 漫畫：什麼是LRU演算法

————— 兩個月前 —————

用戶信息當然是存在資料庫里。但是由於我們對用戶系統的性能要求比較高，顯然不能每一次請求都去查詢資料庫。

所以，小灰在內存中創建了一個哈希表作為緩存，每次查找一個用戶的時候先在哈希表中查詢，以此提高訪問性能。

很快，用戶系統上線了，小灰美美地休息了幾天。

一個多月之後......

———————————————

什麼是哈希鏈表呢？

我們都知道，哈希表是由若干個Key-Value所組成。在「邏輯」上，這些Key-Value是無所謂排列順序的，誰先誰後都一樣。

在哈希鏈表當中，這些Key-Value不再是彼此無關的存在，而是被一個鏈條串了起來。每一個Key-Value都具有它的前驅Key-Value、後繼Key-Value，就像雙向鏈表中的節點一樣。

這樣一來，原本無序的哈希表擁有了固定的排列順序。

讓我們以用戶信息的需求為例，來演示一下LRU演算法的基本思路：

1.假設我們使用哈希鏈表來緩存用戶信息，目前緩存了4個用戶，這4個用戶是按照時間順序依次從鏈表右端插入的。

2.此時，業務方訪問用戶5，由於哈希鏈表中沒有用戶5的數據，我們從資料庫中讀取出來，插入到緩存當中。這時候，鏈表中最右端是最新訪問到的用戶5，最左端是最近最少訪問的用戶1。

3.接下來，業務方訪問用戶2，哈希鏈表中存在用戶2的數據，我們怎麼做呢？我們把用戶2從它的前驅節點和後繼節點之間移除，重新插入到鏈表最右端。這時候，鏈表中最右端變成了最新訪問到的用戶2，最左端仍然是最近最少訪問的用戶1。

4.接下來，業務方請求修改用戶4的信息。同樣道理，我們把用戶4從原來的位置移動到鏈表最右側，並把用戶信息的值更新。這時候，鏈表中最右端是最新訪問到的用戶4，最左端仍然是最近最少訪問的用戶1。

5.後來業務方換口味了，訪問用戶6，用戶6在緩存里沒有，需要插入到哈希鏈表。假設這時候緩存容量已經達到上限，必須先刪除最近最少訪問的數據，那麼位於哈希鏈表最左端的用戶1就會被刪除掉，然後再把用戶6插入到最右端。

以上，就是LRU演算法的基本思路。

private Node head;

private Node end;

//緩存存儲上限

private int limit;

private HashMap<String, Node> hashMap;

public LRUCache(int limit) {

this.limit = limit;

hashMap = new HashMap<String, Node>();

}

public String get(String key) {

Node node = hashMap.get(key);

if (node == null){

return null;

}

refreshNode(node);

return node.value;

}

public void put(String key, String value) {

Node node = hashMap.get(key);

if (node == null) {

//如果key不存在，插入key-value

if (hashMap.size() >= limit) {

String oldKey = removeNode(head);

hashMap.remove(oldKey);

}

node = new Node(key, value);

addNode(node);

hashMap.put(key, node);

}else {

//如果key存在，刷新key-value

node.value = value;

refreshNode(node);

}

}

public void remove(String key) {

Node node = hashMap.get(key);

removeNode(node);

hashMap.remove(key);

}

/**

* 刷新被訪問的節點位置

* @param node 被訪問的節點

*/

private void refreshNode(Node node) {

//如果訪問的是尾節點，無需移動節點

if (node == end) {

return;

}

//移除節點

removeNode(node);

//重新插入節點

addNode(node);

}

/**

* 刪除節點

* @param node 要刪除的節點

*/

private String removeNode(Node node) {

if (node == end) {

//移除尾節點

end = end.pre;

}else if(node == head){

//移除頭節點

head = head.next;

} else {

//移除中間節點

node.pre.next = node.next;

node.next.pre = node.pre;

}

return node.key;

}

/**

* 尾部插入節點

* @param node 要插入的節點

*/

private void addNode(Node node) {

if(end != null) {

end.next = node;

node.pre = end;

node.next = null;

}

end = node;

if(head == null){

head = node;

}

}

class Node {

Node(String key, String value){

this.key = key;

this.value = value;

}

public Node pre;

public Node next;

public String key;

public String value;

}

public static void main(String[] args) {

LRUCache lruCache = new LRUCache(5);

lruCache.put("001", "用戶1信息");

lruCache.put("002", "用戶1信息");

lruCache.put("003", "用戶1信息");

lruCache.put("004", "用戶1信息");

lruCache.put("005", "用戶1信息");

lruCache.get("002");

lruCache.put("004", "用戶2信息更新");

lruCache.put("006", "用戶6信息");

System.out.println(lruCache.get("001"));

System.out.println(lruCache.get("006"));

}

需要注意的是，這段不是線程安全的，要想做到線程安全，需要加上synchronized修飾符。

告訴大家一個好消息，小灰的《漫畫演算法》全面上架啦，在短短的兩周里，本書一度霸佔著各大暢銷榜榜首！

⑤ 什麼是LRU測試請知道的告訴一下

LRU是Least Recently Used的縮寫，即最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。 關 於操作系統的內存管理，如何節省利用容量不大的內存為最多的進程提供資源，一直是研究的重要方向。而內存的虛擬存儲管理，是現在最通用，最成功的方式—— 在內存有限的情況下，擴展一部分外存作為虛擬內存，真正的內存只存儲當前運行時所用得到信息。這無疑極大地擴充了內存的功能，極大地提高了計算機的並發 度。虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，其餘頁面放入外存的管理方式。 然而，有利就有弊，虛擬頁式存儲管理減少了進程所需的內存空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和 內存中已有的進行交換，由於外存的低速，這一步驟所花費的時間不可忽略。因而，採取盡量好的演算法以減少讀取外存的次數，也是相當有意義的事情。 對 於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入內存，同時為了保持原有空間的大小，還要把一個內存中頁 面調出至外存。自然，這種調動越少，進程執行的效率也就越高。那麼，把哪個頁面調出去可以達到調動盡量少的目的？我們需要一個演算法。 自然，達到這樣一種情形的演算法是最理想的了——每次調換出的頁面是所有內存頁面中最遲將被使用的——這可以最大限度的推遲頁面調換，這種演算法，被稱為理想頁面置換演算法。可惜的是，這種演算法是無法實現的。 為了盡量減少與理想演算法的差距，產生了各種精妙的演算法，最近最少使用頁面置換演算法便是其中一個。LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。 如何用具體的數據結構來實現這個演算法？ 首先，最容易想到，也最簡單的方法：計時法。給頁表中的每一頁增加一個域，專門用來存放計時標志，用來記錄該頁面自上次被訪問以來所經歷的時間。頁面每被訪問一次，計時清0。要裝入新頁時，從內存的頁面中選出時間最長的一頁，調出，同時把各頁的計時標志全部清0，重新開始計時。 計時法可以稍作改變，成為計數法：頁面被訪問，計數標志清0，其餘所有內存頁面計數器加1；要裝入新頁時，選出計數最大的一頁調出，同時所有計數器清0。 這兩種方法確實很簡單，但運行效率卻不盡如人意。每個時刻，或是每調用一個頁面，就需要對內存中所有頁面的訪問情況進行記錄和更新，麻煩且開銷相當大。 另一種實現的方法：鏈表法。 操作系統為每個進程維護一條鏈表，鏈表的每個結點記錄一張頁面的地址。調用一次頁面，則把該頁面的結點從鏈中取出，放到鏈尾；要裝入新頁，則把鏈頭的頁面調出，同時生成調入頁面的結點，放到鏈尾。 鏈表法可看作簡單計時/計數法的改良，維護一個鏈表，自然要比維護所有頁面標志要簡單和輕松。可是，這並沒有在數量級上改變演算法的時間復雜度，每調用一個頁面，都要在鏈表中搜尋對應結點並放至鏈尾的工作量並不算小。 以上是單純使用軟體實現的演算法。不過，如果能有特殊的硬體幫忙，我們可以有更有效率的演算法。 首先，如果硬體有一個64位的計數器，每條指令執行完後自動加1。在每個頁表項里添加一個域，用於存放計數器的值。進程運行，每次訪問頁面的時候，都把計數器的值保存在被訪問頁面的頁表項中。一旦發生缺頁，操作系統檢查頁表中所有的計數器的值以找出最小的一個，那這一頁就是最久未使用的頁面，調出即可。 其次，另外一個矩陣演算法：在一個有n個頁框的機器中，LRU硬體可以維持一個n*n的矩陣，開始時所有位都是0。訪問到第k頁時，硬體把k行的位全設為1，之後再把k列的位置設為0。容易證明，在任意時候，二進制值最小的行即為最久未使用的頁面，當調換頁面時，將其調出。 以上的兩種演算法，無疑都要比純粹的軟體演算法方便且快捷。每次頁面訪問之後的操作——保存計數器值和設置k行k列的值，時間復雜度都是O(1)量級，與純軟體演算法不可同日而語。 那是否軟體演算法就毫無用處？當然不是，硬體演算法有它致命的缺陷，那就是需要硬體的支持才能運行。如果機器上恰好有所需硬體，那無疑是再好不過；反之，若機器上沒有這種硬體條件，我們也只能無奈地拋棄硬體演算法，轉而選取相對麻煩的軟體演算法了。 最後，讓我們來談論一下LRU算 法。首先，這是一個相當好的演算法，它是理想演算法很好的近似。在計算機系統中應用廣泛的局部性原理給它打造了堅實的理論基礎，而在實際運用中，這一演算法也被 證明擁有極高的性能。在大規模的程序運行中，它產生的缺頁中斷次數已很接近理想演算法。或許我們還能找到更好的演算法，但我想，得到的收益與付出的代價恐怕就 不成比例了。當然，LRU演算法的缺點在於實現方法的不足——效率高的硬體演算法通常在大多數機器上無法運行，而軟體演算法明顯有太多的開銷。與之相對的，FIFO演算法，和與LRU相似的NRU演算法，性能盡管不是最好，卻更容易實現。所以，找到一個優秀的演算法來實現LRU，就是一個非常有意義的問題。

希望採納

⑥ 什麼是lru置換演算法

LRU是Least
Recently
Used的縮寫，即最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。
LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。
這是一個相當好的演算法，它是理想演算法很好的近似。

⑦ LRU是什麼

LRU是Least Recently Used最近最久未使用演算法。

Oracle系統使用的一種演算法，對於在內存中但最近又不用的數據塊（內存塊）叫做LRU，Oracle會根據那些數據屬於LRU而將其移出內存而騰出空間來載入另外的數據。

什麼是LRU演算法? LRU是Least Recently Used的縮寫，即最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。