页面置换算法的实现.docx
- 文档编号:13466463
- 上传时间:2023-06-14
- 格式:DOCX
- 页数:23
- 大小:112.71KB
页面置换算法的实现.docx
《页面置换算法的实现.docx》由会员分享,可在线阅读,更多相关《页面置换算法的实现.docx(23页珍藏版)》请在冰点文库上搜索。
页面置换算法的实现
题目5页面置换算法的实现
5.1题目的主要研究内容及预期达到的目标
(1)该程序模拟操作系统常用的页面置换算法;
A、最佳置换算法(OPT)
B、先进先出置换算法(FIFO)
C、最近最久未使用置换算法(LRU)
(2)理解页面置换算法相关内容;
(3)掌握页面置换算法主要流程;
(4)掌握常用页面置换算法的实现过程。
5.2题目研究的工作基础或实验条件
(1)硬件环境:
装有Linux操作系统(虚拟机)的计算机一台。
(2)软件环境:
vim编辑器、VisualC++。
5.3设计思想
(1)页面的随机生成
使用rand()函数随机产生页面号,用数组装入页面号,模拟页面调入内存中发生页面置换的过程。
整个过程,都是使用数组来实现每个算法,模拟队列,模拟堆栈的功能,实现每一个置换算法。
(2)先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单,只需把一个进程已调入内存的页面,按照先后次序连接成一个队列,并设置一个替换指针,使它总指向最老的页面。
(3)最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进行决策的。
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。
(4)最佳(OPT)置换算法的思路
其所选择的被淘汰的页面,奖是以后不使用的,或者是在未来时间内不再被访问的页面,采用最佳算法,通常可保证获得最低的缺页率
5.4流程图
图5-1最佳置换算法(OPT)流程图
图5-2先进先出置换算法(FIFO)
图5-3最近最久未使用置换算法(LRU)
5.5主要程序代码
#include
#include
usingnamespacestd;
intconstInsideCount=6;//内存中存放的页面数
intcount=0;//用来记录已存放的页面数
intInside[InsideCount];//存放内存中的页号
intconstPageCount=10;//总的页面数
intPage[PageCount];//存放产生的页面号
intinsert=0;//先到先出置换算法fcfo中表示当内存满的时候,新进入的页号放的位置
intsuiji=0;//随机置换算法randchange当内存满的时候,新进入的页号放的位置
doublelost=0.0;//缺失次数
boolisInside(intnum)//检测页号是否在内存中
{
for(inti=0;i { if(Inside[i]==Page[num]) { returntrue; } } returnfalse; } voidLRU(intnum)//近久未使用置换算法LRU { intmax=0;//表示内存中的页号,下一次出现的距离 intmaxchange;//表示内存中下次出现距离大的页号在内存中的位置 intk; if(isInside(num))//判断是否命中 { cout<<"命中"< for(inti=0;i cout<<"内存Inside["< "< } elseif(count==InsideCount) { lost++;//缺失次数+1 for(intj=0;j { for(k=num;k>0;k--)//从当前的页号向前,发现页号与内存中的页号相同,break;比较内存中InsideCount个页号,哪一个走的远,用max记录 { if(Inside[j]==Page[k]) break; } if(num-k>max)//求最旧未使用 { max=num-k; maxchange=j;//j表示把内存中第j个Inside中的页面从内存拿出,把新的页面放入 } } Inside[maxchange]=Page[num]; for(inti=0;i cout<<"内存Inside["< "< } else { Inside[count]=Page[num]; count++; for(inti=0;i cout<<"内存Inside["< "< } } voidFIFO(intnum)//先进先出置换算法(FIFO): { if(isInside(num))//判断是否命中 { cout<<"命中"< for(inti=0;i cout<<"内存Inside["< "< } elseif(count==InsideCount)//内存是否已满 { lost++;//缺页+1 Inside[insert]=Page[num];//页面放入内存 insert++;//位置移到下一个 insert=insert%InsideCount;//保证循环 for(inti=0;i cout<<"内存Inside["< "< } else//没命中且没满 { Inside[count]=Page[num]; count++; for(inti=0;i cout<<"内存Inside["< "< } } voidOPT(intnum)//最佳置换算法(OPT)(理想置换算法) { intmax=0;//表示内存中的页号,下一次出现的距离 intmaxchange;//表示内存中下次出现距离大的页号在内存中的位置 intk; if(isInside(num)) { cout<<"命中"< for(inti=0;i cout<<"内存Inside["< "< } elseif(count==InsideCount) { lost++;//缺页+1 for(intj=0;j { for(k=num;k { if(Inside[j]==Page[k]) break; } if(k>max) { max=k;//k表示在这个地方会再次出现给定页面 maxchange=j;//j表示把内存中第j个Inside中的页面从内存拿出,把新的页面放入 } } Inside[maxchange]=Page[num]; for(inti=0;i cout<<"内存Inside["< "< } else//没命中且没满 { Inside[count]=Page[num]; count++; for(inti=0;i cout<<"内存Inside["< "< } } intmain() { charch;//选择使用哪种算法 while (1){ for(inti=0;i { Page[i]=rand()%9+1; } cout<<"请选择置换算法"<<"\n"< cout<<"O最佳置换算法(OPT)(理想置换算法)"<<"\n"< cout<<"F先进现出置换算法(FIFO)"<<"\n"< cout<<"U近久未使用(LRU)算法"<<"\n"< cin>>ch; switch(ch){ case'O': { lost=0; count=0; for(intj=0;j { Inside[j]=0; } for(inti=0;i { cout<<"读入Page["< OPT(i); } cout<<"共"< } break; case'F': { lost=0; count=0; for(intj=0;j { Inside[j]=0; } for(inti=0;i { cout<<"读入Page["< FIFO(i); } cout<<"共"< } break; case'U': { lost=0; count=0; for(intj=0;j { Inside[j]=0; } for(inti=0;i { cout<<"读入Page["< LRU(i); } cout<<"共"< } break; } } return0; } 5.6运行结果及分析 O 读入Page[0]=7 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 0 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[1]=1 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[2]=6 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[3]=7 命中 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[4]=3 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 3 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[5]=9 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 3 内存Inside[4]中内容为: 9 内存Inside[5]中内容为: 0 读入Page[6]=8 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 3 内存Inside[4]中内容为: 9 内存Inside[5]中内容为: 8 读入Page[7]=4 内存Inside[0]中内容为: 4 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 3 内存Inside[4]中内容为: 9 内存Inside[5]中内容为: 8 读入Page[8]=5 内存Inside[0]中内容为: 5 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 3 内存Inside[4]中内容为: 9 内存Inside[5]中内容为: 8 读入Page[9]=3 命中 内存Inside[0]中内容为: 5 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 6 内存Inside[3]中内容为: 3 内存Inside[4]中内容为: 9 内存Inside[5]中内容为: 8 共10次,缺失2次,缺失率为0.2 F 读入Page[0]=8 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 0 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[1]=7 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[2]=7 命中 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[3]=9 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[4]=6 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 6 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[5]=4 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 6 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 0 读入Page[6]=7 命中 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 6 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 0 读入Page[7]=3 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 6 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 3 读入Page[8]=9 命中 内存Inside[0]中内容为: 8 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 6 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 3 读入Page[9]=2 内存Inside[0]中内容为: 2 内存Inside[1]中内容为: 7 内存Inside[2]中内容为: 9 内存Inside[3]中内容为: 6 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 3 共10次,缺失1次,缺失率为0.1 U 读入Page[0]=1 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 0 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[1]=2 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 0 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[2]=3 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[3]=2 命中 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 0 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[4]=9 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 9 内存Inside[4]中内容为: 0 内存Inside[5]中内容为: 0 读入Page[5]=4 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 9 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 0 读入Page[6]=6 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 9 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 6 读入Page[7]=3 命中 内存Inside[0]中内容为: 1 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 9 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 6 读入Page[8]=7 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 2 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 9 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 6 读入Page[9]=1 内存Inside[0]中内容为: 7 内存Inside[1]中内容为: 1 内存Inside[2]中内容为: 3 内存Inside[3]中内容为: 9 内存Inside[4]中内容为: 4 内存Inside[5]中内容为: 6 共10次,缺失2次,缺失率为0.2 5.7心得体会 操作系统常用的页面置换算法有最佳置换算法(OPT)、先进先出置换算法(FIFO)、最近最久未使用置换算法(LRU)。 当然还有其他的置换算法,比如说: Clock置换算法、最少使用置换算法等等。 置换算法的好坏直接影响到系统的性能,如何选择一个更好的置换算法显得至关重要,但是我们仅仅研究算法或许并不能很好的提高系统的性能,如何实现硬件和软件的相互提高似乎更关键。 就像现在的固态硬盘,可以很好的提高数据的读取速度。 随着科技的发展,是不是能够实现大容量的高速缓冲存储器呢? 或许说随着云平台的发展,会不会淘汰现有的技术呢? 与其在这模拟实现已经接近淘汰的算法,不如开阔思维寻求新的技术。 或许说我们的课程设计应该更偏向于创新性。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 页面 置换 算法 实现