試驗五：面調(diào)度算法模擬試驗報告

1、計算機操作系統(tǒng)實驗報告實驗五：頁面調(diào)度算法模擬學校：XXX院系：XXX班級：XXX姓名：XXX學號：XXX指導教師：XXX TOC o 1-5 h z 一、實驗題目3.二、實驗學時3.三、指導老師3.四、實驗日期3.五、實驗目的3.六、實驗原理3.頁面的含義3.頁面置換算法的含義 3.置換算法3.最佳置換算法(Optimal) 3先進先出(FIFO)頁面置換算法 3LRU置換算法4.七、實驗步驟及結果 4.驗證最佳置換算法4.實驗截圖4.實驗分析4.驗證先進先出(FIFO)頁面置換算法 5實驗截圖5.實驗分析5.驗證LRUB換算法6.實驗截圖6.實驗分析6.八、報告書寫人6.附錄一最佳置換算法

2、(Optimal) 7.附錄二先進先出(FIFO)頁面置換算法 1.0附錄三LRU置換算法1.3實驗五：頁面調(diào)度算法模擬一、實驗題目頁面調(diào)度算法模擬二、實驗學時2學時三、指導老師XXX四、實驗日期2018年12月10日星期一五、實驗目的(1)熟悉操作系統(tǒng)頁面調(diào)度算法(2)編寫程序模擬先進先出、LRU等頁面調(diào)度算法，體會頁面調(diào)度算法原理六、實驗原理頁面的含義分頁存儲管理將一個進程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。頁面置換算法的含義在進程運行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但 內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁 程序或數(shù)據(jù)，

3、送磁盤的對換區(qū)中。但應將哪個頁面調(diào)出，須根據(jù)一定的算法來確 定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_Replacement Algorithms)。置換算法一個好的頁面置換算法，應具有較低的頁面更換頻率。從理論上講，應將那 些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。最佳置換算法(Optimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面， 將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置 換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預知一個進程在內(nèi) 存的若干個頁面中，哪一個頁面是未來

4、最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。先進先出(FIFO)頁面置換算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi) 存的頁面，按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它 總是指向最老的頁面。LRU置換算法LRU置換算法是選擇最近最久未使用的頁面予以淘汰。七、實驗步驟及結果驗證最佳置換算法實驗截圖The OptimalLisi: 7 27710440804the lost in HQwbuf=7 ii-.wuul i _newbuf=7Optim

5、al：1in一一7interrmptin-2interruptin7successfullyin7successfullyinoutwwbuf=4 S1 Qin4successfullyi n-0successfuIlyinouti n10successfu Uyin一4successfullyinterrupt-4ichange-Esuccessfully=6Pr?ss any key to continue.7.1.2實驗分析in727710440804b1777744b222228b31111b4000out72驗證先進先出(FIFO)頁面置換算法實驗截圖CAU sesAdminirri

6、1d-Dfskt叫人本科大二匕t管機播隼聚秋定險晨驗代m Di?buqF IF OexeThe FIFOList:1 o -13 8 0 8 12 0 5 6the lostin FIFO:nebuf 1in-1interruptti&wbuf_10i n0interruptpe*biif=l0 3in一3interruptin 一3successfullynewbuf- 10 38in-Binterruptin QsuccessfullyinSsuccessfullyin一1successfullynpwhiif=20 3Bi n一2change lir)C0successfullyne*b

7、uf-25 38inoutn?whuf=25 68i noutinterrupt=11change=3successfully_5Press any key to cant inuei7.2.2實驗分析in103380812056bl1111222b2000055b333336b48888out103驗證LRU置換算法實驗截圖XAlhersAdmini?tratorDktp本科大三、計算機孱作率統(tǒng)實羚7實狗林碼D?bugLRU RadonnThe Random List:9 6 8 7 7 3 712 6 7 0the lost in LRU:n?w7)uf=9in一9interruptnew

8、huf=9 6in4一6intermptnewbuf=9 6 8一：interruptnewbuf=9 6 87i n7interruptinoutin-7successfullynewbuf=3 1 87inoutnewbufw3 1 27i -2change8-cutnewbuf-6 1 27inoulin一7successful!ynewbuf6 0 27inoutinterrupt7chanffe=5successfully=3Press any key tocontinue.7.3.2實驗分析in968773712670bl999933366b266661110b388I 88222

9、b4777777out96831八、報告書寫人XXX附錄一最佳置換算法(Optimal)#include #include #include #define N 12/*隨機數(shù)列的長度*/#define B 4/*內(nèi)存頁面數(shù)*/int IsInBuf(int buf口,int list口,int num) int i,j=-1;int max_p;int max_d=0;for(i=0;iB;i+)if(bufi=listnum)當 x 在 buf 中，返回-1return -1;else if(bufi=-1)/ 當 x 不在 buf 中，且 bufi 為空，則把 x填入buf,并返回-1b

10、ufi=listnum;return -2;for(i=0;iB;i+) for(j=num+1;jN;j+)if(bufi=listj)if(max_dj)max_d=j;/bufi 在 list中的最近距離max_p=i;/listj 在 buf的位置 break;if(j=N) /如果buf滿，并且bufi不在list 的后半部分，返回 位置ireturn i;return max_p;/ 返回距離最遠的buf口的位置)int main()(int listN;/=4,3,2,1,4,3,5,4,3,2,1,5;int bufB,i,fN,j,m,bufuse=0,tmp;int cha

11、nge=0;/ 置換次數(shù)int interrupt=0;/ 中斷次數(shù)int successfully=0; / 訪問成功次數(shù)srand(int)time(NULL);for(i=0;iB;i+)bufi=fi=-1;printf(nn);printf(The Optimal List:);for(i=0;iN;i+)listi=(int) rand()%10;printf(%2d,listi);printf(n);printf(nthe lost in Optimal:n);for(i=0;iN;i+)j=IsInBuf(buf,list,i);if(j=-1)successfully+;fo

12、r(m=0;m=B;m+)printf( );/*成功的打印*/成功printf( in-%d successfullyn,listi);/*的打印*/else if(j=-2)bufuse+;interrupt+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁中斷次數(shù)的打印*/for(m;mB;m+)printf( );/*缺頁中斷的打印*/)printf( in-%d interruptn,listi);/* 打印*/) elsetmp=bufj;bufj=listi;change+;printf(newbuf=);for(

13、m=0;mbufuse;m+)printf(%d ,bufm);/* 缺頁置換的打印 */)for(m;moutn,listi,tmp);/*缺頁置換的打印 */)printf(nn);printf(interrupt=%dn,interrupt);printf(change=%dn,change);printf(successfully=%dn,successfully);return 0;缺頁中斷的in-%d)附錄二先進先出(FIFO)頁面置換算法#include #include #include #define N 12/*隨機數(shù)列的長度*/#define B 4/*內(nèi)存頁面數(shù)*/in

14、t IsInBuf(int buf,int x) int i;for(i=0;iB;i+)if(bufi=x)/* 當x在buf中，返回其位置*/ return -1;else if(bufi=-1)/* 當 x 不在 buf 中，且 bufi為空，則把 x 填入buf,并返回其位置*/bufi=x;return -2;return 0;int main() int listN;/=4,3,2,1,4,3,5,4,3,2,1,5;int bufB,i,fN,j,m,bufuse=0,tmp;int old=0;int change=0;/ 置換次數(shù)int interrupt=0;/ 中斷次數(shù)i

15、nt successfully=0; / 訪問成功次數(shù)srand(int)time(NULL);for(i=0;iB;i+)bufi=fi=-1;printf(nn);printf(The FIFO List:); for(i=0;iN;i+) listi=(int) rand()%10;10 printf(%2d,listi);)printf(n);printf(nthe lost in FIFO:n);for(i=0;iN;i+)j=IsInBuf(buf,listi);if(j=-1)successfully+;for(m=0;m=B;m+)printf( );/*成功的打印*/)pri

16、ntf( in-%d successfullyn,listi);/*成功的打印*/)else if(j=-2)bufuse+;interrupt+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁中斷次數(shù)的打印*/)for(m;mB;m+)printf( );/*缺頁中斷的打印*/)printf( in-%d interruptn,listi);/*缺頁中斷的打印*/) elsetmp=bufold;bufold=listi;01d=(old+1)%(int)B;/*數(shù)據(jù)在b u f中的儲存是循環(huán)的*/change+;printf

17、(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/* 缺頁置換的打印 */)for(m;mB;m+)printf( );/*缺頁置換的打印*/)printf(inoutn,listi,tmp);/*缺頁置換的打印 */)printf(nn);printf(interrupt=%dn,interrupt);printf(change=%dn,change);printf(successfully=%dn,successfully);return 0;)12附錄三LRU置換算法#include #include #include #define N 12

18、/*隨機數(shù)列的長度*/#define B 4/*內(nèi)存頁面數(shù)*/int IsInBuf(int buf口,int list口,int num) int i,j=-1;for(i=0;iB;i+) if(bufi=listnum)/* 當 x 在 buf 中，返回其位置 */j=i; break;else if(bufi=-1)/* 當 x 不在 buf 中，且 bufi為空，則把 x 填入buf,并返回其位置*/bufi=listnum; j=-2;break; return j;int Get(int buf口,int list口,int num)int buffB;int buffuse=0

19、;int i,j,k,m;for(m=0;m=0;i-)for(j=0;jB;j+)if(listi=bufj)for(k=0;kbuffuse;k+) 13 if(listi=buffk) break;)if(k=buffuse)(buffbuffuse=listi;buffuse+;if(buffuse=B) return j;) break;)return 0;)int main()(int listN;/int list12=int bufB,i,fN,j,m,bufuse=0,tmp;int old=0;int change=0;int interrupt=0;int successfully=0;srand(int)time(NULL);for(i=0;iB;i+)bufi=fi=-1;printf(The Random List:);for(i=0;iN;i+)(listi=(int) rand()%10;printf(%2d,listi);)printf(nn);printf(nthe lost in LRU: