操作系統(tǒng)課程設(shè)計 請求調(diào)頁存儲管理

1、計算機(jī)科學(xué)與應(yīng)用系操作系統(tǒng)原理課程設(shè)計報告題目 請求調(diào)頁存儲管理 linux的安裝及用戶接口 班級 xxx 學(xué)號 xxx 姓名 xxx 專業(yè) 計算機(jī)科學(xué)與技術(shù) 指導(dǎo)教師 實驗一 請求調(diào)頁存儲管理1實驗?zāi)康?1) 通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬儲技術(shù)的特點。(2) 通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實現(xiàn)過程的理解。(3) 掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。2實驗內(nèi)容 1假設(shè)每個頁面中可存放10條指令，分配給作業(yè)的內(nèi)存塊數(shù)為4。2用c語言或c+語言模擬一個作業(yè)的執(zhí)行過程，該

2、作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果4個內(nèi)存塊均已裝入該作業(yè)，則需進(jìn)行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。在所有320指令執(zhí)行完畢后，請計算并顯示作業(yè)運(yùn)行過程中發(fā)生的缺頁率。3置換算法：請分別考慮最佳置換算法（opt）、先進(jìn)先出（fifo）算法和最近最久未使用（lru）算法。4作業(yè)中指令的訪問次序按下述原則生成；50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令

3、均勻分布在后地址部分。具體的實現(xiàn)辦法是：（1）在0，319之間隨機(jī)選取一條起始執(zhí)行指令，其序號為m；（2）順序執(zhí)行下一條指令，其序號為m+1條指令；（3）通過隨機(jī)數(shù)，跳轉(zhuǎn)到前地址部分0，m-1中的某條指令處，其序號為m1；（4）順序執(zhí)行下一條指令，即序號為m1+1的指令；（5）通過隨機(jī)數(shù)，跳轉(zhuǎn)到后地址部分m1+2,319中的某條指令處，其序號為m2；（6）順序執(zhí)行下一條指令，則序號為m2+1的指令；（7）重復(fù)跳轉(zhuǎn)到前地址部分，順序執(zhí)行，跳轉(zhuǎn)到后地址部分；順序執(zhí)行的過程，直至執(zhí)行320條指令。3實驗步驟1分析及概要設(shè)計在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空

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

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

6、條指令的那頁），而其他頁面則可能要到10、100或者1000條指令后才會被訪問，每個頁面都可以用在該頁面首次被訪問前所要執(zhí)行的指令數(shù)進(jìn)行標(biāo)記。 最佳頁面置換算法只是簡單地規(guī)定：標(biāo)記最大的頁應(yīng)該被置換。如果某頁在八百萬條指令內(nèi)不會被使用，另一頁在600萬條指令內(nèi)不會被使用，則置換前一個頁面，從而把因需要調(diào)回這一頁發(fā)生的缺頁推到將來，越遠(yuǎn)越好。這個算法唯一的一個問題就是它無法實現(xiàn)。當(dāng)缺頁發(fā)生時，操作系統(tǒng)無法知道各個頁面下一次是在什么時候被訪問。雖然這個算法不可能實現(xiàn)，但是最佳頁面置換算法可以用于對可實現(xiàn)算法的性能進(jìn)行衡量比較。2流程圖開始調(diào)用fifo算法調(diào)用lru算法調(diào)用opt算法提示輸入數(shù)據(jù)非法

7、輸出指令執(zhí)行順序和頁面調(diào)用順序得到指令執(zhí)行的順序接收鍵盤輸入數(shù)值判斷輸入數(shù)是否在1320選擇頁面置換算法結(jié)束3程序代碼#include #include#include#include#define size 4typedef struct block/聲明一種新類型物理塊類型 int pagenum;/頁號 int accessed;/訪問字段，其值表示多久未被訪問block; int count;/程序計數(shù)器，用來記錄指令的序號int n;/缺頁計數(shù)器，用來記錄缺頁的次數(shù)static int temp320;/用來存儲320條隨機(jī)數(shù)block blocksize; /定義一大小為4的物理塊

8、數(shù)組void init( ); /程序初始化函數(shù)int findexist(int curpage);/查找物理塊中是否有該頁面int findspace( );/查找是否有空閑物理塊int findreplace( );/查找應(yīng)予置換的頁面void display ( );/顯示void random( );/產(chǎn)生320條隨機(jī)數(shù),顯示并存儲到temp320void pagestring( );/顯示調(diào)用的頁面隊列void opt( );/opt算法void lru( );/ lru算法void fifo( );/fifo算法void init( ) for(int i=0;isize;i+)

9、 blocki.pagenum=-1; blocki.accessed=0; count=n=0; int findexist(int curpage) /查找物理塊中是否有該頁面for(int i=0; isize; 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中的位置re

10、turn -1;int findreplace( ) /查找應(yīng)予置換的頁面int pos = 0; for(int i=0; iblockpos.accessed) pos = i;/找到應(yīng)予置換頁面，返回block中位置 return pos;void display( ) for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理塊不空 printf( %02d,blocki.pagenum); coutcount; cout*按照要求產(chǎn)生的320個隨機(jī)數(shù)：*endl; for(int i=0;i320;i+) tempi=count;if(f

11、lag%2=0)count=+count%320;/產(chǎn)生50%的順序執(zhí)行指令（flag=0或2時順序執(zhí)行） if(flag=1) count=rand( )% (count-1); /產(chǎn)生25%的均勻分布在前地址部分指令 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( %02

12、d,tempi/10); if(i+1)%10=0) coutendl;/-最佳置換算法void opt( )int exist,space,position ; int curpage; for(int i=0;i320;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; els

13、efor(int k=0;ksize;k+)for(int j=i;j320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/將來不會用，設(shè)置為一個很大數(shù) 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,

14、position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接從鍵盤獲取鍵值 count=tempi; /指令在數(shù)組中的位置 curpage=count/10; /指令所在頁面 exist = findexist(curpage); /查找物理塊中是否有該頁面,若有返回物理塊號 if(exist=-1) /物理塊中不存在該頁space = findspace( ); /查找是否有空閑物理塊 if(space != -1) /有空閑物理塊blockspace.pagenum = curpage; displa

15、y( ); n=n+1; else /無空閑物理塊，則尋找置換頁面 position = findreplace( ); /查找應(yīng)予置換的頁面 blockposition.pagenum = curpage; blockposition.accessed = -1; /恢復(fù)剛調(diào)入的block中頁面accessed為-1 display( ); n+; else blockexist.accessed = -1;/恢復(fù)存在的并剛訪問過的block中頁面accessed為-1 for(int j=0; j4; j+) blockj.accessed+; cout缺頁次數(shù):nendl; cout缺頁

16、率:(n/320.0)*100%endl;/- 先進(jìn)先出算法void fifo( ) int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); /getch直接從鍵盤獲取鍵值 count=tempi; curpage=count/10; exist = findexist(curpage); /查找物理塊中是否有該頁面 if(exist=-1)space = findspace( ); /查找是否有空閑物理塊 if(space != -1) /有空閑物理塊 blockspace.page

17、num = curpage; display( ); n=n+1; else /無空閑物理塊，則尋找置換頁面 position = findreplace( ); /查找應(yīng)予置換的頁面 blockposition.pagenum = curpage; display( ); n+; blockposition.accessed-; /置換頁面所在的物理塊中訪問標(biāo)記設(shè)為-1 else/若存在該頁for(int i=0; isize; i+) if(blocki.pagenum != -1) /物理塊不空printf( %02d ,blocki.pagenum);cout指令已經(jīng)存在! 其物理塊地

18、址為:&blockexistendl;for(int j=0; jsize; j+)blockj.accessed+; cout缺頁次數(shù):nendl; cout缺頁率:(n/320.0)*100%endl;void main( )int select; cout請輸入第一條指令號(1320): ; random( ); cout*對應(yīng)的調(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( ); break; case 3:cout先進(jìn)先出置換算法fifo:endl;cout*re.shcd $directorycpio i $1 /dev/fd()d0)exit 0;es