頁面置換算法模擬程序-附代碼

1、目 錄1問題的提出問題的提出.11.1 關于頁面置換算法模擬程序問題的產生.11.2 任務分析 .12需求分析需求分析.13方案設計方案設計.24總體設計總體設計.34.1 程序 N-S 圖 .34.2 主要的函數.34.3 主要流程圖及代碼 .44.3.1 FIFO（先進先出）.44.3.2 LRU（最近最久未使用）.54.3.3 OPT（最佳置換算法）.74.4 實現結果 .105程序測試程序測試.145.1 設計測試數據 .145.2 測試結果及分析 .15摘 要隨著計算機的普及人們的物質生活得到了極大的滿足，人們在精神生活方面同樣也需頁面置換算法模擬程序要提高，所以越來越多的人進行著各

2、種各樣的學習。 操作系統(tǒng)是計算機教學中最重要的環(huán)節(jié)之一，也是計算機專業(yè)學生的一門重要的專業(yè)課程。操作系統(tǒng)質量的好壞，直接影響整個計算機系統(tǒng)的性能和用戶對計算機的使用。一個精心設計的操作系統(tǒng)能極大地擴充計算機系統(tǒng)的功能，充分發(fā)揮系統(tǒng)中各種設備的使用效率，提高系統(tǒng)工作的可靠性。由于操作系統(tǒng)涉及計算機系統(tǒng)中各種軟硬件資源的管理，內容比較繁瑣，具有很強的實踐性。要學好這門課程，必須把理論與實踐緊密結合，才能取得較好的學習效果.本課程設計是學生學習完操作系統(tǒng)教程課程后，進行的一次全面的綜合訓練，通過課程設計，讓學生更好地掌握操作系統(tǒng)的原理及實現方法,加深對操作系統(tǒng)基礎理論和重要算法的理解，加強學生的動手

3、能力。 熟悉頁面置換算法及其實現，引入計算機系統(tǒng)性能評價方法的概念。關鍵詞：關鍵詞：編制頁面置換算法模擬程序、打印頁面、FIFO 頁面算法、LRU 頁面置換算法、OPT 頁面置換算法。頁面置換算法模擬程序引 言1 1問題的提出問題的提出1.11.1 關于頁面置換算法模擬程序問題的產生關于頁面置換算法模擬程序問題的產生在各種存儲器管理方式中，有一個共同的特點，即它們都要求將一個作業(yè)全部裝入內存方能運行，但是有兩種情況：（1） 有的作業(yè)很大，不能全部裝入內存，致使作業(yè)無法運行；（2） 有大量作業(yè)要求運行，但內存容量不足以容納所有這些作業(yè)。而虛擬內存技術正式從邏輯上擴充內存容量，將會解決以上兩個問題

4、。從內存中調出一頁程序或數據送磁盤的對換區(qū)中，通常，把選擇換出的頁面的算法稱為頁面置換算法（Page-Replacement Algorithms） 。進而頁面置換算法模擬程序能客觀的將其工作原理展現在我們面前。1.21.2 任務分析任務分析首先，定義宏變量，設置所占最大內存長度。編輯以時間為種子，初始化隨即發(fā)生器。進行相關頁面輸入程序的編寫以及頁面的打印。爾后，尋找最近最近最久未使用的頁面 、記錄當前內存塊中頁面離下次使用間隔長度等相關程序的代碼編寫。最后，進行)FIFO 、LRU、 OPT 三種算法的編寫。2 2需求分析需求分析 1. 用隨機數方法產生頁面走向，頁面走向長度為 L。2. 根

5、據頁面走向，分別采用 FIFO 和 LRU 算法進行頁面置換，統(tǒng)計缺頁率；為簡化操作，在淘汰一頁時，只將該頁在頁表中抹去,而不再判斷它是否被改寫過，也不將它寫回到輔存。3. 假定可用內存塊和頁表長度 (作業(yè)的頁面數)分別為 m 和 k，初始時，作業(yè)頁面都不在內存。隨機數產生程序：int i,j;頁面置換算法模擬程序 j=time(NULL);/取時鐘時間 srand(j);/以時鐘時間 x 為種子，初始化隨機數發(fā)生器cout輸出隨機數: ; for(i=0;im;i+) pi.num=rand( )%10+1;/產生 1 到 10 之間的隨即數放到數組 p 中 pi.time=0;coutpi

6、.num ; 上述隨機數發(fā)生函數產生的隨機數為 0.01.0，稍另變化就可得到0n1 之間的隨機數。程序開始時，應對變量 Seed (實型)賦初值。根據頁面置換算法的理論操作及要求，首先要進行頁面長度的確定，定義結構體用以儲存數據，進行主界面代碼及 FIFO、LRU、OPT 頁面置換算法代碼的編寫。3 3方案設計方案設計首先，定義宏變量，設置所占最大內存長度。編輯以時間為種子，初始化隨即發(fā)生器。進行相關頁面輸入程序的編寫以及頁面的打印。其次，尋找最近最近最久未使用的頁面 、記錄當前內存塊中頁面離下次使用間隔長度等相關程序的代碼編寫。最后，進行 FIFO 、LRU、 OPT 三種算法的編寫。程序

7、運行平臺VC+6.0具體操作如下：在 VC+6.0 的環(huán)境下準備用時鐘函數調用庫函數（#include ） 、 取時鐘時間并存入 t 調用庫函數（t=time(NULL)） 、 用時間 t 初始化隨機數發(fā)生器調用 庫函數（srand(t)返回一個 110 之間的隨機數（x=rand( )%10+1） 。編寫三種算法。頁面置換算法模擬程序4 4總體設計總體設計4.14.1 程序程序 N-SN-S 圖圖程序開始輸入選擇項（進行判斷）頁面存在進入下一部操作此項不存在輸入要輸出的結果輸出結果結束4.24.2 主要的函數主要的函數Input(int m,Pro pL)（打印頁面走向狀態(tài)） ；void p

8、rint(Pro *page1)（打印當前的頁面） ；int Search(int e,Pro *page1 )（尋找內存塊中與 e 相同的塊號） ； int Max(Pro *page1)（尋找最近最長未使用的頁面） ；int Count(Pro *page1,int i,int t,Pro pL)（記錄當前內存塊中頁面離下次使用間隔長度） ；int main()（主函數） ；.隨機數發(fā)生器 #include #include /準備用時鐘函數調用庫函數t=time(NULL);/取時鐘時間并存入 t 調用庫函數srand(t);/用時間 t 初始化隨機數發(fā)生器調用庫函數x=rand( )%

9、10+1;/返回一個 110 之間的隨機數頁面置換算法模擬程序4.34.3 主要流程圖主要流程圖及代碼及代碼4.3.14.3.1 FIFOFIFO（先進先出）（先進先出）設計原理：需要進行頁面置換，即把內存中裝入最早的那個頁面淘汰，換入當前的頁面。算法流程圖 Y N N Y 圖 4-1FIFO 算法流程圖代碼：if(c=1)/FIFO 頁面置換 n=0;開始頁面走向存入數組 p中，內存塊用 page表示初始化為 0當前 p中第 i 個元素是否已在內存中Page是否有空把 page中最先裝入的頁面置換出去.i+把 pi的內容直接裝入最上面一個空內存塊，i+輸出當前內存塊狀態(tài) 結束i+頁面置換算法

10、模擬程序cout * endl;coutendl; cout FIFO 算法頁面置換情況如下: endl;coutendl; cout * endl; while(i=0)/當前頁面在內存中 coutpi.num ;/輸出當前頁 pi.numcout不缺頁endl;i+;/i 加 1 else /當前頁不在內存中 if(t=M)t=0; else n+;/缺頁次數加 1 paget.num=pi.num; /把當前頁面放入內存中 coutpi.num ; print(page); /打印當前頁面 t+; /下一個內存塊i+; /指向下一個頁面 cout缺頁次數：n 缺頁率：n/mendl; 4

11、.3.24.3.2 LRULRU（最近最久未使用）（最近最久未使用）設計原理：當需要淘汰某一頁時，選擇離當前時間最近的一段時間內最久沒有使用過的頁先淘汰該算法的主要出發(fā)點是，如果某頁被訪問了，則頁面置換算法模擬程序它可能馬上還要被訪問。或者反過來說如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。算法流程圖： Y N Y N圖 4-2 LRU 算法流程圖代碼：if(c=2)/LRU 頁面置換 n=0; cout * endl; 開始頁面走向存入數組 p中，內存塊用 page表示初始化為 0當前 p中第 i 個元素是否已在內存Page是否有空把 page中最近最久未使用的頁面置換出去.i

12、+把 pi的內容直接裝入最上面一個空內存塊，i+輸出當前內存塊狀態(tài) 結束i+頁面置換算法模擬程序coutendl; cout LRU 算法頁面置換情況如下: endl; coutendl;cout * endl; while(i=0) /如果已在內存塊中 paget.time=0; /把與它相同的內存塊的時間置 0for(a=0;aM;a+)if(a!=t)pagea.time+; /其它的時間加 1 coutpi.num ;cout不缺頁endl; else /如果不在內存塊中 n+; /缺頁次數加 1 t=Max(page); /返回最近最久未使用的塊號賦值給 t paget.num=pi

13、.num; /進行替換 paget.time=0; /替換后時間置為 0 coutpi.num ;print(page);for(a=0;aM;a+)if(a!=t)pagea.time+; /其它的時間加 1 i+; cout缺頁次數：n 缺頁率：n/mendl; 頁面置換算法模擬程序4.3.34.3.3 OPTOPT（最佳置換算法）（最佳置換算法）設計原理：需要進行頁面置換，把內存中以后一段時間都不使用或是使用時間離現在最遠的頁面換出。流程圖： Y N Y N 開始頁面走向存入數組 p中，內存塊用 page表示初始化為 0當前 p中第 i 個元素是否已在內存Page是否有空把 page中以

14、后一段時間都不使用或是使用時間離現在最遠的換出.i+把 pi的內容直接裝入最上面一個空內存塊，i+輸出當前內存塊狀態(tài) 結束i+頁面置換算法模擬程序圖 4-3 OPT 流程圖代碼： if(c=3) /OPT 頁面置換 n=0;cout * endl;coutendl;cout OPT 算法置換情況如下:endl;coutendl;cout * endl; while(i=0) /如果已在內存塊中 coutpi.num ;cout不缺頁endl;i+;else /如果不在內存塊中int a=0; for(t=0;tM;t+)if(paget.num=0)a+; /記錄空的內存塊數if(a!=0)

15、/有空內存塊int q=M;for(t=0;tt)q=t; /把空內存塊中塊號最小的找出來pageq.num=pi.num;頁面置換算法模擬程序n+; coutpi.num ;print(page);i+;elseint temp=0,s;for(t=0;tM;t+) /尋找內存塊中下次使用離現在最久的頁面if(tempCount(page,i,t,p)temp=Count(page,i,t,p);s=t; /把找到的塊號賦給 spages.num=pi.num; n+; coutpi.num ; print(page); i+;cout缺頁次數：n 缺頁率：n/mendl;4.44.4 實現

16、結果實現結果程序在運行的情況下，進入主界面輸入菜單，如圖 3-3 所示：輸入 14：圖 4-5 輸入 14 后的輸出圖輸入 25：頁面置換算法模擬程序圖 5-6 輸入數據 25 后輸出圖輸入數據 18：圖 5-7 輸入數據 18 后的輸出圖輸入數據：圖 5-8 輸出圖選 1，進入 FIFO 頁面置換：頁面置換算法模擬程序圖 5-9 FIFO 的輸出圖選 2，進入 LRU 頁面置換：頁面置換算法模擬程序圖 5-10 LRU 的輸出圖輸入 3，進入 OPT 頁面置換：頁面置換算法模擬程序圖 5-11 OPT 的輸出圖5 5程序測試程序測試 5.15.1 設計測試數據設計測試數據A 14 25 18

17、 ；2 6 4 ；B 1C 2 D 3頁面置換算法模擬程序5.25.2 測試結果及分析測試結果及分析1）測試 A 結果及分析 進入主菜單后輸入 14、25，顯示輸入不滿足要求。輸入 18 顯示相關信息;輸入 2 、6 不滿足要求，輸入 4 顯示出相關信息。2）測試結果及分析顯示出 FIFO 頁面置換算法的缺頁信息及缺頁率。3）測試 C 結果及分析顯示出 LRU 頁面置換算法的缺頁信息及缺頁率。4）測試 D 結果及分析顯示出 OPT 頁面置換算法的缺頁信息及缺頁率頁面置換算法模擬程序結 論通過這次課程設計，不僅讓我了解了頁面置換算法，開始我一味的進行調試，急切的想僥幸調試出來，但由于沒有進行深入

18、的考慮，我調試了很久都沒沒有成功，我仔細的分析題目，分析材料，在原由的基礎上我進行了改正，我最后還是調試成功了，還是經過了一翻努力，這次操作系統(tǒng)實習，不僅讓我對操作系統(tǒng)這門課程有了更深入的研究、對很多重要的概念有了鞏固和掌握。通過努力，三個頁面置換算法程序都已經完成，此時此刻，我心里多了些成就感。雖然自己所做的很少也不夠完善，但畢竟也是努力的結果。主要有以下幾點收獲：1.通過對上網和看書查閱相關資料，使自己對 VC +語言的基本框架有新的了解，加深了對可視化程序的認識。2.在使用 VC+語言來實現功能時，不像以往用的其他語言，它比較簡練，更容易理解，實用性很強。3.先進先出頁面置換和 LRU

19、以及 OPT 算法各有特點，但是實踐起來卻很大，使自己對頁面置換算法有了新的認識。一周半的課程設計就要結束了，不但對專業(yè)知識有了更深的理解，更使的自己認識到實踐的重要性，理論、實踐相結合才能達到很好的學習效果，特別是程序語言的學習。 頁面置換算法模擬程序致 謝本次課程設計能順利完成，感謝學校的大力支持,感謝數學與計算機學院為我們提供實練的機會,感謝老師的細心教導。此次的課程設計收獲很多，雖然經過了一段漫長而又痛苦的過程，但是自己還是完成了，這是與自己的努力是分不開的，但是自己在調試過程當中遇到的一些問題，自己仍然不懂，是在同學、老師的幫助下完成的，在這里還要再次對他們的付出表示崇高的敬意。頁面

20、置換算法模擬程序參考文獻參考文獻面向對象程序設計與 VisualC+6.0 教程 陳天華編著C 程序設計（第三版） 譚浩強編著C+入門經典面向對象程序設計與 C+實現 劉晉萍編著計算機操作系統(tǒng)教程 徐甲同等編著 操作系統(tǒng) 羅宇等編著 操作系統(tǒng)實驗教程 張麗芬, 劉利雄, 王全玉編著 計算機操作系統(tǒng) 梁紅兵、哲風屏、湯子瀛 編著操作系統(tǒng)教程 陳向群、楊芙清 編著代碼：#include#include #include #include #define L 20/頁面走向長度最大為 20int M; /內存塊struct Pro/定義一個結構體 int num,time; Input(int m,

21、Pro pL)/打印頁面走向狀態(tài) cout請輸入實際頁面走向長度 L(15=Lm; if(m20|m15)cout實際頁面長度須在 1520 之間;請重新輸入 L： ; else break; while(1); int i,j; j=time(NULL);/取時鐘時間 srand(j);/以時鐘時間 x 為種子，初始化隨機數發(fā)生器cout輸出隨機數: ; for(i=0;im;i+) pi.num=rand( )%10+1;/產生 1 到 10 之間的隨即數放到數組 p 中 pi.time=0;coutpi.num ; coutendl; return m;void print(Pro *p

22、age1)/打印當前的頁面 Pro *page=new ProM; page=page1; for(int i=0;iM;i+) coutpagei.num ; coutendl;int Search(int e,Pro *page1 )/尋找內存塊中與 e 相同的塊號 Pro *page=new ProM; page=page1; for(int i=0;iM;i+)if(e=pagei.num)return i;/返回 i 值 return -1;int Max(Pro *page1)/尋找最近最長未使用的頁面 Pro *page=new ProM; page=page1; int e=p

23、age0.time,i=0; while(iM) /找出離現在時間最長的頁面 頁面置換算法模擬程序 if(epagei.time) e=pagei.time; i+; for( i=0;iM;i+)if(e=pagei.time)return i;/找到離現在時間最長的頁面返回其塊號 return -1;int Count(Pro *page1,int i,int t,Pro pL)/記錄當前內存塊中頁面離下次使用間隔長度 Pro *page=new ProM; page=page1; int count=0; for(int j=i;jL;j+) if(paget.num=pj.num )b

24、reak;/當前頁面再次被訪問時循環(huán)結束 else count+;/否則 count+1 return count;/返回 count 的值 int main() int c; int m=0,t=0;float n=0;Pro pL; m=Input(m,p);/調用 input 函數，返回 m 值 coutM;if(M5|M3)cout內存塊 m 須在 35 之間，請重新輸入 m： ;else break;while(1); Pro *page=new ProM; do頁面置換算法模擬程序 for(int i=0;iM;i+)/初試化頁面基本情況 pagei.num=0; pagei.ti

25、me=m-1-i; i=0; cout1:FIFO 頁面置換endl; cout2:LRU 頁面置換endl; cout3:OPT 頁面置換endl; cout按其它鍵結束程序；c; system(cls); if(c=1)/FIFO 頁面置換 n=0;cout * endl;coutendl; cout FIFO 算法頁面置換情況如下: endl;coutendl; cout * endl; while(i=0) /當前頁面在內存中 coutpi.num ; /輸出當前頁 pi.numcout不缺頁endl;i+; /i 加 1 else /當前頁不在內存中 if(t=M)t=0; else n+; /缺頁次數加 1 paget.num=pi.num; /把當前頁面放入內存中 coutpi.num ; print(page); /打印當前頁面 t+; /下一個內存塊i+; /指向下一個頁面頁面置換算法模擬程序 cout缺頁次數：n 缺頁率：n/mendl; if(c=2)/LRU 頁面置換 n=0; cout * endl;coutendl; cout LRU 算法頁面置換情況如下: endl; coutendl;cout * endl;