使用矩陣實(shí)現(xiàn)LRU的頁(yè)面置換算法

引言

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

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

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

1LRU算法的提出

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

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

1.2LRU頁(yè)面置換算法

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

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

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

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

在每次需要更換頁(yè)面時(shí)，選擇矩陣?yán)飳?duì)應(yīng)行值最小的頁(yè)面。行值是指把此行所有的01代碼連起來(lái)作為二進(jìn)制的取值。

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

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

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

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

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

3結(jié)語(yǔ)

使用矩陣法相比其它頁(yè)面淘汰算法有其突出的優(yōu)點(diǎn)，因?yàn)榭梢允褂镁仃嚨睦碚搧?lái)迅速判斷哪個(gè)矩陣行值最小。即：當(dāng)需要替換掉某一頁(yè)時(shí)，哪個(gè)頁(yè)面將能被最先淘汰掉。使用矩陣來(lái)實(shí)現(xiàn)LRU的成本也比其它的算法要低，因?yàn)榫仃嚨男辛袛?shù)并不需要虛擬頁(yè)面數(shù)，而是內(nèi)存的實(shí)際頁(yè)面數(shù)，而實(shí)際頁(yè)面數(shù)則要小得多。另外，它的缺點(diǎn)是矩陣太大，總的存儲(chǔ)位是頁(yè)面數(shù)的平方。

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