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

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

2、如：分配給該進(jìn)程的頁(yè)塊數(shù)為3, 一個(gè)20位長(zhǎng)的頁(yè)面訪問(wèn)序列為：12560,36536,56042,70435則缺頁(yè)次數(shù)和缺頁(yè)率按下圖給出序 列12550365360427°435111666666666666777332220005b55564440°0555333333hIo01 21 221 444殿頁(yè)是是nJE1是是是是是是是是是日 7H 7EO 7E圖3-1缺頁(yè)欷數(shù)：15缺質(zhì)率：15/20=0. 75假定分配給該進(jìn)程的頁(yè)塊數(shù)為 3,頁(yè)面訪問(wèn)序列長(zhǎng)度為20。本實(shí) 驗(yàn)可以采用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)，首先隨機(jī)產(chǎn)生頁(yè)面序列，當(dāng)發(fā)生請(qǐng)求調(diào)頁(yè) 時(shí)，若內(nèi)存已滿，則需要利用 LRU算法，將當(dāng)

3、前一段時(shí)間內(nèi)最久未 使用過(guò)的頁(yè)替換出去。聞Xf程序?qū)崿F(xiàn)想法：用一個(gè)數(shù)組an來(lái)存放所有需要訪問(wèn)的頁(yè)，用一個(gè)數(shù)組b3來(lái)存放頁(yè)表，用數(shù)組c3 來(lái)存放頁(yè)表每一頁(yè)的權(quán)值，就是最近最少使用的度，度越高則使用率越小，用n次循環(huán)，每次ai進(jìn)行判斷時(shí)先判斷 有沒(méi)有空格，再判斷ai是否已經(jīng)在頁(yè)表中，此時(shí)注意要將權(quán)值歸1, 若都沒(méi)有這些情況，則用函數(shù)int MAX(int a,int b,int c) 找到權(quán)值最大的，進(jìn)行替換，并將其他頁(yè)的權(quán)值加 1.實(shí)驗(yàn)代碼：/LRU 算法，最近最少使用的頁(yè)替換算法#include<iostream>#include <string>using names

4、pace std ;int MAX(int a,int b,int c)/賦值之后的權(quán)值中找到權(quán)值最大的，返回它的下標(biāo)也就是最近最少使用的int max = a ;if(max<b)max = b ;if(max<c)max = c ;elseif(max<c)/找到權(quán)值最大的數(shù)的下標(biāo)max = c ;if(a=max)return 0 ;else if(b=max)return 1 ;else if(c=max)return 2 ;int main()/ string k ;/k 表示當(dāng)前最近最少使用的頁(yè);int i,j,n,l,m,p,q ;/j 表示當(dāng)前訪問(wèn)的頁(yè)是否已經(jīng)

5、在訪問(wèn) ,0 表示沒(méi)有發(fā)生缺頁(yè)， 1 表示發(fā)生缺頁(yè)在使用， 1 表示全部在使用，0 表示還有空格string *b = new string 3 ;/q 來(lái)表示頁(yè)表是否有空格， 即當(dāng)前是否全部/存放頁(yè)表int *c = new int 3 ;/存放頁(yè)表的權(quán)值for(i=0;i<3;i+)bi=""ci = 1 ；)coutvv”請(qǐng)輸入要訪問(wèn)的頁(yè)碼頁(yè)數(shù)："«endl ;cin » n ;string *a = new string n ;/存放所有要訪問(wèn)的貢coutvv”請(qǐng)輸入"«n«"個(gè)每一次要訪問(wèn)

6、的頁(yè)碼頁(yè)號(hào)："«endl;for(i=0;i<n;i+)cin»ai;coutvv”頁(yè)表訪問(wèn)過(guò)程如下，“1”表示發(fā)生缺頁(yè)，“0”表示不發(fā)生缺頁(yè)：“vvendl;for(i=0;i<n;i+)(j = 1 ；q = 1 ；/表示頁(yè)表沒(méi)有空位，全被使用for(l=0;l<3;l+)if(ai=bl)(j = 0 ;cl=1 ;/將權(quán)值設(shè)為1cl-1+；cl-2+;cl+1+;cl+2+;break;)if(j=O)/如果需要訪問(wèn)的頁(yè)正在被訪問(wèn)，即已經(jīng)在頁(yè)表，直接輸出。并將其權(quán)值設(shè)為1(for(l=0;l<3;l+)cout«bl

7、71;" "cout«j«endl;)/如果訪問(wèn)的頁(yè)發(fā)生缺頁(yè)有兩種情況ifO=1)第一種，頁(yè)表有空閑幀for(l=0;l<3;l+)(if(bl="")(bl=ai;cl-1+ ;cl-2+ ;for(p=0;p<3;p+)cout«bp«" "cout«j«endl;break ;)if(j=1&&q=1)/須要訪問(wèn)的頁(yè)不在頁(yè)表中(m = MAX(c0,c1,c2);bm=ai;cm=1 ;cm-1+;cm-2+;cm+1+;cm+2+;for(

8、p=0;p<3;p+)cout<<bp<<""cout<<j<<endl ;)system("pause");return 0 ;)代碼實(shí)現(xiàn):四、思考題：?比較LRU和其他置換算法各自的優(yōu)缺點(diǎn)，能夠?qū)崿F(xiàn)其他置換算法模擬設(shè) 計(jì)，分析內(nèi)存頁(yè)面數(shù)的變化對(duì)各種置換算法命中率的影響。答：內(nèi)存頁(yè)面數(shù)越多，命中率越高，因?yàn)樗许?yè)都使用后，發(fā)生缺頁(yè)下次命中時(shí)有更多的頁(yè)可以與當(dāng)前需要的頁(yè)進(jìn)行比較，所以命中率較高。LRU算法可以減少頁(yè)錯(cuò)誤率，較易理解.最優(yōu)算法頁(yè)錯(cuò)誤最低，且沒(méi)有Belady異常,但是較難實(shí)現(xiàn)FIFO算法容易理解和實(shí)現(xiàn)，但是頁(yè)錯(cuò)誤率較高五、實(shí)驗(yàn)總結(jié)通過(guò)本次實(shí)驗(yàn)明白了 LRU算法的過(guò)程，通過(guò)編程得知 LRU算法發(fā)生缺頁(yè)時(shí)的兩種情況，第一種是頁(yè)表有空閑的幀但是沒(méi)有當(dāng)前所需 要的頁(yè)，另外一種是