页面置换算法.docx
《页面置换算法.docx》由会员分享，可在线阅读，更多相关《页面置换算法.docx（19页珍藏版）》请在冰点文库上搜索。
页面置换算法
信息与计算科学
09级《操作系统实验》课程设计报告
题目:
页面置换方法
班级：
学号：
姓名：
时间：
2011/01/05
【课设题目】：
设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率
【课设要求】：
要求设计主界面以灵活选择某算法，且以下算法都要实现
1）先进先出算法（FIFO）
2）最近最久未使用算法（LRU）
3）最佳置换算法（OPT）
【课设目的】：
1、用C语言编写OPT、FIFO、LRU三种置换算法。
2、熟悉内存分页管理策略。
3、了解页面置换的算法。
4、掌握一般常用的调度算法。
5、根据方案是算法得以模拟实现。
【主要思想】：
先进先出算法（FIFO）
最简单的页面置换算法是先入先出（FIFO）法。
这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。
理由是：
最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。
建立一个FIFO队列，收容所有在内存中的页。
被置换页面总是在队列头上进行。
当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。
因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。
当然，导致这种异常现象的页面走向实际上是很少见的。
最近最久未使用算法（LRU）
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。
如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。
它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。
这种算法就称为最久未使用算法（LeastRecentlyUsed，LRU）。
LRU算法是与每个页面最后使用的时间有关的。
当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。
LRU算法需要实际硬件的支持。
其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
（1）计数器。
最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。
每次存储访问，该时钟都加1。
每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。
这样我们就可以始终保留着每个页面最后访问的“时间”。
在置换页面时，选择该时间值最小的页面。
这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。
（2）栈。
用一个栈保留页号。
每当访问一个页面时，就把它从栈中取出放在栈顶上。
这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。
由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。
在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。
每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。
所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（NotRecentlyUsed，NUR）。
它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。
当某一页被访问时，由硬件将该位置1。
过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。
就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。
最优置换算法（OPT）
最优置换（OptimalReplacement）是在理论上提出的一种算法。
其实质是：
当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。
采用这种页面置换算法，保证有最少的缺页率。
但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。
不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。
【设计方案】：
根据算法的思想：
程序开始时，输入所有的页面号，选择算法，OPT算法用一个
一维的数组来实现，LRU与OPT基本一样，前者是向前看的而后者则是向后看的。
FIFO则用队列来实现，很显然，先进先出是队列的主要特征。
按照所选的算法能
得到相应的结果。
输出时要有命中率，同时输出发生置换的物理块。
可以用switch
语句来实现大体框架，分别用三种算法作为函数来调用。
【算法流程】：
1.FIFO（先进先出）算法
2.LRU（最近最久未使用）算法
3.OPT（最佳置换）算法
【程序体现】：
#include
#include
#definemSIZE3//物理块号
#defineN20//页面个数
intpSIZE;
staticintmemery[mSIZE]={0,0,0};
staticintprocess[N];
voidFIFO（）;//先进先出服务
voidLRU（）;//最近最久未使用
voidget（）;//打印页面号
voidOPT（）;//最佳置换算法
intmain（）
{
inti,code;
get（）;
printf（"请输入页面次数:
"）;
scanf（"%d",&pSIZE）;
puts（"请输入你所需的页面置换数据:
"）;
for（i=0;i{
scanf（"%1d",&process[i]）;
}
do{
puts（"*****************************"）;
printf（"1.先进先出算法（FIFO）\n"）;
printf（"2.最近最久未使用算法（LRU）\n"）;
printf（"3.最佳置换算法（OPT）\n"）;
printf（"4.退出\n"）;
puts（"*****************************"）;
printf（"请选择置换算法:
"）;
scanf（"%d",&code）;
switch（code）
{
case1:
{
FIFO（）;
}break;
case2:
{
LRU（）;
}break;
case3:
{
OPT（）;
}break;
case4:
{}break;
}
}while（code!
=4）;
system（"PAUSE"）;
return0;
}
//打印页面数
voidget（）
{
inti;
for（i=0;i{
printf（"%d",process[i]）;
}
printf（"\n"）;
}
//先进先出
voidFIFO（）
{
intmemery[mSIZE]={0,0,0};
inttime[mSIZE]={0,0,0};
inti,j,k;
intmax=0;
intcount=0;
get（）;
for（i=0;i{
memery[i]=process[i];
time[i]=i;
for（j=0;j{
if（memery[j]!
=0）
printf（"%d",memery[j]）;
}
printf（"\n"）;
}//前mSIZE个数直接放入
for（i=mSIZE;i{
for（j=0,k=0;j{
if（memery[j]!
=process[i]）
k++;
}//判断新页面号是否在物理块中
if（k==mSIZE）//如果都不在物理块中
{
count++;
if（time[0]max=0;
elsemax=1;
if（time[2]max=2;
memery[max]=process[i];//把该页面换入最先来的页面号中
time[max]=i;
for（j=0;j{
if（memery[j]!
=0）
printf（"%d",memery[j]）;
}
printf（"\n"）;
}
else//物理块中有相等的打印上次的物理块数据
{
for（j=0;j{
if（memery[j]!
=0）
printf（"%d",memery[j]）;
}
printf（"\n"）;
}
}
printf（"置换次数:
%d\n",count+3）;
printf（"缺页率q=%d%%\n按任意键继续......\n",（count+3）*100/pSIZE）;
getchar（）;
}
//最近最久未使用
voidLRU（）
{
intmemery[mSIZE]={0,0,0};
intflag[mSIZE]={0,0,0};
inti,j,k;
intmax=0;
intcount=0;
get（）;
for（i=0;i{
memery[i]=process[i];
flag[i]=i;
for（j=0;j{
if（memery[j]!
=0）
printf（"%d",memery[j]）;
}
printf（"\n"）;
}//前mSIZE个数直接放入
for（i=mSIZE;i{
for（j=0,k=0;j{
if（memery[j]!
=process[i]）
k++;
elseflag[j]=i;
}//判断新页面号是否在物理块中
if（k==mSIZE）//如果都不在物理块中
{
count++;
if（flag[0]max=0;
elsemax=1;
if（flag[2]max=2;
memery[max]=process[i];//把该页面换入最久没有被使用的页面
flag[max]=i;
for（j=0;j{
printf（"%d",memery[j]）;
}
printf（"\n"）;
}
else//如果现在物理块中有相等的就打印上次的物理块
{
for（j=0;j{
printf（"%d",memery[j]）;
}
printf（"\n"）;
}
}
printf（"置换次数:
%d\n",count+3）;
printf（"缺页率q=%d%%\n按任意键继续......\n",（count+3）*100/pSIZE）;
getchar（）;
}
//最佳置换算法
voidOPT（）
{
intmemery[mSIZE]={0,0,0};
intnext[mSIZE]={0};
inti,j,k,l;
intcount=0,maxnext,max;
get（）;
for（i=0;i{
memery[i]=process[i];
for（j=0;j{
if（memery[j]!
=0）
printf（"%d",memery[j]）;
}
printf（"\n"）;
}//前mSIZE个数直接放入
for（i=mSIZE;i{
for（j=0,k=0;j{
if（memery[j]!
=process[i]）
k++;
}//判断新页面号是否在物理块中
if（k==mSIZE）//如果都不在物理块中
{
count++;
for（l=i+1;l{
if（memery[0]==process[l]）
{
next[0]=l;
gotolin1;
}
}
next[0]=l;
gotolin1;
lin1:
for（l=i+1;l{
if（memery[1]==process[l]）
{
next[1]=l;
gotolin2;
}
}
next[1]=l;
gotolin2;
lin2:
for（l=i+1;l{
if（memery[2]==process[l]）
{
next[2]=l;
gotolin3;
}
}
next[2]=l;
gotolin3;
lin3:
if（next[0]>=next[1]）
max=0;
elsemax=1;
if（next[2]>=next[max]）
max=2;
memery[max]=process[i];
for（j=0;j{
printf（"%d",memery[j]）;
}
printf（"\n"）;
}
else{
for（j=0;j{
printf（"%d",memery[j]）;
}
printf（"\n"）;
}
}
printf（"置换次数:
%d\n",count+3）;
printf（"缺页率q=%d%%\n按任意键继续......\n",（count+3）*100/pSIZE）;
getchar（）;
}
【程序测试】：
测试例题：
课本P150页例题三个物理块
页面号引用串：
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
1.先进先出算法（FIFO）
2.最近最久未被使用（LRU）
3.最佳置换方法（OPT）
【课设总结】
通过此次课设，使我熟练的掌握了页面置换方法，对最佳置换，先进先出算法，最近最久未被使用算法有了更深的了解。
而在编写程序中也发现了自己的不足，很多地方靠自己并不能完全写出，还需他人指导，因此再以后的学习当中还要更加的努力。
高洁
091002101
升级会员 