fifo页面置换算法
‘壹’ 页面置换算法FIFO 、LRU求缺页中断次数
(1)FIFO
123412512345
----------------------------------------
123412555344
12341222533该行是怎么算出来的？
1234111255该行是怎么算出来的？
----------------------------------------
缺页中断次数=9
FIFO是这样的：3个内存块构成一个队列，前3个页面依次入队（3个缺页），内存中为3-2-1；
接着要访问4号页面，内存中没有（1个缺页），按FIFO，1号页面淘汰，内存中为4-3-2；
接着要访问1号页面，内存中没有（1个缺页），按FIFO，2号页面淘汰，内存中为1-4-3；
接着要访问2号页面，内存中没有（1个缺页），按FIFO，3号页面淘汰，内存中为2-1-4；
接着要访问5号页面，内存中没有（1个缺页），按FIFO，4号页面淘汰，内存中为5-2-1；
接着要访问1号页面，内存中有（命中），内存中为5-2-1；
接着要访问2号页面，内存中有（命中），内存中为5-2-1；
接着要访问3号页面，内存中没有（1个缺页），按FIFO，1号页面淘汰，内存中为3-5-2；
接着要访问4号页面，内存中没有（1个缺页），按FIFO，2号页面淘汰，内存中为4-3-5；
接着要访问5号页面，内存中有（命中），内存中为4-3-5；
缺页中断次数=9（12次访问，只有三次命中）
LRU不同于FIFO的地方是，FIFO是先进先出，LRU是最近最少用，如果1个页面使用了，要调整内存中页面的顺序，如上面的FIFO中：
接着要访问1号页面，内存中有（命中），内存中为5-2-1；
在LRU中，则为
接着要访问1号页面，内存中有（命中），内存中为1-5-2；
‘贰’ 页式管理的请求页式管理中的置换算法
功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacement policy。
出发点：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。
页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lock bit)。 轮转法(RR,round robin)和先进先出算法(FIFO,first in first out):轮转法循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。FIFO算法总是选择在内存驻留时间最长的一员将其淘汰。
FIFO算法认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的页顺次换出，而把换入的页链接在FIFO队尾即可。
由实验和测试发现FIPO算法和RR算法的内存利用率不高。这是因为，这两种算法都是基于CPU按线性顺序访问地址空间这一假设。事实上，许多时候．CPU不是按线性顺序访问地址空间的。
Belady现象:一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。 最近最久未使用页面置换算法(LRU, Least Recently Used):
选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：
(1) 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。
(2) 每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。
比较常用的近似算法有：
(a) 最不经常使用页面淘汰算法(LFU, Least Frequently Used)
(b) 最近没有使用页面淘汰(NRU, Not Recently Used) 理想型淘汰算法（OPT,Optimal Replacement Algorithm）
该算法淘汰在访问串中将来再也不出现的或是离当前最远的位置上出现的页。它是一种理想化的算法，性能最好，但在实际上难于实现。
‘叁’ fifo算法是什么
FIFO（First Input First Output），即先进先出队列。可以类比 我们在饭堂排队打饭，先排到队伍的最后，等待前面的人一个个打完饭再轮到下一个。这就是一种先进先出机制，先排队的人先行打饭离开。
FIFO（先进先出页面置换算法）：看到先进先出，我们想到的数据结构就是队列当分配的内存物理块数量为3时。
6，7，5先进入内存，那么出来的顺序就是5，7，6 缺页次数为3次。
2调入内存，6调出内存，那么顺序就是2，5，7 缺页次数为4次。
6调入内存，7调出内存，那么顺序就是6，2，5 缺页次数为5次。
7调入内存，5调出内存，那么顺序就是7，6，2 缺页次数为6次。
3调入内存，2调出内存，那么顺序就是3，7，6 缺页次数为7次。
6调入内存，已经存在，不需要调入。
7调入内存，已经存在，不需要调入。
5调入内存，6调出内存，那么顺序就是5，3，7 缺页次数为8次。
2调入内存，7调出内存，那么顺序就是2，5，3 缺页次数为9次。
3调入内存，已经存在，不需要调入。
‘肆’ 用C++语言编写FIFO页面置换算法代码
分别使用FIFO、OPT、LRU三种置换算法来模拟页面置换的过程。（Linux、Windows下皆可）
输入：3//页帧数
70120304230321201701//待处理的页
输出：页面置换过程中各帧的变化过程和出现页错误的次数
[cpp]
#include<iostream>
usingnamespacestd;
intinput[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
classpage
{
public:
intnum;
intmark;
page()
{
num=0;
mark=21;
}
};
voidFIFO()
{
cout<<"------FIFO-----------"<<endl;
interror=0;
pageframe[3];//页帧
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
frame[((error-1)%3)].num=input[i];//换掉最旧的页
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidOPT()
{
cout<<"------OPT------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=21;
for(intk=20;k>=i;k--)//向后遍历，找到最长时间不用的页
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
voidLRU()
{
cout<<"------LRU------------"<<endl;
interror=0;
pageframe[3];
for(inti=0;i<3;i++)//处理前三个引用
{
frame[i].num=input[i];
error++;
cout<<frame[i].num<<"|";
for(intj=0;j<=i;j++)
cout<<frame[j].num<<'';
cout<<endl;
}
for(inti=3;i<20;i++)
{
intj;
for(j=0;j<3;j++)
if(input[i]==frame[j].num)
{
cout<<input[i]<<endl;
break;
}
if(j==3)
{
error++;
for(j=0;j<3;j++)
{
frame[j].mark=0;
for(intk=0;k<=i;k++)//向前遍历，找到最近最少使用的
{
if(frame[j].num==input[k])
frame[j].mark=k;
}
}
if(frame[0].mark<frame[1].mark&&frame[0].mark<frame[2].mark)
frame[0].num=input[i];
elseif(frame[1].mark<frame[0].mark&&frame[1].mark<frame[2].mark)
frame[1].num=input[i];
else
frame[2].num=input[i];
cout<<input[i]<<"|";
for(intk=0;k<3;k++)
cout<<frame[k].num<<'';
cout<<endl;
}
}
cout<<"FrameError:"<<error<<endl<<endl;
}
intmain()
{
FIFO();
OPT();
LRU();
}
‘伍’ 下述什么页面置换算法会产生belady现象
先进先出页面置换算法（FIFO）。先闷并进先出页面置换算法（FIFO）页面置换算法会产生Belady异常现数罩塌象。先进先出页面置换算法的基本思想：每次置换最先调入内存的页面，即将内存中等待时间最长的页面进行置换。此算薯圆法的适用范围是顺序结构程序。
‘陆’ 如何用java实现fifo页面置换算法
[fifo.rar] - 操作系统中内存页面的先进先出的替换算法fifo
[先进先出页面算法程序.rar] - 分别实现最佳置换算法(optimal)、先进先出(fifo)页面置换算法和最近最久未使用（LRU）置换算法，并给出各算法缺页次数和缺页率。
[0022.rar] - 模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断
[Change.rar] - 用java实现操作系统的页面置换 其中包括 最佳置换算法(Optimal)、先进先出算法（First-in, First-out） 、最近最久不用的页面置换算法（LeastRecently Used Replacement）三种算法的实现
[M_Management.rar] - 操作系统中内存管理页面置换算法的模拟程序，采用的是LRU置换算法
[detail_of_44b0x_TCPIP.rar] - TCPIP 程序包加载到44b0x 的ADS1.2工程文件的说明书。说名了加载过程的细节和如何处理演示程序和代码。演示代码已经上传，大家可以搜索
[.rar] - java操作系统页面置换算法： （1）进先出的算法（fifo） （2）最近最少使用的算法（LRU） （3）最佳淘汰算法(OPT) （4）最少访问页面算法(LFU) （注：由本人改成改进型Clock算法） （5）最近最不经常使用算法(NUR)
‘柒’ 一个程序的页面走向，FIFO和LRU页面置换算法
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
void FIFO(void);
void LRU(void);
char a;
int m=4,n=12,i,y[12]={1,2,3,4,1,2,5,1,2,3,4,5}; /*m为物理块数，n为要访问的页面数*/
typedef struct page{
int num;
int time;
}Page;
Page x[10];
int GetMax(page *x) /*求出那个物理块中的页面呆的时间最长，返回物理块号*/
{
int i;
int max=-1;
int tag=0;
for(i=0;i<m;i++)
{
if(x[i].time>max)
{ max=x[i].time;
tag=i;
}
}
return tag;
}
void Xunhuan()
{
printf("Please select 1:FIFO算法\n 2:LRU算法\n");
scanf("%s",&a);
printf("物理块数：4\n");
//scanf("%d",&m);
for(i=0;i<m;i++) /*将空的物理块中数据置为-1*/
{
x[i].num=-1;
}
printf("所要访问的页面数：12\n");
//scanf("%d",&n);
//srand(time(NULL));
printf("所要访问的页面号序列为：");
for(i=0;i<n;i++)
printf("%d ",y[i]);
printf("\n");
printf("页面置换步骤如下：\n");
switch(a)
{
case '1':FIFO();break;
case '2':LRU(); break;
}
}
void main()
{
char a;
Xunhuan();
while(1)
{
printf("Continue or Exit:C/Anykey:\n");
scanf("%s",&a);
if(a=='c'||a=='C')
Xunhuan();
else break;
}
exit(0);
}
void FIFO(void)
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i])
{
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1)
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0;
}
if(u!=1&&x[m-1].num==-1)
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++;
for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n");
}
}
void LRU()
{
int i,j,u;
for(i=0;i<m;i++)
x[i].time=0;
x[0].num=y[0];
x[0].time=1;
printf(" %d \n",x[0].num);
for(i=1;i<n;i++)
{ u=0;
for(j=0;j<m;j++)
if(x[j].num==y[i]) /*物理块中存在相同页面*/
{
x[j].time=0; /*将相同的物理块的time置为0*/
u=1;
break;
}
if(u!=1&&x[m-1].num!=-1) /*物理块中无相同页面且物理块已填满*/
{
j=GetMax(x);
x[j].num=y[i];
x[j].time=0; /*将刚替换的页面所在的物理块time置为0*/
}
if(u!=1&&x[m-1].num==-1) /*物理块中无相同页面且物理块未填满*/
{
for(j=0;j<m;j++)
{
if(x[j].num==-1)
{x[j].num=y[i];
break;}
}
}
for(j=0;j<m;j++)
if(x[j].num!=-1)
x[j].time++; /*每执行完一次time加1*/
for(j=0;j<m;j++)
if(x[j].num==-1)
printf("%2c ",32);
else
printf("%2d ",x[j].num);
printf("\n"); /*格式化输出*/
}
}
‘捌’ 操作系统题：页面置换算法 OPT FIFO LRU
fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。