页式虚拟存储管理组织FIFOLRU和OPT页面置换算法Word文件下载.docx
《页式虚拟存储管理组织FIFOLRU和OPT页面置换算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《页式虚拟存储管理组织FIFOLRU和OPT页面置换算法Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。
从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
3．1FIFO（先进先出）页面置换算法：
这是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
3．2LRU（最近最久未使用）置换算法：
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。
最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
3．3OPT（最优页）置换算法
最优页置换算法是所有算法中产生页错误率最低的，而且绝对没有Belady异常的问题。
它会置换最长时间不会使用的页。
最优页（OPT）置换算法，是根据最长时间不会使用的页来决策的。
这就意味着，需要注意内存中的页面和页面的距离了。
因此OPT算法是选择最久未使用的页面进行淘汰的。
该算法赋予内存中每个页面一个访问字段，用来记录距离此处的最近页面的距离，这样通过比较，就能把最久未使用的页面淘汰掉。
4测试
程序在设计过程中，曾经出过这样或者那样的问题，最让我纠结的问题是在设计OPT算法时出现的，当我认为没有问题的时候程序一运行就没有想要的结果，很明显不是语法上的错误，由于在程序编写过程中没有截图，此处没有图片说明了。
都是逻辑上的错误，最让人难以接受的是，不是程序的逻辑，还是思维的逻辑，也就是从一开始编写程序时，自己的想法的错误了，我说怎么老是显示不出正确的结果，后来改正后结果就显示正常了。
5运行结果
5.1主界面
5.2输入错误的选择
5.3选择4的时候自己输入新的页面号引用串，此处输入书上的例子
5.4确认后首部分的页面号引用串改变
5.5选择FIFO算法，相关设置之后
5.6选择LRU算法之后
5.7选择OPT算法之后
5.8如果你选择的物理模块是其他的数量，此处用4个模块，OPT算法为例
6课程设计总结
1、通过完成该课程设计，使我了解了什么是缺页中断，以及处理缺页中断的调度算法。
通过自己编程，加深了对理论学习的理解。
自己动手的编写对缺页终端的调度算法了解加深了不少了解，使我也明白了，真理是在实践中证明的。
程序中也出现过这样或者那样的问题，我也曾经颓废过，为了一个简单的逻辑问题纠结了好久，真正弄明白之后才发现自己是那么的蠢，一种豁然开朗的感觉涌上心头。
2、程序执行是稳定的，高效的。
在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，页面都必须更新这些记录项。
这个记录项在此程序中为
typedefstructpage
{
intyemian;
//页面号
intbiaoji;
//被访问标记
}page;
/*页面逻辑结构，结构为方便算法实现设计*/
如此显然要花费较大的系统开销（包括时间和空间上的），这也是实际系统中不直接采用LRU算法作为页面置换算法的直接原因，但由于其在页面置换的优越性，实际系统常使用LRU的近似算法。
7参考文献
《操作系统概念》第七版
8附录：
源程序清单
#include<
iostream.h>
stdlib.h>
//70120304230321201701书上的例子
constintNsize=10;
constintPsize=20;
pageblock[Nsize];
//物理块
pagepage[Psize];
//页面号串
voidInit（intQString[],intNsize）
{//初始化内存单元、缓冲区
for（inti=0;
i<
Nsize;
i++）
{
block[i].yemian=-1;
//找到空闲内存
block[i].biaoji=0;
}
for（i=0;
Psize;
page[i].yemian=QString[i];
page[i].biaoji=0;
}
intfindSpace（intNsize）
{//查找是否有空闲内存
if（block[i].yemian==-1）
{
returni;
//找到空闲内存，返回BLOCK中位置
}
return-1;
intfindExist（intcurpage,intNsize）
{//查找内存中是否有该页面
if（block[i].yemian==page[curpage].yemian）
//找到内存中有该页面，返回BLOCK中位置
intfindReplace（intNsize）
{//查找应予置换的页面
inta=0;
for（inti=0;
if（block[i].biaoji>
=block[a].biaoji）
{
a=i;
//找到应予置换页面，返回BLOCK中位置
}
returna;
voiddisplay（intNsize）
{//显示
if（block[i].yemian!
=-1）//非空闲内存
cout<
<
block[i].yemian<
"
"
;
cout<
endl;
/*FIFO核心部分*/
voidFIFO（intNsize）
{//先进先出页面置换算法
intexist,space,aition;
floatscore=0;
exist=findExist（i,Nsize）;
if（exist!
=-1）//内存中有该页面
cout<
不缺页"
score+=1;
//统计不缺页次数
else
{
space=findSpace（Nsize）;
if（space!
=-1）//找到空闲内存
block[space]=page[i];
display（Nsize）;
else
aition=findReplace（Nsize）;
//找到应予置换页面
block[aition]=page[i];
for（intj=0;
j<
j++）
block[j].biaoji++;
//BLOCK中所有页面biaoji++
缺页次数为：
20-score<
缺页率为：
（20-score）*100/20<
%"
/*LRU核心部分*/
voidLRU（intNsize）
{//最近最久未使用置换算法
=-1）
block[exist].biaoji=0;
/*OPT算法核心部分*/
voidOPT（intNsize）
{//最优页置换算法
intexist,space,aition;
block[space]=page[i];
display（Nsize）;
for（intj=0;
for（intl=i;
l<
l++）
if（block[j].yemian==page[l].yemian）//计算谁是最长时间没使用的
{
block[j].biaoji=l-i;
break;
}
else
block[j].biaoji=Psize-i;
aition=findReplace（Nsize）;
block[aition]=page[i];
voidBlockClear（intNsize）
{//块清除
block[i].yemian=-1;
block[i].biaoji=0;
/*主程序*/
voidmain（void）
{
inti,select,Nsize,QString[Psize]={0};
while（select）
cout<
页面号引用串:
i<
20;
i++）
QString[i]<
+******************************+"
+------------欢迎--------------+"
+--------页面置换算法----------+"
+-----选择<
1>
应用FIFO算法------+"
2>
应用LRU算法-------+"
3>
应用OPT算法-------+"
+---选择<
4>
插入新的页面号引用串+"
+-------选择<
0>
退出------------+"
请选择：
cin>
>
select;
switch（select）
case0:
break;
case1:
请输入分配的物理块数的大小:
while
（1）
if（Nsize>
0&
&
Nsize<
=10）
Init（QString,Nsize）;
for（i=0;
FIFO算法结果如下:
FIFO（Nsize）;
BlockClear（Nsize）;
----------------------"
system（"
pause"
）;
cls"
else
---输入有误，物理块数请选择1-10的数---"
endl<
cin>
case2:
while
（1）
LRU算法结果如下:
LRU（Nsize）;
break;
cin>
case3:
OPT算法结果如下:
OPT（Nsize）;
case4:
请输入20个数：
\n"
{
QString[i];
system（"
default:
提示:
功能号错误!
system（"
升级会员 