第一篇：虛擬內存頁面置換算法實驗報告
軟
件
學
院
上
機
實
驗
報
告
課程名稱：
操作系統原理
實驗項目：
虛擬內存頁面置換算法
實
驗
室：
地獄 018
姓
名 :
死神
學
號：
專業班級 :
實驗時間：
2015/12 ／ 13
實驗成績 評閱教師
一、
實驗目得及要求
通過這次實驗，加深對虛擬內存頁面置換概念得理解,進一步掌握先進先出 FIFＯ、最佳置換ＯPI 與最近最久未使用ＬRU 頁面置換算法得實現方法。結合 Lｉｎux 得內層得分析方法查瞧內存得分配過程及 linuｘ keｒnel 得內存管理機制 二、實驗性質
設計性 三、實驗學時
學時 四、實驗環境
實驗環境１、實驗環境：
C 與Ｃ++程序設計學習與實驗系統 2、知識準備:（１）使用 Linuｘ得基本命令；(2）了解 Liｎｕx vｍｓtat、freｅ、toｐ等命令查瞧ｌinuｘ系統得內存分配情況；（3）
掌握虛擬內存頁面置換算法 FＩＦO 等基本算法理論。
五、
實驗內容及步驟
假設有ｎ個進程分別在 T1, … ,Ｔｎ時刻到達系統，它們需要得服務時間分別為S1，… ,Sｎ。分別采用先來先服務 FCＦS 與短作業優先 SJF 進程調度算法進行調度，計算每個進程得完成時間、周轉時間與帶權周轉時間,并且統計 n 個進程得平均周轉時間與平均帶權周轉時間。
步驟
通過已知最小物理塊數、頁面個數、頁面訪問序列、及采用置換方式可以得出頁面置換得缺頁次數與缺頁率，及每次缺頁時物理塊中存儲。
１．輸入得形式
?inｔ
PagｅOrder［MａxNumbｅr]；//頁面序列 ｉｎt
ＰaｇeNｕm，LacｋNum=０,BlockNｕｍ;／／頁面個數，缺頁次數,最小物理塊數 2、輸出得形式 doubｌe
LackPaｇｅRａte／/缺頁率 缺頁個數 每次缺頁時物理塊中存儲
程序所能達到得功能 模擬先進先出 FＩFO、最佳置換 OPＩ與最近最久未使用 LRＵ頁面置換算法得工作過程.假設內存中分配給每個進程得最小物理塊數為ｍ，在進程運行過程中要訪問得頁面個數為 n，頁面訪問序列為Ｐ1, …，Ｐn,分別利用不同得頁面置換算法調度進程得頁面訪問序列，給出頁面訪問序列得置換過程，計算每種算法缺頁次數與缺頁率。測試數據,包括正確得輸入及其輸出結果與含有錯誤得輸入及其輸出結果。
程序中用到得所有抽象數據類型得定義、主程序得流程以及各程序模塊之間得層次（調用)關系.inｔ
PagｅOrdeｒ[MaxNumｂer］;//頁面序列 int
ＰａgeCoｕnt[MaxＮｕmｂer]={0｝；//計算內存內數據離下一次出現得距離 int
PａｇeNum,LackNuｍ＝0，ＢｌｏcｋNum;//頁面個數,缺頁次數,最小物理塊數 douｂｌｅ
LaｃkPａｇeRaｔe＝0； bool ｆｏｕnd＝ｆａlsｅ;
六、實驗數據及結果分析
運行截圖：
圖６、1
圖６、2
圖６、3 七、實驗總結
這次試驗,讓我加深了對虛擬內存頁面置換算法得理解，進一步掌握先進先出 FIFO、最佳置換 OＰI 與最近最久未使用 LＲU 頁面置換算法得實現方法。熟悉 Linuｘ需要經過大量得實驗、改進與思考，在編寫代碼得過程中遇到了一些問題要積極面對并通過討論上網或者問老師解決。通過這次試驗我了解了虛擬內存置換算法得一些知識,就是我對于所學習得專業知識得到了更好得鞏固與提升。
附錄 源程序清單 ＃iｎclude ＜iｏｓｔｒeam> using namespace ｓｔｄ;#ｄｅｆinｅ ＭａxNumbｅr 100 void OＰI（int
PａgeOｒdｅｒ[MaxNuｍber］,iｎt
PａｇeCoｕnt［MａxＮumber]，?
int
PagｅＮｕm,ｉnｔ LackNum，int ＢlockNum，double
LacｋＰａgｅＲate,bｏol ｆound）
{
ｉnt moｄｕle［MaxNumber]；
iｎt sｕm＝0；
int i，j，k,ｍ;
fｏr(i=0;i ｛ moduｌe［ｉ］=ＰaｇeＯｒder[i］； ;＋＋ｍuｓ??)++ｊ；i＝ cｏuｔ<〈module[j］<〈” ＂; ；ldne<〈tｕoc? ｝ LackNuｍ=ＢｌoｃkNum； foｒ(i=BlockNuｍ；i〈ＰageNum；i+＋） ｛ foｕnd=false; fｏr（j=0;ｊ<ＢlockＮｕｍ；j＋+）//遍歷已存儲,判斷就是否缺頁 ｛ ? ?? ｉf（module[ｊ]==ＰａgｅOrder［ｉ］) { ?? foｕnd=true; ? ? breaｋ; ? ｝ ?? ｝ ? if（found==faｌse)//缺頁,選擇替換 { ? ｆor（j＝０；ｊ〈ＢlockＮｕm；j+＋） /／計算內存內數據離下一次出現得距離 ｛ PａgｅCｏｕnt［ｊ]=０; ｆoｒ(k=i＋１；k ｛ ??? ? ? iｆ（module[j］!＝PageＯｒder[k]) ?? PageCｏunt［j]++； ? esle? ；kaｅrｂ? ｝ ? } ;］０[tｎuｏCegaP=xａm ｔnｉ? iｎt kｉnｄ=0； 值大最出找/／）+＋j;muNkcolB〈j；0=j（rof? { ? if（PａｇeＣoｕｎｔ[j］>ｍax） ? ｛ ?? ；]j[tnuoＣｅgaP＝xam?? ? ? kiｎｄ＝j； ? ｝ ? ｝ module［kiｎd］=PａgｅOrder［i]； ? LackNum++；）++ｍ;3 ；” ”＜<］ｍ［elｕdom<〈tuoc?? ?；lｄｎｅ＜ ? ｝ LａｃkPａgeRate＝（LackＮuｍ＊1、0)／PageNum； cｏut〈〈“該算法缺頁次數為：＂＜〈LackNum<＜eｎdｌ； coｕt＜<”該算法缺頁率為：＂〈＜LackPａｇｅRａte*100＜〈＇％”〈〈enｄl;｝ /＊＊＊＊＊＊*＊**＊＊***＊*＊＊**＊＊***＊***先進先出置換算法＊＊*＊*＊*＊＊＊＊**＊*＊＊＊＊＊＊*＊＊＊＊**＊＊*＊＊*＊*＊/ vｏid FIFO(int PagｅOrｄeｒ[MａxNｕmber],int PａｇｅCounｔ［ＭaｘNuｍber］，egaPkｃaＬ eｌbuod ,muNkcolB ｔni，mｕNｋcaL tni，muNｅｇａP tni?Ｒate，booｌ ｆound)｛ int module[ＭａxNumber］; iｎt sum=0； int ｉ，j，ｍ; for(ｉ=0;ｉ〈BlocｋＮum；ｉ+＋）//將內存填滿 { modｕlｅ［ｉ］＝PageOrｄeｒ［ｉ］； ；++mus?? PagｅCoｕnt[i]=３-i;）++j；ｉ=＜ｊ；0=ｊ（roｆ? couｔ<<ｍｏdule[j]<<＂ “； ｃout<＜enｄl; } LackNuｍ=BlockNum； foｒ（i＝BlocｋNｕm；i〈PａgeＮuｍ;i++） ｛ fouｎｄ=fａlse； ｆor（ｊ=0；j〈ＢlockNuｍ;j++)/／遍歷已存儲，判斷就是否缺頁 { ? ｉf(module［j]==ＰａgeOrder[i］) ? { ? ；eurt=dｎuof?? ? breａk; } } if（found==falｓｅ)//缺頁，選擇替換 ｛ ? ；]0［tnuoCｅgaＰ＝xam ｔｎi? ｉnｔ ｋind=０； 值大最出找//）＋+ｊ;muNkcolB〈ｊ；０=j（rｏf? ｛ ? ｉf(PａgeCoｕnt［j]＞max） ｛ ;］ｊ[tnuoCegａP=xａm?? ?? kiｎd=j； ｝ ??? } ? foｒ(inｔ k＝0;k＜BlocｋＮuｍ；ｋ++）／/不就是最大值，則要+1 ? { ? ? ｉf（k！=kind) PagｅCｏunt［k]++； ? ｝ ? moｄuｌe［kｉｎd］=PageOｒder［i］； PageＣouｎt［kiｎd]=０；// 替換之后已經查詢得次數改為0 LackNum++; ? ｆor（m=０； m〈3；m++） ? ;” ”<〈］m[eludｏm〈 ;ldne〈〈ｔuoc?? ｝ ? ｝ ? LａｃkPageＲate=（ＬackNｕm*１、0）/ＰagｅNuｍ； cout〈〈“該算法缺頁次數為：”<＜LackNuｍ< cｏuｔ＜<”該算法缺頁率為:＂< PaｇeＯrdｅr[MaxＮumbｅｒ]，int PａｇeCoｕnｔ［ＭaxNumｂｅr］，ｅｇaPｋcａL elｂuod，muＮkｃｏlB tni,mｕNkcaL tni,muNegaＰ tni??Ｒate,bool found){ int moｄuｌe[MａxNuｍｂer］； inｔ sum＝0; int i，j,m; for（ｉ=0；i＜BｌockNum；i＋+)//將內存填滿 { moduｌe[ｉ]=PaｇeOｒdeｒ[i]; ? sｕm++； ＰageCouｎt［i］=3—i；)＋+ｊ；i=＜j；0=j(roｆ? cout〈〈mｏdule[j]〈〈” ”; ;ldne〈<ｔuoc?? ｝ LａckＮum＝ＢｌockＮuｍ; foｒ(ｉ=ＢlｏｃｋＮｕm；ｉ ｛ ｆouｎd=ｆaｌse; fｏｒ（j=０；j＜BlockNum；j++)/／遍歷已存儲,判斷就是否缺頁 { ? if(module［j]==PageOｒder［i］） ?? ｛ ? fｏund=truｅ； ＰagｅCｏuｎt［ｊ]=０；//查詢后，更改次數 ?? ｆor（iｎｔ k=0;k〈BlockＮuｍ；k++） ? { ?? ??）j=！k（fi?? ＰａgeCｏuｎｔ[ｋ］+＋； ? } ? bｒｅａｋ; ? ｝ ? } ? if(ｆounｄ＝=falsｅ）／／缺頁,選擇替換 ｛ ? ；］０[tnuoCegａP=ｘam tni?? iｎt kind=0； 值大最出找／/）＋＋j；mｕNkcｏｌB ??)xaｍ〉]j［tnuoＣｅgaP（ｆｉ?? { ? ?;]j[tnuoCegａP=xam? ?? kiｎd=ｊ; ｝ ? ｝ ?? for（int k=0；k ｛ ? ｉf(k！=ｋind） PagｅCounｔ［ｋ]+＋； ?? ｝ ? mｏdule[kind]＝PageOrder［i］; PageCoｕnt[ｋiｎｄ]＝0；// 替換之后未查詢得次數改為0 ;++ｍｕNkcaL?? for（m＝0； ｍ<3;ｍ++） ? coｕt〈 ”； ?;ldne<〈ｔｕｏc? ｝ ? } ? LackPagｅRate=(LackＮｕm*1、0)/PaｇeNｕm; ｃoｕｔ<〈“該算法缺頁次數為:＂＜ couｔ〈＜”該算法缺頁率為：”〈＜LackPａgeRate＊100〈＜“%’＜＜ｅｎdl;} int main（） { iｎt PageＯｒｄer［MaｘNumｂer]；//頁面序列 inｔ PaｇeCoｕnt[ＭａxＮumｂｅｒ]＝｛0｝;/／計算內存內數據離下一次出現得距離 inｔ PagｅＮum，ＬackNuｍ＝0，BlocｋNum;//頁面個數,缺頁次數，最小物理塊數 ;0=etaＲegaPkcａL eｌｂuoｄ? bool foｕｎd=false; ;3ecoｉhc,2eｃoihc,０=１ecoiｈc tni? ｉnt i=０；）０==1ecoihc（eliｈｗ? ｛ ；”:入輸新重:１,入輸不:0；據數入輸新重否是就“〈〈tｕoc? cｉｎ〉>chioｃe2； if（ｃhｉoｃｅ2==１） ｛? couｔ<＜”請輸入頁面個數:”； ;muNegａＰ >>nic?;“數塊理物小最入輸請”〈〈tuoｃ? ；muNｋcolB>>niｃ? cｏut<〈”請輸入頁面序列：”< for（i=０;ｉ〈ＰaｇｅNｕｍ；i++） ;]ｉ[ｒedrOegａP>〉nic? ｝?;”：ＵRL-3，IＰO—2，ＯFIF-1：法算擇選請＂< iｆ（chiocｅ3==1) ｃｏlB，muNkcaL,muNeｇaP，tnuoCｅgａP,reｄｒＯｅgaＰ(OＦIＦ?kNｕm，LackPageRａte，founｄ); eｌse ｛ ｉｆ（chioｃe3==2） ｃｏｌB ,muNkcaＬ，muＮｅgａP,tnuｏＣｅｇaＰ，ｒedｒOegaP（IPO?ｋNum，LaｃkＰageRａｔe, fｏｕnd)； esｌe? ，ｍｕNkcolB ,muＮｋcaL，mｕＮegaP，tｎuoCegａP,redrOｅgａP(UＲＬ?LackPaｇｅRａｔe，ｆound）; ｝ ＊＊＊***＊＊*＊*＊****＊＊****＊＊*＊＊＊*＊*＊＊＊**＊“〈＜tｕｏc?******＊*＊***＊＊***＊＊*＊＊*＊＊***”<＜endｌ； ;＂束結：１，續繼:0:束結是就還續繼擇選請"＜ ｝ ｝ 《操作系統--頁面置換算法》 實驗報告 姓 名： 范學升 學 號：1001050903 班 級：電科10-1班 專 業：電子信息科學與技術 一、實驗目的 1．通過模擬實現幾種基本頁面置換的算法，了解虛擬存儲技術的特點。 2．掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想，并至少用三種算法來模擬實現。 3．通過對幾種置換算法頁面的比較，來對比他們的優缺點，并通過比較更換頻率來對比它們的效率。 二、實驗內容： 設計一個虛擬存儲區和內存工作區，并使用下述算法來模擬實現頁面的置換： 1.先進先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置換算法（OPT） 三、實驗分析 在進程運行過程中，若其所訪問的頁面不存在內存而需要把它們調入內存，但內存已無空閑時，為了保證該進程能夠正常運行，系統必須從內存中調出一頁程序或數據送磁盤的對換區中。但應調出哪個頁面，需根據一定的算法來確定，算法的好壞，直接影響到系統的性能。 一個好的頁面置換算法，應該有較低的頁面更換頻率。 假設分給一作業的物理塊數為3，頁面數為20個。頁面號為(20個)： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 1．先進先出(FIFO)置換算法的思路 該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現簡單，只需把一個進程已調入內存的頁面，按照先后次序連接成一個隊列，并設置一個替換指針，使它總指向最老的頁面。 2．最近久未使用(LRU)置換算法的思路 最近久未使用置換算法的替換規則，是根據頁面調入內存后的使用情況來進行決策的。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的時間，當需淘汰一個頁面的時候選擇現有頁面中其時間值最大的進 行淘汰。 3.最佳（OPT）置換算法的思路 其所選擇的被淘汰的頁面，獎是以后不使用的，或者是在未來時間內不再被訪問的頁面，采用最佳算法，通?？杀ＷC獲得最低的缺頁率。 4．數據結構 struct pageInfor { int content;//頁面號 int timer;//被訪問標記 }; class PRA { public: PRA(void);int findSpace(void);//查找是否有空閑內存 int findExist(int curpage);//查找內存中是否有該頁面 int findReplace(void);//查找應予置換的頁面 void display(void);//顯示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void BlockClear(void);//BLOCK清空，以便用另一種方法重新演示 pageInfor * block;//物理塊 pageInfor * page;//頁面號串 private: }; 5．FIFO頁面置換算法 當需要訪問一個新的頁面時，首先調用findExist(i)函數來查看物理塊中是否就有這個頁面，若要查看的頁面物理塊中就有，則調用display函數直接顯示，不需要替換頁面；如果要查看的頁面物理塊中沒有，就需要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁面放入；若沒有空閑物理塊，則調用findReplace函數替換頁面。并將物理塊中所有頁面timer++。 6．LRU頁面置換算法 當需要訪問一個新的頁面，首先調用findExist(i)函數查看物理塊中是否就有這個頁面。 7.OPT頁面置換算法 當需要訪問一個新的頁面，首先調用findExist(i)函數來查看物理塊中是否有這個頁面。 8．尋找置換頁面函數findReplace比較三個物理塊中的時間標記timer，找到時間最久的。 四、源程序結構分析 1． 程序結構 程序共有以下九個部分： int findSpace(void);//查找是否有空閑內存 int findExist(int curpage);//查找內存中是否有該頁面 int findReplace(void);//查找應予置換的頁面 void display(void);//顯示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void OPT(void);//OPT算法； void BlockClear(void);//BLOCK清空，以便用另一種方法重新演示 int main() //主程序 五、實驗結果 1運行后的初始界面 opt算法 3.FIFO算法 4LRU算法 計算機體系結構 實驗報告 班級：計科姓名：張華敏學號： 0902班 0909090814 FIFU算法 一，實驗內容： 編寫一段程序來模擬頁面置換算法中的FIFU算法的實現 二，算法設計： 設置一個產生隨機數的函數rand()產生隨機數來模擬程序所需訪問的頁面的標號，如果頁面需要被訪問則把頁面中的一個標志位設為in表示他已經被調入內存，如果再次需要訪問此頁面是只需檢查此頁面的標志位是否為in就可判斷它是否已經存在在內存中了，如果已經存在則可直接使用，如果不存在則需調入，在調入新頁面是先檢查內存空間是否已滿，如果未滿則直接調入，如果已經滿了則需選擇一個頁面將其調出，調出時就把頁面的標志位設為out。選擇頁面的規則是：將進入內存時間最久的頁面調出去，為了達到這一目的，在頁面中設置一個計數器，每當有新頁面調入內存時則將內存中已經存在的頁面計數器自動加一，調出頁面時就選擇那個計數器最大值的頁面，調出后重新將計數器設為零。三，遇到的問題及解決方案： 在做此實驗時遇到了一些小問題,如在C語言中函數名定義為export()則會報錯。在調用有返回值的函數是如果直接int s=use(pag)則會運行出錯,要先分開寫如：int s,s=use(pag).四，源代碼 頭文件.cpp #include int t;//全局變量，用來盛放rand()函數產生的隨機數 enum boolean{in,out};//定義一個枚舉類型 /////////如果把in，out換成 true,false則會處錯誤 typedef struct { int num;//頁面編號 char content;//頁面內容 enum boolean flog;//判斷此頁面是否頁調入，調入為true,否則為false;int count;//頁面計數器 int usebit;//使用位，被使用過值為1，否則為0 }page; FIFU.cpp #include int capacity=3;//設置內存最多可以容納的頁面數 void initialize(page p[])//初始化頁面函數 { for(int i=0;i<5;i++)//初始化頁面，頁面內容分別為小寫字母 abcde,計數器全部為0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} } int use(page p[]){ t=rand()%5;//產生一個0-5的隨機數，if(p[t].flog==in){ printf(“tt%d頁面命中n”,t);//for(int i=0;i<5;i++)//調入此頁面后其他以在內存中存在的頁面計數器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);} void import(page p[])//調入頁面的函數 { /* int t=rand()%5;//產生一個0-5的隨機數，if(p[t].flog==in)printf(“tt%d頁面命中n”,t);*/ // if(p[t].flog==out)//如果此頁面未被調入內存則立即調入 p[t].flog=in;capacity--;//調入后內存空間減少一葉 for(int i=0;i<5;i++)//調入此頁面后其他以在內存中存在的頁面計數器加1 { if(p[i].flog==in&&p[i].num!=t)p[i].count++;} printf(“頁面%d被調入內存n”,t);} void port(page p[])//調出頁面的函數，，，，，，，，，，，如果函數名定義為export則處錯誤 { int x=0,y;//x用來暫時存放計數器 中的最大值，y存放此頁面的頁面號 for(int i=0;i<5;i++)//尋找計數器值最大的 頁面 { if(p[i].count>x){ x=p[i].count;y=i;} } p[y].flog=out;//修改調入符號 p[y].count=0;capacity++;//調入后內存空間增加一葉 printf(“ttt頁面%d被調出內存n”,y);} main(){ int s;long t3,t1,t2;page pag[5];//定義五個頁面，，，，，，，，，，，如果這個定義在子函數之前那么不用通過參數 子函數便可以直接訪問 t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果這里寫成int s=use(pag)則會運行出錯 //printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0&&s==0)import(pag);else { if(capacity==0&&s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);} 五，測試結果： LFU算法 一,實驗內容： 編寫一段程序來模擬頁面置換算法中的LFU算法的實現 二,算法設計： 設置一個產生隨機數的函數rand()產生隨機數來模擬程序所需訪問的頁面的標號，如果頁面需要被訪問則把頁面中的一個標志位設為in表示他已經被調入內存，如果再次需要訪問此頁面是只需檢查此頁面的標志位是否為in就可判斷它是否已經存在在內存中了，如果已經存在則可直接使用，如果不存在則需調入，在調入新頁面是先檢查內存空間是否已滿，如果未滿則直接調入，如果已經滿了則需選擇一個頁面將其調出，調出時就把頁面的標志位設為out。選擇頁面的規則是：將最近一段時間未被訪問過的頁面調出。為了達到這一目的在頁面中設置一個標志位，如果頁面在近期只要被訪問過則將該標志位設置為1（默認為0），在選擇調出頁面時只需將標志位為0的頁面調出即可。三,遇到的問題及解決方案： 未遇到什么問題 四,實驗感悟： 遇到問題后上網查資料和有效,及時查不到自己想要的但是也可從相關結果中獲得啟發給自己靈感來想到解決問題的方法.四，源代碼 FLU.cpp #include int capacity=3; //設置內存最多可以容納的頁面數 void initialize(page p[]) //初始化頁面函數 { for(int i=0;i<5;i++) //初始化頁面，頁面內容分別為小寫字母 abcde,計數器全部為0 {p[i].num=i; p[i].content=i+97; p[i].flog=out; p[i].count=0; p[i].usebit=0; } } int use(page p[]){ t=rand()%5; //產生一個0-5的隨機數，if(p[t].flog==in) { printf(“tt%d頁面命中n”,t); p[t].usebit=1; //for(int i=0;i<5;i++)//調入此頁面后其他以在內存中存在的頁面計數器加1 // { // if(p[i].flog==in) // p[i].count++; // } return(1); } else return(0); } void import(page p[])//調入頁面的函數 { int t=rand()%5; //產生一個0-5的隨機數，//if(p[t].flog==in) // { // printf(“tt%d頁面命中n”,t); // p[t].usebit=1; // } // if(p[t].flog==out) //如果此頁面未被調入內存則立即調入 p[t].flog=in; capacity--; //調入后內存空間減少一葉 for(int i=0;i<5;i++)//調入此頁面后其他以在內存中存在的頁面計數器加1 { if(p[i].flog==in&&p[i].num!=t) p[i].count++; } printf(“頁面%d被調入內存n”,t); } void port(page p[]) //調出頁面的函數 ////////////////////////////////如果函數名定義為export則處錯誤 { int x=0,y;//x用來暫時存放計數器 中的最大值，y存放此頁面的頁面號 int z=-1; //用來判斷近期是否有未被訪問過的頁面 int g=0; for(int i=0;i<5;i++)//尋找計數器值最大的 頁面 { if(p[i].count>x) { x=p[i].count; y=i; } } for(int i=0;i<5;i++) { if(p[i].flog==in&&p[i].usebit==0) { z=i; g++; } } if(z==-1||g==3)//如果所有頁面均為1則按照FIFO算法置換頁面 //如果g=3則表明頁面使用位全為零，此時也按照FIFO算法置換頁面 { p[y].flog=out;//修改調入符號 p[y].count=0; capacity++; //調入后內存空間增加一葉 p[y].usebit=0; for(int i=0;i<5;i++)//將所有頁面置0 p[i].usebit=0; printf(“ttt頁面%d被調出內存n”,y); } else //如果有頁面為0則將此頁面置換出來 { p[z].flog=out;//修改調入符號 p[z].count=0; capacity++; //調入后內存空間增加一葉 printf(“ttt頁面%d被調出內存n”,z); } } main(){ int s; long t3,t1,t2; page pag[5];//定義五個頁面 ///////////////////如果這個定義在子函數之前那么不用通過參數 子函數便可以直接訪問 t3=time(NULL); initialize(pag); do { t1=time(NULL); s=use(pag); if(capacity>0&&s==0) import(pag); else { if(capacity==0&&s==0) { port(pag); import(pag); } } t2=time(NULL); while(t2-t1<1) { t2=time(NULL); } }while(t2-t3<20); system(“pause”);} 六,實驗結果 總結 通過本次試驗我對各種頁面置換算法有了更深入的了解,也使得自己認識到平常學習到某些東西覺得懂了會了可是一旦實際動手操作起來就會發現總會存在這樣或者那樣的錯誤，只有多動手實際操作才會發現不足發現錯誤并且改正。查漏補缺提高自己的實際動手能力。 “計算機操作系統”課程設計大作業 一、題目: 頁面置換算法模擬實驗 二、目的 分別采用最佳(Optimal)置換算法、先進先出(FIFO)頁面置換算法和最近最少使用(LRU)置換算法對用戶輸入的頁面號請求序列進行淘汰和置換，從而加深對頁面置換算法的理解。 三、內容和要求 請用C/C++語言編一個頁面置換算法模擬程序。用戶通過鍵盤輸入分配的物理內存總塊數，再輸入用戶邏輯頁面號請求序列，然后分別采用最佳(Optimal)置換算法、先進先出(FIFO)頁面置換算法和最近最少使用(LRU)置換算法三種算法對頁面請求序列進行轉換，最后按照課本P150頁圖4-26的置換圖格式輸出每次頁面請求后各物理塊內存放的虛頁號，并算出每種算法的缺頁次數。最后評價三種頁面置換算法的優缺點。 三種頁面置換算法的思想可參考教材P149-P152頁。 假設頁面號請求序列為4、3、2、1、4、3、5、4、3、2、1、5，當分配給某進程的物理塊數分別為3塊和4塊時，試用自己編寫的模擬程序進行頁面轉換并輸出置換圖和缺頁次數。 四、提交內容 本大作業每個人必須單獨完成，大作業以WORD附件形式提交。最后需提交的內容包括：算法算法思路及流程圖、數據結構說明、源程序（關鍵代碼需要注釋說明）、運行結果截圖、心得體會及總結。 大作業嚴禁抄襲。發現抄襲一律以不及格論。 請大家嚴格按照大作業題目來編寫程序，不要上交以前布置的大作業。如果提交的大作業題目與本文檔要求不符，成績一律為不及格。 請大家按時在網院網上系統里提交大作業，過了規定時間將無法再補交大作業。 頁面置換算法模擬實驗 算法算法思路 模擬FIFOOPTLRU這3種頁面置換算法，先分配所需的內存空間，在根據已知的序列，分別根據不同的頁面算法去訪問已知序列，得出不同內存空間的置換算法的缺頁數量。總體流程圖 開始輸入內存數執行頁面置換FIFOLRUOPT顯示結果結束 數據結構說明 源程序（關鍵代碼需要注釋說明）FIFO關鍵源碼 LRU關鍵源碼 OPT關鍵源碼 程序源碼 #include int bno;//定義塊號 int time;// 定義最近使用 int status;//定義命中狀態 int order;//定義優先級 }; int list[12]={4,3,2,1,4,2,5,2,3,2,1,5};// 已知序列 // 輸出方法 void output(int *a ,int n){ for(int i=0;i cout<<*a<<'t'; a++;} cout<<'n';} void fifo(int *list,int mem_num){ page p[N];// 定義記錄數組 int flag;int mem[M];// 定義內存 int index =0;// 默認下標 int lack=0;// 初始化內存 for(int i=0;i mem[i]=0;} // 遍歷序列 for(i=0;i flag=0;// 設置默認命中 0 for(int j=0;j if(list[i]==mem[j]){ // 檢測序列與已知內存值，命中返回flag flag=1; break; } } if(flag==1){ // 判斷是否命中，則對 p 賦值 p[i].bno = j+1; p[i].pno = list[i]; p[i].status =1; }else{ p[i].pno = list[i]; p[i].status = 0; mem[index] = list[i]; p[i].bno = index+1;// 賦予 頁號 index =(index+1)%mem_num;// 每次取余 lack++; } } cout<<“FIFO算法：n”;cout<<“---**n”;cout<<“缺頁次數：”<<'t'< cout<<“-----**n”;cout<<“序列號n”; cout<<“-----**n”;for(i=0;i cout<<“-----**n”;} for(i=mem_num;i } struct mem{ int order;//內存優先級 主要用于識別是否不常用 int pno;// 內存頁號 int time;// 記錄是否最近使用 }; void lru(int *list,int mem_num){ page p[N];// 定義記錄數組 int flag;mem m[M];// 定義內存 int index =0;// 默認下標 int lack=0;int temp;int max=0;// 內存賦值 for(int i=0;i m[i].pno=0; //默認初始優先級 0 m[i].order = 0;} for(i=0;i flag=0; for(int j=0;j if(list[i]==m[j].pno){ flag=1; index=j; //m[j].order++; p[i].order =m[j].order; break; } } if(flag==1){ //命中后，p[i].bno = index+1; p[i].pno = list[i]; p[i].status = 1; p[i].order--; temp = p[i].order; for(j=0;j if(p[j].order temp=p[j].order; index = p[j].bno; } } }else{ p[i].status=0; p[i].pno = list[i]; m[index].pno = list[i]; m[index].order = p[i].order; p[i].bno = index+1; for(j=0;j if(m[j].order>max){ index = j; } } index =(index+1)%mem_num;// 每次取余有效的下標 //max++; lack++; } } cout<<“LRU算法：n”;cout<<“---**n”;cout<<“缺頁次數：”<<'t'< cout<<“-----**n”;cout<<“序列號n”; cout<<“-----**n”;for(i=0;i cout<<“-----**n”;} for(i=mem_num;i mem m[M];int flag=0;int index = 0;//下標 int max = N;int lack=0;for(int i=0;i m[i].pno=0; m[i].time = 0;//設置內存使用頻率 } for(i=0;i flag=0; for(int j=0;j if(list[i]==m[j].pno){ flag=1; index = j; break; } } if(flag==1){ p[i].status =1; p[i].bno = index+1; p[i].pno = list[i]; for(j=0;j for(int g=i;g if(m[j].pno==list[g]){ m[j].time = N-g;//獲取到 最近使用 p[i].time = m[j].time; index = j; } } } }else{ p[i].status =0; p[i].pno = list[i]; m[index].pno = list[i]; m[index].time = N;//設置默認不使用 p[i].bno =index+1; for(j=0;j if(m[j].time>max){ index = j; } } index =(index+1)%mem_num; lack++; } } cout<<“OPT算法：n”;cout<<“---**n”;cout<<“缺頁次數：”<<'t'< cout<<“-----**n”;cout<<“序列號n”; cout<<“-----**n”;for(i=0;i cout<<“-----**n”;} for(i=mem_num;i void main(){ int m;cout << “===========================n”;cout << “請輸入內存大?。?/4）n”;cin >> m;cout << “===========================n”;opt(list,m);fifo(list,m);lru(list,m); } 運行結果截圖 FIFO、LRU、OPT運行截圖（開辟3個內存空間）： FIFO、LRU、OPT運行截圖（開辟4個內存空間）： 心得體會及總結： 在開始做題目的時候，需要了解什么是FIOFOLRUOPT這3個頁面置換的知識點，同時參考了網絡上許多實現過程技巧，并在在紙上面簡單畫出頁面如何記錄如何與內存置換，這樣子比較方便寫出算法。由于這次設計的時間比較倉促，其中不免會有些紕漏，比如在程序的實現上還不夠嚴謹，出錯處理不夠完善等多方面問題，這些都有進一步改善。同時，在這次編寫3個頁面算法的過程中，我學到了很多東西，無論在理論上還是實踐中，都得到不少的提高，這對以后的工作中會有一定的幫助。 操作系統課程第七次實驗報告 姓名 學號 系 計算機 任課教師 指導教師 評閱教師 實驗地點 綜合樓B102 實驗時間 2012-9-26 實驗課表現 出勤和個人表現Q1(15+15（組長評分）=30分) 得分： 實驗 總分 (Q1+Q2+Q3+Q4) 實驗完成情況Q2(45分(組長與教師評分的加權平均)) 得分： 實驗編號與實驗名稱： 實驗七、常用頁面置換算法模擬實驗 實驗目的： 通過模擬實現請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現過程，并比較它們的效率。 實驗內容及要求（詳見實驗講義與實驗指導書）： 要求： 1）要求用你熟悉的程序設計語言編寫和調試一個頁面置換模擬程序；要求在主函數中測試。 2）實驗報告中必須包括：設計思想、數據定義（包括詳細說明）、處理流程（詳細算法描述和算法流程圖）、源代碼、運行結果、體會等部分。 3）必須模擬本實驗內容中提到的算法中的至少2種頁面置換算法。 4） 比較不同頁面置換算法的效率 內容：編寫一個程序，使用以下頁面置換算法中的某2種分別模擬一個分頁系統，并統計同一個頁面訪問序列情況下不同頁面置換算法引發的缺頁中斷次數。 1、第二次機會算法（Second Chance） 2、最近最少使用算法（Least Recently Used，LRU） 3、最不常用算法（Not Frequently Used，NFU） 4、最近未使用算法（Not Recently Used，NRU） 5、時鐘頁面置換算法 6、老化算法（aging） 頁框的數量固定為4，虛擬頁面數為8。實驗輸入為訪問頁面序列，比如0，1，3，2，7，1 實驗用到的軟件（：） DevC++,Visio 實驗內容及關鍵步驟（代碼）Q3（15分） 得分： 流程圖：輸入頁面訪問序列 取訪問的頁號 查頁表 是否缺頁？ 是 置缺頁標志flag為’*’ 按算法不同淘汰一頁面 調入所訪問的頁面 否 FIFO算法流程圖 LRU算法流程圖： 函數關系解釋圖： 實現結果： 圖1 圖2 代碼： #include #include #define MEMORY_SIZE /*物理塊數*/ #define PROESS_SIZE /*頁面號引用串個數*/#include #include /*全局變量*/ int mSIZE=4; int pSIZE=8; static int memery[4]={0}; /*物理塊中的頁號*/ static int page[8]={0}; /*頁面號引用串*/ static int temp[8][4]={0}; /*輔助數組*/ /*置換算法函數*/ void FIFO(); void LRU(); void OPT(); void designBy(); /*輔助函數*/ void print(unsigned int t); /*主函數*/ int main() { int i,k,code; designBy(); system(“color 0A“); puts(“請依次輸入頁面號(8個)：“); for(i=0;i scanf(“%1d“,&page[i]); system(“cls“); system(“color 0E“); do{ puts(“輸入的頁面號引用串為：“); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } } printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“* 請選擇頁面置換算法：＼t＼t＼t *＼n“); printf(“* ----------------------------------------- *＼n“); printf(“* 1.先進先出(FIFO) 2.最近最久未使用(LRU) *＼n“); printf(“* 3.退出 *＼n“); printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“請選擇操作：[ ]＼b＼b“); scanf(“%d“,&code); switch(code) { case 1: FIFO(); break; case 2: LRU(); break; case 3: system(“cls“); system(“color 0A“); exit(0); default: printf(“輸入錯誤，請重新輸入：“); } printf(“按任意鍵重新選擇置換算法：>>>“); getch(); system(“cls“); }while (code!=3); getch(); } void print(unsigned int t) { int i,j,k,l; int flag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } for(j=0;j { for(i=20*k;(i if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20*k;(i { for(flag=0,l=0;l if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*頁面在物理塊中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行顯示20個*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺頁次數：%d＼t＼t“,t+mSIZE); printf(“缺頁率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置換次數：%d＼t＼t“,t); printf(“訪問命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*先進先出頁面置換算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/ /*前mSIZE個數直接放入*/ for(i=0;i { memery[i]=page[i]; time[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計算換出頁*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*記錄該頁進入物理塊的時間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } print(count); } /*最近最久未使用置換算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/ /*前mSIZE個數直接放入*/ for(i=0;i { memery[i]=page[i]; flag[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新該頁的訪問時間*/ } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計算換出頁*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*記錄該頁的訪問時間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } // compute(); print(count); } /*顯示設計者信息*/ void designBy() { printf(“┏━━━━━━━━━━━━━━━━━━━━━━━━━┓＼n“); printf(“┃㊣ 實驗七：頁面置換算法 ㊣┃＼n“); printf(“┃ 學號：1001010042 ┃＼n“); printf(“┃ 姓名：黃浩全 4.9.9.0>┃＼n“); printf(“┣━━━━━━━━━━━━━━━━━━━━━━━━━┫＼n“); } 實驗過程中遇到的問題解決辦法與實驗體會Q4（需手寫，10分） 得分： 1、在FIFO算法可以很容易用數組實現，而LRU算法可以用數組實現，不過用結構體會更明顯簡單。結構體成員變量可以記錄頁號進入的時間，和最近使用的記錄。相對比數組更容易理解和實現。 2:首先，FIFO（先進先出）算法和LRU（最近未使用算法）兩者之間，FIFO算法明顯會比LRU容易理解，而且比LRU算法較容易實現，但在性能方面，LRU的確在優化方面做的比較理想。再且在考慮頁框和頁表號之間的問題用代碼可以容易模擬，但是真是在物理內存塊中是如何實現，那確實是很難以理解，需要真正理解到內存內部的知識才知道這兩個算法是怎么實現的。 評閱教師特殊評語： 評閱教師： 日 期：第二篇：頁面置換算法實驗報告（精選）
第三篇：頁面置換算法實驗報告
第四篇：頁面置換算法模擬
第五篇：操作系統 七次實驗報告 常用頁面置換算法模擬實驗
![下載虛擬內存頁面置換算法實驗報告[合集五篇]word格式文檔](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
點擊咨詢 