模擬請求頁式管理

1、目錄一、設(shè)計目的 1二、設(shè)計內(nèi)容 1三、設(shè)計原理 2四、算法實現(xiàn) 4五、流程圖 5六、源程序 6七、運行示例及結(jié)果分析 14八、心得體會 16九、參考資料 16模擬請求頁式管理一、設(shè)計目的1. 通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法， 了解虛擬存儲技術(shù) 的特點。2. 通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬， 加深對請求調(diào)頁系統(tǒng)的 原理和是實驗過程的理解。3. 掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn) 過程，并比較它們的效率。二、設(shè)計內(nèi)容通過隨機數(shù)產(chǎn)生一個指令序列， 共 320 條指令。指令的地址按下述原則生成： 50% 的指令是順序執(zhí)行的； 25%

2、 的指令是均勻分布在前地址部分； 25% 的指令是均勻分布在后地址部分。具體的實施方法是： 在 0,319 的指令地址之間隨機選取一起點 m； 順序執(zhí)行一條指令； 在前地址0,m+1中隨機選取一條指令并執(zhí)行，該指令的地址為m； 順序執(zhí)行一條指令，其地址為 m +1; 在后地址 m +2,319 中隨機選取一條指令并執(zhí)行 ； 重復上述步驟 ， 直到執(zhí)行 320 次指令。將指令序列變換成為頁地址流設(shè)：頁面大小為1K; 用戶內(nèi)存容量為4頁到32頁； 用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛 存中的存放方式為：第0條第9條指令為第0頁（對應虛存地址為0,

3、9）；第10條第19條指令為第1頁（對應虛存地址為10,19）；IIIIII第310條第319條指令為第31頁（對應虛存地址為310,319）。按以上方式，用戶指令可組成 32頁。計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。先進先出的算法（FIFO）;最近最久未使用算法（LRU）；最佳訪問算法（OPT；三、設(shè)計原理FIFO頁面置換算法原理簡述 在分配內(nèi)存頁面數(shù)（AP）小于進程頁面數(shù)（PP）時，當然是最先運行的AP個頁面 放入內(nèi)存。 這時有需要處理新的頁面，則將原來內(nèi)存中的AP個頁面最先進入的調(diào)出（是以 稱為FIFO），然后將新頁面放入。 以后如果再有新頁面需要調(diào)入，則都按的規(guī)則進行。算法特

4、點：所使用的內(nèi)存頁面構(gòu)成一個隊列。LRU頁面置換算法原理算述 當分配內(nèi)存頁面數(shù)（AP）小于進程頁面數(shù)（PP）時，當然是把最先執(zhí)行的 AP個頁 面放入內(nèi)存。 當需要調(diào)頁面進入內(nèi)存，而當前分配的內(nèi)存頁面全部不空閑時， 選擇將其中最 長時間沒有用到的那個頁面調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁面 （稱為LRU）。 算法特點：每個頁面都有屬性來表示有多長時間未被 CPU使用的信息。LRU算法的硬件支持把LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能 適用，但實現(xiàn)起來有相當大的難度，因為它要求系統(tǒng)具有較多的支持硬件。 所要解決的問題有：1. 一個進程在內(nèi)存中的各個頁面各有多久時間未被進程訪問

5、；2. 如何快速地知道哪一頁最近最久未使用的頁面。為此，須利用以下兩 類支持硬件：（1）寄存器用于記錄某進程在內(nèi)存中各頁的使用情況。實頁/RR7R6R5R4R3R2R1R0101010010210101100300O001004011010115110101106001010117000001118011011 1012)?？衫靡粋€特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。四、算法實現(xiàn)A. 命中率=1-頁面失效次數(shù)/頁地址流長度B. 本實驗中，頁地址流長度為 320，頁面失效次數(shù)為每次訪問相應指令時，該指令所對應的頁不在內(nèi)存的

6、次數(shù)。C. 關(guān)于隨機數(shù)產(chǎn)生方法，采用 TC系統(tǒng)提供函數(shù)RAND(和RANDOMIZE來 產(chǎn)生。const int MaxNum=320;/ 指令數(shù)const int M=5;/ 內(nèi)存容量int PageOrderMaxNum;/ 頁面請求int SimulateMaxNumM;/ 頁面訪問過程int PageCountM,LackNum;/PageCount用來記錄LRU算法中最久未使用時間，LackNum記錄缺頁數(shù)float PageRate;/ 命中率;PageRate=1-(float)LackNum/(float)MaxNum);/ 計算命中率int n=rand()%320;/ 隨機

7、數(shù)產(chǎn)生 320 次頁面請求PageOrderk=n/10;/ 根據(jù)指令產(chǎn)生 320次頁面請求五、流程圖六、源程序# include# includeusing namespace std;const int MaxNum=320;/ 指令數(shù)const int M=5;/ 內(nèi)存容量int PageOrderMaxNum;/ 頁面請求int SimulateMaxNumM;/ 頁面訪問過程int PageCountM,LackNum;/PageCount用來記錄LRU算法中最久未使用時間, LackNum記錄缺頁數(shù)int PageCountOPTM;/PageCountOPT用來記錄OPT算法中最

8、久未使用時間 float PageRate;/ 命中率int PageCount132;bool IsExit(int i)/FIFO 算法中判斷新的頁面請求是否在內(nèi)存中bool f=false;for(int j=0;jM;j+)if(Simulatei-1j=PageOrderi)/在前一次頁面請求過程中尋找是否存在新的頁面請求f=true;return f;int IsExitLRU(int i)/LRU 算法中判斷新的頁面請求是否在內(nèi)存中int f=-1;for(int j=0;jM;j+)if(Simulatei-1j=PageOrderi)f=j;return f;int Comp

9、are()/LRU 算法找出內(nèi)存中需要置換出來的頁面int p,q;p=PageCount0;q=0;for(int i=1;iM;i+)if (pPageCounti)p=PageCounti; q=i;return q;int CompareOPT(int i)/OPT 算法找出內(nèi)存中需要置換出來的頁面 int temp5;for(int a=0;a5;a+)tempa=0;for(int j=0;jM;j+)for(int ii=i+1;iiMaxNum;ii+) if(Simulatei-1j!=PageOrderii) tempj+;else break;int max=temp0;

10、int maxIndex=0;for(int i1=1;i1M;i1+) if(maxtempi1) max=tempi1; maxIndex=i1;return maxIndex;void Init()/ 初始化頁框for(int k=0;kMaxNum;k+)int n=rand()%320;/ 隨機數(shù)產(chǎn)生 320 次頁面請求PageOrderk=n/10;/ 根據(jù)指令產(chǎn)生 320 次頁面請求 for(int i=0;iMaxNum;i+)/ 初始化頁面訪問過程for(int j=0;jM;j+)Simulateij=-1;for (int q=0;qM;q+)/初始化最久未使用數(shù)組Pag

11、eCountq=0;PageCountOPTq=0;void AllNum()int j;cout 頁面訪問序列： endl;for(j=0;jMaxNum;j+)coutPageOrderj ;void OutPut()/ 輸出int i,j;coutendl;cout 頁面訪問過程(只顯示前十個) ： endl; for(i=0;i10;i+)for(j=0;jM;j+)if(Simulateij=-1) cout ;else coutSimulateij ; coutendl;cout 缺頁率 = LackNumendl;cout 命中率 = PageRateendl;coutendl;

12、void FIFO()/FIFO 算法int j,x=0,y=0;LackNum=0;Init(); / 初始化for(j=0;jM;j+)/ 將前五個頁面請求直接放入內(nèi)存中for(int k=0;k=j;k+)if(j=k) Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k;LackNum+; for(x=M;xMaxNum;x+)for(int t=1;tM;t+)Simulatext=Simulatex-1t;if(!IsExit(x)/ 根據(jù)新訪問頁面是否存在內(nèi)存中來更新頁面訪問過程 LackNum+;Simulatexy%M=Pag

13、eOrderx;y+; PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率AllNum();OutPut();void LRU()/LRU 算法int j,x=0,y=0;LackNum=0;Init();for(j=0;jM;j+)/ 將前五個頁面請求直接放入內(nèi)存中for(int k=0;k=j;k+)PageCountk+; if(j=k)Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先將前一次

14、頁面訪問過程賦值給新的頁面訪問 過程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/ 根據(jù)返回的 p 值來更新頁面訪問過程int k; k=Compare(); for(int w=0;wM;w+) if(w!=k)PageCountw+;else PageCountk=1;Simulatexk=PageOrderx;LackNum+;elsefor(int w=0;wM;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/ 算

15、出命中率AllNum();OutPut();void OPT()/ 最佳訪問算法 Optimalint j,x=0,y=0;LackNum=0;Init();for(j=0;jM;j+)/ 將前五個頁面請求直接放入內(nèi)存中for(int k=0;k=j;k+)PageCountOPTk+; if(j=k)Simulatejk=PageOrderj;elseSimulatejk=Simulatej-1k;LackNum+;AllNum();for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先將前一次頁面訪問過程賦值給新的頁面訪問 過程Simulatext=Simulat

16、ex-1t;int p=IsExitLRU(x);/OPT 算法中判斷新的頁面請求是否在內(nèi)存中 if(p=-1)/ 根據(jù)返回的 p 值來更新頁面訪問過程int k;k=CompareOPT(x);/OPT 算法找出內(nèi)存中需要置換出來的頁面for(int w=0;wM;w+) if(w!=k)PageCountOPTw+;elsePageCountOPTk=1;Simulatexk=PageOrderx;LackNum+;elsefor(int w=0;wM;w+) if(w!=p)PageCountOPTw+;elsePageCountOPTp=1;PageRate=1-(float)Lack

17、Num/(float)MaxNum);/ 算出命中率 OutPut();void YourChoice(int choice)switch(choice)case 1:coutendl;coutFIFO 算法結(jié)果如下： endl; FIFO();break;case 2:退出endl;退出 endl;coutendl;coutLRU 算法結(jié)果如下： endl; LRU(); break;case 3:coutendl;coutOPT 算法結(jié)果如下： endl; OPT(); break;case 4:break;default:coutchoice;YourChoice(choice);voi

18、d main()int choice,i=1;while(i)coutchoice;if(choice=1|choice=2|choice=3|choice=4) YourChoice(choice);七、運行示例及結(jié)果分析Pggj曲rADktop鎮(zhèn)擬請求員式苣理課程設(shè)計陋氓b喊皿凸&2 2 30 30 23 ?26 27 20 5 13 27 10 5 IS S ?28 25 522 14 12Z? 13 271 fl 9 Ifl7 17 ? 1826 20 14 20 17 08 2018238 28 26 631 02126 12 30192282417 27 21 2? 112?16

19、27 3120727212 3 31 KA 271S4 27 2fl 3B2H2R1 0 23 12 22 13 26 12 21 30 31 23 22 8 23 6 14貞面訪間過程（只顯示前十個）：e 3 5 11 9 14 11 2 14 15 14 1621 9 23 22 25 5 1? 12 12 1? 1? 7 1 21 16 27 7 24 6 31 1G 2? 31 2E16 24 丄Z $ 31 27 10 38 1& 13 12 3 1H 21 i訶2耳S! 1 R 4 20斤門7陽2 27 23 13 26 27 7 4 44 22 2S4 22 25 264 22

20、25 26 28226252-279482愴竭華算法：1FIFO 2LRU 3OPT 4 一退出少瞠法結(jié)果如下: 頁圓昉冋序列；14 15 2 14 19 15 9 25 12 10 16 28 29 13 19 18 27 19 2 10 15 3 14 21 27 24 23 141 .23163 28 14 163E）15 6 8 24 9292922IS242522 30 3 32810 23 25 3 22212? S2222169 26 0 25126 26 0 14 21261028125 19 523 11 19161 18 24 ? 14251318| 31 11 24 16

21、 2 0 520 21 5 19 29 18 23 7 26 16 6 31 3131 31 23 12 13 15 17 17 27 16 10 2323 22 ? 9 23 17 14 26 24 26 22 30 41? 20 1 25 25 6 9 6 19 19 17 20 5 30!4 12 27 21 14 2729 4 2D 27 24 138 7 17 2 7 2R 229 25 1 1 28 12 819 30 3 2S 3 292720 30 26 12 11 23 16 21 53 6 28 15 R 7 3021 23 18 24 94 24 27 11 1411 7

22、 25 10 2417 15 29 14 20 3 12 30 20 121 26 313 6 213 6 46 7 1112 28 13 ? 6 2 18 24 14 4 18 8 3 20 10 0 14 5 10 6 18 11 ?2212203117192016 2S19 2313 3R19 1R10 122 1130 1 0 1 21 2 26 92022221514 7 8 152 2726 322 3 3 31 23 2629 21 9 21 B 62 25 16 1H 17 115 20耳面訪問過複（只顯示前十個），p 15 25 14 1? b 15 25 12 19 I?

23、15 25 12 101414151415214152141415214191415214199 15 25 12 10觸頁峑二275命中率=0.140625請選擇算法：1FIFO 2LRU 3-0PT4退岀4-|D|x|請選擇算法：1FIFO 2LRU 3OPT 4 退岀C:DocajnexktH Set3ugO2. cxc蘭T畀法結(jié)杲如下貝面訪冋序列：13 19 12 3 23 23 1 29 5 21 27 29 4 15 20 24 20 21 29 2 7 10 15 11 9 18 28 5 1 11|31 24 30 2 230 9 12 1723261128 266 10 20

24、 2029 512 31 5 4 21 31 22 16 3 |7 11 1818 2415 22 13 120162818 1026 26 12 59280026 25 11 23 30 13 27i11 24 17 25 3A 22 29 4 14 20 9 26 19 19 1R 23 26 11 16 22 19 22 12 26 3R 3A M 2 15 30 16 1 15 27 12 9 A14142 A 8R 25 12 26 16f；15 A 22 24 20 3A 1418 11 26 20 25 10 8 30 14 5 17 1 24 3! 31 2 17 5 22 1

25、9 1 11 29 1 24 22 15 1 I 0 22 6 15 20 2 18 4 0 30 0 21 27 30 2 29 14 24 17 15 1 丄0 丄5 2 4 “ 9 23 3 8 23 16 13 6 b 3 1428 6 10IS 198 6 5 26 4312 10 18 5 30 11 22 14 3125226 8 IS 25 12 14 23 27 8 13 22 19 2814 21 2234307 31 14 151 2 9 23 25 2525 11 07211731 24 22930 31 6 17 14 24 15 5 22 2 8 28 19 21 5 158 20