什么是lru置换算法_百度知道
什么是lru置换算法
我有更好的答案
LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。这就是LRU算法的全部内容。这是一个相当好的算法，它是理想算法很好的近似。
采纳率：58%
为您推荐：
其他类似问题
lru的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。博客分类：
在操作系统的内存管理里，如何节省有限的内存并为尽可能多的进程提供资源是一个很重要的问题。
内存的虚拟存储管理
，是现在最通用，最成功的方式——在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。
然而，有利就有弊，虚拟页式存储管理减少了进程所需的内存空间，却也带来了运行时间变长这一缺点：进程运行过程中，不可避免地要把在外存中存放的一些信息和内存中已有的进行交换，由于外存的低速，这一步骤所花费的时间不可忽略。解决的办法：采取尽量好的算法以减少读取外存的次数（进程所需的页基本上命中在主存中）
LRU算法思想
达到这样一种情形的算法是最理想的——每次调换出的页面是所有内存页面中最迟将被使用的——这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。
为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到
。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存
LRU实现思路
页表中每一页（cache中每个对象）增加一个域（or属性）”新鲜度量时间“，每次根据”
新鲜度量时间 “最长的规则来选择”出局“候选人，然后将新的页放入主存中，并设置其”
新鲜度量时间 “为0。每个页的”
新鲜度量时间 “根据其加入主存的时间和选择操作发生时的时间来确定。如果hit主存中某页，则设置
以上两个方法仅仅考虑使用标识来进行算法判断，每次存取都要对所有页进行计算和判断。没有考虑选择一个合适的数据结构。
其他相关算法
LRU算法算是一种集合元素选择算法（or置换选择算法）
，处理同样问题的算法还有FIFO，NRU等。
浏览: 199014 次
来自: 北京
分析查询结果的打分小于11.query=* ...
query=.013709 = (MA ...
query=.6772446 = (MA ...
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'FIFO调度算法和LRU算法_百度知道
FIFO调度算法和LRU算法
我有更好的答案
FIFO：先进先出调度算法LRU：最近最久未使用调度算法两者都是缓存调度算法，经常用作内存的页面置换算法。打一个比方，帮助你理解。你有很多的书，比如说10000本。由于你的书实在太多了，你只能放在地下室里面。你看书的时候不会在地下室看书，而是在书房看书。每次，你想看书都必须跑到地下室去找出来你想看的书，然后抱回来放到书桌上，之后才开始看。还有就是，有一些书你会反复的看，今天看了也许过几天又要看。总之，你自己是不知道你哪天会需要看哪本书的。你的老师每天下课的时候会给你布置一个书单，让你晚上回去去看哪本书。（假设你老师让你看的书在你的地下室里面都有）跑地下室当然是非常麻烦的，所以你希望你的经常看的那些书最好放在书桌上。但是你的书房的书桌同时只能摆放10本书（这个是假设的啊）。那么，问题来了。到底把哪些说留在书桌上最好呢？这里说的最好，就是说你尽量少的跑地下室去找书。为了解决这个问题，人们发明了很多的算法。其中，比较常见的就是上面这两种：FIFO算法和LRU算法。FIFO算法很简单，我把书桌上的10本书按照放置时间先后堆放成一堆。这里的放置时间，就是说这本书在我的书桌上放了几天了。每次要看书的时候，我先在书桌上找，找到就直接可以读了。读完之后放回原来的位置就可以，不打乱顺序。如果书桌上面没有我要读的书，就去地下室找。找来之后，我就把书桌上放的时间最长的那本（也就是书堆里面最下面的那本书）放回地下室。然后把我今天需要看的这本书放在书堆的最上面。LRU算法也不难，我把书桌上的10本书按照阅读时间先后堆放成一堆。这里的阅读时间，就是说我最近一次读这本书是几天之前。每次要看书的时候，我先在书桌上找，找到就直接可以读了。读完之后放在书堆的最上面。如果书桌上面没有我要读的书，就去地下室找。找来之后，我就把书桌上最久没有阅读的那本（也就是书堆里面最下面的那本书）放回地下室。然后把我今天需要看的这本书放在书堆的最上面。上面这个比方，相信你可以看明白吧。这里的地下室对应内存，书桌对应缓存，书对应页面。
采纳率：62%
内存管理的页面置换算法：FIFO 先进先出算法
最先加载到内存的最先被置换出去LRU 最近自己少用算法
最近最少被访问的最先被置换出去
这个不懂。
1条折叠回答
为您推荐：
其他类似问题
调度算法的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。一道LeetCode OJ上的题目，要求设计一个LRU（Least Recently Used）算法，题目描述如下：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
花了一个上午的时间来做这道题，终于Accepted了。感觉这道题出的非常好，做完这道题，对LRU算法的理解就不只局限在理论上了。LRU算法是一种cache置换算法，当cache容量不够时，将最久未使用的条目置换出去，换入新的当前需要使用的条目。
既然是设计题，那么首先就要确定数据结构。如何快速定位某条记录是否位于cache中，可以使用map，map的内部机制是一颗红黑树，时间复杂度为O(logn)，但是我使用了另一个结构&&unordered_map，这个关联容器是C++11中新加入的，利用hash函数进行定位，时间复杂度为O(1)。将unordered_map初始化为unordered_map&key, value&，就能快速读写某个key对应的记录了。下面考虑如何实现LRU的相关算法。既然每次要淘汰最久未使用的记录，那么可以使用一个优先队列，队列开头存放最久未使用的记录，队列结尾存放最近刚刚被使用（读或写）过的记录。当需要换出记录时，选择优先队列开头的元素即可；当读、写完某条记录后，需要将该记录放到优先队列末尾，这里分两种情况：
Cache中存在这条记录，则将记录移动到队列尾部。
Cache中不存在这条记录，则将记录加入到队列尾部。
那么问题来了，用C++中的什么结构充当这个优先队列呢？STL中的queue和priority_queue肯定不行，因为这两个数据结构只有两端开放，无法遍历内部元素，这对于上面的情况1是不适用的。刚开始我想到了使用vector，使用完某个记录后就在vector中线性查找该记录，然后将它移动到vector末尾。这种操作的效率是O(n)，提交后系统出现了&Time Limit Exceeded&的错误，看来光有线性时间复杂度是不行的。后来想到了list，在list上移动一个节点只需要常数时间，我将list中的每一个节点关联到unordered_map的value成员上，也就是unordered_map&key, node*&。这样一来，查找某条记录、修改优先队列这两个操作都只需要常数时间。说起来有一点拗口，代码表达的意思更加直白，整个代码如下所示：
* https://oj.leetcode.com/problems/lru-cache/
#include &iostream&
#include &vector&
#include &unordered_map&
using namespace
class Node {
Node(int k, int v) : key(k), value(v), prev(NULL), next(NULL)
class LinkList {
LinkList(int c) : capacity(c), size(0)
first = new Node(0, 0);
last = new Node(0, 0);
first-&next =
last-&prev =
class LRUCache{
LRUCache(int capacity) : PriorityLink(capacity)
int get(int key)
if (mp.find(key) != mp.end())
Node *pNode = mp[key];
if (pNode-&next != PriorityLink.last)
unlink(pNode);
link(pNode);
return pNode-&
return -1;
void set(int key, int value)
if (mp.find(key) != mp.end())
Node *pNode = mp[key];
pNode-&value =
if (pNode-&next != PriorityLink.last)
unlink(pNode);
link(pNode);
if (PriorityLink.size == PriorityLink.capacity)
Node *remove = PriorityLink.first-&
unlink(remove);
mp.erase(remove-&key);
PriorityLink.size++;
Node *add = new Node(key, value);
link(add);
void link(Node *pNode)
// put node to back of PriorityLink
pNode-&prev = PriorityLink.last-&
pNode-&next = PriorityLink.
PriorityLink.last-&prev = pN
pNode-&prev-&next = pN
void unlink(Node *pNode)
pNode-&prev-&next = pNode-&
pNode-&next-&prev = pNode-&
pNode-&prev = NULL;
pNode-&next = NULL;
LinkList PriorityL
unordered_map&int, Node*&
int main()
LRUCache mem(2);
mem.set(2, 1);
mem.set(3, 2);
cout && mem.get(3);
cout && mem.get(2);
mem.set(4, 3);
//mem.set(4, 1);
cout && mem.get(2);
cout && mem.get(3);
cout && mem.get(4);
system("pause");
阅读(...) 评论()1.概念分析
& & & &LRU(Least Recently Used),即最近最少使用.怎么理解这个概念呢?我一开始见到这个概念的时候,以为"最近","最少"都是修饰使用的(从中文解释中可以看出),不过这种理解是错误的,最近是修饰最少的,故应该理解为"最近这段时间最少访问的,最少使用".
& & & 这样理解是不是更清晰一些呢?也就是说,LRU这种算法是会将近期最少使用的数据淘汰掉.这样说的话,LRU淘汰算法似乎是将最近次数上使用最少的数据淘汰[1],其实不然,或者说理解的不确切,更准确地说,LRU算法是将近期最不会访问的数据淘汰掉[2](请注意[1]和[2]的不同,[1]处注重了次数上的比较,[2]处却没有这层意义).它的核心思想是"如果数据最近被访问过,那么将来被访问的概率也很高".反过来说,"如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低".Well,我知道这两句都是伪命题,就好像说一个人最近一直倒霉,那么他一辈子都会倒霉.不过,LRU就是基于这种思想来的.如果一个指导思想本身就有很多问题,那么在指导现实行为时就更加荒唐了(似乎有点形而上学的意味了...).
& & & 因此,我们在这里可以说,LRU是荒唐的,是简单粗暴的,是片面的.打住,似乎变成了LRU的批斗会了.
& & & --那么LRU就一无是处了?
& & & --不是的.LRU算法的优点在于简单,而且也可以解决一些实际问题.只不过没那么精确而已,很多时候LRU算法也会有不少冤假错案,本来不该剔除的数据就白白的牺牲掉了.但是我们还是要正式LRU的优点.
& & & 下面就讲解LRU的算法实现.
我画了一个LRU淘汰算法的过程图:
&下面简单讲解一下(需要在这里说明一下,LRU一般采用链表方式实现,便于快速移动数据位置,虽然图中使用似乎是数组方式):
一开始,缓存池是空的,缓存池中插入数据时不用担心容量不足的事情.因此这个过程就是类似队列的FIFO(但不止这些);
在第5步将E插入到缓存池中后,缓存池已经满了(当然实际应用中不会让到达缓存池的尺寸,一般到70%左右就要考虑淘汰机制了);
当第6步将E插入缓存池的时候,发现缓存池已经满了,LRU会将最早加入到缓存池的数据淘汰掉(A,实在不要意思啊);
第7步,从缓存池中访问C,C被访问,从时间点上是最近最近访问的,将C移动到链表的头部(C侥幸暂时远离被淘汰的边缘);
第8步,将G插入缓存池中,G处于链表头部,B不幸被淘汰.
大致的过程就是这样,关于淘汰机制只是后面的三步中会用到,画出前面六步的过程只是说明,LRU插入元素的方式.在这个图中,我想大家应该可以明白为什么使用链表,而不使用数组(链表的插入和删除的时间复杂度都是O(1)).
3.优劣分析
&【命中率】
命中率较高,不过偶发性的情况对LRU的命中影响很大,同时也会引入很多数据污染(比如很长时间只访问一次的数据,在后期的文章中会涉及到这一话题,会有改进的方案).
&【复杂度】
实现起来较为简单.
&【存储成本】
几乎没有空间上浪费.
仅仅从最近使用时间上考虑淘汰算法,没有考虑缓存单元的使用频率,可能会淘汰一些仍有价值的单元.
暂时略,以后会采用伪代码和java语言的方式做简单的实现.
最后,如有哪里不正确的地方,请多多指教. 后续会将其他缓存淘汰算法一一介绍,敬请期待.
&相关文章:
阅读(...) 评论()}