操作系統(tǒng)請求分頁式管理(共18頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上目錄專心-專注-專業(yè)課程設(shè)計(jì)題目：請求頁式管理模擬實(shí)現(xiàn)一、需求分析請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本設(shè)計(jì)通過請求頁式存儲管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬 存儲技術(shù)的特點(diǎn)，掌握請求頁式管理的頁面置換算法。 1.設(shè)計(jì)目的1、通過模擬實(shí)現(xiàn)請求分頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點(diǎn)。2、通過頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實(shí)現(xiàn)過程的理解。3、掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實(shí)現(xiàn)過程，并比較它們的效率。 2.設(shè)計(jì)要求通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原

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

3、存放方式為：第 0 條 第 9 條指令為第 0 頁 ( 對應(yīng)虛存地址為 0,9)；第 10 條 第 19 條指令為第 1 頁 ( 對應(yīng)虛存地址為 10,19 ) ；第 310 條 第 319 條指令為第 31 頁 ( 對應(yīng)虛存地址為 310,319) 。按以上方式，用戶指令可組成 32 頁。計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。先進(jìn)先出的算法 (FIFO)；最近最少使用算法 (LRR)；最少訪問頁面算法 (LFR)；最近最不經(jīng)常使用算法 (NUR)。 3.解決方案（一）FIFO頁面置換算法先用bool IsExit()函數(shù)判斷請求頁面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話，就通過

4、Simulatexy%M算出先進(jìn)來的頁面，比如假如第6個數(shù)內(nèi)存中沒有，那置換時(shí)第6行第1列數(shù)一定是第一個進(jìn)來的，我y的值這時(shí)候是6，然后y除以m取余，就是6除以5取余也就是1，然后將第一個置換出來，下面的就是重復(fù)上面的過程了。每次要置換時(shí)LackNum的值就會加1,最后輸出頁面的置換的過程，算出缺頁率。（二）LRU頁面置換算法先用int IsExitLRU()函數(shù)判斷請求頁面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話，int Compare()算出需要置換的頁面，這個功能的實(shí)現(xiàn)需要數(shù)組PageCount來實(shí)現(xiàn)。PageCount這個數(shù)組記錄著內(nèi)存里5個物理塊使用情況，找出需要置換的頁面的列數(shù)，

5、然后賦值給k，再通過Simulatexk=PageOrderx語句置換，每次要置換時(shí)LackNum的值就會加1,最后輸出頁面的置換的過程，算出缺頁率。（三）OPT頁面置換算法先用int IsExitOPT()函數(shù)判斷請求頁面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話，int Compare()2算出需要置換的頁面，我將請求數(shù)后面產(chǎn)生的的隨機(jī)數(shù)一個一個和內(nèi)存中的物理塊的數(shù)比較，當(dāng)相等的時(shí)候，記下相等的物理塊號，再做第二個循環(huán)，第二個循環(huán)比較是除了第一個記錄下來的數(shù)之外的4個數(shù)，相等的時(shí)候，再記下相等的物理塊號，然后再做第三個循環(huán).第四個做完后返回10減去剛剛找到的物理塊號之和。這個就是要置換的數(shù)

6、的列號，然后置換，每次要置換時(shí)LackNum的值就會加1,最后輸出頁面的置換的過程，算出缺頁率。 4實(shí)驗(yàn)提示提示：A.命中率=1-頁面失效次數(shù)/頁地址流長度B.本實(shí)驗(yàn)中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。C.關(guān)于隨機(jī)數(shù)產(chǎn)生方法，采用TC系統(tǒng)提供函數(shù)RAND()和RANDOMIZE()來產(chǎn)生。二、概要設(shè)計(jì) 1、結(jié)構(gòu)說明（一）FIFO頁面置換算法在分配內(nèi)存頁面數(shù)小于進(jìn)程頁面數(shù)時(shí)，當(dāng)然是最先運(yùn)行的頁面放入內(nèi)存。這時(shí)有需要處理新的頁面，則將原來內(nèi)存中的頁面最先進(jìn)入的調(diào)出(是以稱為FIFO)，然后將新頁面放入。以后如果再有新頁面需要調(diào)入，則都按的規(guī)則

7、進(jìn)行。（二）LRU頁面置換算法當(dāng)分配內(nèi)存頁面數(shù)小于進(jìn)程頁面數(shù)時(shí)，當(dāng)然是把最先執(zhí)行的頁面放入內(nèi)存。當(dāng)需要調(diào)頁面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁面全部不空閑時(shí)，選擇將其中最長時(shí)間沒有用到的那個頁面調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁面(稱為LRU)。以后如果再有新頁面需要調(diào)入，則都按的規(guī)則進(jìn)行。（三）OPT頁面置換算法當(dāng)分配內(nèi)存頁面數(shù)小于進(jìn)程頁面數(shù)時(shí)，當(dāng)然是把最先執(zhí)行的頁面放入內(nèi)存。當(dāng)需要調(diào)頁面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁面全部不空閑時(shí)，選擇將其中最近時(shí)間不會用到的那個頁面調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁面(稱為OPT)。以后如果再有新頁面需要調(diào)入，則都按的規(guī)則進(jìn)行 2、數(shù)據(jù)結(jié)構(gòu)及模塊說明定義的變量:co

8、nst int MaxNum=320;/指令數(shù)const int M=5;/內(nèi)存容量int PageOrderMaxNum;/頁面請求int SimulateMaxNumM;/頁面訪問過程int PageCountM,LackNum;/PageCount用來記錄LRU算法中最久未使用時(shí)間,LackNum記錄缺頁數(shù)float PageRate;/命中率函數(shù)說明：bool IsExit(int i) /FIFO算法中判斷新的頁面請求是否在內(nèi)存中int IsExitLRU(int i) /LRU算法中判斷新的頁面請求是否在內(nèi)存中int Compare() /LRU算法找出內(nèi)存中需要置換出來的頁面in

9、t IsExitOPT(int i) /OPT算法中判斷新的頁面請求是否在內(nèi)存中int Compare2(int i) /OPT算法找出內(nèi)存中需要置換出來的頁面void Init() /初始化頁框void designBy() /給自己加的一個標(biāo)題void OutPut() /輸出void FIFO() /FIFO算法void LRU() /LRU算法void OPT() /OPT算法void YourChoice(int choice) /實(shí)現(xiàn)你選擇哪個算法的功能 3、流程圖NYNY開 始隨機(jī)產(chǎn)生320個數(shù) 初始化頁框 輸入算法1=choice=4FIFO算法LRU算法OPT算法 退 出請求

10、頁面是否在內(nèi)存中頁面置換繼續(xù)運(yùn)行輸出運(yùn)行結(jié)果，顯示缺頁率三、詳細(xì)設(shè)計(jì)主要函數(shù)設(shè)計(jì)及說明：#include#includeusing namespace std;const int MaxNum=320;/指令數(shù)const int M=5;/內(nèi)存容量int PageOrderMaxNum;/頁面請求int SimulateMaxNumM;/頁面訪問過程int PageCountM,LackNum;/PageCount用來記錄LRU算法中最久未使用時(shí)間,LackNum記錄缺頁數(shù)float PageRate;/命中率bool IsExit(int i)/FIFO算法中判斷新的頁面請求是否在內(nèi)存中 b

11、ool 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 Compare()/LRU算法找出內(nèi)存中需要置換出來的頁面int p,q;p=PageCount0;q=0; for(int i=1;iM;i+)if(pPageCo

12、unti)p=PageCounti;q=i;return q;int IsExitOPT(int i)/OPT算法中判斷新的頁面請求是否在內(nèi)存中int h=-1; for(int j=0;jM;j+) if(Simulatei-1j=PageOrderi) h=j; return h;int Compare2(int i)/OPT算法找出內(nèi)存中需要置換出來的頁面int q,n,l,m,y,j;q=-1,n=-1,m=-1,l=-1,y=-1; for(int d=i;d320;d+)for(j=0;jM;j+)if(Simulatei-1j=PageOrderd)q=j;break;for(d

13、=i;d320;d+)for( j=0;jM;j+)if(j!=q)if(Simulatei-1j=PageOrderd)n=j;break; for(d=i;d320;d+)for( j=0;jM;j+)if(j!=q&j!=n)if(Simulatei-1j=PageOrderd)m=j;break;for(d=i;d320;d+)for( j=0;jM;j+)if(j!=q&j!=n&j!=m)if(Simulatei-1j=PageOrderd)l=j;break;return (10-q-n-m-l); 說明：將請求數(shù)后面產(chǎn)生的的隨機(jī)數(shù)一個一個和內(nèi)存中的物理塊的數(shù)比較，當(dāng)相等的時(shí)候，

14、記下相等的物理塊號，再做第二個循環(huán)，第二個循環(huán)比較是除了第一個記錄下來的數(shù)之外的4個數(shù)，相等的時(shí)候，再記下相等的物理塊號，然后再做第三個循環(huán).第四個做完后返回10減去剛剛找到的物理塊號之和，這個就是要置換的數(shù)的列號。void Init() /初始化頁框for(int k=0;kMaxNum;k+)int n=rand()%320;/隨機(jī)數(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+)/初始化

15、最久未使用數(shù)組 PageCountq=0;void designBy()printf(n);printf( 課題四：頁面置換算法 n);printf( 班 級：11計(jì)本2班 n);printf( 學(xué) 號： n);printf( 姓 名：周玉亭 n);printf(n);void OutPut()/輸出int i,j;cout頁面訪問序列:endl;for(j=0;jMaxNum;j+)coutPageOrderj ;coutendl;cout頁面訪問過程:endl;for(i=0;i10;i+)for(j=0;jM;j+)if(Simulateij=-1)cout ;elsecoutSimul

16、ateij ;coutendl;coutendl;cout缺頁數(shù)= LackNumendl;cout命中率= PageRateendl;cout-endl;說明：將FIFO算法、LRU算法、OPT算法的頁面訪問過程顯示出來，并輸出缺頁數(shù)和命中率。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;xM

17、axNum;x+)for(int t=0;tM;t+)/先將前一次頁面訪問過程賦值給新的頁面訪問過程Simulatext=Simulatex-1t;if(!IsExit(x)/根據(jù)新訪問頁面是否存在內(nèi)存中來更新頁面訪問過程LackNum+;Simulatexy%M=PageOrderx;y+;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();說明：用Simulatexy%M算出需要置換頁面，比如假如第6個數(shù)內(nèi)存中沒有，那置換時(shí)第6行第1列數(shù)一定是第一個進(jìn)來的，我y的值這時(shí)候是6，然后y除以m取余，就是6除以5取余也就是1，然后將第一

18、個置換出來。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+)/先將前一次頁面訪問過程賦值給新的頁面訪問過程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/根據(jù)反回

19、的p值來更新頁面訪問過程int k;k=Compare();for(int w=0;wM;w+)if(w!=k)PageCountw+;elsePageCountk=1;Simulatexk=PageOrderx;LackNum+;elsefor(int w=0;wM;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();說明:先用一開始的五個頁面放入內(nèi)存中，然后判斷下面要運(yùn)行的頁面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話，int Compare()算出需

20、要置換的頁面。PageCount這個數(shù)組記錄著內(nèi)存里5個物理塊使用情況，找出需要置換的頁面的列數(shù)，然后賦值給k，再通過Simulatexk=PageOrderx語句置換，每次要置換時(shí)LackNum的值就會加1。void OPT()/OPT算法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;

21、x+)for(int t=0;tM;t+)/先將前一次頁面訪問過程賦值給新的頁面訪問過程Simulatext=Simulatex-1t;int p=IsExitOPT(x);if(p=-1)/根據(jù)反回的p值來更新頁面訪問過程int k;k=Compare2(x);Simulatexk=PageOrderx;LackNum+;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();說明：先用一開始的五個頁面放入內(nèi)存中，然后判斷下面要運(yùn)行的頁面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話，就將int Compare2()算出需要置換的頁面的列數(shù)

22、，帶入置換，每次要置換時(shí)LackNum的值就會加1,最后輸出頁面的置換的過程，算出缺頁率。void YourChoice(int choice)switch(choice)case 1:cout-endl;coutFIFO算法結(jié)果如下：endl;FIFO();break;case 2:cout-endl;coutLRU算法結(jié)果如下：endl;LRU();break;case 3:cout-endl;coutOPT算法結(jié)果如下：endl; OPT();break;case 4:break;default:cout重新選擇算法：1-FIFO 2-LRU 3-OPT 4-退出 choice;YourChoice(choice);void main()system(color 0E);designBy();int choice,i=1;while(i)cout請選擇算法：1-FIFO 2-LRU 3-OPT 4-退出 choice;if