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

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

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

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

4、最長時間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，便可以利用此算法來評價其它算法。先進(jìn)先出(FIFO)頁面置換算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi) 存的頁面，按先后次序鏈接成一個隊(duì)列，并設(shè)置一個指針，稱為替換指針，使它 總是指向最老的頁面。LRU置換算法LRU置換算法是選擇最近最久未使用的頁面予以淘汰。七、實(shí)驗(yàn)步驟及結(jié)果驗(yàn)證最佳置換算法實(shí)驗(yàn)截圖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實(shí)驗(yàn)分析in727710440804b1777744b222228b31111b4000out72驗(yàn)證先進(jìn)先出(FIFO)頁面置換算法實(shí)驗(yàn)截圖CAU sesAdminirri

6、1d-Dfskt叫人本科大二匕t管機(jī)播隼聚秋定險晨驗(yàn)代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實(shí)驗(yàn)分析in103380812056bl1111222b2000055b333336b48888out103驗(yàn)證LRU置換算法實(shí)驗(yàn)截圖XAlhersAdmini?tratorDktp本科大三、計算機(jī)孱作率統(tǒng)實(shí)羚7實(shí)狗林碼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實(shí)驗(yàn)分析in968773712670bl999933366b266661110b388I 88222

9、b4777777out96831八、報告書寫人XXX附錄一最佳置換算法(Optimal)#include #include #include #define N 12/*隨機(jī)數(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)當(dāng) x 在 buf 中，返回-1return -1;else if(bufi=-1)/ 當(dāng) 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;/ 返回距離最遠(yuǎn)的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)附錄二先進(jìn)先出(FIFO)頁面置換算法#include #include #include #define N 12/*隨機(jī)數(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)/* 當(dāng)x在buf中，返回其位置*/ return -1;else if(bufi=-1)/* 當(dāng) 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、/*隨機(jī)數(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)/* 當(dāng) x 在 buf 中，返回其位置 */j=i; break;else if(bufi=-1)/* 當(dāng) 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: