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

23/23《计算机操作系统》实验报告实验五：页面调度算法模拟学校：╳╳╳院系：╳╳╳班级：╳╳╳某：╳╳╳学号：╳╳╳指导教师：╳╳╳目录TOC\o"1-3"\h\u18510一、实验题目319322二、实验学时325689三、指导老师32309四、实验日期32522五、实验目的317597六、实验原理3322856.1页面的含义3279886.2页面置换算法的含义33406.3置换算法3177506.3.1最佳置换算法(Optimal)3190656.3.2先进先出(FIFO)页面置换算法351296.3.3LRU置换算法41827七、实验步骤及结果4282617.1验证最佳置换算法4100197.1.1实验截图4247777.1.2实验分析4148217.2验证先进先出(FIFO)页面置换算法5182627.2.1实验截图550907.2.2实验分析5210127.3验证LRU置换算法6257727.3.1实验截图6233737.3.2实验分析627227八、报告书写人610697附录一最佳置换算法(Optimal)75479附录二先进先出(FIFO)页面置换算法1017864附录三LRU置换算法13实验五：页面调度算法模拟一、实验题目页面调度算法模拟二、实验学时2学时三、指导老师╳╳╳四、实验日期2018年12月10日星期一五、实验目的(1)熟悉操作系统页面调度算法(2)编写程序模拟先进先出、LRU等页面调度算法，体会页面调度算法原理六、实验原理6.1页面的含义分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。6.2页面置换算法的含义在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_ReplacementAlgorithms)。6.3置换算法一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。6.3.1最佳置换算法(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。6.3.2先进先出(FIFO)页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。6.3.3LRU置换算法LRU置换算法是选择最近最久未使用的页面予以淘汰。七、实验步骤及结果7.1验证最佳置换算法7.1.1实验截图7.1.2实验分析in727710440804b1777744b222228b31111b4000out727.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<time.h>#defineN12/*随机数列的长度*/#defineB4/*内存页面数*/intIsInBuf(intbuf[],intlist[],intnum){inti,j=-1;intmax_p;intmax_d=0;for(i=0;i<B;i++){if(buf[i]==list[num])//当x在buf中，返回-1return-1;elseif(buf[i]==-1)//当x不在buf中，且buf[i]为空，则把x填入buf，并返回-1{buf[i]=list[num];return-2;}}for(i=0;i<B;i++){for(j=num+1;j<N;j++){if(buf[i]==list[j]){if(max_d<j){max_d=j;//buf[i]在list[]中的最近距离max_p=i;//list[j]在buf[]的位置}break;}}if(j==N)//如果buf满，并且buf[i]不在list[]的后半部分，返回位置ireturni;}returnmax_p;//返回距离最远的buf[]的位置}intmain(){intlist[N];//={4,3,2,1,4,3,5,4,3,2,1,5};intbuf[B],i,f[N],j,m,bufuse=0,tmp;intchange=0;//置换次数intinterrupt=0;//中断次数intsuccessfully=0;//访问成功次数srand((int)time(NULL));for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("\n\n");printf("TheOptimalList:");for(i=0;i<N;i++){list[i]=(int)rand()%10;printf("%2d",list[i]);}printf("\n");printf("\nthelostinOptimal:\n");for(i=0;i<N;i++){j=IsInBuf(buf,list,i);if(j==-1){successfully++;for(m=0;m<=B;m++){printf("");/*成功的打印*/}printf("in<--%dsuccessfully\n",list[i]);/*成功的打印*/}elseif(j==-2){bufuse++;interrupt++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺页中断次数的打印*/}for(m;m<B;m++){printf("");/*缺页中断的打印*/}printf("in<--%dinterrupt\n",list[i]);/*缺页中断的打印*/}else{tmp=buf[j];buf[j]=list[i];change++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺页置换的打印*/}for(m;m<B;m++){printf("");/*缺页置换的打印*/}printf("in<--%dchange%d-->out\n",list[i],tmp);/*缺页置换的打印*/}}printf("\n\n");printf("interrupt=%d\n",interrupt);printf("change=%d\n",change);printf("successfully=%d\n",successfully);return0;}附录二先进先出(FIFO)页面置换算法#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN12/*随机数列的长度*/#defineB4/*内存页面数*/intIsInBuf(intbuf[],intx){inti;for(i=0;i<B;i++){if(buf[i]==x)/*当x在buf中，返回其位置*/return-1;elseif(buf[i]==-1)/*当x不在buf中，且buf[i]为空，则把x填入buf，并返回其位置*/{buf[i]=x;return-2;}}return0;}intmain(){intlist[N];//={4,3,2,1,4,3,5,4,3,2,1,5};intbuf[B],i,f[N],j,m,bufuse=0,tmp;intold=0;intchange=0;//置换次数intinterrupt=0;//中断次数intsuccessfully=0;//访问成功次数srand((int)time(NULL));for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("\n\n");printf("TheFIFOList:");for(i=0;i<N;i++){list[i]=(int)rand()%10;printf("%2d",list[i]);}printf("\n");printf("\nthelostinFIFO:\n");for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){successfully++;for(m=0;m<=B;m++){printf("");/*成功的打印*/}printf("in<--%dsuccessfully\n",list[i]);/*成功的打印*/}elseif(j==-2){bufuse++;interrupt++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺页中断次数的打印*/}for(m;m<B;m++){printf("");/*缺页中断的打印*/}printf("in<--%dinterrupt\n",list[i]);/*缺页中断的打印*/}else{tmp=buf[old];buf[old]=list[i];old=(old+1)%(int)B;/*数据在ｂｕｆ中的储存是循环的*/change++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺页置换的打印*/}for(m;m<B;m++){printf("");/*缺页置换的打印*/}printf("in<--%dchange%d-->out\n",list[i],tmp);/*缺页置换的打印*/}}printf("\n\n");printf("interrupt=%d\n",interrupt);printf("change=%d\n",change);printf("successfully=%d\n",successfully);return0;}附录三LRU置换算法#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN12/*随机数列的长度*/#defineB4/*内存页面数*/intIsInBuf(intbuf[],intlist[],intnum){inti,j=-1;for(i=0;i<B;i++){if(buf[i]==list[num])/*当x在buf中，返回其位置*/{j=i;break;}elseif(buf[i]==-1)/*当x不在buf中，且buf[i]为空，则把x填入buf，并返回其位置*/{buf[i]=list[num];j=-2;break;}}returnj;}intGet(intbuf[],intlist[],intnum){intbuff[B];intbuffuse=0;inti,j,k,m;for(m=0;m<B;m++)buff[m]=-1;for(i=num-1;i>=0;i--){for(j=0;j<B;j++){if(list[i]==buf[j]){for(k=0;k<buffuse;k++){if(list[i]==buff[k])break;}if(k==buffuse){buff[buffuse]=list[i];buffuse++;if(buffuse==B)returnj;}break;}}}return0;}intmain(){intlist[N];//intlist[12]=intbuf[B],i,f[N],j,m,bufuse=0,tmp;intold=0;intchange=0;intinterrupt=0;intsuccessfully=0;srand((int)time(NULL));for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("TheRandomList:");for(i=0;i<N;i++){list[i]=(int)rand()%10;printf("%2d",list[i]);}printf("\n\n");printf("\nthelostinLRU:\n");change=0;/*中断的次数*/for(i=0;i<N;i++)