引言

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

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

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

1LRU算法的提出

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

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

1.2LRU頁面置換算法

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

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

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

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

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

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

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

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

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

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

3結(jié)語

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

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