页面置换算法(C语言)

《操作系统》实验报告题目:页面置换算法班级：网络工程姓名：朱锦涛学号：E31314037一、实验目的用代码实现页面置换算法，通过代码的具体实现，加深对两个页面置换算法：先进先出页面置换算法和最近最久未使用算法的核心的理解。二、实验原理1.先进先出页面置换算法：地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出(FIFO)法。2.最近最久未使用算法：LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最少使用的那个页面调出内存。这就是LRU算法的全部内容。三、实验内容源程序：#includeiostream.h#includestdlib.h#includetime.h#includestdio.h#defineL20//页面走向长度最大为20intM;//内存块structPro//定义一个结构体{intnum,time;};voidprint(Pro*page1)//打印当前的页面{Pro*page=newPro[M];page=page1;for(inti=0;iM;i++)coutpage[i].num;coutendl;}intSearch(inte,Pro*page1)//寻找内存块中与e相同的块号{Pro*page=newPro[M];page=page1;for(inti=0;iM;i++)//遍历内存if(e==page[i].num)returni;//返回i值return-1;}intMax(Pro*page1)//寻找最近最长未使用的页面{Pro*page=newPro[M];page=page1;inte=page[0].time,i=0;while(iM)//找出离现在时间最长的页面{if(epage[i].time)e=page[i].time;i++;}for(i=0;iM;i++)if(e==page[i].time)returni;//找到离现在时间最长的页面返回其块号return-1;}intCount(Pro*page1,inti,intt,Prop[L])//记录当前内存块中页面离下次使用间隔长度{Pro*page=newPro[M];page=page1;intcount=0;for(intj=i;jL;j++){if(page[t].num==p[j].num)break;//当前页面再次被访问时循环结束elsecount++;//否则count+1}returncount;//返回count的值}intmain(){intc,i;intt=0;floatn=0;Prop[L];//20个结构体srand(time(NULL));//随机数发生器cout输出随机数:;for(i=0;i20;i++)//20个随机数{p[i].num=rand()%10+1;//产生1到10之间的随即数放到数组p中p[i].time=0;coutp[i].num;}coutendl;cout请输入可用内存页面数m(3～5):;do{cinM;if(M5||M3)cout内存块m须在3～5之间，请重新输入m：;elsebreak;}while(1);Pro*page=newPro[M];//动态结构体数组do{for(inti=0;iM;i++)//初试化页面基本情况{page[i].num=0;page[i].time=20-1-i;}cout1:FIFO页面置换endl;cout2:LRU页面置换endl;cout按其它键结束程序；endl;cinc;system(cls);//清屏if(c==1)//FIFO页面置换{n=0;cout******************************************endl;coutendl;coutFIFO算法页面置换情况如下:endl;coutendl;cout******************************************endl;while(i20){if(Search(p[i].num,page)=0)//当前页面在内存中{coutp[i].num;//输出当前页p[i].numcout不缺页endl;i++;//i加1}else//当前页不在内存中{if(t==M)t=0;else{n++;//缺页次数加1page[t].num=p[i].num;//把当前页面放入内存中coutp[i].num;print(page);//打印当前页面t++;//下一个内存块i++;//指向下一个页面}}}cout缺页次数：n缺页率：n/20endl;}if(c==2)//LRU页面置换{n=0;cout******************************************endl;coutendl;coutLRU算法页面置换情况如下:endl;coutendl;cout******************************************endl;while(i20){inta;t=Search(p[i].num,page);if(t=0)//如果已在内存块中{page[t].time=0;//把与它相同的内存块的时间置0for(a=0;aM;a++)if(a!=t)page[a].time++;//其它的时间加1coutp[i].num;cout不缺页endl;}else//如果不在内存块中{n++;//缺页次数加1t=Max(page);//返回最近最久未使用的块号赋值给tpage[t].num=p[i].num;//进行替换page[t].time=0;//替换后时间置为0coutp[i].num;print(page);for(a=0;aM;a++)if(a!=t)page[a].time++;//其它的时间加1}i++;}cout缺页次数：n缺页率：n/20endl;}}while(c==1||c==2);return0;}实验结果：FIFO置换算法：LRU置换算法：四.实验小结本次试验，使用顺序表来存储包括内存页面和页面号引用串，structPro{intnum,time;};其中num表示页面号，页面号引用串用随机数循环20次来初始化20个页面号，同时物理块号可由用户自己在3~5之间选择，初始化页面号全为0。Time为该页面在内存的时间，这只在LRU算法有使用到。第一个页面进入物理块时初始化为0，以后每有新页面过来询问时，不管有没有替换内存中的页面，都将其值加一。当新页面进来时，若内存中有该页面号，则将该块号重新置为0，内存中其他页面的时间+1，若没有该页面号，则替换内存中页面时间最长的。通过本次试验，我加深了对两个页面置换算法：先进先出页面置换算法和最近最久未使用算法的核心的理解。