LRU表示Least Recently Used,即最近最少被使用的页面替换算法。其理论基础是局部性原理,也就是说最近被访问的对象将在不久以后再次被访问。
对于LRU算法,可以使用一个链表和hashmap来实现。链表中的节点表示缓存的页面,链表中的第一个元素就是要被替换的元素,所以替换的复杂度是O(1)。同时,还维护一个hashmap来建立访问对象和缓存页面的映射关系。
当需要访问某个对象时,先从hashmap中查看该对象是否在缓存中,如果在,则将该缓存页面从链表中取出并插入到链表尾部,并访问对象。否则,从链表头取出一个缓存页面,将要访问的对象写入该缓存并插入到链表尾部,并且在hashmap中更新该项。这样,所有最近被访问的页面总是处于链表的尾部,即表头的元素表示最近最少被使用的可替换的页面。
LRU的实现
在JDK1.5中,LinkedHashMap已经实现了LRU的功能,只需要根据需要重写removeEldestEntry就行了。LinkedHashMap维护着一个运行于所有条目的双向链表。有了这个双向链表,就可以在迭代的时候按照插入的顺序迭代出元素,或者通过LRU算法迭代元素。
在LinkedHashMap的构造方法中,你可以指定accessOrder参数,当其为true时,将按照LRU算法对entry进行遍历;当其为false时,按照插入的顺序进行遍历。其值默认为true。想要详细了解LinkedHashMap可参见 http://boy00fly.iteye.com/blog/1144691
这里贴一个使用LinkedHashMap实现LRU的线程安全的代码
http://www.iteye.com/topic/123856
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V>
{
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private final Lock lock = new ReentrantLock();
public LRULinkedHashMap(int maxCapacity)
{
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
this.maxCapacity = maxCapacity;
}
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest)
{
return size() > maxCapacity;
}
@Override
public V get(Object key)
{
try {
lock.lock();
return super.get(key);
}
finally {
lock.unlock();
}
}
@Override
public V put(K key, V value)
{
try {
lock.lock();
return super.put(key, value);
}
finally {
lock.unlock();
}
}
}
分享到:
相关推荐
自己写的,虽然比较简单,但已经实现了LRU的思想
用LRU的思想实现缺页中断以及页面置换。C语言实现,按照最近最久未被访问的思想去实现这个算法。输出每一次页面置换之后的过程以及最后的缺页中断次数与缺页中断率。
如何编程思想FIFO和LRU算法,写一个程序来实现本章中介绍的FIFO和LRU页置换算法。首先产生一个随机的页面引用序列,页面数从0~9。将这个序列应用到每个算法并记录发生的页错误的次数。实现这个算法时,要将页帧的...
操作系统课设 分页式存储管理(内含OPT,FIFO,LRU,LFU四种算法,用到了线程),用eclipse打开,我给的是创建的整个源包,打开就可以运行,这个是经过最佳改正过的
LRU实验报告57119101 王晨阳2021年6月8日实验目的实验步骤程序运行结果算法分析实验体会实验目的通过实验,理解LRU页面置换算法的算法思想及其实现方
LRU算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。。这篇文章主要介绍了python实现LRU热点缓存,需要的朋友可以参考下
通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
在此次实训过程中,我先是完成了FIFO、LRU、OPT、Clock四个算法的实现,之后结合Java的Swing图形化界面,将算法融入到图形化界面中,并且可以进行序列长度和运行时间的初始化,紧接着,可以将序列和物理块进行随机...
通过编写和调试请求页式存储管理的模拟程序以加深对请求页式存储管理方案的理解。 为了简单起见。页面淘汰算法采用 FIFO页面淘汰算法,并且在淘汰一页时,判断它是否被改写过,如果被修改过,将它写回到辅存。...
特点是实现简单,但因为与进程实际的运行规律不适应,所以算法效率不高。 LRU算法每次都选择最近最久未使用的页面淘汰,即总是淘汰最后一次访问时间距当前时间间隔最长的页面。该算法的思想依据是根据程序执行时所...
通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。 [实验学时] 4学时 [实验类型] 设计...
了解虚拟存储技术的特点 ,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并 比较它们的效率。 实验内容 1、常用页面置换算法模拟实验 设计一个虚拟存储区和内存工作区,并使用下述算法...
一.实验目的 (1)加深对 Cache的基本概念、基本组织结构以及基本工作原理的理解。 (2)掌握 Cache容量、相联度、块大小对Cache性能的影响。...(4)理解LRU与随机法的基本思想以及它们对Cache性能的影响。
它的核心思想是,如果一个数据被访问过,我们有理由相信它在将来被访问的概率就越高。于是当LRU缓存达到设定的最大值时将缓存中近期最少使用的对象移除。LRUCache内部使用LinkedHashMap来存储key-value键值对,并将...
关于C语言一些简单的实例,里面有些思想值得借鉴 1 一个价值“三天”的BUG 2 灵活使用递增(递减)操作符 3 算术运算符计算器 4 逻辑运算符计算器 5 IP地址解析 6 用if…else语句解决奖金发放问题...
一、Android中的缓存策略 一般来说,缓存策略主要包含缓存的添加、获取和删除这三类操作。...采用LRU算法的缓存有两种:LrhCache和DisLruCache分别用于实现内存缓存和硬盘缓存,其核心思想都是LRU缓存算法。 二、Lru
3.最近最久未使用(LRU)算法:这种算法的基本思想是:利用局部性原理,根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面,在最近的将来可能也不会再被访问。...
Topology拓扑部分 包含一个使用IOC设计思想的控件初始化方式:可通过注解的方式进行UI绑定,与设置监听,在Activity和Fragment中均可以通过一行代码绑定控件并实现点击监听;还包含了在目前应用开发中常见的布局界面...
(要求全部用哈希思想实现!)(选做)(注意:在第四天会进行继续学习) 链表 实现单链表、循环链表、双向链表,支持增删操作 实现单链表反转 实现两个有序的链表合并为一个有序链表 实现求链表的中间结点 Task1 ...
解决方案按关键思想分类。 Python 练习 Python 套接字实现: /socket_multithread 。 Python OO 特性练习: /object_oriented Python 专属特性说明: /python_features 其他一些 Python 代码: /others