引言

操作系統(tǒng)的內存管理一直是計算機領域研究的一個重要方向，而內存的虛存管理是存儲管理的核心。其原因在于內存的價格昂貴，用大量的內存存儲所有被訪問的程序與數(shù)據(jù)段是不可能的；而外存盡管訪問速度較慢，但價格便宜，適合于存放大量的信息。因此，在內存有限的情況下，擴展一部分外存作為虛擬內存，真正的內存只存儲當前運行時所用得到的信息，這無疑可以大大擴充內存的功能，并大大提高計算機的并發(fā)度。虛擬頁式存儲管理，就是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，其余頁面放入外存的管理的一種假內存擴充方式。在程序執(zhí)行時，如果發(fā)現(xiàn)要訪問的頁面不在內存，則系統(tǒng)將產(chǎn)生缺頁中斷。缺頁中斷服務程序將負責把位于磁盤上的數(shù)據(jù)加載到物理內存。

虛擬頁式存儲管理雖然在某些程度上可以減少進程所需的內存空間，但同時也會帶來運行時間變長的問題。進程在運行的過程中，不可避免地要把在外存中存放的一些信息和內存中已有的數(shù)據(jù)進行交換，由于內外存運行速度的差異,這一步驟所花費的時間一般不可忽略，因而必須采取盡量好的算法來減少讀取外存的次數(shù)。

對于虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的。當需要一個放在外存的頁面時，系統(tǒng)便把它調入內存,同時又要把內存中的一個頁面調出至外存。當然，這種調動越少，進程執(zhí)行的效率也就越高。那么，把哪個頁面調出去就可以達到調動盡量少的目的？操作系統(tǒng)中提出了很多種頁面置換算法，LRU(LeastRecentlyUsed)最近最少使用頁面置換算法就是比較接近理想算法的一種解決方案。

1LRU算法的提出

1.1傳統(tǒng)的頁面置換算法

為了盡量減少與理想算法的差距，現(xiàn)在已經(jīng)出現(xiàn)了各種精妙的算法，如隨機淘汰算法、輪轉法(RR)和先進先出算法(FIFO)等，但這幾種算法都有著各自的缺點。隨機淘汰算法的思想是無法確定哪些頁面被訪問的概率較低時，隨機地選擇某個用戶的頁面并將其換出的一種方法。這種算法的隨機性太大，無法達到減少頁面調動的目的。輪轉法是循回換出內存可用區(qū)內一個可以被換出的頁，無論該頁是剛被換進或已換進內存很長時間。FIFO認為先調入內存的頁不再被訪問的可能性要比其它頁大，因而選擇最先調入內存的頁并將其換出。但是實驗證明，F(xiàn)IFO算法和RR算法的內存利用率都不高，因為這兩種算法都是基于CPU按線性順序訪問地址空間這一假設。事實上，CPU不一定是按線性順序訪問地址空間的。FIFO算法的另一個重要的缺點是它會產(chǎn)生Belady現(xiàn)象，即對于一個進程，如果給它分配的頁面數(shù)增多，缺頁次數(shù)反而會增加這一奇怪現(xiàn)象。

1.2LRU頁面置換算法

LRU算法是基于這樣一個事實：在前面幾條指令中使用頻繁的頁面也很可能在后面的幾條指令中頻繁使用。反過來說,已經(jīng)很久沒有使用過的頁面很可能在未來較長的一段時間內也不會被用到。這就是著名的局部性原理。比內存速度還要快的cache，也是基于同樣的原理運行的。因此，從程序運行的原理來看，LRU算法是比較接近理想的置換算法。

2LRU算法的實現(xiàn)

用矩陣的方法來實現(xiàn)LRU算法的思想是使用矩陣來記錄頁面使用的頻率和時間。設矩陣是nXn維的，n是相關程序當前駐內存的頁面數(shù)。矩陣的初值為0,每次訪問一個頁面，例如第i個虛擬頁被訪問時，可對矩陣進行如下操作：

一是將第i行的值全部置1:二是將第i列的值全部置0。

在每次需要更換頁面時，選擇矩陣里對應行值最小的頁面。行值是指把此行所有的01代碼連起來作為二進制的取值。

假如某程序有3個虛擬頁面0、1、2,該頁面的訪問次序是0、1、2、2、1、0、2、1。隨著頁面的訪問，矩陣的狀態(tài)變換如圖1中的(a)~(i)所示。

在經(jīng)過一系列的頁面訪問之后，行值最小的是第1行,也就是說，虛頁面0是最近最少被訪問過的頁面。如果此時需要替換某個頁面，則第0個虛擬頁面將被淘汰。

當一個頁面被訪問時，該頁面所對應的行值將被置1，這樣就保證了該頁面對應的行值為最大之一，隨后將該頁面的對應列值置0,以保證該頁面對應的行值為唯一最大。每次訪問都將某一列置0,長時間沒有被訪問的頁面，所對應的行元素里面被置0的列個數(shù)就越多，即它對應的行值就越小。因此,

用矩陣的方法可以實現(xiàn)接近理想算法的頁面置換。

圖1矩陣的狀態(tài)變換

3結語

使用矩陣法相比其它頁面淘汰算法有其突出的優(yōu)點，因為可以使用矩陣的理論來迅速判斷哪個矩陣行值最小。即：當需要替換掉某一頁時，哪個頁面將能被最先淘汰掉。使用矩陣來實現(xiàn)LRU的成本也比其它的算法要低，因為矩陣的行列數(shù)并不需要虛擬頁面數(shù)，而是內存的實際頁面數(shù)，而實際頁面數(shù)則要小得多。另外，它的缺點是矩陣太大，總的存儲位是頁面數(shù)的平方。

20210916_614358ce1bf72__使用矩陣實現(xiàn)LRU的頁面置換算法