實驗五：頁面調(diào)度算法模擬實驗報告材料

1、計算機操作系統(tǒng)實驗報告實驗五：頁面調(diào)度算法模擬學(xué)校：XXX院系：XXX班級：XXX:XXX學(xué)號：XXX指導(dǎo)教師：XXX目錄一、實驗題目 3.二、實驗學(xué)時 3.三、指導(dǎo)老師 4.四、實驗日期 4.五、實驗?zāi)康?4.六、實驗原理 4.6.1 頁面的含義 4.6.2 頁面置換算法的含義 4.6.3 置換算法 4.6.3.1 最佳置換算法 (Optimal) 4.6.3.2 先進(jìn)先出 (FIFO) 頁面置換算法 5.6.3.3 LRU 置換算法 5.七、實驗步驟及結(jié)果 5.7.1 驗證最佳置換算法 5.7.1.1 實驗截圖 5.7.1.2 實驗分析 5.7.2 驗證先進(jìn)先出 (FIFO) 頁面置換算法

2、 6.7.2.1 實驗截圖 6.7.2.2 實驗分析 6.7.3 驗證LRU置換算法7.7.3.1 實驗截圖 7.7.3.2 實驗分析 8.八、報告書寫人 8.附錄一 最佳置換算法 (Optimal) 9.附錄二 先進(jìn)先出 (FIFO) 頁面置換算法 1.3附錄三 LRU 置換算法 1.8實驗五：頁面調(diào)度算法模擬、實驗題目頁面調(diào)度算法模擬、實驗學(xué)時2 學(xué)時三、指導(dǎo)老師XXX四、實驗日期2018年 12 月 10 日星期一五、實驗?zāi)康?1) 熟悉操作系統(tǒng)頁面調(diào)度算法(2)編寫程序模擬先進(jìn)先出、LRU等頁面調(diào)度算法，體會頁面調(diào)度算法原理六、實驗原理6.1 頁面的含義分頁存儲管理將一個進(jìn)程的邏輯地址

3、空間分成若干大小相等的片， 稱為頁面 或頁。6.2 頁面置換算法的含義在進(jìn)程運行過程中，若其所要訪問的頁面不在存而需把它們調(diào)入存，但存已 無空閑空間時， 為了保證該進(jìn)程能正常運行， 系統(tǒng)必須從存中調(diào)出一頁程序或數(shù) 據(jù)，送磁盤的對換區(qū)中。 但應(yīng)將哪個頁面調(diào)出， 須根據(jù)一定的算法來確定。 通常， 把選擇換出頁面的算法稱為頁面置換算法 (Page_Replacement Algorithms) 。6.3 置換算法一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那 些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間不會再訪問的頁面調(diào)出。6.3.1 最佳置換算法 (Optimal)它是由 B

4、elady 于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面， 將是以后永不使用的或許是在最長 (未來)時間不再被訪問的頁面。 采用最佳置換 算法，通?？杀ＷC獲得最低的缺頁率。 但由于人目前還無法預(yù)知一個進(jìn)程在存的 若干個頁面中， 哪一個頁面是未來最長時間不再被訪問的， 因而該算法是無法實 現(xiàn)的，便可以利用此算法來評價其它算法。632先進(jìn)先出(FIFO)頁面置換算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入存的頁面，即選擇在存 中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入存的頁 面，按先后次序成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最 老的頁面。

5、633 LRU置換算法LRU置換算法是選擇最近最久未使用的頁面予以淘汰。七、實驗步驟及結(jié)果7.1驗證最佳置換算法實驗截圖Th總 OptimalList: 7 27 7 10 44 0 8 0 4the lostinOptima1:nwbuf=7in7interruptnewbuf-72in<一2interrupt£n<7successfcllyin7sdccessfLllynerwbuf=7Iin<1interruptnewbuf=7I 0in<一0interruptjiewbufM1 0in<4change7一一>outin<4succes

6、sfullyin<一-0successful 1ynevbuf=431 0in<Schange2一一>outin<一0successful1yin<4successful 1yinterrupt.-successfull'尸6Pr?ss anykey to conti nu-.實驗分析in727710440804b1777744b222228b31111b4000out727.2驗證先進(jìn)先出(FIFO)頁面置換算法實驗截圖C:U4eRAdminiit rale NDesIctapM 科去三、計負(fù)機提柞磁讀盃7實驗代咼DEbugVF I FOje)貳the

7、FIFOList; 1 0 33 8 0 8 12 0 5 6th色 lostinFIFO:newbuf=lin<-一1interruptnewbuf=l0in<0interruptjnewbuf=103in<3mtrrup tin<3successfullymewbuf=103 8in<8interruptin<-一0successfullyin<-Ssuccessfullyin<一1successfullyheffbuf=203 3in<2change1>outin<一Qsuccessfullynewblif=253 3in

8、<5change0一>autriewbuf=25b 8in<一6change3>outintcrrjpt-4changedsuccessfull；尸5Press anykey to continueB實驗分析in103380812056bl1111222b2000055b333336b48888out1037.3驗證LRU置換算法實驗截圖The Raiitlutu Lisi :9 6 8 7 7：3 712 6 7 0the lost in LRU;newmf=9in<-9nterrliptnewbuf=9 61 n<6interruptnewbuf=9 S

9、 Bin< 8interruptnpwbtif=9 6 呂7in<-7i nterrlip tin<-7successfullynewbuf=3 6 87in<-3change9>outin<-7successfullynewbuf=3 187m<-1change6>outnewbuf=3 127in<_,-2change8>outnewbuf=6 127in<-j-6change3>cutin<-successfullynettbuf-6 027in<-0change 1-/outnt errtipt=4-c

10、hanfie=5successfullyPress any key tci continue.732實驗分析in968773712670bl999933366b266661110b38888222b4777777out96831八、報告書寫人附錄一 最佳置換算法 (Optimal)#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 12 /* 隨機數(shù)列的長度 */#define B 4 /* 存頁面數(shù) */int IsInBuf(int buf,int list,int num)in

11、t i,j=-1;int max_p;int max_d=0;for(i=0;i<B;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;i<B;i+)for(j=num+1;j<N;j+)if(bufi=listj)if(max_d<j)max_d=j;/bufi 在 list 中的最近距離max_p=i;/listj 在 buf 的位置b

12、reak;的后半部分，返回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;i<B;i+)bufi=fi=-1;printf("n

13、n");printf("The Optimal List:");for(i=0;i<N;i+)listi=(int) rand()%10;printf("%2d",listi);printf("n");printf("nthe lost in Optimal:n");for(i=0;i<N;i+)j=IsInBuf(buf,list,i);if(j=-1)successfully+;for(m=0;m<=B;m+)printf(" "); /* 成功的打印 */pri

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

15、=bufj; bufj=listi;change+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm); /* 缺頁置換的打印 */ for(m;m<B;m+)printf(" ");/* 缺頁置換的打印 */printf("*/缺頁中斷的in<-%dchange %d->outn",listi,tmp);/*缺頁置換的打印 */printf("nn");printf("interrupt=%dn&q

16、uot;,interrupt);printf("change=%dn",change);printf("successfully=%dn",successfully); return 0;附錄二 先進(jìn)先出 (FIFO) 頁面置換算法#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 12 /* 隨機數(shù)列的長度 */#define B 4/* 存頁面數(shù) */int IsInBuf(int buf,int x)int i;for(i=0;i<

17、B;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 interrupt=0; / 中斷次數(shù)int successfully=0; / 訪問成功次數(shù)srand(int)time(NULL

18、);for(i=0;i<B;i+)bufi=fi=-1;printf("nn");printf("The FIFO List:");for(i=0;i<N;i+)listi=(int) rand()%10;printf("%2d",listi);printf("n");printf("nthe lost in FIFO:n");for(i=0;i<N;i+)j=IsInBuf(buf,listi);if(j=-1)successfully+;for(m=0;m<=B;m+

19、)printf(" "); /* 成功的打印 */printf("in<-%d successfullyn",listi);/* 成功的打印 */else if(j=-2)bufuse+;interrupt+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm); /* 缺頁中斷次數(shù)的打印 */for(m;m<B;m+)printf(" "); /* 缺頁中斷的打印 */打印*/printf(" in<

20、-%d interruptn",listi);/* 缺頁中斷的elsetmp=bufold;bufold=listi;old=(old+1)%(int)B;/*數(shù)據(jù)在buf中的儲存是循環(huán)的*/change+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm);/* 缺頁置換的打印 */for(m;m<B;m+)printf(" ");/* 缺頁置換的打印 */in<-%d缺頁置換的打印 */printf("change %d->o

21、utn",listi,tmp);/*printf("nn");printf("interrupt=%dn",interrupt);printf("change=%dn",change);printf("successfully=%dn",successfully); return 0;附錄三 LRU 置換算法#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 12 /* 隨機數(shù)列的長度 */#d

22、efine B 4/* 存頁面數(shù) */int IsInBuf(int buf,int list,int num)int i,j=-1;for(i=0;i<B;i+)if(bufi=listnum) /* 當(dāng) x 在 buf 中，返回其位置 */ j=i;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;int i,j,k,m; f

23、or(m=0;m<B;m+)buffm=-1;for(i=num-1;i>=0;i-)for(j=0;j<B;j+)if(listi=bufj)for(k=0;k<buffuse;k+)if(listi=buffk) 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

24、=0;int successfully=0;srand(int)time(NULL);for(i=0;i<B;i+)bufi=fi=-1;printf("The Random List:");for(i=0;i<N;i+)listi=(int) rand()%10; printf("%2d",listi);printf("nn");printf("nthe lost in LRU:n");change=0; /* 中斷的次數(shù) */for(i=0;i<N;i+)j=IsInBuf(buf,list,i);if(j=-1)old=Ge