试验五：面调度算法模拟试验报告

1、计算机操作系统实验报告实验五：页面调度算法模拟学校：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实验五：页面调度算法模拟一、实验题目页面调度算法模拟二、实验学时2学时三、指导老师XXX四、实验日期2018年12月10日星期一五、实验目的(1)熟悉操作系统页面调度算法(2)编写程序模拟先进先出、LRU等页面调度算法，体会页面调度算法原理六、实验原理页面的含义分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。页面置换算法的含义在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但 内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页 程序或数据，

3、送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确 定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。置换算法一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那 些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。最佳置换算法(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面， 将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置 换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内 存的若干个页面中，哪一个页面是未来

4、最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。先进先出(FIFO)页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内 存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它 总是指向最老的页面。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本科大三、计算机孱作率统实羚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/*随机数列的长度*/#define B 4/*内存页面数*/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;/ 置换次数int interrupt=0;/ 中断次数int successfully=0; / 访问成功次数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);/*缺页中断次数的打印*/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/*随机数列的长度*/#define B 4/*内存页面数*/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;/ 置换次数int interrupt=0;/ 中断次数i

15、nt successfully=0; / 访问成功次数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);/*缺页中断次数的打印*/)for(m;mB;m+)printf( );/*缺页中断的打印*/)printf( in-%d interruptn,listi);/*缺页中断的打印*/) elsetmp=bufold;bufold=listi;01d=(old+1)%(int)B;/*数据在b u f中的储存是循环的*/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、/*随机数列的长度*/#define B 4/*内存页面数*/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: