1、中北大學(xué)軟件學(xué)院實(shí) 驗(yàn) 報(bào) 告 專 業(yè) 軟件工程 課程名稱 計(jì)算機(jī)操作系統(tǒng) 學(xué) 號(hào) 姓 名 輔導(dǎo)教師 張 靜 成績(jī) 實(shí)驗(yàn)日期2015.11.20實(shí)驗(yàn)時(shí)間1實(shí)驗(yàn)名稱 ：實(shí)驗(yàn)四 頁(yè)面置換算法模擬2、實(shí)驗(yàn)?zāi)康模?）了解內(nèi)存分頁(yè)管理策略（2）掌握調(diào)頁(yè)策略（3）掌握一般常用的調(diào)度算法（4）學(xué)會(huì)各種存儲(chǔ)分配算法的實(shí)現(xiàn)方法。（5）了解頁(yè)面大小和內(nèi)存實(shí)際容量對(duì)命中率的影響。3、實(shí)驗(yàn)要求編程實(shí)現(xiàn)頁(yè)面置換算法，最少實(shí)現(xiàn)兩種算法，比較算法的優(yōu)劣，并將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上，并檢測(cè)機(jī)算和筆算的一致性。（1）采用頁(yè)式分配存儲(chǔ)方案，通過(guò)分別計(jì)算不同算法的命中率來(lái)比較算法的優(yōu)劣，同時(shí)也考慮頁(yè)面大小及內(nèi)存實(shí)際容量對(duì)命中率

2、的影響；（2）實(shí)現(xiàn)OPT 算法 (最優(yōu)置換算法)、LRU 算法 (Least Recently)、 FIFO 算法 (First IN First Out)的模擬；（3）使用某種編程語(yǔ)言模擬頁(yè)面置換算法。4、實(shí)驗(yàn)算法描述（1）FIFO（先進(jìn)先出）開(kāi)始頁(yè)面走向存入數(shù)組p中，內(nèi)存塊用page表示初始化為0 當(dāng)前p中第i個(gè)元素是否已在內(nèi)存中 i+ Y Page是否有空 N N把pi的內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊，i+把page中最先裝入的頁(yè)面置換出去.i+ Y 輸出當(dāng)前內(nèi)存塊狀態(tài) 結(jié)束圖4-1FIFO算法流程圖 開(kāi)始（2） LRU（最近最久未使用）頁(yè)面走向存入數(shù)組p中，內(nèi)存塊用page表示初始化為

3、0當(dāng)前p中第i個(gè)元素是否已在內(nèi)存i+ Y NPage是否有空 Y N把pi的內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊，i+把page中最近最久未使用的頁(yè)面置換出去.i+輸出當(dāng)前內(nèi)存塊狀態(tài) 結(jié)束圖4-2 LRU算法流程圖（3）OPT（最佳置換算法） 開(kāi)始頁(yè)面走向存入數(shù)組p中，內(nèi)存塊用page表示初始化為0當(dāng)前p中第i個(gè)元素是否已在內(nèi)存i+ YPage是否有空 N Y N把pi的內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊，i+把page中以后一段時(shí)間都不使用或是使用時(shí)間離現(xiàn)在最遠(yuǎn)的換出.i+輸出當(dāng)前內(nèi)存塊狀態(tài) 結(jié)束圖4-3 OPT 流程圖6、實(shí)驗(yàn)代碼#include using namespace std;#defin

4、e 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);/OPTIMA

5、L算法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; iBsize; i+)blocki.content = -1;blocki.timer = 0;page = new pageInforPsize;for(i=0; iPsize; i+)pagei.conten

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

7、os = 0;for(int i=0; i= blockpos.timer)pos = i;/找到應(yīng)予置換頁(yè)面，返回BLOCK中位置return pos;void PRA:display(void)for(int i=0; iBsize; i+)if(blocki.content != -1)coutblocki.content ;coutendl;void PRA:Optimal(void)int exist,space,position ;for(int i=0; iPsize; i+) exist = findExist(i);if(exist != -1) cout不缺頁(yè)endl; e

8、lse space = findSpace();if(space != -1)blockspace = pagei; display();elsefor(int k=0; kBsize; k+)for(int j=i; jPsize; j+)if(blockk.content != pagej.content) blockk.timer = 1000; /將來(lái)不會(huì)用，設(shè)置TIMER為一個(gè)很大數(shù)elseblockk.timer = j;break;position = findReplace(); blockposition = pagei; display();void PRA:LRU(voi

9、d)int exist,space,position ;for(int i = 0; i Psize; i+)exist = findExist(i);if(exist != -1)cout不缺頁(yè)endl;blockexist.timer = -1;/恢復(fù)存在的并剛訪問(wèn)過(guò)的BLOCK中頁(yè)面TIMER為-1else space = findSpace();if(space != -1)blockspace = pagei; display();elseposition = findReplace();blockposition = pagei; display();for(int j=0; jB

10、size; j+)blockj.timer+;void PRA:FIFO(void)int exist,space,position ;for(int i=0; iPsize; i+)exist = findExist(i);if(exist != -1)cout不缺頁(yè)endl;else space = findSpace();if(space != -1)blockspace = pagei; display();elseposition = findReplace();blockposition = pagei; display();for(int j=0; jBsize; j+)bloc

11、kj.timer+;/BLOCK中所有頁(yè)面TIMER+void PRA:BlockClear(void)for(int i=0; iBsize; i+)blocki.content = -1;blocki.timer = 0;void main(void)cout頁(yè) 面 置 換 算 法:endl;cout頁(yè)面號(hào)引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1endl;cout選擇應(yīng)用LRU算法endl;cout選擇應(yīng)用FIFO算法endl;cout選擇應(yīng)用Optimal算法endl;cout選擇退出select;switch(select)case 0:b

12、reak;case 1:coutLRU算法結(jié)果如下:endl;test.LRU();test.BlockClear();cout-endl;break;case 2:coutFIFO算法結(jié)果如下:endl;test.FIFO();test.BlockClear();cout-endl;break;case 3: coutOptimal算法結(jié)果如下:endl;test.Optimal();test.BlockClear();cout-endl;break;default:cout請(qǐng)輸入正確功能號(hào)endl;break;6、實(shí)驗(yàn)結(jié)果7、實(shí)驗(yàn)心得加深了對(duì)操作系統(tǒng)的認(rèn)識(shí),了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn),特別是對(duì)虛擬存儲(chǔ),頁(yè)面置換有了深入的了解,并能夠用高級(jí)語(yǔ)言進(jìn)行模擬演示。在這短短的兩周時(shí)間里，通