操作系統(tǒng)請(qǐng)求分頁(yè)式管理

1、目錄一、需求分析 11. 設(shè)計(jì)目的 12. 設(shè)計(jì)要求 13. 解決方案 24實(shí)驗(yàn)提示 2二、概要設(shè)計(jì) 21、結(jié)構(gòu)說(shuō)明 22、數(shù)據(jù)結(jié)構(gòu)及模塊說(shuō)明 33、流程圖 4三、詳細(xì)設(shè)計(jì) 4四調(diào)試分析 14五、總結(jié) 171、遇到的問(wèn)題 172、不足 173、心得體會(huì) 17六、參考文獻(xiàn) 18課程設(shè)計(jì)題目：請(qǐng)求頁(yè)式管理模擬實(shí)現(xiàn)一、需求分析請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。 本設(shè)計(jì)通過(guò)請(qǐng)求頁(yè)式存儲(chǔ)管 理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬 存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式管理的 頁(yè)面置換算法。1. 設(shè)計(jì)目的1、通過(guò)模擬實(shí)現(xiàn)請(qǐng)求分頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解虛擬 存儲(chǔ)技術(shù)的特點(diǎn)。2、通過(guò)頁(yè)面、頁(yè)表、地址

2、轉(zhuǎn)換和頁(yè)面置換過(guò)程的模擬，加深對(duì)請(qǐng)求調(diào)頁(yè)系 統(tǒng)的原理和實(shí)現(xiàn)過(guò)程的理解。3、掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想和 實(shí)現(xiàn)過(guò)程，并比較它們的效率。2. 設(shè)計(jì)要求通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列， 共 320 條指令。指令的地址按下述原則生成： 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ī)

3、選取一條指令并執(zhí)行 ； 重復(fù)上述步驟 ， 直到執(zhí)行 320 次指令。 將指令序列變換成為頁(yè)地址流設(shè)：頁(yè)面大小為1K; 用戶內(nèi)存容量為 4 頁(yè)到 32 頁(yè) ； 用戶虛存容量為 32K 。在用戶虛存中， 按每 K 存放 10 條指令排列虛存地址， 即 320 條指令在虛 存中的存放方式為：第 0 條 第 9 條指令為第 0 頁(yè) （ 對(duì)應(yīng)虛存地址為 0,9）；第 10 條 第 19 條指令為第 1 頁(yè) （ 對(duì)應(yīng)虛存地址為 10,19 ）；第 310 條 第 319 條指令為第 31 頁(yè) （ 對(duì)應(yīng)虛存地址為 310,319） 按以上方式，用戶指令可組成 32 頁(yè)。計(jì)算并輸出下述各種算法在不同內(nèi)存容量下

4、的命中率。先進(jìn)先出的算法 （FIFO） ；最近最少使用算法 （LRR） ；操作系統(tǒng)-課程設(shè)計(jì)最少訪問(wèn)頁(yè)面算法（LFR）;最近最不經(jīng)常使用算法（NUR）。3. 解決方案（一）FIFO頁(yè)面置換算法先用bool lsExit（）函數(shù)判斷請(qǐng)求頁(yè)面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn)行， 不在的話，就通過(guò)Simulatexy%M算出先進(jìn)來(lái)的頁(yè)面，比如假如第6個(gè)數(shù)內(nèi)存中沒(méi)有，那置換時(shí)第6行第1列數(shù)一定是第一個(gè)進(jìn)來(lái)的，我y的值這時(shí)候是6, 然后y除以m取余，就是6除以5取余也就是1，然后將第一個(gè)置換出來(lái)，下面 的就是重復(fù)上面的過(guò)程了。每次要置換時(shí)LackNum的值就會(huì)加1,最后輸出頁(yè)面的置換的過(guò)程，算出缺頁(yè)率。（

5、二）LRU頁(yè)面置換算法先用int IsExitLRU（）函數(shù)判斷請(qǐng)求頁(yè)面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn) 行，不在的話，int Compare。算出需要置換的頁(yè)面，這個(gè)功能的實(shí)現(xiàn)需要數(shù)組 PageCount來(lái)實(shí)現(xiàn)。PageCount這個(gè)數(shù)組記錄著內(nèi)存里5個(gè)物理塊使用情況， 找出需要置換的頁(yè)面的列數(shù)，然后賦值給 k，再通過(guò) Simulatexk=PageOrderx語(yǔ)句置換，每次要置換時(shí)LackNum的值就會(huì)加1,最后輸出頁(yè)面的置換的過(guò)程，算出缺頁(yè)率。（三）OP頂面置換算法先用int IsExitOPT（）函數(shù)判斷請(qǐng)求頁(yè)面是否在內(nèi)存中，在內(nèi)存中就直接運(yùn) 行，不在的話，int Compare（）2

6、算出需要置換的頁(yè)面，我將請(qǐng)求數(shù)后面產(chǎn)生的 的隨機(jī)數(shù)一個(gè)一個(gè)和內(nèi)存中的物理塊的數(shù)比較，當(dāng)相等的時(shí)候，記下相等的物理塊號(hào)，再做第二個(gè)循環(huán)，第二個(gè)循環(huán)比較是除了第一個(gè)記錄下來(lái)的數(shù)之外的4個(gè)數(shù)，相等的時(shí)候，再記下相等的物理塊號(hào)，然后再做第三個(gè)循環(huán) 第四個(gè)做完后返回10減去剛剛找到的物理塊號(hào)之和。這個(gè)就是要置換的數(shù)的列號(hào)，然后 置換，每次要置換時(shí)LackNum的值就會(huì)加1,最后輸出頁(yè)面的置換的過(guò)程，算出 缺頁(yè)率。4 實(shí)驗(yàn)提示提示：A.命中率=1-頁(yè)面失效次數(shù)/頁(yè)地址流長(zhǎng)度B. 本實(shí)驗(yàn)中，頁(yè)地址流長(zhǎng)度為320，頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí)， 該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存的次數(shù)。C. 關(guān)于隨機(jī)數(shù)產(chǎn)生方法，采

7、用 TC系統(tǒng)提供函數(shù)RAND（和 RANDOMIZE來(lái)產(chǎn) 生。、概要設(shè)計(jì)1、結(jié)構(gòu)說(shuō)明（一）FIFO頁(yè)面置換算法 在分配內(nèi)存頁(yè)面數(shù)小于進(jìn)程頁(yè)面數(shù)時(shí)，當(dāng)然是最先運(yùn)行的頁(yè)面放入內(nèi)存。 這時(shí)有需要處理新的頁(yè)面，則將原來(lái)內(nèi)存中的頁(yè)面最先進(jìn)入的調(diào)出（是以稱為FIFO），然后將新頁(yè)面放入。 以后如果再有新頁(yè)面需要調(diào)入，則都按的規(guī)則進(jìn)行。（二）LRU頁(yè)面置換算法 當(dāng)分配內(nèi)存頁(yè)面數(shù)小于進(jìn)程頁(yè)面數(shù)時(shí)，當(dāng)然是把最先執(zhí)行的頁(yè)面放入內(nèi) 存。操作系統(tǒng)-課程設(shè)計(jì) 當(dāng)需要調(diào)頁(yè)面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁(yè)面全部不空閑時(shí)， 選擇將其中最長(zhǎng)時(shí)間沒(méi)有用到的那個(gè)頁(yè)面調(diào)出，以空出內(nèi)存來(lái)放置新調(diào)入的頁(yè)面（稱為L(zhǎng)RU）。 以后如果再有新頁(yè)

8、面需要調(diào)入，則都按的規(guī)則進(jìn)行。（三）0P頂面置換算法 當(dāng)分配內(nèi)存頁(yè)面數(shù)小于進(jìn)程頁(yè)面數(shù)時(shí)，當(dāng)然是把最先執(zhí)行的頁(yè)面放入內(nèi) 存。 當(dāng)需要調(diào)頁(yè)面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁(yè)面全部不空閑時(shí)， 選擇將其中最近時(shí)間不會(huì)用到的那個(gè)頁(yè)面調(diào)出，以空出內(nèi)存來(lái)放置新調(diào)入的頁(yè)面（稱為OPT） 以后如果再有新頁(yè)面需要調(diào)入，則都按的規(guī)則進(jìn)行2、數(shù)據(jù)結(jié)構(gòu)及模塊說(shuō)明定義的變量：const int MaxNum=320; 指令數(shù)const int M=5;內(nèi)存容量int PageOrderMaxNum; 頁(yè)面請(qǐng)求int SimulateMaxNumM;頁(yè)面訪問(wèn)過(guò)程int PageCountM,LackNum;/PageCount

9、用來(lái)記錄 LRU算法中最久未使用時(shí)間丄ackNu m記錄缺頁(yè)數(shù)float PageRate;/ 命中率函數(shù)說(shuō)明：bool IsExit(i nt i)/FIFO在內(nèi)存中int IsExitLRU(int i)/LRU在內(nèi)存中int Compare。/LRUint lsExitOPT(i nt i)/OPT在內(nèi)存中int Compare2(i nt i)/OPT貝面void Init()/void desig nBy()/void OutPut()/void FIFO()/FIFOvoid LRU()/LRUvoid OPT()/OPTvoid YourChoice(i nt choice) /

10、算法中判斷新的頁(yè)面請(qǐng)求是否算法中判斷新的頁(yè)面請(qǐng)求是否算法找出內(nèi)存中需要置換出來(lái)的頁(yè)面 算法中判斷新的頁(yè)面請(qǐng)求是否算法找出內(nèi)存中需要置換出來(lái)的初始化頁(yè)框給自己加的一個(gè)標(biāo)題輸出算法算法算法實(shí)現(xiàn)你選擇哪個(gè)算法的功能操作系統(tǒng)-課程設(shè)計(jì)3、流程圖三、詳細(xì)設(shè)計(jì)主要函數(shù)設(shè)計(jì)及說(shuō)明： #in clude #in clude using n amespace std;const int MaxNum=320;/ 指令數(shù)const int M=5;/ 內(nèi)存容量int PageOrderMaxNum;/ 頁(yè)面請(qǐng)求int SimulateMaxNumM;/ 頁(yè)面訪問(wèn)過(guò)程int PageCountM,LackNum;/

11、PageCount 用來(lái)記錄 LRU算法中最久未使用 時(shí)間丄ackNu m記錄缺頁(yè)數(shù)float PageRate;/ 命中率bool IsExit(int i)/FIFO 算法中判斷新的頁(yè)面請(qǐng)求是否在內(nèi)存中bool f=false;for(int j=0;jM;j+)if(Simulatei-1j=PageOrderi)/在前一次頁(yè)面請(qǐng)求過(guò)程中尋找是否存在新的頁(yè)面請(qǐng)求f=true;return f;int IsExitLRU(int i)/LRU 算法中判斷新的頁(yè)面請(qǐng)求是否在內(nèi)存中int f=-1;for(int j=0;jM;j+)if(Simulatei-1j=PageOrderi)f=j

12、;return f;int Compare()/LRU 算法找出內(nèi)存中需要置換出來(lái)的頁(yè)面int p,q;p=PageCount0;q=0;for(int i=1;iM;i+)if(pPageCounti)p=PageCounti; q=i;return q;int IsExitOPT(int i)/OPT算法中判斷新的頁(yè)面請(qǐng)求是否在內(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)存中需要置換出來(lái)的頁(yè)面 int q,n,l,m,y,j; q=-1

13、,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=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

14、!=m)if(Simulatei-1j=PageOrderd)l=j;break;return (10-q-n-m-l);說(shuō)明：將請(qǐng)求數(shù)后面產(chǎn)生的的隨機(jī)數(shù)一個(gè)一個(gè)和內(nèi)存中的物理塊的數(shù)比較， 當(dāng)相等的時(shí)候， 記下相等的物理塊號(hào)， 再做第二個(gè)循環(huán)， 第二個(gè)循環(huán)比較是除了 第一個(gè)記錄下來(lái)的數(shù)之外的 4 個(gè)數(shù)，相等的時(shí)候， 再記下相等的物理塊號(hào)， 然后 再做第三個(gè)循環(huán) . 第四個(gè)做完后返回 10 減去剛剛找到的物理塊號(hào)之和， 這個(gè)就 是要置換的數(shù)的列號(hào)。void Init() / 初始化頁(yè)框for(int k=0;kMaxNum;k+)int n=rand()%320;/ 隨機(jī)數(shù)產(chǎn)生 320 次指令P

15、ageOrderk=n/10;/ 根據(jù)指令產(chǎn)生 320 次頁(yè)面請(qǐng)求 for(int i=0;iMaxNum;i+)/ 初始化頁(yè)面訪問(wèn)過(guò)程for(int j=0;jM;j+)Simulateij=-1;for(int q=0;qM;q+)/ 初始化最久未使用數(shù)組PageCountq=0;void designBy()printf( iin);prin tf(|課題四：頁(yè)面置換算法n);prin tf(|班級(jí)：11計(jì)本 2 班n);printf( |學(xué)號(hào)： 20110303214n);printf( |姓名：周玉亭n);printf(n);void OutPut()/ 輸出int i,j;cout

16、 頁(yè)面訪問(wèn)序列 :endl; for(j=0;jMaxNum;j+)coutPageOrderj ;coutendl;cout 頁(yè)面訪問(wèn)過(guò)程 :endl; for(i=0;i10;i+)for(j=0;jM;j+) if(Simulateij=-1) cout ;else coutSimulateij ;coutendl;coutendl;cout 缺頁(yè)數(shù)= LackNumendl;cout 命中率= PageRateendl;coutendl;說(shuō)明：將FIFO算法、LRU算法、OPT算法的頁(yè)面訪問(wèn)過(guò)程顯示出來(lái)，并輸出 缺頁(yè)數(shù)和命中率。void FIFO()/FIFO 算法int j,x=0,

17、y=0;LackNum=0,Init();for(j=0;jM;j+)/ 將前五個(gè)頁(yè)面請(qǐng)求直接放入內(nèi)存中for(int k=0;k=j;k+) if(j=k)Simulatejk=PageOrderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先將前一次頁(yè)面訪問(wèn)過(guò)程賦值給新的頁(yè)面 訪問(wèn)過(guò)程 Simulatext=Simulatex-1t;if(!IsExit(x)/ 根據(jù)新訪問(wèn)頁(yè)面是否存在內(nèi)存中來(lái)更新頁(yè)面訪問(wèn) 過(guò)程LackNum+;Simulatexy%M=PageOrderx;y+;

18、PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率 OutPut();說(shuō)明：用 Simulatexy%M 算出需要置換頁(yè)面，比如假如第 6 個(gè)數(shù)內(nèi)存中 沒(méi)有，那置換時(shí)第6行第1列數(shù)一定是第一個(gè)進(jìn)來(lái)的，我y的值這時(shí)候是6,然 后y除以m取余，就是6除以5取余也就是1，然后將第一個(gè)置換出來(lái)。void LRU()/LRU 算法int j,x=0,y=0;LackNum=0,Init();for(j=0;jM;j+)/ 將前五個(gè)頁(yè)面請(qǐng)求直接放入內(nèi)存中for(int k=0;k=j;k+)PageCountk+;if(j=k)Simulatejk=PageO

19、rderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先將前一次頁(yè)面訪問(wèn)過(guò)程賦值給新的頁(yè)面 訪問(wèn)過(guò)程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/ 根據(jù)反回的 p 值來(lái)更新頁(yè)面訪問(wèn)過(guò)程int k;k=Compare();for(int w=0;wM;w+) if(w!=k) PageCountw+;elsePageCountk=1;Simulatexk=PageOrderx;LackNum+;elsefor(int w=0;wM

20、;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率 OutPut();說(shuō)明: 先用一開始的五個(gè)頁(yè)面放入內(nèi)存中，然后判斷下面要運(yùn)行的頁(yè)面是否 在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話， int Compare() 算出需要置換的頁(yè) 面。 PageCount 這個(gè)數(shù)組記錄著內(nèi)存里 5個(gè)物理塊使用情況，找出需要置換的 頁(yè)面的列數(shù)，然后賦值給 k，再通過(guò)Simulatexk=PageOrderx 語(yǔ)句置換， 每次要置換時(shí)LackNum的值就會(huì)加1。void OPT()/OPT

21、算法int j,x=0,y=0;LackNum=0,Init();for(j=0;jM;j+)/ 將前五個(gè)頁(yè)面請(qǐng)求直接放入內(nèi)存中for(int k=0;k=j;k+)/PageCountk+;if(j=k)Simulatejk=PageOrderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先將前一次頁(yè)面訪問(wèn)過(guò)程賦值給新的頁(yè)面 訪問(wèn)過(guò)程Simulatext=Simulatex-1t;int p=IsExitOPT(x);if(p=-1)/ 根據(jù)反回的 p 值來(lái)更新頁(yè)面訪問(wèn)過(guò)程int k

22、; k=Compare2(x); Simulatexk=PageOrderx; LackNum+;PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率 OutPut(); 說(shuō)明：先用一開始的五個(gè)頁(yè)面放入內(nèi)存中， 然后判斷下面要運(yùn)行的頁(yè)面是否 在內(nèi)存中，在內(nèi)存中就直接運(yùn)行，不在的話，就將 int Compare2() 算出需要置 換的頁(yè)面的列數(shù)，帶入置換，每次要置換時(shí)LackNum的值就會(huì)加1,最后輸出頁(yè)面的置換的過(guò)程，算出缺頁(yè)率。void YourChoice(int choice) switch(choice) case 1:coutendl;co

23、utFIFO 算法結(jié)果如下： endl; FIFO();break;3-OPT 4- 退 出退出 endl;case 2:coutendl;coutLRU 算法結(jié)果如下： endl; LRU();break;case 3:coutendl;coutOPT 算法結(jié)果如下： endl; OPT();break;case 4: break;default:cout 重 新選擇算 法： 1-FIFO 2-LRU choice; YourChoice(choice);void main()system(color 0E); designBy(); int choice,i=1;while(i)coutc

24、hoice;if(choice=4)i=0;else YourChoice(choice);四. 調(diào)試分析調(diào)試過(guò)程和調(diào)試結(jié)果 一開始運(yùn)行出來(lái)的界面:頁(yè)面置換算法 過(guò)計(jì)本2班 2011303214周玉亭請(qǐng)選擇算法：1FIFO 2LRU 3OPT百-退岀F:3-Debug3.exe題選擇FIFO算法運(yùn)行的界面:操作系統(tǒng)-課程設(shè)計(jì)如下:情選擇算法】1FIFO 2LRU 3OPT 4-退岀274 0,14375請(qǐng)選擇算法：1FIFO 2LRU 3OPT 4-退岀1節(jié)中*F：-3Debug3-ex15 11 24 26 2 6 IB G24 24 12 21 Q S31 28G 7 21B14e it1

25、901i17 G3i3 12 9 9 11 1G 2022 3 7 15 21 30 121 631 3U22264 191962121291717 20 7 27 12 29 2119 21 15 19 30 2820 23G 118139 122314222B20152 2 30 30 23 9 4 2627 20 5 13 27 105 18 87 ZU83 S11號(hào)141121415142S 25 5 7 17 9 1S 2620 14 2B 17 Q B20 1823 2192322 2551712121919*2 14 12 8 28 26 6 31B 21 26 12 30 1922 824 1 :211Q27 724 16 311627 31 :!9 1J 27 1? 2? 21 2711 29 16 2? 31 287 2721 1624128 312?Ifi1 30