實(shí)驗(yàn)五：頁面調(diào)度算法模擬 實(shí)驗(yàn)報(bào)告

1、計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)五：頁面調(diào)度算法模擬學(xué)校：院系：班級：姓名：學(xué)號：指導(dǎo)教師：目 錄一、實(shí)驗(yàn)題目3二、實(shí)驗(yàn)學(xué)時3三、指導(dǎo)老師3四、實(shí)驗(yàn)日期3五、實(shí)驗(yàn)?zāi)康?六、實(shí)驗(yàn)原理36.1頁面的含義36.2 頁面置換算法的含義36.3 置換算法36.3.1最佳置換算法(Optimal)36.3.2先進(jìn)先出(FIFO)頁面置換算法36.3.3 LRU置換算法4七、實(shí)驗(yàn)步驟及結(jié)果47.1 驗(yàn)證最佳置換算法47.1.1 實(shí)驗(yàn)截圖47.1.2 實(shí)驗(yàn)分析47.2 驗(yàn)證先進(jìn)先出(FIFO)頁面置換算法57.2.1 實(shí)驗(yàn)截圖57.2.2 實(shí)驗(yàn)分析57.3 驗(yàn)證LRU置換算法67.3.1 實(shí)驗(yàn)截圖67.3.2 實(shí)驗(yàn)

2、分析6八、報(bào)告書寫人6附錄一 最佳置換算法(Optimal)7附錄二 先進(jìn)先出(FIFO)頁面置換算法10附錄三 LRU置換算法13實(shí)驗(yàn)五：頁面調(diào)度算法模擬一、實(shí)驗(yàn)題目頁面調(diào)度算法模擬二、實(shí)驗(yàn)學(xué)時2學(xué)時三、指導(dǎo)老師四、實(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)原理6.1頁面的含義分頁存儲管理將一個進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。6.2 頁面置換算法的含義在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運(yùn)

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

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

5、b222228b31111b4000out727.2 驗(yàn)證先進(jìn)先出(FIFO)頁面置換算法7.2.1 實(shí)驗(yàn)截圖7.2.2 實(shí)驗(yàn)分析in103380812056b11111222b2000055b333336b48888out1037.3 驗(yàn)證LRU置換算法7.3.1 實(shí)驗(yàn)截圖7.3.2 實(shí)驗(yàn)分析in968773712670b1999933366b266661110b38888222b4777777out96831八、報(bào)告書寫人附錄一 最佳置換算法(Optimal)#include #include #include #define N 12/*隨機(jī)數(shù)列的長度*/#define B 4 /*內(nèi)存

6、頁面數(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，并返回-1bufi=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

7、的位置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 change=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

8、 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+;for(m=0;m=B;m+)printf( );/*成功的打印*/printf( in-%d successfullyn,listi);/*成功的打印*/else if(j=-2)bufuse+;interrupt+;printf(newbuf=);for(m=0;mbufu

9、se;m+)printf(%d ,bufm);/*缺頁中斷次數(shù)的打印*/for(m;mB;m+)printf( );/*缺頁中斷的打印*/printf( in-%d interruptn,listi);/*缺頁中斷的打印*/elsetmp=bufj;bufj=listi;change+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁置換的打印*/for(m;mB;m+)printf( );/*缺頁置換的打印*/printf( inoutn,listi,tmp);/*缺頁置換的打印*/printf(nn);printf(inter

10、rupt=%dn,interrupt);printf(change=%dn,change);printf(successfully=%dn,successfully);return 0;附錄二 先進(jìn)先出(FIFO)頁面置換算法#include #include #include #define N 12/*隨機(jī)數(shù)列的長度*/#define B 4/*內(nèi)存頁面數(shù)*/int 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為空

11、，則把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ù)int 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

12、) rand()%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( );/*成功的打印*/printf( in-%d successfullyn,listi);/*成功的打印*/else if(j=-2)bufuse+;interrupt+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁中斷次數(shù)的打印*/

13、for(m;mB;m+)printf( );/*缺頁中斷的打印*/printf( in-%d interruptn,listi);/*缺頁中斷的打印*/elsetmp=bufold;bufold=listi;old=(old+1)%(int)B;/*數(shù)據(jù)在中的儲存是循環(huán)的*/change+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁置換的打印*/for(m;mB;m+)printf( );/*缺頁置換的打印*/printf( inoutn,listi,tmp);/*缺頁置換的打印*/printf(nn);printf(int

14、errupt=%dn,interrupt);printf(change=%dn,change);printf(successfully=%dn,successfully);return 0;附錄三 LRU置換算法#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;for(i=0;iB;i+)if(bufi=listnum)/*當(dāng)x在buf中，返回其位置*/j=i;break;else if(bufi=-1)/*當(dāng)

15、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;int i,j,k,m;for(m=0;m=0;i-)for(j=0;jB;j+)if(listi=bufj)for(k=0;kbuffuse;k+)if(listi=buffk)break;if(k=buffuse)buffbuffuse=listi;buffuse+;if(buffuse=B)return j;break;return 0;int

16、 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:n);change=0;/*中斷的次數(shù)*/f

17、or(i=0;iN;i+)j=IsInBuf(buf,list,i);if(j=-1)old=Get(buf,list,i);tmp=bufold;bufold=listi;change+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁置換的打印*/for(m;mB;m+)printf( );/*缺頁置換的打印*/printf( inoutn,listi,tmp);/*缺頁置換的打印*/else if(j=-2)bufuse+;interrupt+;printf(newbuf=);for(m=0;mbufuse;m+)printf(%d ,bufm);/*缺頁中斷次數(shù)的打印*/for(m;mB;m+)printf