(LRU)置換算法-操作系統(tǒng)

1、實(shí)驗(yàn)報(bào)告三內(nèi)存頁面置換算法的設(shè)計(jì)姓名：田玉祥 班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)一班實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)最近最久未使用LRU置換算法二、實(shí)驗(yàn)?zāi)康腖INUX中，為了提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制，內(nèi)存空間的分配和回收均以頁為單位進(jìn)行，一個(gè)進(jìn)程只需將其一局部調(diào)入內(nèi)存便可運(yùn)行，還支持請(qǐng)求調(diào)頁的存儲(chǔ)管理方式。本實(shí)習(xí)要求學(xué)生通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式存儲(chǔ)管理的頁面置換算法。三、實(shí)驗(yàn)題目1. 最近最久未使用LRU置換算法原理就是：當(dāng)需要淘汰某頁面時(shí)，選擇當(dāng)前一段時(shí)間內(nèi)最久未使用過的頁先淘汰，即淘汰距當(dāng)前最遠(yuǎn)的上次使用的頁。例如: 分配給該進(jìn)程的頁塊數(shù)為3，一

2、個(gè)20位長(zhǎng)的頁面訪問序列為:12560,36536,56042,70435， 那么缺頁次數(shù)和缺頁率按以下圖給出: 假定分配給該進(jìn)程的頁塊數(shù)為3，頁面訪問序列長(zhǎng)度為20。本實(shí)驗(yàn)可以采用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)，首先隨機(jī)產(chǎn)生頁面序列，當(dāng)發(fā)生請(qǐng)求調(diào)頁時(shí)，假設(shè)內(nèi)存已滿，那么需要利用LRU算法，將當(dāng)前一段時(shí)間內(nèi)最久未使用過的頁替換出去。程序?qū)崿F(xiàn)想法：用一個(gè)數(shù)組an來存放所有需要訪問的頁，用一個(gè)數(shù)組b3來存放頁表，用數(shù)組c3來存放頁表每一頁的權(quán)值，就是最近最少使用的度，度越高那么使用率越小，用n次循環(huán)，每次ai進(jìn)行判斷時(shí)先判斷有沒有空格，再判斷ai是否已經(jīng)在頁表中，此時(shí)注意要將權(quán)值歸1，假設(shè)都沒有這些情況，那么用函數(shù)

3、int MAX(int a,int b,int c)找到權(quán)值最大的，進(jìn)行替換，并將其他頁的權(quán)值加1.實(shí)驗(yàn)代碼：/LRU算法，最近最少使用的頁替換算法#include#include using namespace std ;int MAX(int a,int b,int c)/賦值之后的權(quán)值中找到權(quán)值最大的，返回它的下標(biāo)也就是最近最少使用的int max = a ;if(maxb)max = b ;if(maxc)max = c ;elseif(maxc)max = c ;if(a=max)/找到權(quán)值最大的數(shù)的下標(biāo)return 0 ;else if(b=max)return 1 ;else i

4、f(c=max)return 2 ;int main()/string k ;/k表示當(dāng)前最近最少使用的頁;int i,j,n,l,m,p,q ;/j表示當(dāng)前訪問的頁是否已經(jīng)在訪問,0表示沒有發(fā)生缺頁，1表示發(fā)生缺頁/q來表示頁表是否有空格，即當(dāng)前是否全部在使用，1表示全部在使用，0表示還有空格string *b = new string 3 ;/存放頁表int *c = new int 3 ;/存放頁表的權(quán)值for(i=0;i3;i+)bi = ;ci = 1 ;cout請(qǐng)輸入要訪問的頁碼頁數(shù)： n ;string *a = new string n ;/存放所有要訪問的頁cout請(qǐng)輸入 n

5、 個(gè)每一次要訪問的頁碼頁號(hào)：endl ;for(i=0;iai ;cout頁表訪問過程如下，“1表示發(fā)生缺頁，“0表示不發(fā)生缺頁：endl ;for(i=0;in;i+)j = 1 ;q = 1 ;/表示頁表沒有空位，全被使用for(l=0;l3;l+)if(ai=bl)j = 0 ;cl=1 ;/將權(quán)值設(shè)為1cl-1+;cl-2+;cl+1+;cl+2+;break ;if(j=0)/如果需要訪問的頁正在被訪問，即已經(jīng)在頁表，直接輸出。并將其權(quán)值設(shè)為1for(l=0;l3;l+)coutbl ;coutjendl ;/如果訪問的頁發(fā)生缺頁有兩種情況if(j=1)/第一種，頁表有空閑幀for(

6、l=0;l3;l+)if(bl= )bl=ai ;cl-1+ ;cl-2+ ;for(p=0;p3;p+)coutbp ;coutjendl ;q = 0 ;break ;if(j=1&q=1)/須要訪問的頁不在頁表中m = MAX(c0,c1,c2) ;bm=ai ;cm=1 ;cm-1+;cm-2+;cm+1+;cm+2+;for(p=0;p3;p+)coutbp ;coutjendl ;system(pause) ;return 0 ;代碼實(shí)現(xiàn)：四、思考題： 比較LRU和其他置換算法各自的優(yōu)缺點(diǎn)，能夠?qū)崿F(xiàn)其他置換算法模擬設(shè)計(jì)，分析內(nèi)存頁面數(shù)的變化對(duì)各種置換算法命中率的影響。答：內(nèi)存頁面數(shù)越多，命中率越高，因?yàn)樗许摱际褂煤?，發(fā)生缺頁下次命中時(shí)有更多的頁可以與當(dāng)前需要的頁進(jìn)行比較，所以命中率較高。LRU算法可以減少頁錯(cuò)誤率,較易理解.最優(yōu)算法頁錯(cuò)誤最低,且沒有Belady異常,但是較難實(shí)現(xiàn)FIFO算法容易理解和實(shí)現(xiàn),但是頁錯(cuò)誤率較高實(shí)驗(yàn)總結(jié)通過本次實(shí)驗(yàn)明白了LRU算法的過程，通過編程得知LRU算法發(fā)生缺頁時(shí)的兩種情況，第一種是頁表有空閑的幀但是沒有當(dāng)前所需要的頁，另外一種是沒有空閑幀也沒有當(dāng)前所需要的頁，要分兩種情況