操作系統(tǒng)實(shí)驗(yàn)報(bào)告頁(yè)面置換VIP

1、實(shí)驗(yàn)三 內(nèi)存頁(yè)面置換算法的設(shè)計(jì)l 實(shí)習(xí)內(nèi)容設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法來(lái)模擬實(shí)現(xiàn)頁(yè)面的置換： 1. 先進(jìn)先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置換算法（OPT）l 實(shí)習(xí)目的本實(shí)習(xí)要求學(xué)生通過(guò)請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的技術(shù)特點(diǎn)，掌握請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。LINUX中，為了提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制，內(nèi)存空間的分配和回收均以頁(yè)為單位進(jìn)行，一個(gè)進(jìn)程只需將其一部分（段或頁(yè)）調(diào)入內(nèi)存便可運(yùn)行，還支持請(qǐng)求調(diào)頁(yè)的存儲(chǔ)管理方式。當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，發(fā)現(xiàn)其所在頁(yè)面不在內(nèi)存，就立即提出請(qǐng)求（

2、向CPU發(fā)出缺中斷），由系統(tǒng)將其所需頁(yè)面調(diào)入內(nèi)存。這種頁(yè)面調(diào)入方式叫請(qǐng)求調(diào)頁(yè)。 當(dāng)CPU接收到缺頁(yè)中斷信號(hào)，中斷處理程序先保存現(xiàn)場(chǎng)，分析中斷原因，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過(guò)查找頁(yè)表，得到該頁(yè)所在外存的物理塊號(hào)。如果此時(shí)內(nèi)存未滿，能容納新頁(yè)，則啟動(dòng)磁盤(pán)I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須按某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出，是否重新寫(xiě)盤(pán)由頁(yè)表的修改位決定，然后將缺頁(yè)調(diào)入，修改頁(yè)表。利用修改后的頁(yè)表，去形成所要訪問(wèn)數(shù)據(jù)的物理地址，再去訪問(wèn)內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過(guò)程對(duì)用戶是透明的。l 實(shí)習(xí)原理算法思想：1先進(jìn)先出(FIFO)置換算法的思路該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)

3、面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按照先后次序連接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，使它總指向最老的頁(yè)面。2最近久未使用(LRU)置換算法的思路最近久未使用置換算法的替換規(guī)則，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況來(lái)進(jìn)行決策的。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁(yè)面的時(shí)候選擇現(xiàn)有頁(yè)面中其時(shí)間值最大的進(jìn)行淘汰。3.最佳（OPT）置換算法的思路其所選擇的被淘汰的頁(yè)面，獎(jiǎng)是以后不使用的，或者是在未來(lái)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，采用最佳算法，通?？杀ＷC獲得最低的缺頁(yè)率。l 實(shí)習(xí)編程思路和流程數(shù)據(jù)結(jié)構(gòu)s

4、truct pageInforint content;/頁(yè)面號(hào)int timer;/被訪問(wèn)標(biāo)記;class PRApublic: PRA(void);int findSpace(void); /查找是否有空閑內(nèi)存int findExist(int curpage); /查找內(nèi)存中是否有該頁(yè)面int findReplace(void); /查找應(yīng)予置換的頁(yè)面void display(void); /顯示void FIFO(void); /FIFO算法void LRU(void); /LRU算法void BlockClear(void);/BLOCK清空，以便用另一種方法重新演示pageInfor

5、 * block; /物理塊pageInfor * page; /頁(yè)面號(hào)串private:;Ø FIFO頁(yè)面置換算法當(dāng)需要訪問(wèn)一個(gè)新的頁(yè)面時(shí)，首先調(diào)用findExist(i)函數(shù)來(lái)查看物理塊中是否就有這個(gè)頁(yè)面，若要查看的頁(yè)面物理塊中就有，則調(diào)用display函數(shù)直接顯示，不需要替換頁(yè)面；如果要查看的頁(yè)面物理塊中沒(méi)有，就需要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁(yè)面放入；若沒(méi)有空閑物理塊，則調(diào)用findReplace函數(shù)替換頁(yè)面。并將物理塊中所有頁(yè)面timer+。Ø LRU頁(yè)面置換算法當(dāng)需要訪問(wèn)一個(gè)新的頁(yè)面時(shí)，首先調(diào)用findExist(i)函數(shù)來(lái)查看物理塊中是否就有這

6、個(gè)頁(yè)面Ø OPT頁(yè)面置換算法當(dāng)需要訪問(wèn)一個(gè)新的頁(yè)面時(shí)，也首先調(diào)用findExist(i)函數(shù)來(lái)查看物理塊中是否就有這個(gè)頁(yè)面尋找應(yīng)予置換頁(yè)面函數(shù)findReplace比較三個(gè)物理塊中的時(shí)間標(biāo)記timer，找到時(shí)間最久的。開(kāi)始取一條指令取指令中訪問(wèn)的頁(yè)號(hào)=>L查 頁(yè) 表頁(yè)標(biāo)記=1？形成絕對(duì)地址是“存”指令？置L頁(yè)修改標(biāo)記“1”輸出絕對(duì)地址輸出“*頁(yè)號(hào)”有后繼指令？取一條指令結(jié) 束J:=PkJ頁(yè)的修改標(biāo)記=1？輸出“OUTj”輸出“INL”P(pán)k:=L k:=(k+1) mod m修改頁(yè)面是否是否否（產(chǎn)生缺頁(yè)中斷）是否程序流程圖l 源程序結(jié)構(gòu)分析程序結(jié)構(gòu)程序共有以下九個(gè)部分：int f

7、indSpace(void);/查找是否有空閑內(nèi)存int findExist(int curpage);/查找內(nèi)存中是否有該頁(yè)面int findReplace(void);/查找應(yīng)予置換的頁(yè)面void display(void);/顯示void FIFO(void);/FIFO算法void LRU(void);/LRU算法void OPT(void);/OPT算法；void BlockClear(void);/BLOCK清空，以便用另一種方法重新演示int main() /主程序10 / 10文檔可自由編輯打印Ø 源程序代碼#include <iostream.h>#de

8、fine Bsize 3#define Psize 20struct pageInforint content;/頁(yè)面號(hào)int timer;/被訪問(wèn)標(biāo)記;class PRApublic: PRA(void);int findSpace(void);/查找是否有空閑內(nèi)存int findExist(int curpage);/查找內(nèi)存中是否有該頁(yè)面int findReplace(void);/查找應(yīng)予置換的頁(yè)面void display(void);/顯示void FIFO(void);/FIFO算法void LRU(void);/LRU算法void Optimal(void);/OPTIMAL算法

9、void BlockClear(void);/BLOCK恢復(fù)pageInfor * block;/物理塊pageInfor * page;/頁(yè)面號(hào)串private:;PRA:PRA(void)int QString20=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1; block = new pageInforBsize;for(int i=0; i<Bsize; i+) blocki.content = -1; blocki.timer = 0;page = new pageInforPsize;for(i=0; i<Psize; i+) page

10、i.content = QStringi; pagei.timer = 0;int PRA:findSpace(void)for(int i=0; i<Bsize; i+) if(blocki.content = -1) return i;/找到空閑內(nèi)存，返回BLOCK中位置return -1;int PRA:findExist(int curpage)for(int i=0; i<Bsize; i+) if(blocki.content = pagecurpage.content) return i;/找到內(nèi)存中有該頁(yè)面，返回BLOCK中位置return -1;int PRA:f

11、indReplace(void)int pos = 0;for(int i=0; i<Bsize; i+) if(blocki.timer >= blockpos.timer) pos = i;/找到應(yīng)予置換頁(yè)面，返回BLOCK中位置return pos;void PRA:display(void)for(int i=0; i<Bsize; i+) if(blocki.content != -1) cout<<blocki.content<<" "cout<<endl;void PRA:Optimal(void)int

12、exist,space,position ;for(int i=0; i<Psize; i+) exist = findExist(i); if(exist != -1) cout<<"不缺頁(yè)"<<endl; else space = findSpace(); if(space != -1) blockspace = pagei; display(); else for(int k=0; k<Bsize; k+) for(int j=i; j<Psize; j+) if(blockk.content != pagej.content

13、) blockk.timer = 1000; /將來(lái)不會(huì)用，設(shè)置TIMER為一個(gè)很大數(shù) else blockk.timer = j; break; position = findReplace(); blockposition = pagei; display(); void PRA:LRU(void)int exist,space,position ;for(int i=0; i<Psize; i+) exist = findExist(i); if(exist != -1) cout<<"不缺頁(yè)"<<endl; blockexist.tim

14、er = -1;/恢復(fù)存在的并剛訪問(wèn)過(guò)的BLOCK中頁(yè)面TIMER為-1 else space = findSpace(); if(space != -1) blockspace = pagei; display(); else position = findReplace(); blockposition = pagei; display(); for(int j=0; j<Bsize; j+) blockj.timer+;void PRA:FIFO(void)int exist,space,position ;for(int i=0; i<Psize; i+) exist =

15、findExist(i); if(exist != -1) cout<<"不缺頁(yè)"<<endl; else space = findSpace(); if(space != -1) blockspace = pagei; display(); else position = findReplace(); blockposition = pagei; display(); for(int j=0; j<Bsize; j+) blockj.timer+;/BLOCK中所有頁(yè)面TIMER+void PRA:BlockClear(void)for(in

16、t i=0; i<Bsize; i+) blocki.content = -1; blocki.timer = 0;void main(void)cout<<"|-頁(yè) 面 置 換 算 法-|"<<endl;cout<<"|-power by wangxinchuang(080501228)-|"<<endl;cout<<"|-|"<<endl; cout<<"頁(yè)面號(hào)引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,

17、1,7,0,1"<<endl;cout<<"-"<<endl;cout<<"選擇<1>應(yīng)用Optimal算法"<<endl;cout<<"選擇<2>應(yīng)用FIFO算法"<<endl;cout<<"選擇<3>應(yīng)用LRU算法"<<endl;cout<<"選擇<0>退出"<<endl;int select;PRA t

18、est;while(select) cin>>select; switch(select) case 0: break; case 1: cout<<"Optimal算法結(jié)果如下:"<<endl; test.Optimal(); test.BlockClear(); cout<<"-"<<endl; break; case 2: cout<<"FIFO算法結(jié)果如下:"<<endl; test.FIFO(); test.BlockClear(); cout<<"-"<<endl; break; case 3: cout<<"LRU算法結(jié)果如下