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

1、精选文档计算机操作系统试验报告试验五：页面调度算法模拟学校：院系：班级：姓名：学号：指导老师：目 录一、试验题目3二、试验学时3三、指导老师3四、试验日期3五、试验目的3六、试验原理36.1页面的含义36.2 页面置换算法的含义36.3 置换算法36.3.1最佳置换算法(Optimal)36.3.2先进先出(FIFO)页面置换算法36.3.3 LRU置换算法4七、试验步骤及结果47.1 验证最佳置换算法47.1.1 试验截图47.1.2 试验分析47.2 验证先进先出(FIFO)页面置换算法57.2.1 试验截图57.2.2 试验分析57.3 验证LRU置换算法67.3.1 试验截图67.3.

2、2 试验分析6八、报告书写人6附录一 最佳置换算法(Optimal)7附录二 先进先出(FIFO)页面置换算法10附录三 LRU置换算法13试验五：页面调度算法模拟一、试验题目页面调度算法模拟二、试验学时2学时三、指导老师四、试验日期2018年12月10日星期一五、试验目的(1)生疏操作系统页面调度算法(2)编写程序模拟先进先出、LRU等页面调度算法，体会页面调度算法原理六、试验原理6.1页面的含义分页存储管理将一个进程的规律地址空间分成若干大小相等的片，称为页面或页。6.2 页面置换算法的含义在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程

3、能正常运行，系统必需从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须依据肯定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。6.3 置换算法一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。6.3.1最佳置换算法(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(将来)时间内不再被访问的页面。接受最佳置换算法，通常可保证获得最低的缺页率。但由于人目前

4、还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。6.3.2先进先出(FIFO)页面置换算法这是最早消灭的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简洁只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。6.3.3 LRU置换算法LRU置换算法是选择最近最久未使用的页面予以淘汰。 七、试验步骤及结果7.1 验证最佳置换算法7.1.1 试验截图7.1.2 试验分析in727710440804b177

5、7744b222228b31111b4000out727.2 验证先进先出(FIFO)页面置换算法7.2.1 试验截图7.2.2 试验分析in103380812056b11111222b2000055b333336b48888out1037.3 验证LRU置换算法7.3.1 试验截图7.3.2 试验分析in968773712670b1999933366b266661110b38888222b4777777out96831八、报告书写人附录一 最佳置换算法(Optimal)#include <stdio.h>#include <stdlib.h>#include <

6、time.h>#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;i<B;i+)if(bufi=listnum)/当x在buf中，返回-1return -1;else if(bufi=-1) /当x不在buf中，且bufi为空，则把x填入buf，并返回-1bufi=listnum;return -2;for(i=0;i<B;i+)for(j=num+1;j<N;j+)if(bufi

7、=listj)if(max_d<j) 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 change=0;/置换次数int interrupt=0;/中断次数int successfully=0;/访问成功次数srand(int)

8、time(NULL);for(i=0;i<B;i+)bufi=fi=-1;printf("nn");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+;fo

9、r(m=0;m<=B;m+)printf(" ");/*成功的打印*/printf(" in<-%d successfullyn",listi);/*成功的打印*/else if(j=-2)bufuse+;interrupt+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm);/*缺页中断次数的打印*/for(m;m<B;m+)printf(" ");/*缺页中断的打印*/printf(" in&l

10、t;-%d interruptn",listi);/*缺页中断的打印*/elsetmp=bufj;bufj=listi;change+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm);/*缺页置换的打印*/for(m;m<B;m+)printf(" ");/*缺页置换的打印*/printf(" in<-%d change %d->outn",listi,tmp);/*缺页置换的打印*/printf("nn&

11、quot;);printf("interrupt=%dn",interrupt);printf("change=%dn",change);printf("successfully=%dn",successfully);return 0;附录二 先进先出(FIFO)页面置换算法#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 12/*随机数列的长度*/#define B 4/*内存页面数*/int IsInBuf(int b

12、uf,int x)int i;for(i=0;i<B;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;/中断次数int successfully=0;/访问成功次数

13、srand(int)time(NULL);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+

14、;for(m=0;m<=B;m+)printf(" ");/*成功的打印*/printf(" in<-%d successfullyn",listi);/*成功的打印*/else if(j=-2)bufuse+;interrupt+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm);/*缺页中断次数的打印*/for(m;m<B;m+)printf(" ");/*缺页中断的打印*/printf(" i

15、n<-%d interruptn",listi);/*缺页中断的打印*/elsetmp=bufold;bufold=listi;old=(old+1)%(int)B;/*数据在中的储存是循环的*/change+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm);/*缺页置换的打印*/for(m;m<B;m+)printf(" ");/*缺页置换的打印*/printf(" in<-%d change %d->outn&quo

16、t;,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/*随机数列的长度*/#defi

17、ne B 4/*内存页面数*/int IsInBuf(int buf,int list,int num)int i,j=-1;for(i=0;i<B;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;int i,j,k,m;for(m=0;m<B;m+)buf

18、fm=-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)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 successfull

19、y=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;/*中断的次数*/for(i=0;i<N;i+)j=IsInBuf(buf,list,i);if(j=-1)old=Get(buf,list,i);tmp=bufold;bufold=listi;change+;printf("newbuf=");for(m=0;m<bufuse;m+)printf("%d ",bufm);/*缺页置换的打印*/