頁面置換演算法（LRU演算法）

LRU

• LRU是一種頁面置換演算法，在對於內存中但是又不用的數據塊，叫做LRU，操作系統會根據那些數據屬於LRU而將其移出內存而騰出空間來載入另外的數據
• LRU演算法：最近最少使用，簡單來說就是將數據塊中，每次使用過的數據放在數據塊的最前端，然後將存在的時間最長的，也就是數據塊的末端的數據剔除掉這就是LRU演算法
• 如果進程被調度，該進程需要使用的外存頁（數據）不存在於數據塊中，這個現象就叫做缺頁。如果這個數據此時不在，就會將這個數據從加入到數據塊首部
• 數據塊插入與剔除：每次有新數據到來時，會將其放入數據塊首部，當數據每次被訪問時，將這個數據插入數據塊的首部如果數據塊滿了，每次新進的數據都會將數據塊尾部的數據擠出數據塊

為什麼要使用LRU

• 關於操作系統內存管理，如何節省利用容量不大的內存多的進程提供資源。而內存的虛擬存儲管理是現在最通用，最成功的方式。在內存有限的情況下，擴展一部分外存作為虛擬內存，真正的內存只存儲當前運行時所用到的信息，極大的擴充了內存的功能，極大提高計算機的並發度，虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，將其餘頁面放入外存的管理方式
• 虛擬頁式存儲管理增加了進程所需的內存空間，卻也帶來了運行時間變長這一缺點，運行過程中，需要將外存中存放的信息和內存中已有的進行交換，由於外存的低速，影響了運行時間因此，應當採取盡量好的演算法以減少讀取外存的次數
• 對於虛擬頁式存儲，內外存信息替換是以頁面為單位進行的，當需要一個外存中的頁面是 將它調入內存，同時為了保持原有空間大小，我們需要不斷地剔除掉一些存頁面。數據塊大小有限，因此我們需要每次調用外存數據時，都能準確的命中。這時就需要一個較好的頁面管理演算法。

使用方法：

如下題

假如現在有一組進程：進程編號為1,2,3,4,5

虛擬頁式存儲管理的數據塊大小為3（也就是這個頁式存儲區的大小，能放置3個頁面）。

假如進程被調度順序為3.4.2.1.4.5.3.4.5.1.2。

問：在該訪問中發生的缺頁次數是多少？

解法：

1. 開始時，數據塊中為空，因此第一個進程被調度時，未命中緩存，此時發生缺頁。然後將進程對應數據放入數據塊中

2. 第二步調用進程4，此時數據塊中也沒有進程4數據，因此未命中數據塊緩存，也發生缺頁0

3. 同理，發生缺頁，但是此時數據塊已經存滿了數據，下一步如果加入新數據，將會剔除掉數據塊尾部的數據

4. 插入新進程的數據1，此時將隊尾的數據剔除掉。當然這個數據1也未命中，發生缺頁

5. 調用到數據4，此時數據4在數據塊緩存中，所以沒有發生缺頁。然後將數據4重新插入到數據塊的首部。

如下圖：

以此類推;得到最後的結果，缺頁次數為8次。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！