第一篇：頁面置換算法模擬
“計算機操作系統”課程設計大作業
一、題目: 頁面置換算法模擬實驗
二、目的
分別采用最佳(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 << “請輸入內存大小（3/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個頁面算法的過程中，我學到了很多東西，無論在理論上還是實踐中，都得到不少的提高，這對以后的工作中會有一定的幫助。 《操作系統--頁面置換算法》 實驗報告 姓 名： 范學升 學 號：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）置換算法的思路 其所選擇的被淘汰的頁面，獎是以后不使用的，或者是在未來時間內不再被訪問的頁面，采用最佳算法，通常可保證獲得最低的缺頁率。 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算法 中北大學軟件學院 實 驗 報 告 專 業 軟件工程 課程名稱 計算機操作系統 學 號 姓 名 輔導教師 張 靜 成績 實驗日期 2015、１1、20 實驗時間實驗名稱 :實驗四 頁面置換算法模擬 ２、實驗目得(１）了解內存分頁管理策略（2）掌握調頁策略(3）掌握一般常用得調度算法（4）學會各種存儲分配算法得實現方法。 （5）了解頁面大小與內存實際容量對命中率得影響。 3、實驗要求 編程實現頁面置換算法，最少實現兩種算法，比較算法得優劣,并將調試結果顯示在計算機屏幕上，并檢測機算與筆算得一致性。 （1）采用頁式分配存儲方案，通過分別計算不同算法得命中率來比較算法得優劣，同時也考慮頁面大小及內存實際容量對命中率得影響;（2）實現 OＰT 算法(最優置換算法)、ＬRU 算法(Lｅast Recｅｎtly）、FIFO 算法（Fｉrst IN Firｓｔ Out）得模擬;（3)使用某種編程語言模擬頁面置換算法.4、實驗算法描述 （1）ＦIFO（先進先出） Y Ｎ N Y 開始 頁面走向存入數組 p[]中,內存塊用page[]表示初始化為 0 當前p[]中第i個元素就是否已在內Page[]就是否有空把 page[]中最先裝入得頁面置換出去、i++ 把 p[i]得內容直接裝入最上面一個空內存塊,i++ 輸出當前內存塊狀態 i++ 圖 4－1FIFＯ算法流程圖 結束 (2） LＲU（最近最久未使用） Y N Y Ｎ 圖 4—2 LＲU 算法流程圖 開始 頁面走向存入數組 p[]中,內存塊用 page[]表示初始化為 0 當前 p[]中第 i 個元素就是否已在內存 Page[]就是否有空把 page[]中最近最久未使用得頁面置換出去、i++ 把 p[i]得內容直接裝入最上面一個空內存塊,i++ 輸出當前內存塊狀態 結束 i++ (3）OＰＴ（最佳置換算法） Y N Y Ｎ 圖４－3 ＯPT 流程圖 開始 頁面走向存入數組 p[]中,內存塊用 page[]表示初始化為 0 當前 p[]中第 i 個元素就是否已在內存 Page[]就是否有空把 page[]中以后一段時間都不使用或就是使用時間離現在最遠得換出、i++ 把 p[i]得內容直接裝入最上面一個空內存塊,i++ 輸出當前內存塊狀態 結束 i++ 6、實驗代碼 ＃iｎcｌuｄe ＜iostreａm〉 usiｎｇ ｎａmespace sｔｄ;#defiｎe Bｓｉzｅ ３ #dｅfine Psｉｚe 20 ｓｔruct ｐaｇｅInｆor ｛ 號面頁// ;ｔneｔｎoc tni? int tｉmer; //被訪問標記 ｝;ｃlasｓ ＰＲA{ ｐuｂｌiｃ： PRA(ｖoid）； 存內閑空有否是就找查/／ ;)diov（eｃaｐSdnif tni? iｎt ｆindExist（int curpage）; ／／查找內存中就是否有該頁面 int findReplacｅ（vｏid）; //查找應予置換得頁面 void ｄisplay(void）; //顯示 法算 OＦIF//;）dioｖ（OFIＦ ｄiov? 法算 UＲL／/；)dｉov(URL diov? vｏid Ｏptimａl(ｖoid);／／ＯPTIＭAL 算法 ｖoｉd BlockＣlear（voiｄ)；/／ＢLOCK 恢復 pageＩｎfor ＊ ｂlｏck；//物理塊 pageInfoｒ ＊ page；／／頁面號串 privaｔe: };PＲA：：PＲＡ(vｏid）{ ｉnt QStriｎg［２0］=｛7，0，1，２,0，3,0，4,２，3,0,3,２,1，2，0，1,7,0,１}; block = ｎew paｇeIｎfor[Bｓizｅ］;)++i;ｅzisB＜ｉ;0＝i ｔnｉ(rof? { ;1— = tnｅtnｏc、］ｉ［ｋcolb? ；0 ＝ remｉt、]ｉ［kcolb?? } page = ｎew pageInfｏｒ［Psｉze];）＋+ｉ;eｚiｓP〈i ；０=i（ｒof? { ；]i[gｎiｒtSQ = tｎetnoｃ、］i[egａp?;0 = rｅmit、]i[eｇａｐ?? }?} iｎt ＰRA：：fｉndSpace（voiｄ） { for（iｎt i=0； i if(bｌocｋ[i]、cｏntent =＝ －1） 置位中 KＣOLＢ回返，存內閑空到找//;i nrutｅｒ?;1— ｎruteｒ?｝ inｔ ＰRA：：fiｎｄExisｔ（iｎt cｕrpage） { ｆor（int i=0;ｉ<Ｂsizｅ； i++））tｎetnｏc、]egapruc［ｅgａp =＝ tneｔｎoc、］ｉ［kｃoｌb(fi?? 置位中 KCOＬB 回返,面頁該有中存內到找//;i nrｕter? ；1— nruter?｝ iｎt PRA：：findReplａce(void） { ;0 ＝ sop tｎi? foｒ（iｎt i=0;i<Ｂsｉzｅ； ｉ+＋）)rｅmit、］soｐ[ｋcｏlb =＞ rｅmit、］i［kcｏlb（fi?? ? pos = i;//找到應予置換頁面,返回 BLOCＫ中位置 ｒeturn pos； } voｉd ＰRＡ：:display（voiｄ） { for（inｔ i=0;i＜Ｂsiｚe； ｉ++） ｉｆ(bｌock［ｉ］、coｎteｎｔ!＝-１） ?；” ”<〈ｔnetnoc、］i[kcｏlb〈〈tuoc? ；ldｎe＜＜tuoc?｝ void PRA：：Optimａｌ（ｖoid)｛ ； noｉtisop,ecapｓ，tsiｘe tｎi? fｏr（ｉnt i=0； i ｛?;)i（tsixEdｎif = tｓｉxe??）1-=！ ｔsixe（fｉ? {? ;ｌdnｅ〈〈”頁缺不“<<ｔｕoｃ? ｝?? esｌｅ? {?? ?? spａｃe = findSpacｅ（）； ?）1— ＝！ eｃaｐs（fi? ? {? ? ；]i［egaｐ = ］eｃapｓ［kcolｂ? ? ;）（yalpsid?? ? } ? ｅslｅ? {?? ?)+＋k ；ezisB<ｋ ；0＝k tｎｉ（roｆ? ? for（iｎｔ j＝i； j＜Psize； ｊ+＋) ? {??? ??)ｔnetnoc、]ｊ［ｅgaｐ =!ｔnｅtnoc、］k[ｋcolb（ｆi? ｛ 為 RＥMＩT 置設，用會不來將//};00０1 = ｒemiｔ、］k［kcoｌb??一個很大數 ?? esle? ?? ｛ ?? ? ? bloｃk［k]、ｔｉmeｒ = j; ? ?? ｂreaｋ； ｝ ??? }????? ? ｐoｓition ＝ fiｎdReｐｌａce（）； ? ；］i［ｅｇap ＝ ]ｎｏiｔｉｓｏｐ[ｋcolｂ? ；）(yalｐsｉｄ?? ｝?? ? } }?｝ voiｄ PRA:：LRU（ｖoid){ int ｅxｉsｔ,ｓpace，ｐositioｎ ； for(int ｉ ＝ 0； i < Psizｅ;ｉ++） ｛? ? ｅxist = fｉndEｘｉst(i);)1－ =！ tsｉxｅ(ｆi? { ?? cout＜<”不缺頁”＜ ? blｏck［eｘisｔ］、tiｍｅｒ = —1；//恢復存在得并剛訪問過得ＢLOCK 中頁面 TＩMＥR 為－1 ? } ? else ｛? ?? sｐace = fｉｎdSpace();?）１-=!ecaｐs（fi? ? {?;]i[ｅgａp = ］ecaｐs［ｋｃolｂ?? ? ；)（ｙalpｓid? ?? ｝ ? eｓle? ｛?? ；）（eｃａｌｐeRｄｎif = noｉtiｓop?? ? bｌoｃk[positiｏn］ = ｐagｅ［i］； ? ;）(yａlｐsid? ｝?? ｝? for(int ｊ=0;j〈Ｂsizｅ;j++) ;+＋rｅmit、］j[kcolb?? ｝?｝ ｖoｉd PRA:：ＦIFO（ｖoid） { int exｉｓt,ｓpace,position ； for（iｎt i=0;i ｛? exｉｓt ＝ findExist(ｉ）； ? ｉf（eｘist!＝-１） {cout＜<＂不缺頁＂＜ esle? ｛ sｐａce = findSｐａｃe（）； ?)1-=！ ecaｐs（ｆi? ?? ｛ ? block［spaｃｅ］ = paｇe[ｉ]； ? ? displaｙ(); ｝?? ｅsｌe?? ? ｛ ?? pｏsition = findReplaｃe（）； ?? block［pｏsitioｎ] ＝ paｇe[i］； ;)（yａlｐsｉd?? ?? ｝ }?）＋+j;ezｉsB ｂlock[j］、tｉmｅr+＋；//BLOCK 中所有頁面ＴIMER+＋ ｝?｝ void ＰＲA：：BlockＣleａr（vｏiｄ)｛ for(inｔ ｉ=０;i {? blocｋ[i］、contｅnt =-1； ? ｂｌｏcｋ[i]、timeｒ = ０; ｝ } ｖoid mａｉn(vｏiｄ)｛ ;lｄne<〈”:法 算 換 置 面 頁“＜＜tuｏc? ｃｏｕｔ〈〈”頁面號引用串：7,０,1,2，0,3,0，4,2，３，0，３,2,1,2，0，1，7，０,1＂<〈ｅndｌ； cout〈〈”選擇<１＞應用 LＲU 算法”〈＜eｎdl； coｕt<＜”選擇<２〉應用 FIFO 算法”〈 ｃout<<”選擇＜3>應用 Optｉmａl 算法“<〈ｅndl; ；ldne<<＂出退>0〈擇選”〈＜ｔuoc? int select； ＰRA tesｔ;? whｉle(seleｃｔ) ｛ ? cｉｎ〉>select;）tcｅｌｅs（ｈctｉws? ｛? :0 esac??;ｋaerb? :1 esａc???;ｌdnｅ＜<“：下如果結法算ＵRL”＜〈tuoc? ;）（URL、tset?? ；)(raelCkｃｏｌB、tｓeｔ??;ldne＜<”－－-—-—－-—-—--—-—－—－———“< ? break； ：2 esac? cｏut<〈”FIFO 算法結果如下:“<＜endl； tesｔ、FIFO();?；）（raelCｋcoｌＢ、ｔset? ? cｏuｔ<〈”-——-－－－－－-—－—－－---－—－-”＜〈eｎdl; ? ｂreak； caｓe 3: ；ｌdnｅ〈＜”：下如果結法算 lａmiｔｐＯ”< test、Optimal（）; ? ；)（rａeｌCkｃolB、tｓet??；ldｎe＜<＂－-－-—－－--－-——-－————－－－＂〈〈tuoc??;ｋaeｒb? defaulｔ： ? ；ldｎe〈＜”號能功確正入輸請“＜＜tuoｃ? ;ｋaerb?? }?? } ｝ 6、實驗結果 7、實驗心得 加深了對操作系統得認識,了解了操作系統中各種資源分配算法得實現，特別就是對虛擬存儲，頁面置換有了深入得了解，并能夠用高級語言進行模擬演示。在這短短得兩周時間里，通過瀏覽、閱讀有關得資料，學到了很多東西,同時也發現僅僅書本得知識就是遠遠不夠得,需要把知識運用到實踐中去,能力才能得到提高。 使用 MFＣ可視化編程極大得減少了編寫得代碼量，直觀得界面設計，不但便于修改，而且簡化了界面程序代碼得編寫 兩種頁面置換算法 FIＦO 與ＬRＵ理解起來相當容易，但在實際編程實現得時候需要注意各種細節,需要耐心細致,實際編程中遇到一些細節上得小問題確實需要仔細考慮才行. 計算機體系結構 實驗報告 班級：計科姓名：張華敏學號： 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”);} 六,實驗結果 總結 通過本次試驗我對各種頁面置換算法有了更深入的了解,也使得自己認識到平常學習到某些東西覺得懂了會了可是一旦實際動手操作起來就會發現總會存在這樣或者那樣的錯誤，只有多動手實際操作才會發現不足發現錯誤并且改正。查漏補缺提高自己的實際動手能力。 實驗5 頁面置換算法 一、實驗題目：頁面置換算法（請求分頁） 二、實驗目的： 進一步理解父子進程之間的關系。 1）理解內存頁面調度的機理。2）掌握頁面置換算法的實現方法。3）通過實驗比較不同調度算法的優劣。4）培養綜合運用所學知識的能力。 頁面置換算法是虛擬存儲管理實現的關鍵，通過本次試驗理解內存頁面調度的機制，在模擬實現FIFO、LRU等經典頁面置換算法的基礎上，比較各種置換算法的效率及優缺點，從而了解虛擬存儲實現的過程。將不同的置換算法放在不同的子進程中加以模擬，培養綜合運用所學知識的能力。 三、實驗內容及要求 這是一個綜合型實驗，要求在掌握父子進程并發執行機制和內存頁面置換算法的基礎上，能綜合運用這兩方面的知識，自行編制程序。 程序涉及一個父進程和兩個子進程。父進程使用rand()函數隨機產生若干隨機數，經過處理后，存于一數組Acess_Series[]中，作為內存頁面訪問的序列。兩個子進程根據這個訪問序列，分別采用FIFO和LRU兩種不同的頁面置換算法對內存頁面進行調度。要求： 1）每個子進程應能反映出頁面置換的過程，并統計頁面置換算法的命中或缺頁情況。 設缺頁的次數為diseffect。總的頁面訪問次數為total_instruction。缺頁率 = disaffect/total_instruction 命中率 = 1-disaffect/total_instruction 2）將為進程分配的內存頁面數mframe 作為程序的參數，通過多次運行程序，說明FIFO算法存在的Belady現象。 四、程序流程圖 開始創建子進程1創建子進程2 結束 子進程1邏輯頁面讀完？N命中？N內存頁面滿？Y命中次數+1YY最先進入的進程退出內存頁面N當前調入頁面進入內存頁面退出 2邏輯頁面讀完？N命中？N內存頁面滿？N當前調入頁面進入內存頁面Y被訪問次數最少的進程退出內存頁面Y命中次數+1，命中頁面訪問數+1Y退出 五、運行結果及其說明 FIFO: LRU: ： 六、回答以下問題： ① 父進程、子進程之間的并發執行的過程 父進程與子進程之間的并發執行宏觀并行，微觀串行。從宏觀來說，父進程創建子進程1，子進程1和父進程同時執行，直到父進程創建子進程2遇到wait()函數掛機為止，當子進程1結束父進程和子進程2并發執行到再次遇見wait()函數是掛起等待子進程2結束，到子進程2結束返回父進程父進程繼續執行至結束。從微觀來說，父進程先執行至創建子進程1，接下來父進程掛起執行子進程1知道子進程1結束回到父進程；父進程繼續執行到創建子進程2再次掛起，執行子進程2，直到子進程2結束回到父進程繼續執行至結束。 ② 通過完成實驗，根據你的體會，闡述虛擬存儲器的原理。虛擬存儲器實際上是用來解決作業大而內存小的問題，他通過頁面置換算法來提供遠大于內存地址空間的地址范圍，針對不同的程序將不同的數據頁面讀取到虛擬存儲器中用來實現。 ③ 寫出FIFO算法中出現Belady現象的內存頁面訪問序列。 4個內存頁面數： 序列2 2 5 3 3 1 3 1 2 5 5 2 3個內存頁面數： 序列2 1 3 2 1 4 3 1 3 1 5 5 7次命中，命中率為0.58 6次命中，命中率為0.5 七、程序源代碼、文檔注釋及文字說明 #include main(){ srand(time(0));int pid1, pid2, fd[2], Acess_Series[12], temp;float effect, rate = 0;char str1[100], str2[100];struct M_Frame { int page_no; char flag;};struct M_Frame one_frame[4];one_frame[0].page_no = 0;one_frame[1].page_no = 0;one_frame[2].page_no = 0;one_frame[3].page_no = 0;effect = 0;int i = 0;printf(“內存訪問頁面序列:”);for(;i<12;i++){ Acess_Series[i] = rand()% 5 + 1; printf(“%d ”, Acess_Series[i]);} while((pid1 = fork())==-1);if(pid1 == 0){ int no = 0; int pno = 0; printf(“FIFO頁面置換算法:n”); for(;no<12;no++) { printf(“調入的頁面號是%d ”, Acess_Series[no]); int k = 0; for(;k <= Frame;k++) { if(one_frame[k].page_no == Acess_Series[no]){ effect++;printf(“命中n”);break;} if(one_frame[k].page_no == 0) { one_frame[k].page_no = Acess_Series[no]; printf(“未命中n”); break; } if(k == Frame) { int j = 1; for(;j <= Frame;j++) { one_frame[j1].page_no;one_frame[t1].page_no = one_frame[j].page_no; } one_frame[Frame].page_no = Acess_Series[no]; printf(“未命中n”); } } printf(“內存情況為:%d |%d |%d |%dn”, one_frame[0].page_no, one_frame[1].page_no, one_frame[2].page_no, one_frame[3].page_no); } rate = effect / 12; printf(“命中次數：%fn”, effect); printf(“命中率：%fn”, rate); } wait(0); exit(0);} }第二篇：頁面置換算法實驗報告（精選）
第三篇：頁面置換算法模擬,實驗報告
第四篇：頁面置換算法實驗報告
第五篇：實驗5 頁面置換算法
點擊咨詢 