1、 網(wǎng)絡(luò)操作系統(tǒng)課 程 設(shè) 計(jì) 報(bào) 告 書題 目：請求調(diào)頁存儲管理方式的模擬 學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 2010 年 12 月 10 日目錄課程設(shè)計(jì)一：請求調(diào)頁存儲管理方式的模擬一、實(shí)驗(yàn)?zāi)康亩?、?shí)驗(yàn)內(nèi)容三、設(shè)計(jì)思路四、文件系統(tǒng)結(jié)構(gòu)的說明五、數(shù)據(jù)結(jié)構(gòu)的說明六、程序流程圖七、源代碼八、運(yùn)行結(jié)果以及分析九、使用說明十、總結(jié)課程設(shè)計(jì)二：通過DNS協(xié)議，可實(shí)現(xiàn)IP地址和主機(jī)名之間的轉(zhuǎn)換一、實(shí)驗(yàn)?zāi)康亩?shí)驗(yàn)內(nèi)容三、設(shè)計(jì)思路四、文件系統(tǒng)結(jié)構(gòu)的說明五、源代碼六、運(yùn)行結(jié)果以及分析七、使用說明八、總結(jié)課程設(shè)計(jì)一一：實(shí)驗(yàn)?zāi)康?通過模擬實(shí)現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬儲技術(shù)的特點(diǎn)。2通過對頁

2、面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實(shí)現(xiàn)過程的理解。3掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實(shí)現(xiàn)過程，并比較它們的效率。二：實(shí)驗(yàn)內(nèi)容1假設(shè)每個(gè)頁面中可存放10條指令，分配給一個(gè)作業(yè)的內(nèi)存塊數(shù)為42用C語言模擬一作業(yè)的執(zhí)行過程。該作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時(shí)需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果4個(gè)內(nèi)存塊中均已裝入該作業(yè)，則需進(jìn)行頁面轉(zhuǎn)換。最后顯示其物理地址，并轉(zhuǎn)下一條指令。

3、在所有320條指令執(zhí)行完畢后，請計(jì)算并顯示作業(yè)運(yùn)行過程中發(fā)生的缺頁率。3置換算法：請分別考慮OPT、FIFO和LRU算法。4作業(yè)中指令的訪問次序按下述原則生成：50%的指令是順序執(zhí)行的25%的指令是均勻分布在前地址部分25%的指令是均勻分布在后地址部分具體的實(shí)施辦法：在0,319之間隨機(jī)選取一條起始指令，其序號為m順序執(zhí)行下一條指令，即序號為m+1的指令通過隨機(jī)數(shù)，跳轉(zhuǎn)到前地址部分0,m-1中的某條指令處，其序號為m1；順序執(zhí)行下一條指令，即序號為m1+1的指令通過隨機(jī)數(shù)，跳轉(zhuǎn)到后地址部分m1+2,319中的某條指令處，其序號為m2;順序執(zhí)行下一條指令，即序號為m2+1的指令重復(fù)跳轉(zhuǎn)到前地址部

4、分、順序執(zhí)行、跳轉(zhuǎn)到后地址部分、順序執(zhí)行的過程，直至執(zhí)行320條指令。三：設(shè)計(jì)思路因?yàn)樵诔绦蜻\(yùn)行的過程中，當(dāng)我們訪問一個(gè)頁面時(shí)，倘若此頁面不在內(nèi)存當(dāng)中，我們就需要將其調(diào)入內(nèi)存。此時(shí)就產(chǎn)生了兩個(gè)問題：內(nèi)存是否有空閑和倘若內(nèi)存有空閑我們要將那個(gè)頁面調(diào)出的問題。這樣的話就需要根據(jù)一定的算法來判斷決定。我們大家都知道，算法的好壞反映在程序執(zhí)行的效率上面，所以我們要根據(jù)不同的情況調(diào)用不同的算法。這里我們有三種置換算法：1最佳置換算法（Optimal） 2、先進(jìn)先出法（First In First Out） 3、最近最久未使用（Least Recently Used）。所謂最佳置換算法，就是其所選擇的被淘

5、汰頁是將來不再被使用，或者是在最遠(yuǎn)的將來才被訪問的頁面。 采用這種頁面置換算法， 保證有最少的缺頁率。但由于目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪個(gè)在最長的時(shí)間內(nèi)不會被訪問，因而，現(xiàn)實(shí)中該算法是無法實(shí)現(xiàn)的。因此在該算法的模擬過程中，頁面訪問次序必須是給定的，具體實(shí)現(xiàn)為：對每一個(gè)物理塊設(shè)置一個(gè)整數(shù)型的訪問標(biāo)志位，當(dāng)需要置換物理塊中的某一頁時(shí)，將每一個(gè)物理塊中的頁面號與當(dāng)前需調(diào)入頁以后的每一頁面號進(jìn)行比較，若物理塊中的頁面號與所有的頁面號都不同，則該頁即為將來不再使用的頁，將訪問標(biāo)記設(shè)置為1000，表示將來不會用，設(shè)置為一個(gè)很大數(shù)；若找到頁號相同的則將其訪問次序記入訪問標(biāo)記，比較訪問標(biāo)記，

6、最大的即為最久不會被訪問的，將其換出。所謂先進(jìn)先出法，就是總是淘汰最先進(jìn)入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。在該算法的模擬過程中，每當(dāng)某一頁面進(jìn)入內(nèi)存時(shí)（包括頁面置換時(shí)頁面的置入），物理塊中各頁面訪問標(biāo)記自動加一，置換后，將置換頁面所在的物理塊中訪問標(biāo)記減一；這樣能防止當(dāng)物理塊訪問標(biāo)記出現(xiàn)兩個(gè)以上相同的值的錯(cuò)誤執(zhí)行，更好地模擬了先進(jìn)先出法。所謂最近最久未使用，就是以最近的過去作為不久將來的近似， 將過去最長一段時(shí)間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當(dāng)物理塊中的頁面被訪問時(shí)，便將其訪問標(biāo)記置為1。以后每執(zhí)行一條指令，便將物理塊中各頁面的訪問標(biāo)記加一，需置換時(shí)訪

7、問標(biāo)記最大的便是將要被置換的。四：文件系統(tǒng)結(jié)構(gòu)的說明#include #include#include#include#define Bsize 4typedef struct BLOCK/聲明一種新類型物理塊類型 int pageNum;/頁號 int accessed;/訪問字段，其值表示多久未被訪問BLOCK; int pc;/程序計(jì)數(shù)器，用來記錄指令的序號int m;/缺頁計(jì)數(shù)器，用來記錄缺頁的次數(shù) static int random320;/用來存儲320條隨機(jī)數(shù)BLOCK blockBsize; /定義一大小為4的物理塊數(shù)組void init( ); /程序初始化函數(shù)int fin

8、dExist(int curpage);/查找物理塊中是否有該頁面int findSpace( );/查找是否有空閑物理塊int findReplace( );/查找應(yīng)予置換的頁面void display ( );/顯示void suijishu( );/產(chǎn)生320條隨機(jī)數(shù),顯示并存儲到random320void pagestring( );/顯示調(diào)用的頁面隊(duì)列void OPT( );/OPT算法最佳置換算法void LRU( );/ LRU算法最近最久未使用算法void FIFO( );/FIFO算法五：數(shù)據(jù)結(jié)構(gòu)的說明在本程序中，對于物理塊使用了結(jié)構(gòu)體。最后主函數(shù)通過依次調(diào)用三種算法函數(shù)來實(shí)

9、現(xiàn)功能。頭文件：#include #include#include#include#define Bsize 4物理塊：typedef struct BLOCK/聲明一種新類型物理塊類型 int pageNum;/頁號 int accessed;/訪問字段，其值表示多久未被訪問BLOCK; 六：程序流程圖整體六：程序流程圖LRU開始是得到執(zhí)行指令是否是指令所在頁是否在內(nèi)存中否內(nèi)存中是否有空閑物理塊查找內(nèi)存中accessed值最大的物理塊，置換修改內(nèi)存中該頁所在的物理塊的Accessed的值-1是修改內(nèi)存中該頁所在的物理塊的Accessed的值-1輸出該內(nèi)存塊的物理地址將所有物理塊的access

10、ed的值加1結(jié)束七：源代碼#include #include#include#include#define Bsize 4typedef struct BLOCK/聲明一種新類型物理塊類型 int pageNum;/頁號 int accessed;/訪問字段，其值表示多久未被訪問BLOCK; int pc;/程序計(jì)數(shù)器，用來記錄指令的序號int m;/缺頁計(jì)數(shù)器，用來記錄缺頁的次數(shù) static int random320;/用來存儲320條隨機(jī)數(shù)BLOCK blockBsize; /定義一大小為4的物理塊數(shù)組void init( ); /程序初始化函數(shù)int findExist(int cu

11、rpage);/查找物理塊中是否有該頁面int findSpace( );/查找是否有空閑物理塊int findReplace( );/查找應(yīng)予置換的頁面void display ( );/顯示void suijishu( );/產(chǎn)生320條隨機(jī)數(shù),顯示并存儲到random320void pagestring( );/顯示調(diào)用的頁面隊(duì)列void OPT( );/OPT算法最佳置換算法void LRU( );/ LRU算法最近最久未使用算法void FIFO( );/FIFO算法void init( ) /程序初始化函數(shù) for(int i=0;iBsize;i+) blocki.pageNum

12、=-1; blocki.accessed=0; pc=m=0; int findExist(int curpage)/查找物理塊中是否有該頁面 for(int i=0; iBsize; i+) if(blocki.pageNum = curpage ) return i;/檢測到內(nèi)存中有該頁面，返回block中的位置 return -1;int findSpace( )/查找是否有空閑物理塊 for(int i=0; iBsize; i+) if(blocki.pageNum = -1) return i;/找到空閑的block，返回block中的位置 return -1;int findRe

13、place( )/查找應(yīng)予置換的頁面 int pos = 0; for(int i=0; iblockpos.accessed) pos = i;/找到應(yīng)予置換頁面，返回BLOCK中位置 return pos;void display( ) for(int i=0; iBsize; i+) if(blocki.pageNum != -1) printf( %02d,blocki.pageNum); coutendl;void suijishu( ) int flag=0; printf(請輸入一個(gè)0320之間的隨機(jī)數(shù)：n); scanf(%d,&pc); printf(-按照要求產(chǎn)生的320個(gè)

14、隨機(jī)數(shù)：-n); for(int i=0;i320;i+) randomi=pc; if(flag%2=0) pc=+pc%320;/順序執(zhí)行下一條指令，即序號為m+1的指令if(flag=1) pc=rand( )% (pc-1);/通過隨機(jī)數(shù)，跳轉(zhuǎn)到前地址部分0,m-1中的某條指令處，其序號為m1 if(flag=3) pc=pc+1+(rand( )%(320-(pc+1);/通過隨機(jī)數(shù)，跳轉(zhuǎn)到后地址部分m1+2,319中的某條指令處，其序號為m2flag=+flag%4;/如果4個(gè)內(nèi)存塊中均已裝入該作業(yè)，則需進(jìn)行頁面轉(zhuǎn)換 printf( %03d,randomi); if(i+1)%1

15、0=0) coutendl;/每個(gè)頁面中可存放10條指令 void pagestring( ) for(int i=0;i320;i+) printf( %02d,randomi/10);/顯示該頁面 if(i+1)%10=0) printf(n);/每個(gè)頁面中可存放10條指令 void OPT( )/*OPT算法最佳置換算法.最佳置換算法是Blady在理論上提出的一種算法。其所選擇的被淘汰頁是將來不再被使用，或者是在最遠(yuǎn)的將 來才被訪問的頁面.采用這種頁面置換算法， 保證有最少的缺頁率。但由于目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁面中，哪個(gè)在最長的 時(shí)間內(nèi)不會被訪問，因而，現(xiàn)實(shí)中該算法是無法

16、實(shí)現(xiàn)的。因此在該算法的模擬過程中，頁面訪問次序必須是給定的，具體實(shí)現(xiàn)為：對每一 物理塊設(shè)置一個(gè)整數(shù)型的訪問標(biāo)志位，當(dāng)需要置換物理塊中的某一頁時(shí)，將每一個(gè)物理塊中的頁面號與當(dāng)前需調(diào)入頁以后的每一頁面號進(jìn)行 比較，若物理塊中的頁面號與所有的頁面號都不同，則該頁即為將來不再使用的頁，將訪問標(biāo)記設(shè)置為1000，表示將來不會用，設(shè)置為一個(gè) 很大數(shù)；若找到頁號相同的則將其訪問次序記入訪問標(biāo)記，比較訪問標(biāo)記，最大的即為最久不會被訪問的，將其換出。*/ int exist,space,position ; int curpage; for(int i=0;i320;i+) if(i%100=0) getch(

17、 ); pc=randomi; curpage=pc/10; exist = findExist(curpage);if(exist=-1) space = findSpace ( ); if(space != -1) blockspace.pageNum = curpage; display( ); m=m+1; else for(int k=0;kBsize;k+) for(int j=i;j320;j+) if(blockk.pageNum!= randomj/10)/物理塊中的頁面號與所有的頁面號都不同 blockk.accessed = 1000; /將來不會用，設(shè)置為一個(gè)很大數(shù)el

18、se/找到頁號相同的則將其訪問次序記入訪問標(biāo)記blockk.accessed = j;break; position = findReplace( ); blockposition.pageNum = curpage; display( );m+; printf(缺頁次數(shù):%dn,m);cout缺頁率:(m/320.0)*100%endl;void LRU( )/*LRU算法最近最久未使用算法.該算法以最近的過去作為不久將來的近似， 將過去最長一段時(shí)間里不曾被使用的頁面置換掉。在該算法的模擬過程中，每當(dāng)物理塊中的頁面被訪問時(shí)，便將其訪問標(biāo)記置為1以后每執(zhí)行一條指令，便將物理塊中各頁面的訪問標(biāo)記

19、加一，需置換時(shí)訪問標(biāo)記最大的便是將要被置換的。*/int exist,space,position ;int curpage;for(int i=0;i320;i+) if(i%100=0) getch( );pc=randomi; curpage=pc/10;/每頁十個(gè)指令exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pageNum = curpage; display( );m=m+1;elseposition = findReplace( ); blockposi

20、tion.pageNum = curpage; display( );m+; else blockexist.accessed = -1;/恢復(fù)存在的并剛訪問過的BLOCK中頁面accessed為-1for(int j=0; j4; j+)blockj.accessed+;/每執(zhí)行一條指令，便將物理塊中各頁面的訪問標(biāo)記加一 printf(缺頁次數(shù):%dn,m);cout缺頁率:(m/320.0)*100%endl;void FIFO( )/*該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。在該算法的模擬過程中，每當(dāng)某一頁面進(jìn)入內(nèi)存時(shí)（包括頁面置換時(shí)頁面的置入），物理

21、塊中各頁面訪問標(biāo)記自動加一，置換后，將置換頁面所在的物理塊中訪問標(biāo)記減一；這樣能防止當(dāng)物理塊訪問標(biāo)記出現(xiàn)兩個(gè)以上相同的值的錯(cuò)誤執(zhí)行，更好地模擬了先進(jìn)先出法；*/int exist,space,position ;int curpage; for(int i=0;i320;i+) if(i%100=0) getch( ); pc=randomi; curpage=pc/10; exist = findExist(curpage); if(exist=-1)space = findSpace( ); if(space != -1)blockspace.pageNum = curpage; disp

22、lay( );m=m+1; else position = findReplace( ); blockposition.pageNum = curpage; display( );m+;blockposition.accessed-; for(int j=0; jBsize; j+) blockj.accessed+;/每當(dāng)某一頁面進(jìn)入內(nèi)存時(shí)（包括頁面置換時(shí)頁面的置入），物理塊中各頁面訪問標(biāo)記自動加一 printf(缺頁次數(shù):%dn,m);cout缺頁率:(m/320.0)*100%endl;void main( ) int select;cout請輸入第一條指令號(0320)：;suijis

23、hu( );cout-對應(yīng)的調(diào)用頁面隊(duì)列-endl;pagestring( );do cout-endl;cout*endl;cout-1:OPT 2:LRU 3:FIFO 4:退出-endl;cout*endl;cout-endl;coutselect;cout-endl;init( );switch(select)case 1:printf(您選擇的是最佳置換算法OPT:n);printf(-n);OPT( );/輸出結(jié)果break;case 2:printf(您選擇的是最近最久未使用置換算法LRU:n);printf(-n);LRU( );/輸出結(jié)果break;case 3:printf

24、(您選擇的是先進(jìn)先出置換算法FIFO:n);printf(-n);FIFO( );/輸出結(jié)果break; default: ; while(select!=4);/每頁分配4個(gè)內(nèi)存塊 八：運(yùn)行結(jié)果及分析九：使用說明1、首先進(jìn)入程序，在0320之間隨意挑選一個(gè)數(shù)輸入，按回車鍵。2、程序產(chǎn)生320個(gè)隨機(jī)數(shù)。3、開始選擇一種置換算法進(jìn)行頁面的置換。輸入置換算法前面的數(shù)字，回車。4、回車，得到置換算法的結(jié)果。5、換做其他的算法，依然回車，得到置換算法的結(jié)果。6、完成后選擇退出。十：總結(jié)1、通過這次操作系統(tǒng)課程設(shè)計(jì)的編寫，我學(xué)到了很多。剛開始見到設(shè)計(jì)要求時(shí)，我有點(diǎn)沒有思路。通過從網(wǎng)上參考了一些資料以后，

25、我開始慢慢的了解了程序設(shè)計(jì)中的一些問題。首先：我對OPT、FIFO和LRU算法三種算法有了一定的了解。其次，在分析題目要求的時(shí)候，對于如何將作業(yè)中指令的訪問次序按一定原則生成的問題我沒有一點(diǎn)思路。最后，在仔細(xì)的看了一些類似的題目代碼以后，我終于有了一定的理解。原來在實(shí)現(xiàn)的時(shí)候，通過先順序執(zhí)行一條隨機(jī)指令，譬如該指令為M0，然后開始順序執(zhí)行下一條指令M0+1，緊接著通過跳轉(zhuǎn)函數(shù)跳轉(zhuǎn)到地址部分0，M-1中的某條指令處，其序號記為M1，然后再次順序執(zhí)行下一條指令，即序號為M1+1的指令，最后通過跳轉(zhuǎn)函數(shù)跳轉(zhuǎn)到地址部分M1+2,319中的某條指令處，其序號為M2,，然后通過重復(fù)執(zhí)行跳轉(zhuǎn)到前址，順序執(zhí)行

26、，跳轉(zhuǎn)到后址，順序執(zhí)行的方法實(shí)現(xiàn)了50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分的目的。其中跳轉(zhuǎn)函數(shù)上我復(fù)習(xí)了以前的rand函數(shù)。2、其次，在實(shí)現(xiàn)設(shè)計(jì)要求功能的時(shí)候，對于那些頁面跳轉(zhuǎn)，頁面置換的細(xì)節(jié)內(nèi)容通過使用if(i+1)%10=0) coutendl;flag=+flag%4;來實(shí)現(xiàn)。期間的參數(shù)值的返回問題也需要考慮，以免弄錯(cuò)了。3、關(guān)于這次程序設(shè)計(jì)，我學(xué)到的還有很多，譬如說在先進(jìn)先出(FIFO)算法中，如何通過“當(dāng)某一頁面進(jìn)入內(nèi)存時(shí)（包括頁面置換時(shí)頁面的置入），物理塊中各頁面訪問標(biāo)記自動加一，置換后，將置換頁面所在的物理塊中訪問標(biāo)記減一”

27、的方法來防止當(dāng)物理塊訪問標(biāo)記出現(xiàn)兩個(gè)以上相同的值的錯(cuò)誤執(zhí)行問題。還有在最佳置換算法中對于不將來不再使用的頁面，將其訪問標(biāo)記設(shè)置為1000的方法。以及一些計(jì)算比如缺頁率計(jì)算問題我也學(xué)習(xí)到了很多。4、由于時(shí)間關(guān)系，對于一些細(xì)節(jié)問題我沒有能夠考慮好，比如說輸入控制，以后一定做好。5、通過本次的課程設(shè)計(jì)，我意識到了自己的編程能力還很差，以后必須通過練習(xí)來提高自己的能力。另外，對于自己的思路老是打不開的問題，我認(rèn)識到，這也是專業(yè)知識掌握的不夠扎實(shí)，缺乏實(shí)際操作的問題。以后我一定努力改正。同時(shí)，我認(rèn)識到了，程序設(shè)計(jì)，不僅僅要的是編程能力，對于設(shè)計(jì)全局的把握，整體的思考，以及算法的深入理解分析也是必不可少的

28、，這也是我以后個(gè)人需要特別注意學(xué)習(xí)的地方?？傊?，通過這次的設(shè)計(jì)作業(yè)，我學(xué)習(xí)到了很多很多。課程設(shè)計(jì)二一：實(shí)驗(yàn)?zāi)康耐ㄟ^DNS協(xié)議，可實(shí)現(xiàn)IP地址和主機(jī)名之間的轉(zhuǎn)換。通過該程序可以得到：(1)獲取本機(jī)名(gethostname()函數(shù))/(2)獲得給定主機(jī)名的IP地址(gethostbyname()函數(shù))(3)獲得給定IP地址的主機(jī)名(gethostbyaddr()函數(shù))二：實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)簡單的Winsock網(wǎng)絡(luò)程序，模擬UDP數(shù)據(jù)報(bào)，加深對DNS作用的理解。三：設(shè)計(jì)思路1、啟動 Visual C+，進(jìn)入集成開發(fā)環(huán)境;2、建立一個(gè)“Win32 Console Application類型的工程，工程

29、名自擬;3、在該工程下，新建一個(gè)源程序文件，即選擇“C+ SourceFile，文件名自擬;4、輸入以下源程序(注釋部分可不必輸入);四：文件系統(tǒng)結(jié)構(gòu)的說明#include#include#include #pragma comment(lib,ws2_32.lib)五：源代碼#include#include#include #pragma comment(lib,ws2_32.lib)/主文件/ int main() WORD wVersionRequested=MAKEWORD(1,1); WSADATA wsaData;/初始化 windows sockets API/ if(WSASt

30、artup(wVersionRequested,&wsaData) printf(WSAStartup failed%sn,WSAGetLastError(); return -1; char hostname256;/獲得本主機(jī)名/ int res=gethostname(hostname,sizeof(hostname); if(res!=0)/錯(cuò)誤處理/ printf(Error:%un,WSAGetLastError(); return -1; printf(本主機(jī)名為：%sn,hostname); /打印本主機(jī)名字/ printf(請輸入一個(gè)主機(jī)域名:); /輸入一個(gè)主機(jī)的域名/ scanf(%s,hostname);/利用主機(jī)名獲得主機(jī)的地址/ hostent* pHostent=gethostbyname(hostname);