lru算法实现

㈠ LRU算法解释

看我写的这个,有详细注释
.......................................

#include <stdio.h>
#include <stdlib.h>
#define mSIZE 3//分配三个内存页块
#define pSIZE 12//总共12个进程
struct mem
{
int num;
int count;
}memery[3]={0,-1,0,-1,0,-1};
static int process[pSIZE] ={1,2,3,4,1,2,5,1,2,3,4,5};//页面访问序列
void LRU();
void get();
int main()
{
get();
printf("\n(LRU)\treplace\n");
LRU();
system("PAUSE");
return 0;
}

void 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 LRU()
{
int i = 0, j = 0,k=0,x,y;
int replace;

for(i = 0; i<pSIZE; i++) //对输入序列进行循环
{
x=0;y=0; //置x，y初值为0
for(j = 0; j < mSIZE; j++) //对三个内存块进行循环，先查找有没有与即将访问页号相同的
if(memery[j].num == process[i])
{ x=1;//有相同的则置x为1
replace=process[i];
memery[j].count=0;//置此块count为0
for(k=0;k<3;k++)
if(k!=j&&memery[k].num!=0)memery[k].count++;//其他不为0页count++
break;//跳出此次内存块循环
}

if(x==0)//没有与即将访问页号相同的内存块
{
for(j = 0; j < mSIZE; j++)//对内存块循环，查找有没有空内存块
if(memery[j].num== 0)
{
y=1;//有则置y为1
replace=0;
memery[j].num=process[i];// 置此内存块为访问页号
memery[j].count=0;//置此块count为0
for(k=0;k<3;k++)
if(k!=j&&memery[k].num!=0)memery[k].count++;//其他不为0页count++
break;//跳出此次内存块循环
}
}

if(x==0&&y==0)//既没有与即将访问页号相同的内存块也没有空内存块
{
int m=memery[0].count;
for(j = 0; j < mSIZE; j++)
{
if(memery[j].count>m)
m=memery[j].count;
}//查找出count最大的内存块m
for(j=0;j<mSIZE;j++)//对内存块循环，count=m的内存块
{
if(memery[j].count==m)
{
replace=memery[j].num;
memery[j].num=process[i]; //置此内存块为访问页号块
memery[j].count=0;//置此块count为0
}
else memery[j].count++;//其他块count++
}
}

for(j = 0 ;j < mSIZE; j++) //打印每次访问后的情况
printf("%d ",memery[j].num);
printf("\t%d\n",replace);
}
}

㈡ lru算法是什么

lru算法是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

特点：

LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。

㈢ 给出一种高级语言实现LRU算法和FIFO算法的源程序。

/*
* Created on 2004-12-25
*
* TODO To change the template for this generated file go to
* Window - Preferences - java - Code Style - Code Templates
*/

/**
* @Michelangelo
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/

import java.util.*;
public class TestReplacement {

/**
*
*/
private final int ArraySize=20;
private int digitalArray[]=new int [ArraySize];

//private int digitalArray[]={1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6};

private static final int frameSize[]={1,2,3,4,5,6,7};
private static int errorCount=0;

Vector frame=new Vector();

public TestReplacement() {
super();
// TODO Auto-generated constructor stub
}

public static void main(String[] args) {
TestReplacement aT=new TestReplacement();

aT.generateRandomDigit();
aT.output();

System.out.println("-------------Using FIFO--------------");
System.out.println();
for(int i=0;i<frameSize.length;i++){
System.out.println("Frame size: "+frameSize[i]+"\n");
aT.initFrameForFIFO(frameSize[i]);
aT.FIFOReplace(frameSize[i]);
System.out.println("Total errors found: "+errorCount);
System.out.println("\n************************************\n");

errorCount=0;
}
System.out.println();
System.out.println("----------------Using LRU----------------");
System.out.println();
for(int i=0;i<frameSize.length;i++){
System.out.println("Frame size: "+frameSize[i]+"\n");
aT.initFrameForLRU(frameSize[i]);
aT.LRUReplace(frameSize[i]);
System.out.println("Total errors found: "+errorCount);
System.out.println("\n************************************\n");
errorCount=0;
}
}

public void generateRandomDigit(){
for(int i=0;i<ArraySize;i++){
digitalArray[i]=(int)Math.round(Math.random()*9);
}
}

public void output(){
System.out.println("随机序列：");
for(int i=0;i<ArraySize;i++){
System.out.print(" "+digitalArray[i]);
}
System.out.println();
}

public void initFrameForFIFO(int fS){
frame.removeAllElements();
for(int i=0;i<fS;i++){
frame.addElement(new Couple(fS-i));
}
}
public void initFrameForLRU(int fS){
frame.removeAllElements();
for(int i=0;i<fS;i++){
frame.addElement(new Couple(0));
}
}

public void LRUReplace(int fS){
boolean findThesame=false;
int pre=-1;//存放刚刚查找到的位置
int flag=-1;

for(int j=0;j<digitalArray.length;j++){
boolean match=false;
for(int i=0;i<fS;i++){

if(((Couple)frame.elementAt(i)).value==digitalArray[j]){
((Couple)frame.elementAt(i)).time=0;
match=true;//是否找到匹配
System.out.println(j+": find "+((Couple)frame.elementAt(i)).value+" "+"at location "+i);
System.out.println();

flag=i;
break;
}
}

if(match==true&&flag!=pre){
for(int i=0;i<fS;i++){
if(i!=flag){
((Couple)frame.elementAt(i)).time--;
}
}
pre=flag;
}
else if(match==false){
int temp=0;
int index=0;
for(int i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).time<temp){
temp=((Couple)frame.elementAt(i)).time;
index=i;
}
}
for(int i=0;i<fS;i++){
if(i!=index){
((Couple)frame.elementAt(i)).time--;
}
else{
((Couple)frame.elementAt(i)).time=0;
System.out.print(j+": replace "+((Couple)frame.elementAt(i)).value+" ");
System.out.print("at location "+index+" ");
((Couple)frame.elementAt(i)).value=digitalArray[j];
System.out.println("with "+((Couple)frame.elementAt(i)).value);
errorCount++;
System.out.println("error count "+errorCount);
System.out.println();
}
}
}
}
}
public void FIFOReplace(int fS){
//boolean blank=true;//是否开始的已填充完
int i=0;
for(int j=0;j<digitalArray.length;j++){
boolean match=false;
for(i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).value==digitalArray[j]){
match=true;//是否找到匹配
System.out.println(j+": find "+((Couple)frame.elementAt(i)).value+" "+"at location "+i);
break;
}
}
if(match==false){
int temp=0;
int index=-1;
for(i=0;i<fS;i++){
if(((Couple)frame.elementAt(i)).time>temp){
temp=((Couple)frame.elementAt(i)).time;
index=i;
}
}
for(i=0;i<fS;i++){
if(i==index){
System.out.print(j+": replace "+((Couple)frame.elementAt(i)).value+" ");
System.out.print("at location "+i+" ");
((Couple)frame.elementAt(i)).value=digitalArray[j];
System.out.println("with "+((Couple)frame.elementAt(i)).value);
((Couple)frame.elementAt(i)).time=1;
errorCount++;
System.out.println("error count "+errorCount);
System.out.println();
}

else{
((Couple)frame.elementAt(i)).time++;
}

}
}

}
}

}

class Couple{
public int value=-1;
public int time=-1;
public Couple(int t){
time=t;
}
}

算法思想：用Vector来模拟页表，而扔进去的Couple的个数就是表的大小。Couple 中的Time设置衰老时间（FIFO）或未使用周期（LRU），Value为请求序列中digitalArray[]的值。序列长为20由随机函数产生的0-9的整型值。frameSize[]中存放的是页表的大小（也就是对应着扔几个Couple进去啦）

FIFO：初始化时先清空然后放Couple，将他们的Time属性按放的顺序分别置为frameSize,frame-1,frame-2.......1.数值越大放的越早,value通通置-1。接下来的工作就是对value和time的处置。若在vector中的couple的value里找到了value匹配则pass。如果没有找的话就从中time里找最老的，（谁的time最大就最老），找到后把它的value变成相应的请求的页面值，把它的time=1.对于不是最老的呢，就把他们的岁数都加一吧。

LRU:初始化时先清空然后放Couple,将他们的Time属性置-1，value通通置-1。接下来处理请求序列了。若在value里找到对应的页面话就把对应的Time置0。其他的Couple对应的time- -。如果没有找到的话就找一个最近使用的最少的啦（就是对应的time最负的那个），找到以后就把它的Value换成请求的页面值并且把它的time置0.与此同时，其他的time--。

㈣ LRU页面置换算法的实现

我会。就是最近未使用的算法吧。例如一个三道程序，等待进入的是1，2，3，4，4，2，5，6，3，4，2，1。先分别把1，2，3导入，然后导入4，置换的是1，因为他离导入时间最远。然后又是4，不需要置换，然后是2，也不需要，因为内存中有，到5的时候，因为3最远，所以置换3，依次类推，还有不懂联系我吧。QQ：243926566

㈤ 用java语言实现LRU算法和FIFO算法。急急急！！！！！！！

您好，网络贴吧专家团很高兴能够回答您的问题。您的采纳是我们前进的动力。
public class LRU {

private int theArray[];
private int back; //定义队尾
private int currentSize; //队列中存放元素个数
private int maxSize=5; //队列中能存放元素的个数

public LRU(){
theArray=new int[maxSize];
back=0;
currentSize=0;
}
public void queue(int a[]){
for(int i=0;i<a.length;i++){
enQueue(a[i]);
}
}

public void enQueue(int x){ //入队
beUsed(x); //先判断是否已存在该页号，若存在，删除
if(currentSize<maxSize){
theArray[back]=x;
back++;
currentSize++;
}else if(currentSize==maxSize){ //满了
for(int i=0;i<maxSize-1;i++){
theArray[i]=theArray[i+1];
}
theArray[maxSize-1]=x;
}
for(int i=0;i<currentSize;i++){
System.out.print(theArray[i]);
}
System.out.println();
}
public void beUsed(int x){ //判断是否已存在该页号,若存在，删除已有的
for(int i=0;i<currentSize;i++){
if(theArray[i]==x){
for(int j=i;j<currentSize-1;j++){
theArray[j]=theArray[j+1];
}
currentSize--;
back--;
}
}
}
public static void main(String[] args) {
LRU lru=new LRU();
int a[]={4,7,0,7,1,0,1,2,1,2,6};
lru.queue(a);
}

}

㈥ 求LRU算法流程图！！！

一行注释没有，懒得看

㈦ 实现LRU算法的硬件支持是什么

寄存器、栈

实现LRU算法的硬件支持是寄存器、栈。寄存器用于记录某进程在内存中各页的使用情况；栈用于保存当前使用的各个页面的页面号。LRU是最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。寄存器的功能是存储二进制代码，它是由具有存储功能的触发器组合起来构成的。一个触发器可以存储1位二进制代码，故存放n位二进制代码的寄存器，需用n个触发器来构成。

(7)lru算法实现扩展阅读：

大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法是LRU算法。该算法的思路是，发生缺页中断时，选择未使用时间最长的页面置换出去。从程序运行的原理来看，最近最少使用算法是比较接近理想的一种页面置换算法，这种算法既充分利用了内存中页面调用的历史信息，又正确反映了程序的局部问题。

㈧ 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 1 3（原理同上）
最后 2调入内存 2 4 1

过程就是这样的，楼主只要明白最近最久未使用这个道理，再回去参考书上的例子就明白是怎么算的啦！呵呵！

㈨ LRu算法具体步骤

内存已有页面 需要页面 操作 内存结果页面 页面是否失效
1 加入内存 1 否
8 加入内存 18 否
1 18 否
7 加入内存 718 否
8 871 否
2 加入内存 2871 否
7 7281 否
2 2781 否
1 1278 否
8 8127 否
3 换出7 3812 是
8 8312 否
2 2831 否
1 1283 否
3 3128 否
1 1328 否
7 换出8 7132 是
1 1732 否
3 3172 否
7 7312 否

页面失效2次。

㈩ lru缓存算法用什么数据结构实现

1、请求分页的页表机制，他是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构。 2、缺页中断机构，即每当用户程序要访问的页面尚未调入时，便产生一缺页中断，以请求OS将所缺的页调入内存。 3、地址变换机构，他同样是在纯分页