lfu页面置换算法java代码

1. java程序设计

I am sorry; in China; please speak Chinese;谢谢；我之所以写了句英语只是因为担心你是外国人；哎；

2. [求助]LFU页面置换算法

least frequently used (LFU)，要求在页置换时置换引用计数最小的页。
3，2，1
0进入时，缺页。置换最近最小的1。内存：3，2，0
3，2
4进入时，缺页。置换最近最小的0。内存：3，2，4
3，2
1进入时，缺页。置换最近最小的4。内存：3，2，1
0进入时，缺页。置换最近最小的1。内存：3，2，0
4进入时，缺页。置换最近最小的0。内存：3，2，4

3. 内存页面置换算法代码

没有仔细看，但发现了一个很容易发生的错误，即函数参数的传递问题。
Init()的最后一句insert(node,head),因为C语言里函数参数采用值传递，那么insert函数执行前head为NULL，执行时，程序会生成一个临时的值为NULL的指针变量作为参数来处理,函数执行完后,head仍为NULL，没有任何改变。因此，就算循环执行了20次，head仍为NULL.

4. 页面置换算法的操作系统页面置换算法代码

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> #define TRUE 1
#define FALSE 0
#define INVALID -1
#define NUL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清零周期*/
typedef struct{ /*页面结构*/
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*页面结构数组*/
struct pfc_struct{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect,a[total_instruction];
int page[total_instruction], offset[total_instruction];
void initialize(int);
void FIFO(int);
void LRU(int);
void NUR(int);
int main()
{
int S,i;
srand((int)getpid());
S=(int)rand()%390;
for(i=0;i<total_instruction;i+=1) /*产生指令队列*/
{
a[i]=S; /*任选一指令访问点*/
a[i+1]=a[i]+1; /*顺序执行一条指令*/
a[i+2]=(int)rand()%390; /*执行前地址指令m’*/
a[i+3]=a[i+2]+1; /*执行后地址指令*/
S=(int)rand()%390;
}
for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf(%2d page frames,i);
FIFO(i);
LRU(i);
NUR(i);
printf( );
}
return 0;
}
void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*/
/*用户进程的内存页面数*/
{
int i;
pfc_type *p, *t;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NUL) /*无空33闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/
freepf_head=busypf_head;
freepf_head->next=NUL;
busypf_head=p;
}
p=freepf_head->next; /*按方式调新页面入内存页面*/
freepf_head->next=NUL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NUL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf(FIFO:%6.4F,1-(float)diseffect/320);
}
void LRU(int total_pf)
{
int min,minj,i,j,present_time;
initialize(total_pf);present_time=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲2页面*/
{
min=32767;
for(j=0;j<total_vp;j++)
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
freepf_head=&pfc[pl[minj].pfn];
pl[minj].pfn=INVALID;
pl[minj].time=-1;
freepf_head->next=NUL;
}
pl[page[i]].pfn=freepf_head->pfn;
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page[i]].time=present_time;
present_time++;
}
printf(LRU:%6.4f,1-(float)diseffect/320);
}
void NUR(int total_pf)
{
int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NUL) /*无空闲1页面*/
{
cont_flag=TRUE;old_dp=dp;
while(cont_flag)
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if(dp==total_vp)
dp=0;
if(dp==old_dp)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NUL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf(NUR:%6.4f,1-(float)diseffect/320);
}
void initialize(int total_pf) /*初始化相关数据结构*/
/*用户进程的内存页面数*/
{
int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/
}
for(i=1;i<total_pf;i++)
{
pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之间的连接*/
}
pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/
}
/*说明：本程序在Linux的gcc下和c-free下编译运行通过*/

5. 一个程序的页面走向，FIFO和LRU页面置换算法

FIFO(先进先出页面置换算法)：
1 2 3 4 1 2 5 1 2 3 4 5
————————————
1 1 1 1 1 1 2 3 4 5 1 2
2 2 2 2 2 3 4 5 1 2 3
3 3 3 3 4 5 1 2 3 4
4 4 4 5 1 2 3 4 5
X X X X X X X X X X
共10次缺页中断

LRU（最近最少使用页面置换算法）：
1 2 3 4 1 2 5 1 2 3 4 5
————————————
1 1 1 1 2 3 4 4 4 5 1 2
2 2 2 3 4 1 2 5 1 2 3
3 3 4 1 2 5 1 2 3 4
4 1 2 5 1 2 3 4 5
X X X X X X X X

共八次缺页中断

6. 页面置换算法之LRU算法

三种常见的页面置换算法:FIFO、LFU、LRU
参考：
缓存算法（页面置换算法）-FIFO、LFU、LRU

LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是： 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1

如果让我们设计一个LRU Cache的数据结构，它应该支持两个操作：

一种是采用数组来存储每个数据项，再对每个key关联一个时间戳，在cache中维护一个最大时间戳，其设计要点如下：

另一种是采用hashmap+双向链表的数据结构，其设计要点如下：

对比上一节的两种设计思路，不难发现，设计1需要为每个key维护一个时间戳，而且set和get操作的时间复杂度都是O(n)。显而易见，随着数据量的增大，set和get操作的速度越来越慢。而设计2通过采用hashmap+双向链表，set和get操作的时间复杂度只需O(1)，下面给出设计2的具体实现。

运行结果为：

参考：
LRU Cache
LRU原理和Redis实现——一个今日头条的面试题

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

8. 如何用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)