fifo算法

1. 关于先进先出（FIFO）页面淘汰算法

输入：1，2，3，4，1，2，5，1，2，3，4，5

先进先出，就是保存最近3个访问的记录在内存中
, , <—1 中断1次
, ,1<—2 中断1次
, 1,2<—3 中断1次
1,2,3 <—4 中断1次
2,3,4 <—1 中断1次
3,4 ,1<—2 中断1次
4,1,2<—5 中断1次
1,2,5<—1 命中，不中断
2,5,1 <—2 命中，不中断
5,1,2<—3 中断1次
1,2,3 <—4 中断1次
2,3,4 <—5 中断1次
3,4,5

累计中断12次

2. 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);
}
}

3. LRU和FIFO算法计算缺页次数(急)

没分
LRU：9次

4. 先进先出置换算法，（fifo）

的确是书错了

5. 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;
}

6. 请大佬帮忙讲解一下这个FIFO算法和LRU算法 跪求(T^T)

注意：

1. 书上的表示方法不能很好的表示LRU的思想，所以我们都采用上图的画图方法

2. 对于前三个是否算做缺页这个不同的教材有不同的说法，要具体看题目说明
   

7. 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次缺页

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

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

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

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

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

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

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

(8)fifo算法扩展阅读

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

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

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

9. fifo算法适用于什么场合又有何缺点

适用于:按线性顺序访问的地址空间
缺点:可能抖动，会发生Belady异常

10. FIFO调度算法和LRU算法

FIFO：先进先出调度算法
LRU：最近最久未使用调度算法

两者都是缓存调度算法，经常用作内存的页面置换算法。

打一个比方，帮助你理解。

你有很多的书，比如说10000本。
由于你的书实在太多了，你只能放在地下室里面。
你看书的时候不会在地下室看书，而是在书房看书。
每次，你想看书都必须跑到地下室去找出来你想看的书，
然后抱回来放到书桌上，之后才开始看。
还有就是，有一些书你会反复的看，今天看了也许过几天又要看。
总之，你自己是不知道你哪天会需要看哪本书的。
你的老师每天下课的时候会给你布置一个书单，让你晚上回去去看哪本书。
（假设你老师让你看的书在你的地下室里面都有）

跑地下室当然是非常麻烦的，所以你希望你的经常看的那些书最好放在书桌上。
但是你的书房的书桌同时只能摆放10本书（这个是假设的啊）。
那么，问题来了。
到底把哪些说留在书桌上最好呢？
这里说的最好，就是说你尽量少的跑地下室去找书。

为了解决这个问题，人们发明了很多的算法。
其中，比较常见的就是上面这两种：FIFO算法和LRU算法。

FIFO算法
很简单，我把书桌上的10本书按照放置时间先后堆放成一堆。
这里的放置时间，就是说这本书在我的书桌上放了几天了。
每次要看书的时候，我先在书桌上找，找到就直接可以读了。
读完之后放回原来的位置就可以，不打乱顺序。
如果书桌上面没有我要读的书，就去地下室找。
找来之后，我就把书桌上放的时间最长的那本（也就是
书堆里面最下面的那本书）放回地下室。
然后把我今天需要看的这本书放在书堆的最上面。

LRU算法
也不难，我把书桌上的10本书按照阅读时间先后堆放成一堆。
这里的阅读时间，就是说我最近一次读这本书是几天之前。
每次要看书的时候，我先在书桌上找，找到就直接可以读了。
读完之后放在书堆的最上面。
如果书桌上面没有我要读的书，就去地下室找。
找来之后，我就把书桌上最久没有阅读的那本
（也就是书堆里面最下面的那本书）放回地下室。
然后把我今天需要看的这本书放在书堆的最上面。

上面这个比方，相信你可以看明白吧。
这里的地下室对应内存，书桌对应缓存，书对应页面。