頁面置換算法模擬 實驗報告材料
word中北大學軟件學院實 驗 報 告 專 業(yè) 軟件工程 課程名稱 計算機操作系統(tǒng) 學 號 姓 名 輔導教師 靜 成績實驗日期實驗時間1實驗名稱 :實驗四 頁面置換算法模擬2、實驗目的1了解存分頁管理策略2掌握調(diào)頁策略3掌握一般常用的調(diào)度算法4學會各種存儲分配算法的實現(xiàn)方法。5了解頁面大小和存實際容量對命中率的影響。3、實驗要求編程實現(xiàn)頁面置換算法,最少實現(xiàn)兩種算法,比擬算法的優(yōu)劣,并將調(diào)試結果顯示在計算機屏幕上,并檢測機算和筆算的一致性。1采用頁式分配存儲方案,通過分別計算不同算法的命中率來比擬算法的優(yōu)劣,同時也考慮頁面大小與存實際容量對命中率的影響;2實現(xiàn)OPT 算法 (最優(yōu)置換算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模擬;3使用某種編程語言模擬頁面置換算法。4、實驗算法描述1FIFO先進先出開始頁面走向存入數(shù)組p中,內(nèi)存塊用page表示初始化為0當前p中第i個元素是否已在內(nèi)存中i+YPage是否有空NN把pi的內(nèi)容直接裝入最上面一個空內(nèi)存塊,i+把page中最先裝入的頁面置換出去.i+Y輸出當前內(nèi)存塊狀態(tài) 完畢圖4-1FIFO算法流程圖 開始2 LRU最近最久未使用頁面走向存入數(shù)組p中,內(nèi)存塊用page表示初始化為0當前p中第i個元素是否已在內(nèi)存i+YNPage是否有空Y N把pi的內(nèi)容直接裝入最上面一個空內(nèi)存塊,i+把page中最近最久未使用的頁面置換出去.i+輸出當前內(nèi)存塊狀態(tài) 完畢圖4-2 LRU算法流程圖3OPT最優(yōu)置換算法 開始頁面走向存入數(shù)組p中,內(nèi)存塊用page表示初始化為0當前p中第i個元素是否已在內(nèi)存i+YPage是否有空NY N把pi的內(nèi)容直接裝入最上面一個空內(nèi)存塊,i+把page中以后一段時間都不使用或是使用時間離現(xiàn)在最遠的換出.i+輸出當前內(nèi)存塊狀態(tài) 完畢圖4-3 OPT 流程圖6、實驗代碼#include <iostream>using namespace std;#define Bsize 3#define Psize 20struct pageInforint content; /頁面號int timer; /被訪問標記;class PRApublic: PRA(void);int findSpace(void); /查找是否有空閑存int findExist(int curpage); /查找存中是否有該頁面int findReplace(void); /查找應予置換的頁面void display(void); /顯示void FIFO(void);/FIFO算法void LRU(void);/LRU算法void Optimal(void);/OPTIMAL算法void BlockClear(void);/BLOCK恢復pageInfor * block;/物理塊pageInfor * page;/頁面號串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+)pagei.content = QStringi;pagei.timer = 0;int PRA:findSpace(void)for(int i=0; i<Bsize; i+)if(blocki.content = -1)return i;/找到空閑存,返回BLOCK中位置return -1;int PRA:findExist(int curpage)for(int i=0; i<Bsize; i+)if(blocki.content = pagecurpage.content)return i;/找到存中有該頁面,返回BLOCK中位置return -1;int PRA:findReplace(void)int pos = 0;for(int i=0; i<Bsize; i+)if(blocki.timer >= blockpos.timer)pos = i;/找到應予置換頁面,返回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 exist,space,position ;for(int i=0; i<Psize; i+) exist = findExist(i);if(exist != -1) cout<<"不缺頁"<<endl; else space = findSpace();if(space != -1)blockspace = pagei; display();elsefor(int k=0; k<Bsize; k+)for(int j=i; j<Psize; j+)if(blockk.content != pagej.content) blockk.timer = 1000; /將來不會用,設置TIMER為一個很大數(shù)elseblockk.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<<"不缺頁"<<endl;blockexist.timer = -1;/恢復存在的并剛訪問過的BLOCK中頁面TIMER為-1else space = findSpace();if(space != -1)blockspace = pagei; display();elseposition = 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 = findExist(i);if(exist != -1)cout<<"不缺頁"<<endl;else space = findSpace();if(space != -1)blockspace = pagei; display();elseposition = findReplace();blockposition = pagei; display();for(int j=0; j<Bsize; j+)blockj.timer+;/BLOCK中所有頁面TIMER+void PRA:BlockClear(void)for(int i=0; i<Bsize; i+)blocki.content = -1;blocki.timer = 0;void main(void)cout<<"頁 面 置 換 算 法:"<<endl;cout<<"頁面號引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"<<endl;cout<<"選擇<1>應用LRU算法"<<endl;cout<<"選擇<2>應用FIFO算法"<<endl;cout<<"選擇<3>應用Optimal算法"<<endl;cout<<"選擇<0>退出"<<endl;int select;PRA test;while(select)cin>>select;switch(select)case 0:break;case 1:cout<<"LRU算法結果如下:"<<endl;test.LRU();test.BlockClear();cout<<"-"<<endl;break;case 2:cout<<"FIFO算法結果如下:"<<endl;test.FIFO();test.BlockClear();cout<<"-"<<endl;break;case 3: cout<<"Optimal算法結果如下:"<<endl;test.Optimal();test.BlockClear();cout<<"-"<<endl;break;default:cout<<"請輸入正確功能號"<<endl;break;6、實驗結果7、實驗心得加深了對操作系統(tǒng)的認識,了解了操作系統(tǒng)中各種資源分配算法的實現(xiàn),特別是對虛擬存儲,頁面置換有了深入的了解,并能夠用高級語言進展模擬演示。在這短短的兩周時間里,通過瀏覽、閱讀有關的資料,學到了很多東西,同時也發(fā)現(xiàn)僅僅書本的知識是遠遠不夠的,需要把知識運用到實踐中去,能力才能得到提高。使用MFC可視化編程極大的減少了編寫的代碼量,直觀的界面設計,不但便于修改,而且簡化了界面程序代碼的編寫兩種頁面置換算法FIFO和LRU理解起來相當容易,但在實際編程實現(xiàn)的時候需要注意各種細節(jié),需要耐心細致,實際編程中遇到一些細節(jié)上的小問題確實需要仔細考慮才行。14 / 14