最近在看关于线程锁的算法,做一个整理。资料出自于《The Art of Multiprocessor Programming》,算是一个读书笔记吧。示范代码基于java。
第一章是Craig, Landin, and Hagersten (CLH) locks。先上CLHLock的实现逻辑:
public class CLHLock implements Lock {
private final AtomicReference tail;
private final ThreadLocal myPred;
private final ThreadLocal myNode;
public CLHLock() {
tail = new AtomicReference(new QNode());
myNode = new ThreadLocal() {
protected QNode initialValue() {
return new QNode();
}
};
myPred = new ThreadLocal();
}
@Override
public void lock() {
QNode node = myNode.get();
node.locked = true;
QNode pred = tail.getAndSet(node);
myPred.set(pred);
while (pred.locked) {
}
}
@Override
public void unlock() {
QNode node = myNode.get();
node.locked = false;
myNode.set(myPred.get());
}
private static class QNode {
volatile boolean locked;
}
}
CLH Lock是一个自旋锁,能确保无饥饿性,提供先来先服务的公平性。
锁本身被表示成QNode的虚拟链表。共享的tail保存申请的最后的一个申请lock的线程的myNode域。每个申请lock的线程通过一个本地线程变量pred指向它的前驱。另外一个本地线程变量myNode的locked保存本身的状态,true:正在申请锁或已申请到锁;false:已释放锁。每个线程通过监视自身的前驱状态,自旋等待锁被释放。释放锁时,把自身myNode的locked设为false,使后继线程获的锁,并回收前驱的QNode,等待下次使用,因为自身的QNode可能被tail获后继引用,而前驱不再使用老的QNode。
该算法也是空间有效的,如果有n个线程,L个锁,每个线程每次只获取一个锁,那么需要的存储空间是O(L+n),n个线程有n个myNode,L个锁有L个tail。这种算法有一个缺点是在NUMA系统架构下性能表现很差,因为它自旋的locked是前驱线程的,如果内存位置较远,那么性能会受到损失。但是在SMP这种cache一致性的系统架构上表现良好。
下一章会整理MCSLock,它更适用于NUMA架构。
分享到:
相关推荐
国际环保巨头系列报告之四:CLH:逆势迎风起,时势造英雄.pdf
在线程获取锁时会调用AQS的acquire()方法,该方法第一次尝试获取锁如果失败,会将该线程加入到CLH队列中:public final void acqui
C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)...
AQS内部维护着一个FIFO队列,该队列就是CLH同步队列。下面小编来简单介绍下这个队列
C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)...
新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)新手乐园笔记(CLH)
windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程模型(CLH)windows编程...
环保行业报告:国际环保巨头-CLH-时势造英雄(30页),资源名称:环保行业报告:国际环保巨头-CLH-时势造英雄(30页)国际环保巨头系列-CLH-时势造英雄.zip...
c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)c与c++嵌入式系统编程(CLH)...
1234123412341234123412341234
windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)windows 编程基础(CLH)
C语言课程设计案例精编(CLH)C语言课程设计案例精编(CLH)C语言课程设计案例精编(CLH)C语言课程设计案例精编(CLH)C语言课程设计案例精编(CLH)C语言课程设计案例精编(CLH)C语言课程设计案例精编(CLH)C语言课程设计案例...
windows API 每日一练(CLH)windows API 每日一练(CLH)windows API 每日一练(CLH)windows API 每日一练(CLH)windows API 每日一练(CLH)windows API 每日一练(CLH)windows API 每日一练(CLH)windows API...
C语言鼠标操作方法及源码(CLH)C语言鼠标操作方法及源码(CLH)C语言鼠标操作方法及源码(CLH)C语言鼠标操作方法及源码(CLH)C语言鼠标操作方法及源码(CLH)C语言鼠标操作方法及源码(CLH)C语言鼠标操作方法及源码(CLH)...
《the c programming language》(CLH)《the c programming language》(CLH)《the c programming language》(CLH)《the c programming language》(CLH)《the c programming language》(CLH)《the c programming ...
简单来说 AQS 会把所有的请求线程构成一个 CLH 队列,当一个线程执行完毕 (lock.unlock())时会激活自己的后继节点,但正在执行的线程并不在队列中, 而那些等待执行的线程全部处于阻塞状态,经过调查线程的显式...
相比于多线程防止CPU空转Quine 不通过读源文件的方式输出程序源代码本身Vertx 基于netty的NIO实现的小清新WebServer和HttpClientReentrantReadWriteLock的用例以及实现写锁降级为读锁实现三种自旋锁SpinLock直接基于...
很好用的拷贝工具fastcopy_clh fastcopy_clh
VB基础教程,VB数据库编程教程,VB网上资料,VB网站。
java8 看不到源码DLock - 分布式锁 ...并且重试线程会周期性的唤醒CLH队列的头线程进行重试,这样每个进程只有一个线程可以参与锁竞争,避免了不必要的锁竞争。 同时,还为吞吐量提供了不公平锁。 快速