lru算法

1. lru 淘汰算法

最佳算法（OPT算法）

当需要淘汰一个内存页面时，这种算法力图选择该进程内存各个页面中永远不再需要的页，若找不到，则选择最久以后才会用到的页。这种算法有最小的缺页率。问题是它需要知道运行进程今后的整个访问踪迹，这往往难以做到，因而它只有理论上的意义。

先进先出算法（FIFO算法）

FIFO算法维护一个先进先出队列，队列长度为分配给这个进程的页面数M。开始时队列是空的，装入进程的第一页即可启动运行，当访问到某个不在内存的页面时，把它从辅存调入，加入FIFO队列的尾部。

最久未使用淘汰算法（LRU算法）

LRU（least recently used）算法维护一个后进先出栈，栈大小为分配给这个进程的页面数M。开始时栈是空的，装入进程的第一页即可启动运行，当访问到某个不在内存的页面时，把它从辅存调入，加入栈顶。

FIFO和LRU算法的例子：http://osjx.8100988.net/LWR/RAM/HLM/FIFOsf.HTM

CLOCK算法

又叫NRU（Not Recently Used）算法，NRU又名近似的LRU置换算法。
当一存储块中的页面访问时，其相应的“页面访问”位由硬件自动置“1”，而由页面管理体制软件周期性地（设周期为T，其值通常为几百毫秒），把所有的页面访问位重新置为“0”。这样，在时间T内，某些被访问的页面，其对应的访问位为“1”而未访问的页面，其对应的访问位为“0”。查寻页面访问位为“0”的页面。在查找过程中，那些被访问的页所对应的访问位被重新置为“0”。由此可见，实际上这种近似LRU算法，已经退化成一种“最近不用”的算法NRU（Not Recently Used）。

CLOCK算法的例子：http://www.cskaoyan.com/thread-4898-1-1.html

其实这个问题我也不太会，去临时查的资料，第一个例子是我自己算的，不知道我理解得对不对；如果有错误的地方还请指正，共同进步~其他的算法的例子我都给了链接，你自己去看吧。

2. C++实现LRU算法

#include<iostream>
using namespace std;
int size;
int *w;

//定义一个动态数组
struct mem
{
int num;
int count;
}memBlock[3]={0,0,0,0,0,0};

void LRU()
{
for( int i = 0; i < size; i++ )
{
int maxCount = memBlock[0].count;
int maxPos = 0;

int j = 0;
bool bFind = false;
for( j = 0; j < 3; j++ )
{
// 标记出count值最大的位置
if( maxCount < memBlock[j].count )
{
maxCount = memBlock[j].count;
maxPos = j;
}

// 将所有的count值都+1
memBlock[j].count++;

// 如果命中，将其count值置为0
if( w[i] == memBlock[j].num )
{
memBlock[j].count = 0;
bFind = true;
}
}

// 未命中，将count最大的拿来替换
if( !bFind )
{
memBlock[maxPos].num = w[i];
memBlock[maxPos].count = 0;
}

for(j = 0; j < 3; j++) //输出
cout << memBlock[j].num << " ";
cout <<" "<< endl;
}
}

int main() //主函数
{
cout<<"请输入需访问的页面数量:"<<endl;
cin>>size;
w = new int[size];
cout<<"请输入需要访问的页面"<<endl;
for(int a=0;a<size;a++)
{
cin>>w[a];//输入数组
}
cout<<endl<<"(LRU)"<<endl;
LRU();
return 0;
}
引用 ： 回答者： floxer | 三级

3. 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次。

4. lru 算法一题

物理页面就是一次能存放的最多页面数，LRU算法是淘汰最久未使用的页面。给你具体的计算过程吧：
顺序：1 2 3 4 5 6 7 8 9 10 11 12
页面：3 5 2 3 4 7 4 9 1 3 8 3
M（5):3 5 2 3 4 7 4 9 1 3 8 3
3 5 2 3 4 7 4 9 1 3 8
3 5 2 3 3 7 4 9 1 1
5 2 2 3 7 4 9 9
5 5 2 3 7 4 4
F： + + + + + + + +
缺页数：8（F为+代表缺页）缺页率：8/12

5. 什么是lru置换算法

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。
LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。
这是一个相当好的算法，它是理想算法很好的近似。

6. lru页面置换算法是什么

用双向链表和哈希表来实现。

LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是着名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。

一种LRU近似算法是最近未使用算法。

它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。

以上内容参考：网络-页面置换算法

7. 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

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

8. 求LRU算法流程图！！！

一行注释没有，懒得看

9. lru的算法是什么

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

对于虚拟页式存储，内外存信息的替换是以页面为单位进行的——当需要一个放在外存的页面时，把它调入内存，同时为了保持原有空间的大小，还要把一个内种调动越少，进程执行的效率也就越高。

硬件支持

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

寄存器

为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为：

R = Rn-1 Rn-2 Rn-3…R2 R1 R0。

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