本文为原创,转载请注明出处
1、为什么要引入CLH锁
在前一篇文章中,介绍了TAS、TTAS两种自旋锁。这两种锁的缺点是:任何一个处理器每一次对锁成功的访问(getAndSet(true)和set(false)任意一个方法的调用),都会将其他处理器的cache中的缓存失效掉。这样会导致以下后果:
- 其他处理器无法再采用局部自旋的方式对相同数据进行访问,后续的其他处理器对锁的访问都会独占bus发送消息。而锁的释放也是需要占用bus,因此有可能其他处理器对bus的占用而导致锁的释放被延迟;
- 当锁释放后的一刹那,其他正在局部自旋的处理器同时竞争去获取锁(调用getAndSet(true)),原本只有一个处理器能在此次竞争中获胜,但其他获取失败的处理器还是在bus上制造了大量无用的交通阻塞,因此也会导致锁的释放被延迟;
- 由于数据访问存在局部性,cache从memory中加载数据时,一次会加载一个数据块,即cache存储的是cache line。Cache中锁状态数据的失效,会导致其他和锁状态处于同一个cache line中的数据也被失效掉,从而影响其他原本与锁不存在竞争的处理器的执行速度。
- 另外,最后一个缺点就是无法实现锁的公平性,最先自旋等待获取锁的处理器,在竞争中,不一定最先获取到锁。
虽然基于时间延迟的BackoffTTAS锁能一定程度的降低cache被无故失效的次数,但如何设置最优的延迟时间却是一个难题,因为不同的平台会有不同的最优参数,同时,引入延迟后,有可能导致处理器不能及时的得到锁,造成无谓的等待。 那么我们希望最理想的情况是:
- 由于锁(此处指排它锁)同一时刻只能由一个处理器持有,所以在锁释放后的一刹那,最多只需要通知一个正在等待持有锁的处理器去获取锁,其他处理器就不需要同时去凑热闹了,轮到它的时候,会自动只通知他。
- 当某个处理器获取到锁或者释放锁时,不要失效掉其他还未轮到顺序的处理器的cache,这样这些处理器就能一直在自己的cache中局部自旋,不会占用bus。
CLH锁就是基于这种理念设计出来的
2、CLH锁介绍
CLH算法中,每个申请锁的线程通过一个QNode对象表示,QNode中有一个volatile boolean类型的成员变量locked,locked为true,则表示对应的线程已经获取到了锁或者正在等待获取锁;locked为false,则表示对应的线程已经释放了锁。
public class QNode {
public volatile boolean locked = false;
}
而锁则由多个QNode对象组成的虚拟链表表示,之所以称为虚拟链表,是因为QNode之间并没有类似于next指针之类的引用,QNode之间通过锁的一个本地线程(ThreadLocal)变量myPred相连,myPred指向当前节点的前驱节点,即当前线程的前一个线程。而链表的尾节点则通过锁AtomicReference<QNode>类型的tail成员变量指向,即tail指向加入到申请锁的队列中的最近一个线程。
public class CLHLock implements Lock {
private AtomicReference<QNode> tail;
private ThreadLocal<QNode> myNode;
private ThreadLocal<QNode> myPred;
public CLHLock() {
tail = new AtomicReference<QNode>(new QNode());
myNode = new ThreadLocal<QNode>() {
protected QNode initialValue() {
return new QNode();
}
};
myPred = new ThreadLocal<QNode>() {
protected QNode initialValue() {
return null;
}
};
}
public void lock() {
QNode qnode = myNode.get();
qnode.locked = true;
QNode pred = tail.getAndSet(qnode);
myPred.set(pred);
while (pred.locked) {}
}
public void unlock() {
QNode qnode = myNode.get();
qnode.locked = false;
myNode.set(myPred.get());
}
}
当一个线程申请锁时:
- 首先会实例化一个QNode节点,并将其设置为自己的本地线程变量myNode;
- 然后将myNode的locked域设置为true,表明该线程正在等待获取锁;
- 接着通过AtomicReference的getAndSet()方法,将myNode设置为队列的最后一个节点,并返回其前驱节点;
- 最后该线程一直在其前驱节点的locked域自旋,直到locked域变为false,即前驱节点释放了锁。注意,对于SMP架构,由于是在cache中自旋,所以是高效的;
当一个线程释放锁时:
- 将myNode的locked域设置为false,使得后继线程停止自旋以便获取到锁;
- 然后重用前驱节点,将前驱节点设置为myNode,以便下一次该线程获取锁时使用。之所以能重用,是因为此时其前驱线程不会再使用该前驱节点了。而该线程原来的myNode,可能被其后继线程或tail引用。对于java语言来说,重用实际上是没有必要的,因为如果不重用,则前驱节点是可以被jvm回收的,从而降低内存的使用。
下图阐述了所得获取和释放过程(引自The art of Multiprocessor Programming一书)
3、结论
CLH算法将多个线程的自旋分散在不同的节点进行,当一个线程释放锁时,只会将其后继结点的cache失效掉,对于其他线程没有任何影响,其他线程还是在各自的cache中进行局部自旋。这样,就大大减少了bus上的交通阻塞,不会导致锁的释放被延迟。
另外,CLH算法由于总是将最近一个申请锁的线程放在链表的最后,从而带来了一个附加的功能,那就是对锁竞争的公平性,保证了先申请锁的线程先得到锁。
而且,CHL算法也是空间有效的,对于N个线程,L个锁,如果每个线程每次最多只能获取一个锁,则需要的存储空间是O(N+L),其中N个线程对应N个myNode,L个锁对应L个tail。
当然,CLH算法也有一个缺点,在cache-less的NUMA架构体系下,因为每个线程自旋的是其前驱线程的QNode中的locked域,如果内存位置比较远,则性能是要打折扣的。
- 大小: 128.4 KB
分享到:
相关推荐
C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)C语言高级编程技术(CLH)...
C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(CLH)C语言也能做大事1笔记(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编程...
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...
也对线程池,AQS的基础CLH 锁,提供了简易的实现,帮助理解。 jvm 将深入理解 jvm 的内容与oracle 官网的内容进行了总结,将其分为了几部分。便于查看。 Spring 对spring core、mvc 等模块的源码进行分析。 例如 ...
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 ...
很好用的拷贝工具fastcopy_clh fastcopy_clh
VB基础教程,VB数据库编程教程,VB网上资料,VB网站。
在线程获取锁时会调用AQS的acquire()方法,该方法第一次尝试获取锁如果失败,会将该线程加入到CLH队列中:public final void acqui
环保行业报告:国际环保巨头-CLH-时势造英雄(30页),资源名称:环保行业报告:国际环保巨头-CLH-时势造英雄(30页)国际环保巨头系列-CLH-时势造英雄.zip...
AQS内部维护着一个FIFO队列,该队列就是CLH同步队列。下面小编来简单介绍下这个队列
国际环保巨头系列报告之四:CLH:逆势迎风起,时势造英雄.pdf
java8 看不到源码DLock - 分布式锁 ...并且重试线程会周期性的唤醒CLH队列的头线程进行重试,这样每个进程只有一个线程可以参与锁竞争,避免了不必要的锁竞争。 同时,还为吞吐量提供了不公平锁。 快速
语言:English 将CLH报表视图转换成表格 用于将CLH结果表转换为Excel兼容视图的自定义脚本