marshan
- 浏览: 485740 次
- 性别:
- 来自: 北京
-
文章分类
- 全部博客 (250)
- concurrent (11)
- io (1)
- CI (10)
- linux (57)
- windows (2)
- java (38)
- mac (4)
- eclipse (9)
- db (13)
- python (5)
- groovy (5)
- flex (7)
- hibernate (5)
- odb (8)
- netbeans (1)
- web (31)
- book (14)
- erlang (2)
- communication (2)
- virtualization (5)
- jUnit (0)
- jsf (1)
- perl (1)
- java jax-rs (5)
- Jenkins (2)
- Jenkins Plugin (3)
- android (2)
- git (1)
- big data (0)
- 试读 (1)
最新评论
-
yzzy4793：
讲的很清楚，明白
同步synchronized方法和代码块 -
aa51513：
中文乱码式硬伤
Jersey2.x对REST请求处理流程的分析 -
feiwomoshu1991：
...
同步synchronized方法和代码块 -
marshan：
启动失败的原因是加载的类版本冲突，因此你首先要保证依赖的版本和 ...
richfaces中facelet版本升级到2时的典型错误和解决办法 -
zhaohang6688：
请问我按照你的方式修改还是报错 错误信息还是这个 是为什么啊 ...
richfaces中facelet版本升级到2时的典型错误和解决办法
LinkedHashMap是一个现成的LRU实现。但其缺乏并发机制，并且没有实现满载删除条件(removeEldestEntry)，因此本文认为LinkedHashMap是预留扩展的LRU类。
本文将继承该类进一步实现LRU缓存。
首先，并发使用可重入锁。对于封读锁后是否可写，封写锁后是否可读的问题，这是一个封锁策略。一般而言，读后，若写，会产生脏数据。写后，若读则没有问题。
可重入锁之读写锁，封锁顺序测试：
package lock;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LockTest1{
final static ReadWriteLock rwlock = new ReentrantReadWriteLock();
final static Lock readLock = rwlock.readLock();
final static Lock writeLock = rwlock.writeLock();
public static void main(String[] args) throws InterruptedException {
System.out.println("test readlock-writelock");
lockR2W();
System.out.println("test writelock-readlock");
lockW2R();
System.out.println("test readlock-readlock");
lockRR();
System.out.println("test writelock-writelock");
lockWW();
}
private static void lockWW() {
writeLock.lock();
System.out.println("w lock.");
try {
if (writeLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("w lock.");
else
System.out.println("when w lock, cannot w lock again.");
} catch (InterruptedException e0) {
e0.printStackTrace();
}
try {
writeLock.unlock();
System.out.println("w unlock.");
writeLock.unlock();
System.out.println("w unlock.");
} catch (Exception e) {
//ignore;
}
}
private static void lockRR() {
readLock.lock();
System.out.println("r lock.");
readLock.lock();
System.out.println("r lock.");
readLock.unlock();
System.out.println("r unlock.");
readLock.unlock();
System.out.println("r unlock.");
}
private static void lockW2R() throws InterruptedException {
writeLock.lock();
System.out.println("w lock.");
if (readLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("r lock.");
else
System.out.println("when w lock, cannot r lock.");
writeLock.unlock();
System.out.println("w unlock.");
readLock.unlock();
System.out.println("r unlock.");
}
private static void lockR2W() {
readLock.lock();
System.out.println("r lock.");
try {
if (writeLock.tryLock(1, TimeUnit.SECONDS))
System.out.println("w lock.");
else
System.out.println("when r lock, cannot w lock.");
} catch (InterruptedException e0) {
e0.printStackTrace();
}
try {
readLock.unlock();
System.out.println("r unlock.");
writeLock.unlock();
System.out.println("w unlock.");
} catch (Exception e) {
//ignore;
}
}
}
测试结果：
test readlock-writelock r lock. when r lock, cannot w lock. r unlock. test writelock-readlock w lock. r lock. w unlock. r unlock. test readlock-readlock r lock. r lock. r unlock. r unlock. test writelock-writelock w lock. w lock. w unlock. w unlock.
LRU的意义在于最近被访问的数据总是可以最快从缓存中读取到。因此，下面要测试最新数据的位置和缓存已满时数据的处理。
package lru;
import java.util.Iterator;
import java.util.Map.Entry;
public class LRUTest{
public static void main(String[] args) {
int maxCapacity = 5;
OjadbMap<Integer, String> lruMap = new OjadbMap<Integer, String>(maxCapacity);
for (int i = 0; i < maxCapacity; i++) {
lruMap.put(i, "data[" + i + "]");
}
lruMap.get(3);
Iterator<Entry<Integer, String>> iter = lruMap.entrySet().iterator();
while (iter.hasNext()) {
System.out.println(iter.next().getValue());
}
System.out.println();
lruMap.put(9, "data[ 9 ]");
Iterator<Entry<Integer, String>> iter1 = lruMap.entrySet().iterator();
while (iter1.hasNext()) {
System.out.println(iter1.next().getValue());
}
}
}
测试结果：
data[0] data[1] data[2] data[4] data[3] //最近访问的数据在队尾。 data[1] data[2] data[4] data[3] data[ 9 ] //最新访问的数据插入队尾(若队满，最老的数据被移除)。
本文使用的LRU缓存类：
(参考：这个类是我的一个开源数据库项目中，缓存部分的实现类。
你可以通过访问http://code.google.com/p/ojadb 查看整个项目)
/*******************************************************************************************
* oJadb is free software: you can redistribute it and/or modify it under
* the terms of the GNU General Public License as published by the Free Software Foundation,
* either version 3 of the License, or (at your option) any later version.
*
* oJadb is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY;
* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along with this library.
* If not, see <http://www.gnu.org/licenses/>.
*
* Author:EricHan
* Time:2008-8-28
******************************************************************************************/
package lru;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class OjadbMap<K, V> extends LinkedHashMap<K, V>{
private static final long serialVersionUID = -6970580442519842034L;
private final int maxCapacity;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
//private final Lock lock = new ReentrantLock();
private final ReadWriteLock rwlock = new ReentrantReadWriteLock();
private final Lock readLock = rwlock.readLock();
private final Lock writeLock = rwlock.writeLock();
public OjadbMap(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 boolean containsKey(Object key) {
try {
readLock.lock();
return super.containsKey(key);
} finally {
readLock.unlock();
}
}
@Override
public V get(Object key) {
try {
readLock.lock();
return super.get(key);
} finally {
readLock.unlock();
}
}
@Override
public V put(K key, V value) {
try {
writeLock.lock();
return super.put(key, value);
} finally {
writeLock.unlock();
}
}
public int size() {
try {
readLock.lock();
return super.size();
} finally {
readLock.unlock();
}
}
public void clear() {
try {
writeLock.lock();
super.clear();
} finally {
writeLock.unlock();
}
}
public Collection<Map.Entry<K, V>> getAll() {
try {
readLock.lock();
return new ArrayList<Map.Entry<K, V>>(super.entrySet());
} finally {
readLock.unlock();
}
}
}
分享到：
评论
31 楼
yiyidog125
2010-10-20
想问下为什么要用linkedHashMap 用这个的话每次都是O(n)的操作吧
对一个经常要更新的LRU好吗？
对一个经常要更新的LRU好吗？
30 楼
sdh5724
2010-09-03
在线程安全上， 总是有人以为极低概率是的事件是不会发生的。 事实证明， 只要有一个口子做不好， 总是会有机会发生。
29 楼
mht19840918
2010-08-31
有时间看以看看jcs下的LRUMap。这个是速度最快的。
28 楼
火星来客
2009-12-10
火星来客 写道
OK，感谢二位！如果可能，请给出重入读锁的失败例子。
多线程操作链表，带来的结果是链表中的顺序。。。。。。乱啊，可能和我们预期的效果完全不同，同步比较保险
27 楼
jiabiao011
2009-12-10
请好好看看LinkHashMap的说明
26 楼
mikeandmore
2009-12-10
dennis_zane 写道
貌似我没有说多核单核在抢占上有什么区别，我说的是这个测试在多核上容易出现。
嗯。这个不太好说。
但是都会产生这个问题啊，没区别的。
25 楼
dennis_zane
2009-12-10
貌似我没有说多核单核在抢占上有什么区别，我说的是这个测试在多核上容易出现。
24 楼
mikeandmore
2009-12-10
还有，多核的OOE处理器会发生倒序构成的争抢。不过这个明显不足以考虑，因为这个实在太tricky了。
所以，在这个程序中多核，单核都会发生我和某前辈指出过的那个争抢问题，而且相当显而易见。
所以，在这个程序中多核，单核都会发生我和某前辈指出过的那个争抢问题，而且相当显而易见。
23 楼
mikeandmore
2009-12-10
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">mikeandmore 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
</div>
<p> </p>
<p>单核多核没关系吗？建议你自己找机器试下。</p>
</div>
<p>至少是java来说，其他的green thread的语言不好说。</p>
<p>java基本是native thread的。</p>
<p> </p>
<p>单核争抢发生在切换的时候，多核争抢发生在并发中不需要切换。</p>
<p>所以，都会同样发生争抢，这是显而易见的。</p>
<div class="quote_div">
<div class="quote_title">mikeandmore 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
</div>
<p> </p>
<p>单核多核没关系吗？建议你自己找机器试下。</p>
</div>
<p>至少是java来说，其他的green thread的语言不好说。</p>
<p>java基本是native thread的。</p>
<p> </p>
<p>单核争抢发生在切换的时候，多核争抢发生在并发中不需要切换。</p>
<p>所以，都会同样发生争抢，这是显而易见的。</p>
22 楼
dennis_zane
2009-12-10
<div class="quote_title">mikeandmore 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
</div>
<p> </p>
<p>单核多核没关系吗？建议你自己找机器试下。</p>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
</div>
<p> </p>
<p>单核多核没关系吗？建议你自己找机器试下。</p>
21 楼
mikeandmore
2009-12-10
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
<div class="quote_div">
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
</div>
<p>和单核多核没关系。并发数小，测试次数少。测试构造不够精巧。</p>
20 楼
dennis_zane
2009-12-10
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
<div class="quote_div">
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
</div>
<p> </p>
<p>我说的也是不能用读写锁，可能你的机器是单核的吧，那就增大并发看看。在多核机器上很容易出现的。</p>
19 楼
marshan
2009-12-10
<div class="quote_title">dennis_zane 写道</div>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
<div class="quote_div">
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
</div>
<p>测试结果：</p>
<p>Current map size:1000<br>我没太懂你要测什么，起初我们在讨论get时，readLock的问题。</p>
<p> </p>
<p>你的表达很中肯，我有的只有敬重和感谢！而且，我的项目或将考虑你们的建议，进行修改。</p>
18 楼
mikeandmore
2009-12-10
marshan 写道
你们俩的回复速度惊人。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
1 这个东西很难测到的
2 这个东西还是可以测到的。。。见上面的case
17 楼
dennis_zane
2009-12-09
<div class="quote_title">marshan 写道</div>
<div class="quote_div">
<br>OK，感谢二位！如果可能，请给出重入读锁的失败例子。</div>
<p><br>我想构建并发测试程序是一项基本技能，比如我随手写的一个并发测试：</p>
<p>
</p>
<pre name="code" class="java">package lru;
import java.util.concurrent.CyclicBarrier;
public class LRUMapConcurrentTest {
static int limit = 1000;
static int count = 100000;
static int threadCount = 100;
private final OjadbMap<Integer, Integer> map = new OjadbMap<Integer, Integer>(
1000);
class TestThread implements Runnable {
private final CyclicBarrier barrier;
private final int beginIndex;
public TestThread(int beginIndex, CyclicBarrier barrier) {
super();
this.beginIndex = beginIndex;
this.barrier = barrier;
}
public void run() {
try {
barrier.await();
for (int i = beginIndex; i < beginIndex + count; i++)
map.put(i, i);
for (int i = beginIndex; i < beginIndex + count; i++)
map.get(i);
barrier.await();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
public void concurrentTest() {
CyclicBarrier barrier = new CyclicBarrier(threadCount + 1);
for (int i = 0; i < threadCount; i++) {
new Thread(new TestThread(i, barrier)).start();
}
try {
barrier.await();
barrier.await();
} catch (Exception e) {
throw new RuntimeException(e);
}
System.out.println("Current map size:" + map.size());
}
public static void main(String[] args) {
new LRUMapConcurrentTest().concurrentTest();
}
}
</pre>
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
<p> </p>
<div class="quote_div">
<br>OK，感谢二位！如果可能，请给出重入读锁的失败例子。</div>
<p><br>我想构建并发测试程序是一项基本技能，比如我随手写的一个并发测试：</p>
<p>
</p>
<pre name="code" class="java">package lru;
import java.util.concurrent.CyclicBarrier;
public class LRUMapConcurrentTest {
static int limit = 1000;
static int count = 100000;
static int threadCount = 100;
private final OjadbMap<Integer, Integer> map = new OjadbMap<Integer, Integer>(
1000);
class TestThread implements Runnable {
private final CyclicBarrier barrier;
private final int beginIndex;
public TestThread(int beginIndex, CyclicBarrier barrier) {
super();
this.beginIndex = beginIndex;
this.barrier = barrier;
}
public void run() {
try {
barrier.await();
for (int i = beginIndex; i < beginIndex + count; i++)
map.put(i, i);
for (int i = beginIndex; i < beginIndex + count; i++)
map.get(i);
barrier.await();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
public void concurrentTest() {
CyclicBarrier barrier = new CyclicBarrier(threadCount + 1);
for (int i = 0; i < threadCount; i++) {
new Thread(new TestThread(i, barrier)).start();
}
try {
barrier.await();
barrier.await();
} catch (Exception e) {
throw new RuntimeException(e);
}
System.out.println("Current map size:" + map.size());
}
public static void main(String[] args) {
new LRUMapConcurrentTest().concurrentTest();
}
}
</pre>
<p> 尽管讲LRU的maxCapacity设置为1000，然而最后的结果却是maxCapacity的十倍，最大限制形同虚设，如果你将循环次数count设置为Integer.MAX_VALUE，那么很容易跑出个内存溢出。既然这样的代码是放在google code上，我想基于对用户负责的态度，也不应该让这样明显的并发隐患存在于你的系统中吧。可能口气重了点，我想表达的意思是对于并发，不要用“可能、我认为不会”这样的字眼，事实上看起来很小的错误在高并发下都将被放大并显现。</p>
<p> </p>
16 楼
dennis_zane
2009-12-09
marshan 写道
你们俩的回复速度惊人。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
不会发生吗？事实上发生的几率相当大，特别是在高并发并且缓存数据急剧增加的情况下。我们的系统吃过苦头，因为这个问题OOM。这本身是不安全的代码，拿出来误导人是很不应该的。
15 楼
marshan
2009-12-09
你们俩的回复速度惊人。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
单纯从缓存角度，synchronized是最好的，但是考虑并发读写上的不同逻辑，当一个线程put时，另一个线程是无法get的。
同一个线程重入get的间隔基本可以保证链表重排完成，而且两次进入该锁的可能性并不高。
技术上存在你们说的问题，但实际上并不太会发生。因此，我不打算做改变。
14 楼
mikeandmore
2009-12-09
火星来客 写道
mikeandmore 写道
理论上只会升高。不过cache这个东西本身就是越快越好的。
我认为是够用就好，
比如说我做一个cache app，每秒可以接受30w次socket请求，那我这个cache再快也没有用，在这种场景下，我们可以考虑如何降低cpu的消耗，而不是一味的追求快。
总之看场景吧，在速度和cpu的负载之间取一个平衡点
嗯，我不是做这个场景的。嘿嘿。。。
要是数据库的话，这块东西必然是越快越好。。。因为io操作远远比request的数量多。
anyway, tuning is tricky.
13 楼
火星来客
2009-12-09
mikeandmore 写道
理论上只会升高。不过cache这个东西本身就是越快越好的。
我认为是够用就好，
比如说我做一个cache app，每秒可以接受30w次socket请求，那我这个cache再快也没有用，在这种场景下，我们可以考虑如何降低cpu的消耗，而不是一味的追求快。
总之看场景吧，在速度和cpu的负载之间取一个平衡点
12 楼
mikeandmore
2009-12-09
火星来客 写道
mikeandmore 写道
火星来客 写道
mikeandmore 写道
原来也是搞链表鸟。。。嗯。。。还是自己写靠谱。。。-,-
于是
我觉得lz的实现有点问题。。。
readlock和readlock互溶
于是会同时发生get，这估计也是lz想要的。
但是看看hashedlinklist的代码
第323行，会开始对lru queue进行访问，要把当前的访问放在queue head。这会发生争抢。造成链表出现一些诡异的现象。
于是
我觉得lz的实现有点问题。。。
readlock和readlock互溶
于是会同时发生get，这估计也是lz想要的。
但是看看hashedlinklist的代码
第323行，会开始对lru queue进行访问，要把当前的访问放在queue head。这会发生争抢。造成链表出现一些诡异的现象。
这个也是我用synchronized的原因，get操作会修改链表，用ReentrantLock没问题，但是要用同一把锁做get和put,读写锁用在这里不合适
嗯。对。
而且我觉得这个东西如果用spinlock会好一些。。这么短操作不要陷入内核...
250w/s的操作我想对于一个cache来说应该没有问题了，只是在我的测试中cpu上升到95%，应该是内核互斥命令造成的。不知道用spinlock会不会能降低cpu的消耗
理论上只会升高。不过cache这个东西本身就是越快越好的。
发表评论
-
[童虎退壳系列]死锁演示
2011-10-13 01:53 910package creative.fire.multit ... -
[童虎退壳系列]方法加锁测试
2011-10-13 01:34 1117package creative.fire.multit ... -
线程池 浅析
2010-12-03 15:26 1012本文是对java线程池的粗浅分析，视野局限于线程池的基本实现， ... -
并发集合 CopyOnWrite
2010-11-28 01:59 1042CopyOnWriteArrayList 内部结构比较简 ... -
并发集合 Queue
2010-11-28 01:54 1197ArrayBlockingQueue 内部结构 ... -
并发集合 ConcurrentHash
2010-11-21 21:09 1219Synchronized Collections -- ... -
同步器
2010-11-17 02:08 1014Latch 门闩 CountDownLatch 的一个有用特 ... -
线程池的实现
2009-12-19 21:51 1365自己实现了一个简单的线程池。希望回复者讨论技术问题，不要说都已 ... -
LRU缓存的实现之性能测试
2009-12-08 15:19 1363针对上一篇文章，这里给出性能测试：10000条随机数据，50个 ... -
同步synchronized方法和代码块
2009-03-15 22:40 7640同步synchronized方法和代码块 打个比方：一个ob ...
相关推荐
描述：这个项目有点像实验，涉及 3 种不同的 LRU 缓存实现。 一个使用最小堆（通常用于优先级队列）而不是 OrderedDict，第二个使用集合包中的内置 OrderedDict，最后一个使用我自己的 OrderedDict 的简单实现。 ...
PHP LRU缓存实现介绍WTF 是 LRU 缓存吗？ LRU 代表最近最少使用。 它是一种缓存类型，通常具有固定容量并丢弃最旧的条目。 如果您需要控制缓存内存使用，这将特别有用。 如果您想了解有关 LRU Cache 的更多详细信息...
lru-cache：C ++中功能完整的LRU缓存实现
“Python—LRU缓存.zip”是一个压缩文件，其中包含了使用Python实现的最近最少使用（Least Recently Used, LRU）缓存算法的代码和相关文档。LRU缓存算法是一种常用的缓存淘汰策略，它根据数据项最近被使用的时间来...
lru缓存leetcode LRU缓存实现 从实现接口
链表（上）：如何实现LRU缓存淘汰算法
c语言实现LRU缓存
ratelimit-lru 使用LRU缓存进行通用速率限制的小型模块
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能: 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 2. get(key)：如果关键字 ...
Node.js中的LRU缓存实现 用法 const lru = require ( 'LRU-Cache' ) ; 。放 capacity -列表容量，不允许0，默认值：1000 maxAge节点将在maxAge ms内自行销毁 const cache = new lru ( { capacity : 100 } ) ; cache...
一种简单，快速，最近最少使用（LRU）的缓存实现，用于Servo的样式系统。 LRUCache使用固定容量的阵列进行存储。 它提供O(1)插入和O(n)查找。 它不需要分配器，可以在no_std包装箱中使用。 它在100％安全的Rust中...
快速的，仅标头的通用C ++ 17 LRU缓存库，带有可自定义的后端。 LRU缓存一种快速的，仅标头的通用C ++ 17 LRU缓存库，带有可自定义的后端。 用法示例缓存对昂贵函数的调用#include“ lru_cache / lru_cache.h” int ...
LRU算法是常用的缓存替代算法，文档中告诉我们如何实现LRU算法
LRU缓存HashMap+双向链表实现，java版本，导入即用
06丨链表（上）：如何实现LRU缓存淘汰算法？1
node-lru-native, 面向 node.js的高性能LRU缓存 node-lru-native这是 node.js 内存缓存的简单实现，支持 LRU ( least-recently-used ) 备份和 TTL expirations 。它是作为与( 精彩) node-lru-cache库的替代
主要介绍了Java实现简单LRU缓存机制的方法,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
06丨链表（上）：如何实现LRU缓存淘汰算法？.pdf
本算法为 C++ 实现的 LRU 缓存算法，包含普通 LRU、定时过期的 LRU、不定时过期的LRU，数据结构为双向链表及哈希表结合的方式，实现了 get() 和 put() 两个操作，且所有操作的平均时间复杂度均可以控制在 O(1) 内。