請求調(diào)頁存儲管理方式的模擬實驗報告

1、 網(wǎng)絡操作系統(tǒng)課 程 設 計 報 告 書題 目： 請求調(diào)頁存儲管理方式的模擬 學 號： 學生姓名： 指導教師： 2010 年 12 月 9 日目錄一. 實驗內(nèi)容1二. 實驗目的1三. 設計思想2四. 程序流程圖3五. 程序清單4六. 運行結(jié)果及分析10七. 總結(jié)14一、 實驗內(nèi)容1假設每個頁面中可存放10條指令，分配給作業(yè)的內(nèi)存塊數(shù)為4。2用c語言或c+語言模擬一個作業(yè)的執(zhí)行過程，該作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，

2、并將相應頁調(diào)入內(nèi)存。如果4個內(nèi)存塊均已裝入該作業(yè)，則需進行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。在所有320指令執(zhí)行完畢后，請計算并顯示作業(yè)運行過程中發(fā)生的缺頁率。3置換算法：請分別考慮最佳置換算法（opt）、先進先出（fifo）算法和最近最久未使用（lru）算法。4作業(yè)中指令的訪問次序按下述原則生成；50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令均勻分布在后地址部分。具體的實現(xiàn)辦法是：（1）在0，319之間隨機選取一條起始執(zhí)行指令，其序號為m；（2）順序執(zhí)行下一條指令，其序號為m+1條指令；（3）通過隨機數(shù)，跳轉(zhuǎn)到前地址部分0，m-1中的某條指令處，其序號

3、為m1；（4）順序執(zhí)行下一條指令，即序號為m1+1的指令；（5）通過隨機數(shù)，跳轉(zhuǎn)到后地址部分m1+2,319中的某條指令處，其序號為m2；（6）順序執(zhí)行下一條指令，則序號為m2+1的指令；（7）重復跳轉(zhuǎn)到前地址部分，順序執(zhí)行，跳轉(zhuǎn)到后地址部分；順序執(zhí)行的過程，直至執(zhí)行320條指令。二、 實驗目的1通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬儲技術(shù)的特點。2通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解。3掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。三、 設計思想在進程運行過程中，若其所要訪問

4、的頁面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應將哪個頁面調(diào)出，所以需要根據(jù)一定的算法來確定。在這一過程中，選擇換出頁面的算法稱為頁面置換算法。一個好的頁面置換算法，應具有較低的頁面更換頻率。頁面置換算法的好壞，將直接影響到系統(tǒng)的性能。以下分別是實驗要求的兩個頁面置換算法的介紹及設計思想。（1）先進先出法（first in first out）：該算法總是淘汰最先進入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。在該算法的模擬過程中，每當頁面被置換進入內(nèi)存時，將置換頁面所在的物理塊中訪問標記設為-

5、1；并且每執(zhí)行一次指令，便將物理塊的訪問標記自動加1，需要置換時將訪問標記最大的物理塊中的頁面置換出去，這樣能防止當物理塊訪問標記出現(xiàn)兩個以上相同的值的錯誤執(zhí)行，更好地模擬了先進先出法；（2）最近最久未使用（least recently used）： 該算法以最近的過去作為不久將來的近似， 將過去最長一段時間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當物理塊中的頁面被訪問時（包括原先存在的和后來置換進入的頁面），便將其物理塊訪問標記置為1。以后每執(zhí)行一條指令，便將物理塊中各頁面的訪問標記加1，需置換時訪問標記最大的便是將要被置換的。（3）最佳置換算法（opt）：發(fā)生缺頁時，有些頁面在內(nèi)

6、存中，其中有一頁見很快被訪問（也包含緊接著的下一條指令的那頁），而其他頁面則可能要到10、100或者1000條指令后才會被訪問，每個頁面都可以用在該頁面首次被訪問前所要執(zhí)行的指令數(shù)進行標記。最佳頁面置換算法只是簡單地規(guī)定：標記最大的頁應該被置換。如果某頁在八百萬條指令內(nèi)不會被使用，另一頁在600萬條指令內(nèi)不會被使用，則置換前一個頁面，從而把因需要調(diào)回這一頁發(fā)生的缺頁推到將來，越遠越好。這個算法唯一的一個問題就是它無法實現(xiàn)。當缺頁發(fā)生時，操作系統(tǒng)無法知道各個頁面下一次是在什么時候被訪問。雖然這個算法不可能實現(xiàn)，但是最佳頁面置換算法可以用于對可實現(xiàn)算法的性能進行衡量比較。四、 程序流程圖及數(shù)據(jù)結(jié)構(gòu)

7、320條待執(zhí)行指令顯示隨機產(chǎn)生的指令執(zhí)行順序和頁面的調(diào)用順序內(nèi)存物理塊選擇調(diào)頁存儲算法lru 算法1-319輸入一個隨機數(shù)optfifo算法程序結(jié)束數(shù)據(jù)結(jié)構(gòu)：typedef struct block/聲明一種新類型物理塊類型 int pagenum;/頁號 int accessed;/訪問字段，其值表示多久未被訪問 block; int count;/程序計數(shù)器，用來記錄指令的序號int n;/缺頁計數(shù)器，用來記錄缺頁的次數(shù)static int temp320;/用來存儲320條隨機數(shù)block blocksize; /定義一大小為4的物理塊數(shù)組void init( ); /程序初始化函數(shù)in

8、t findexist(int curpage);/查找物理塊中是否有該頁面int findspace( );/查找是否有空閑物理塊int findreplace( );/查找應予置換的頁面void display ( );/顯示void random( );/產(chǎn)生320條隨機數(shù),顯示并存儲到temp320void pagestring( );/顯示調(diào)用的頁面隊列void opt( );/opt算法void lru( );/ lru算法void fifo( );/fifo算法五、 程序清單#include #include#include#include#define size 4 typed

9、ef struct block/聲明一種新類型物理塊類型 int pagenum;/頁號 int accessed;/訪問字段，其值表示多久未被訪問 block; int count;/程序計數(shù)器，用來記錄指令的序號int n;/缺頁計數(shù)器，用來記錄缺頁的次數(shù)static int temp320;/用來存儲320條隨機數(shù)block blocksize; /定義一大小為4的物理塊數(shù)組void init( ); /程序初始化函數(shù)int findexist(int curpage);/查找物理塊中是否有該頁面int findspace( );/查找是否有空閑物理塊int findreplace( )

10、;/查找應予置換的頁面void display ( );/顯示void random( );/產(chǎn)生320條隨機數(shù),顯示并存儲到temp320void pagestring( );/顯示調(diào)用的頁面隊列void opt( );/opt算法void lru( );/ lru算法void fifo( );/fifo算法void init( ) for(int i=0;isize;i+) blocki.pagenum=-1; blocki.accessed=0; count=n=0; int findexist(int curpage) /查找物理塊中是否有該頁面for(int i=0; isize;

11、i+) if(blocki.pagenum = curpage ) return i; /檢測到內(nèi)存中有該頁面，返回block中的位置 return -1;int findspace( ) /查找是否有空閑物理塊 for(int i=0; isize; i+) if(blocki.pagenum = -1) return i; /找到空閑的block，返回block中的位置return -1;int findreplace( ) /查找應予置換的頁面int pos = 0; for(int i=0; iblockpos.accessed) pos = i;/找到應予置換頁面，返回block中位

12、置 return pos;void display( ) for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理塊不空 printf( %02d,blocki.pagenum); coutcount; cout*按照要求產(chǎn)生的320個隨機數(shù)：*endl; for(int i=0;i320;i+) tempi=count;if(flag%2=0)count=+count%320;/產(chǎn)生50%的順序執(zhí)行指令（flag=0或2時順序執(zhí)行） if(flag=1) count=rand( )% (count-1); /產(chǎn)生25%的均勻分布在前地址部分指令

13、 if(flag=3) count=count+1+(rand( )%(320-(count+1); /產(chǎn)生25%的均勻分布在后地址部分指令 flag=+flag%4;printf( %03d,tempi); if(i+1)%10=0) coutendl;void pagestring( ) /顯示調(diào)用的頁面隊列 for(int i=0;i320;i+) printf( %02d,tempi/10); if(i+1)%10=0) coutendl;/-最佳置換算法void opt( )int exist,space,position ; int curpage; for(int i=0;i32

14、0;i+) if(i%100=0) getch( ); count=tempi; curpage=count/10; exist = findexist(curpage); if(exist=-1) space = findspace ( ); if(space != -1)blockspace.pagenum = curpage; display( ); n=n+1; elsefor(int k=0;ksize;k+)for(int j=i;j320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/將來不會用，設置為一個很大數(shù)

15、elseblockk.accessed = j;break; position = findreplace( ); blockposition.pagenum = curpage; display( ); n+; cout缺頁次數(shù):nendl; cout缺頁率:(n/320.0)*100%endl;/- 最近最少使用算法 void lru( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接從鍵盤獲取鍵值 count=tempi; /指令在數(shù)組中的位置 cur

16、page=count/10; /指令所在頁面 exist = findexist(curpage); /查找物理塊中是否有該頁面,若有返回物理塊號 if(exist=-1) /物理塊中不存在該頁space = findspace( ); /查找是否有空閑物理塊 if(space != -1) /有空閑物理塊blockspace.pagenum = curpage; display( ); n=n+1; else /無空閑物理塊，則尋找置換頁面 position = findreplace( ); /查找應予置換的頁面 blockposition.pagenum = curpage; block

17、position.accessed = -1; /恢復剛調(diào)入的block中頁面accessed為-1 display( ); n+; else blockexist.accessed = -1;/恢復存在的并剛訪問過的block中頁面accessed為-1 for(int j=0; j4; j+) blockj.accessed+; cout缺頁次數(shù):nendl; cout缺頁率:(n/320.0)*100%endl;/- 先進先出算法void fifo( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%1

18、00=0) getch( ); /getch直接從鍵盤獲取鍵值 count=tempi; curpage=count/10; exist = findexist(curpage); /查找物理塊中是否有該頁面 if(exist=-1)space = findspace( ); /查找是否有空閑物理塊 if(space != -1) /有空閑物理塊 blockspace.pagenum = curpage; display( ); n=n+1; else /無空閑物理塊，則尋找置換頁面 position = findreplace( ); /查找應予置換的頁面 blockposition.pag

19、enum = curpage; display( ); n+; blockposition.accessed-; /置換頁面所在的物理塊中訪問標記設為-1 else/若存在該頁for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理塊不空printf( %02d ,blocki.pagenum);cout指令已經(jīng)存在! 其物理塊地址為:&blockexistendl;for(int j=0; jsize; j+)blockj.accessed+; cout缺頁次數(shù):nendl; cout缺頁率:(n/320.0)*100%endl;void ma

20、in( )int select; cout請輸入第一條指令號(1320): ; random( ); cout*對應的調(diào)用頁面隊列*endl; pagestring( ); docout*endl; cout* 1:opt 2:lru 3:fifo 4:退出 *endl; cout*endl; coutselect; cout*endl; init( ); switch(select) case 1:cout最佳置換算法opt:endl; cout*endl; opt( ); break; case 2:cout最近最久未使用置換算法lru:endl; cout*endl; lru( ); b

21、reak; case 3:cout先進先出置換算法fifo:endl;cout*endl;fifo( ); break; default: ; while(select!=4); 六、 使用說明及運行結(jié)果分析運行程序依次測試相應的算法：1、 先輸入一個指令號（1-319）隨意輸入；2、 然后選擇測試算法；本程序能通過輸入第一條指令號（用3位整數(shù)代表指令號），產(chǎn)生320個隨機數(shù)，并以每行10個顯示出來。再把這320個隨機數(shù)轉(zhuǎn)換成對應的頁面號，并以每行10個顯示出來。然后，通過輸入選擇鍵，分別執(zhí)行兩個置換算法。各個置換算法能顯示頁面置換的情況，如果所訪問的指令已在內(nèi)存，則顯示“該指令已經(jīng)存在”并顯示其物理地址；如果所訪問的指令還未裝入內(nèi)存，則顯示“調(diào)入的頁面是?！保@示其