分頁系統(tǒng)模擬實(shí)驗(yàn)

1、1*實(shí)踐教學(xué)實(shí)踐教學(xué)* 蘭州理工大學(xué)蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2013 年秋季學(xué)期操作系統(tǒng)原理操作系統(tǒng)原理課程設(shè)計(jì)課程設(shè)計(jì)題 目： 分頁系統(tǒng)模擬實(shí)驗(yàn) 專業(yè)班級:計(jì)算機(jī)科學(xué)與技術(shù)基地班 姓 名： 孫要全 學(xué) 號： 11240311 指導(dǎo)教師： 王旭陽 成 績： _ 2目目 錄錄前前 言言.3摘摘 要要.41 設(shè)計(jì)思想.52 相關(guān)的各模塊的偽碼算法.63 函數(shù)的調(diào)用關(guān)系圖.124 調(diào)試結(jié)果.14總總 結(jié)結(jié).17參考文獻(xiàn)參考文獻(xiàn).18致致 謝謝.19附件附件源程序代碼源程序代碼.203前前 言言分頁式虛擬存儲系統(tǒng)將作業(yè)信息的副本存放在磁盤中，不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，僅裝入立即使用的頁面，

2、在執(zhí)行過程中訪問到不在主存的頁面時(shí)，產(chǎn)生缺頁中斷，再把它們動態(tài)地裝入。虛擬存儲的基本思想是基于程序的局部性原理，僅把目前需要的部分程序加載到內(nèi)存，其余暫時(shí)不用的程序及數(shù)據(jù)還保留在輔存中。在進(jìn)程運(yùn)行過程中，如果所要執(zhí)行的程序不在內(nèi)存，系統(tǒng)要將要執(zhí)行的程序段自動調(diào)入內(nèi)存。 此時(shí)如果內(nèi)存已滿，則要通過置換操作將暫時(shí)不用的程序段先調(diào)出到輔存，然后將所需的程序段調(diào)入內(nèi)存，繼續(xù)執(zhí)行該進(jìn)程。 虛擬存儲器的引入，實(shí)際上是利用了存儲管理中邏輯地址空間和物理地址空間的關(guān)系，將計(jì)算機(jī)的內(nèi)存和輔存結(jié)合起來，使得用戶感覺具有大容量的內(nèi)存，虛擬內(nèi)存在將邏輯地址轉(zhuǎn)換成物理地址時(shí)，必須通過一個(gè)內(nèi)存管理單元MMU（Memory

3、 Management Unit）來完成。 存儲管理一直是操作系統(tǒng)中的重要組成部分，因?yàn)轳T諾依曼體系結(jié)構(gòu)就是建立在存儲程序概念上的，訪問存儲器的操作占 CPU 時(shí)間的 70%左右。計(jì)算機(jī)系統(tǒng)中的存儲器一般分為主存儲器（簡稱主存、內(nèi)存）和輔助存儲器（簡稱輔存） 。由于 CPU 只能直接與內(nèi)存進(jìn)行通信，因此計(jì)算機(jī)系統(tǒng)的程序以及與該程序相關(guān)的數(shù)據(jù)，只有被裝入到內(nèi)存中才能有效地執(zhí)行。計(jì)算機(jī)系統(tǒng)能否高效地管理內(nèi)存空間，不僅直接反映存儲器的利用率，還會影響整個(gè)操作系統(tǒng)的性能。4摘摘 要要請求分頁虛擬存儲系統(tǒng)時(shí)間作業(yè)信息的副本存放在磁盤這一類輔助存儲器中當(dāng)作業(yè)被調(diào)度投入運(yùn)行時(shí)，并不把作業(yè)的程序和數(shù)據(jù)全部裝入

4、主存，而僅僅裝入立即使用的那些頁面，至少要將作業(yè)的第一頁信息裝入主存，在執(zhí)行過程中訪問到不在主存的頁面時(shí)，再把它們動態(tài)裝入。分頁式虛擬存儲管理是請求分頁，當(dāng)需要執(zhí)行某條指令或使用某個(gè)數(shù)據(jù)，而發(fā)現(xiàn)它們不再主存時(shí)，產(chǎn)生一個(gè)缺頁中斷，系統(tǒng)從輔存中把該指令或數(shù)據(jù)所在的頁面調(diào)入內(nèi)存。關(guān)鍵詞：分頁 虛擬 輔存 缺頁中斷51 1 設(shè)計(jì)思想設(shè)計(jì)思想 1.1 算法思想算法思想1 1）先進(jìn)先出法（）先進(jìn)先出法（FirstFirst InIn FirstFirst OutOut）：）：該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。在該算法的模擬過程中，每當(dāng)頁面需要被置換進(jìn)入內(nèi)存時(shí)，最先

5、進(jìn)入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組 0 號單元，即最頂部，這時(shí)缺頁數(shù)加 1；當(dāng)不需要進(jìn)行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時(shí)，不需要操作，繼續(xù)讀下一條指令。這樣就實(shí)現(xiàn)了總是淘汰最先進(jìn)入內(nèi)存的頁面，選擇了在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。（2 2）最近最久未使用（）最近最久未使用（LeastLeast RecentlyRecently UsedUsed）：）： 該算法將過去最長一段時(shí)間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當(dāng)頁面需要被置換進(jìn)入內(nèi)存時(shí)，最先進(jìn)入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組 0 號單元，即最頂部，這時(shí)缺頁數(shù)加 1；當(dāng)不需要進(jìn)

6、行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時(shí)，將要訪問的指令移到內(nèi)存頂部，其他指令依次向下移一位，這樣就把最久不用的指令沉到了底部，有必要時(shí)淘汰，即實(shí)現(xiàn)了總是淘汰最近最久未使用的指令。1.2.功能設(shè)計(jì)：功能設(shè)計(jì)： (1)(1) voidvoid changeaddr(structchangeaddr(struct PagePage p,intp,int logaddr)logaddr)的功能的功能 實(shí)現(xiàn)模擬請求分頁虛擬存儲管理中的硬件地址變化過程。（2）chushihua（）（）函數(shù)的功能：函數(shù)的功能： 先由 Srand()和 Rand()函數(shù)定義和隨機(jī)產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址

7、流存入地址流數(shù)組里。（3 3）FIFOFIFO（）的功能：（）的功能： 實(shí)現(xiàn) FIFO 算法，淘汰最先進(jìn)入內(nèi)存的頁面并根據(jù)缺頁數(shù)算出命中率。（4 4）LRULRU（）的功能：（）的功能：實(shí)現(xiàn) LRU 算法，淘汰最近最久未使用的頁面并根據(jù)缺頁數(shù)算出命中率。62 2 相關(guān)的各模塊的偽碼算法相關(guān)的各模塊的偽碼算法2.12.1 voidvoid changeaddr(structchangeaddr(struct PagePage p,intp,int logaddr)logaddr) /地址變換地址變換 logaddr 比上 64 為頁面號碼 記為 j logaddr 對 64 取余為頁面號碼 記為

8、 k for if（找到對應(yīng)的頁面號碼） if（在內(nèi)存中） 物理地址=對應(yīng)頁面的主存號*64+k 輸出物理地址 輸出此頁面的對應(yīng)信息Elsecout該頁不在主存,產(chǎn)生缺頁中斷endl; 詳細(xì)設(shè)計(jì)如下：void changeaddr(struct Page p,int logaddr) /地址變換 int j=logaddr/64;/對應(yīng)的塊號int k=logaddr%64;/對應(yīng)的偏移量int flag=0;int addr;for(int i=0;i8;i+)if(pi.pno=j)/找到對應(yīng)的頁號if(pi.flag=1)/頁面標(biāo)志為 17addr=o*64+k;cout物理地址為: a

9、ddrendl;cout詳細(xì)信息: t 頁面號：pi.pnot 主存號:ot 偏移量：kendl;flag=1;break;if(flag=0)cout該頁不在主存,產(chǎn)生缺頁中斷endl; 2.22.2 voidvoid chushihua()/chushihua()/初始化函數(shù)初始化函數(shù)int t;srand(time(0);/隨機(jī)產(chǎn)生指令序列 p=12+rand()%32;cout地址流序列：;coutendl;for(int i=0;i=0;i-)coutyemianliui ;coutendl;82.32.3 FIFOFIFO 算法實(shí)現(xiàn)時(shí)算法實(shí)現(xiàn)時(shí)： 如 M=4 時(shí) 進(jìn)入一個(gè)頁面時(shí) I

10、f（此頁面在內(nèi)存中） 則 fifo32不變 else For 循環(huán) 把 fifok=fifok-1; 最后 fifo0=yemianliue 詳細(xì)設(shè)計(jì)如下： void FIFO(int n) /FIFO 算法，n 是 M 的值int i;int q=p;int e;int queye=0;int flag;int fifo32=0;while(q-)flag=0;e=q;for(i=0;in;i+)if(fifoi=yemianliuq)flag=1;9break;if(flag=0)int m=n-1;int k=m;while(m-)fifok=fifok-1;k-;fifo0=yemia

11、nliue;queye+;coutM=n時(shí) FIFO 的命中率為：(1-(double)queye/p)*100% ;2.42.4 LRULRU 算法實(shí)現(xiàn)時(shí)：算法實(shí)現(xiàn)時(shí)： 如 M=4 時(shí) 進(jìn)入一個(gè)頁面時(shí) If（此頁面在內(nèi)存中） 則 flag=1，記錄位置 k else flag=0；if（flag=1） 把 k 前面的依次后移一位，即：lruk=lruk-1; 最后 lru0= yemianliue10 If(flag=0)For 循環(huán) 把 lruk=fifok-1; 最后 lru0=yemianliue詳細(xì)設(shè)計(jì)如下：void LRU(int n)/LRU 算法int i;int q=p;in

12、t e;int queye=0;int flag;int flag1;int y;int lru32=0;while(q-)flag=0;e=q;for(i=0;in;i+)if(lrui=yemianliuq)flag=1;flag1=i;break;11if(flag=0)int m=n-1;int k=m;while(m-)lruk=lruk-1;k-;lru0=yemianliue;queye+;else if(flag=1) y=flag1;while(y-)lruflag1=lruflag1-1;flag1-;lru0=yemianliue;coutM=n時(shí) LRU 的命中率為：(

13、1-(double)queye/p)*100%endl;123 3 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖1. FIFO（）函數(shù)流程圖（）函數(shù)流程圖; 2.否是是否開始得到執(zhí)行的指令指令是否在內(nèi)存中queye 加1，指令存入內(nèi)存，最先存入指令被淘汰下面是否還有指令結(jié)束得出命中率132.LRU（）函數(shù)流程圖：（）函數(shù)流程圖：否是是否開始得到執(zhí)行的指令指令是否在內(nèi)存中queye 加1，指令存入內(nèi)存，淘汰數(shù)組底部指令下面是否還有指令結(jié)束得出命中率將指令移到數(shù)組頂部，其他依次下移一位4 4 調(diào)試結(jié)果調(diào)試結(jié)果 14 圖 4-1 主菜單圖 4-2 地址轉(zhuǎn)換菜單圖 4-3 頁面置換菜單圖 4-4 頁面置換菜單15

14、圖 4-5 地址轉(zhuǎn)換圖 4-6 地址轉(zhuǎn)換圖 4-7 頁面置換16 圖 4-9 頁面置換圖 4-10 頁面置換 圖 4-11 頁面置換17總總 結(jié)結(jié)在兩周的課程設(shè)計(jì)中，我針對頁面模擬的有關(guān)資料進(jìn)行了調(diào)查，分析。針對題目的要求我把任務(wù)先分成兩大模塊：一是地址轉(zhuǎn)換，二是頁面置換。地址轉(zhuǎn)換：輸入一個(gè)邏輯地址，求出此地址所在的頁面號碼以及偏移量。查表看其是否在表中，若在則有找到其內(nèi)存地址并由內(nèi)存地址和偏移量計(jì)算出物理地址，最后輸出其物理地址以及頁面信息。頁面置換我采用 FIFO 和 LRU 算法。首先隨即產(chǎn)生地址序列，然后在不同的 M 值下用 FIFO 算法和 LRU 算法。FIFO 算法總是淘汰最先進(jìn)

15、入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。在該算法的模擬過程中，每當(dāng)頁面需要被置換進(jìn)入內(nèi)存時(shí)，最先進(jìn)入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組 0 號單元，即最頂部，這時(shí)缺頁數(shù)加 1；當(dāng)不需要進(jìn)行頁面置換，即所需訪問的內(nèi)容在內(nèi)存中時(shí)，不需要操作，繼續(xù)讀下一條指令。這樣就實(shí)現(xiàn)了總是淘汰最先進(jìn)入內(nèi)存的頁面，選擇了在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。LRU 算法將過去最長一段時(shí)間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當(dāng)頁面需要被置換進(jìn)入內(nèi)存時(shí)，最先進(jìn)入內(nèi)存的內(nèi)容們都依次向底移一位，需要訪問的內(nèi)容存入數(shù)組 0 號單元，即最頂部，這時(shí)缺頁數(shù)加 1；當(dāng)不需要進(jìn)行頁面置

16、換，即所需訪問的內(nèi)容在內(nèi)存中時(shí)，將要訪問的指令移到內(nèi)存頂部，其他指令依次向下移一位，這樣就把最久不用的指令沉到了底部，有必要時(shí)淘汰，即實(shí)現(xiàn)了總是淘汰最近最久未使用的指令操作系統(tǒng)的發(fā)展是永無止境的，在前進(jìn)的過程中必將有更多的知識需要我去學(xué)習(xí)與研究，并能將其應(yīng)用到實(shí)際的問題解決之中。由于分頁系統(tǒng)模擬的復(fù)雜以及自己能力的有限，在論述中不可能面面俱到，同時(shí)也由于我知識水平有限，文中的不足和錯(cuò)誤在所難免，希望老師多多指點(diǎn)和更正。本課程設(shè)計(jì)是在指導(dǎo)教師王旭陽老師的指導(dǎo)下完成的，在此對老師表示感謝。18參考文獻(xiàn)參考文獻(xiàn)1. 湯子瀛，哲鳳屏.計(jì)算機(jī)操作系統(tǒng).西安電子科技大學(xué)學(xué)出版社.2. 王清，李光明.計(jì)算機(jī)

17、操作系統(tǒng).冶金工業(yè)出版社.3. 孫鐘秀等. 操作系統(tǒng)教程. 高等教育出版社4. 曾明. Linux 操作系統(tǒng)應(yīng)用教程. 陜西科學(xué)技術(shù)出版社. 5. 張麗芬，劉利雄.操作系統(tǒng)實(shí)驗(yàn)教程. 清華大學(xué)出版社.6. 孟靜， 操作系統(tǒng)教程原理和實(shí)例分析. 高等教育出版社7. 周長林，計(jì)算機(jī)操作系統(tǒng)教程. 高等教育出版社8. 張堯?qū)W，計(jì)算機(jī)操作系統(tǒng)教程，清華大學(xué)出版社9. 任滿杰，操作系統(tǒng)原理實(shí)用教程，電子工業(yè)出版社致致 謝謝本次課程設(shè)計(jì)的順利完成離不開老師和同學(xué)們的幫助，在我遇到疑問的時(shí)候老師及時(shí)詳細(xì)的給我解答，讓我學(xué)到了很多。19在此感謝操作系統(tǒng)王旭陽老師，您以往的基礎(chǔ)課程為我的這次課設(shè)打下了基礎(chǔ)。再次

18、感謝操作系統(tǒng)課程設(shè)計(jì)指導(dǎo)老師王旭陽老師兩周來的辛勤指導(dǎo)，使我的這次課設(shè)能夠順利完成。感謝同學(xué)們幾天來的幫助，在他們無私的幫助下我的任務(wù)才能如此順利的完成。20附件附件源程序代碼源程序代碼#include#include#include#include #include using namespace std;void chushihua();/初始化函數(shù)void FIFO(int n) ; /FIFO 算法，n 是 M 的值void LRU(int n);/LRU 算法void ymzh();void yemianzhihuan();void changeaddr(struct Page p,

19、int logaddr);void dizhizhuanhuan();void menu();int yemianliu32=0;/全局變量數(shù)組，地址流int p; struct Pageint pno;/頁號int flag;/標(biāo)志位int cno;/主存號int modf;/修改位int addr;/外存地址Page; /全局變量 p 是一共有多少地址流21void chushihua()/初始化函數(shù)int t;srand(time(0);/隨機(jī)產(chǎn)生指令序列 p=12+rand()%32;cout地址流序列：;coutendl;for(int i=0;i=0;i-)coutyemianli

20、ui ;coutendl;void FIFO(int n) /FIFO 算法，n 是 M 的值 coutM=n時(shí) FIFO 的頁面置換詳情;coutendl;int i;int j;int q=p;int e;int queye=0;int flag;int fifo32=0;22while(q-)flag=0;e=q;for(i=0;in;i+)if(fifoi=yemianliuq)flag=1;for(j=0;jn&fifoj!=0;j+) coutfifoj; coutendl;break;if(flag=0)int m=n-1;int k=m;while(m-)fifok=f

21、ifok-1;k-;fifo0=yemianliue;for(j=0;jn&fifoj!=0;j+)coutfifoj;coutendl;queye+;23coutM=n時(shí) FIFO 的命中率為：(1-(double)queye/p)*100% ;coutendl;coutendl;void LRU(int n)/LRU 算法coutM=n時(shí) LRU 的頁面置換詳情;coutendl;int i;int j;int q=p;int e;int queye=0;int flag;int flag1;int y;int lru32=0;while(q-)flag=0;e=q;for(i=0

22、;in;i+)if(lrui=yemianliuq)flag=1;flag1=i;24break;if(flag=0)int m=n-1;int k=m;while(m-)lruk=lruk-1;k-;lru0=yemianliue;for(j=0;jn&lruj!=0;j+) coutlruj; coutendl;queye+;else if(flag=1) y=flag1;while(y-)lruflag1=lruflag1-1;flag1-;lru0=yemianliue;for(j=0;jn&lruj!=0;j+) coutlruj; coutendl;25coutM=

23、n時(shí) LRU 的命中率為：(1-(double)queye/p)*100%endlendl;void ymzh()chushihua();for(int i=3;i5;i+)FIFO(i);LRU(i); yemianzhihuan();void yemianzhihuan()int a;cout-歡迎使用頁面置換模擬實(shí)驗(yàn)系統(tǒng)-endl;cout-tt1.進(jìn)入頁面置換算法tt-endl;cout-tt2.返回上一級tt-endl;cout-歡迎使用頁面置換模擬實(shí)驗(yàn)系統(tǒng)-endl;coutendla;switch(a)case 1:ymzh();26break;case 2: menu();br

24、eak;default:cout輸入有誤，請重新輸入！endl;break;void changeaddr(struct Page p,int logaddr)/地址變換int j=logaddr/64;/對應(yīng)的塊號int k=logaddr%64;/對應(yīng)的偏移量int flag=0;int addr;for(int i=0;i8;i+)if(pi.pno=j)/找到對應(yīng)的頁號if(pi.flag=1)/頁面標(biāo)志為 1addr=o*64+k;cout物理地址為: addrendl;cout詳細(xì)信息: t 頁面號：pi.pnot 主存號:ot 偏移量：kendl;flag=1;break;27if(flag=0)cout該頁不在主存,產(chǎn)生缺頁中斷endl; void dizhizhuanhuan()int a;int ins;/指令邏輯地址struct Page p8;p0.pno=0;p0.flag=1;o=5;p0.modf=1;p0.addr=011;p1.pno=1;p1.flag=1;