fifo替换算法

‘壹’ 操作系统题：页面置换算法 OPT FIFO LRU

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。

‘贰’ 用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();
}

‘叁’ fifo算法怎么写

用C语言编写简单的FIFO置换算法#include "stdio.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define NULL 0
#define status int
typedef int Elemtype;

/*这个定义的是队列的元素的数据结构*/
typedef struct tailDATA{
Elemtype data;/*这个存放的是队列元素的值*/
struct tailDATA *next;//指向下一个元素
}datatail,*map;

/*以下定义的是队列头的数据结构*/
typedef struct Tail{
/*说明:对队列进行操作的时候,插入的时候是对front操作,删除*/
Elemtype data;/*这个记载的是队列的元素的个数*/
map front;/*这个是队列的头*/
map rear;/*这个是队列的尾*/
}tail,*mappath;

/*以下定义的就是操作了,初始话的操作就不想做了,直接写个插入和删除等的一些的算法就可以了*/
status inserttail(mappath &T,map P)
{/*这个函数的功能是将一个个已知的元素插入队列中*/
if(T==NULL)
{
T=(mappath)malloc(sizeof(tail));
T->data=0;
T->front=NULL;
T->rear=NULL;
}
if(!P) return OK;
T->rear->next=P;
T->rear=P;
if(!(T->front)) T->front=P;
return OK;
}

status insertdatatail(mappath &T,int a)
{/*这个函数将一个元素插入队列中,其实这个函数是没有必要的,但是为了方便起见,还是写了个*/
if(T==NULL)
{
T=(mappath)malloc(sizeof(tail));
T->data=0;
T->front=NULL;
T->rear=NULL;
map linshi=(map)malloc(sizeof(datatail));
linshi->data=a;
linshi->next=NULL;
T->front=linshi;
T->rear=linshi;
T->data=1;
return OK;
}
map linshi=(map)malloc(sizeof(datatail));
linshi->data=a;
linshi->next=NULL;
T->rear->next=linshi;
T->rear=linshi;
if(!(T->front)) T->front=linshi;
T->data++;
return OK;
}

status deltail(mappath &T)
{/*因为对队列进行删除操作的时候,基本上是没有什么条件,就是对front做一些相应的操作就可以了
,所以他的函数列表也就比较少了*/
if(!T) return ERROR;/*如果队列本来就是空的,那么就返回一个错误的信息*/
if(T->front==T->rear)
{/*如果队列只有一个元素,就执行下面的操作,防止出现了错误*/
map linshi=T->front;
free(linshi);
T->data=0;
T->front=NULL;
T->rear=NULL;
return OK;
}
map linshi=T->front;
T->front=T->front->next;
T->data--;
free(linshi);
return OK;
}

status puttail(mappath T)
{/*这个是对一个已经存在的队列进行输出*/
if(!T) return ERROR;
printf("the tail'count is %d\n",T->data);
int count=T->data;map q=T->front;
for(int i=0;i<count;i++)
{
printf("%d ",q->data);
q=q->next;
}
return OK;
}

int main()
{
printf("hello,world!\n");
mappath q=NULL;int count1=0;int dataa=0;
printf("please input a number to the count of tail\n");
scanf("%d",&count1);
for(int i=0;i<count1;i++)
{
printf("please input a number to tail\n");
scanf("%d",&dataa);
insertdatatail(q,dataa);
}
puttail(q);
deltail(q);
puttail(q);
return 0;
}

‘肆’ 计算机组成原理-----替换算法

fifo先进先出算法 有abc 三个存储空间 每个空间能存放一个元素按照队列方式
进出，以此是 a b c 命中率=abc中访问到的次数/元素个数
------------------2 1 0 此时存储空间已满 要调用新的元素就要出队列
------------------4 2 1 下一个元素2在b内 访问成功一次
------------------。。。。 以此类推
--------------最后3 1 2 最后一个元素又从存储单元里访问到一次 所以2/11

fifo+lru：同上加上最近虽少使用。列出上面的表格按队列进入 把最长时间没使用到的替换掉 一共访问到2这个元素3次 所以就是3/11

‘伍’ FIFO和LRU置换算法的问题

FIFO 先进先出
-------------
刚开始内存为空 null, null, null
使用2，缺页读入 2, null, null
使用3，缺页读入 2, 3, null
使用2，直接使用 2, 3, null
使用1，缺页读入 2, 3, 1
使用5，缺页读入 3, 1, 5 因为2是最先读入的，所以就把它删掉
使用2，缺页读入 1, 5, 2
使用4，缺页读入 5, 2, 4
使用5，直接使用 5, 2, 4
使用3，缺页读入 2, 4, 3
使用2，直接使用 2, 4, 3
使用5，缺页读入 4, 3, 5
使用2，缺页读入 3, 5, 2

共9次缺页
========================

LRU 会删除最不常访问的
----------------------
刚开始内存为空 null, null, null
使用2，缺页读入 2, null, null
使用3，缺页读入 3, 2, null
使用2，直接使用 2, 3, null
使用1，缺页读入 1, 2, 3
使用5，缺页读入 5, 1, 2 因为最近1和2都访问过而3是很早之前用过的，所以就把它删掉
使用2，直接使用 2, 5, 1
使用4，缺页读入 4, 2, 5
使用5，直接使用 5, 4, 2
使用3，缺页读入 3, 5, 4
使用2，缺页读入 2, 3, 5
使用5，直接使用 5, 2, 3
使用2，直接使用 2, 5, 3

共7次缺页

‘陆’ 虚拟存储器采用的页面调度算法是“先进先出”（FIFO）算法吗

虚拟存储器采用的页面调度算法是“先进先出”（FIFO）算法吗。常见的替换算法有4种。

①随机算法：用软件或硬件随机数产生器确定替换的页面。

②先进先出：先调入主存的页面先替换。

③近期最少使用算法（LRU，Least Recently Used）：替换最长时间不用的页面。

④最优算法：替换最长时间以后才使用的页面。这是理想化的算法，只能作为衡量其他各种算法优劣的标准。

虚拟存储器的效率是系统性能评价的重要内容，它与主存容量、页面大小、命中率，程序局部性和替换算法等因素有关。

(6)fifo替换算法扩展阅读

虚拟存储器地址变换基本上有3种形虚拟存储器工作过程式：全联想变换、直接变换和组联想变换。任何逻辑空间页面能够变换到物理空间任何页面位置的方式称为全联想变换。每个逻辑空间页面只能变换到物理空间一个特定页面的方式称为直接变换。

组联想变换是指各组之间是直接变换，而组内各页间则是全联想变换。替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。

在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：有效位(指明该段是否已经调入主存)、段起址(该段在实存中的首地址)和段长(记录该段的实际长度)。

‘柒’ FIFO算法的解释

/*我知道FIFO算法的原理，可还是不理解这代码，哪位高手指教下各个程序段的意思啊？不胜感激！ */
#include <stdio.h>
#include <stdlib.h>
#define mSIZE 3//分配三个内存页框
#define pSIZE 12//总共12个进程
static int memery[mSIZE] = {0};
static int process[pSIZE] = {1,2,3,4,1,2,5,1,2,3,4,5};//页面访问序列
void FIFO();
int main()
{
get();
printf("\n(FIFO)\tcount\n");
FIFO();
system("PAUSE");
return 0;
}

get()
{
int w[12]={1,2,3,4,1,2,5,1,2,3,4,5}; //需要访问的资源序列
int i,n;
for(i=0;i<12;i++) //输出序列
{
printf("%d ",w[i]);
}
}
void FIFO()
{
int time[mSIZE] = {0}; //分配的三个页框初始化为0
int i = 0, j = 0;
int m = -1, n = -1;
int max = -1,maxtime = 0;
int count = 0;

for(i = 0; i<pSIZE; i++) //开始循环，在页框中寻找所需资源
{

for(j=0; j<mSIZE; j++) //判断页框中是否满
{
if(memery[j] == 0) //寻找空页框，并且记录页号
{
m = j;
break;
}
}

for(j = 0; j < mSIZE; j++)
{
if(memery[j] == process[i]) //判断页框中是否有进程所需访问的资源
{
n = j;
}
}

for(j = 0; j < mSIZE;j++) //记录在页框中存放最长时间的资源，即第一个进入的资源
{
if(time[j]>maxtime)
{
maxtime = time[j]; //将存放最长时间资源的计数器的值赋给maxtime
max = j;
}
}

if(n == -1) //由于没有在页框中找到所需资源，并且也表已满，发生缺页中断。
{
if(m != -1)
{
memery[m] = process[i]; //没有替换的资源，则它对应的计数器加一
time[m] = 0;
for(j = 0;j <= m; j++)
{
time[j]++;
}
m = -1;
}
else
{
memery[max] = process[i]; //发生缺页中断，从前面的标记中寻找第一个进入页表的资源替换
time[max] = 0; //替换后原来的最长则清0，
for(j = 0;j < mSIZE; j++)
{
time[j]++; //替换后，此资源对应的计数器加一
}
max = -1;
maxtime = 0;
count++;
}
}
else
{
memery[n] = process[i];
for(j = 0;j < mSIZE; j++) //一次分配对所有在页表中的资源的计数器加一
{
time[j]++;
}
n = -1;
}
for(j = 0 ;j < mSIZE; j++)
{
printf("%d ",memery[j]); //输出此次资源访问时页表中资源的情况。
}
printf("\t%d\n",count);
}
}

‘捌’ 如何用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页面置换算法到底是怎么算的呀，先进先出是怎么个先进先出下面这图是怎么算的，这个差又是怎么

fifo就是先进先出，可以想象成队列
lru是最久未使用，当需要替换页面的时候，向前面看，最久没使用的那个被替换
opt是替换页面的时候，优先替换后面最迟出现的。
不懂再问。。