CLH是一个基于链表(队列)非线程饥饿的自旋(公平)锁,由于是 Craig、Landin 和 Hagersten三人的发明,因此命名为CLH锁。每一个等待锁的线程封装成节点,不断自旋判断前一个节点的状态,如果前一个节点释放锁就结束自旋。
CLH lock
CLH是一个基于链表(队列)非线程饥饿的自旋(公平)锁,由于是 Craig、Landin 和 Hagersten三人的发明,因此命名为CLH锁。每一个等待锁的线程封装成节点,不断自旋判断前一个节点的状态,如果前一个节点释放锁就结束自旋。
特点:该算法只一个CAS操作,即可让所有等待获取锁的线程构建有序全局队列。
原理
1、首先有一个尾节点指针,通过这个尾结点指针来构建等待线程的逻辑队列(所有每个线程还应该保存前面Node的状态,链表形式),因此能确保线程线程先到先服务的公平性,因此尾指针可以说是构建逻辑队列的桥梁;此外这个尾节点指针是原子引用类型,避免了多线程并发操作的线程安全性问题;
2、每个等待锁的线程在自己的前驱节点某个变量上自旋等待,等待前驱解锁之后即可去获取锁。
原理实现
1、因为是基于链表,所以每个线程除了保存当前线程的node情况还需保存前一个节点的node情况。
(1)、保存当前线程的node是为了解锁的时候可以直接获取当前节点的node,释放锁
(2)、保存前驱节点的node是为了构建有序列表。
2、因为其它线程哪个先开始不确定且方便当前线程安全的获取上一个线程的node作为前驱节点,所以应该有个变量(称为tail变量)保存每一个某时刻的线程node方便下一时刻获取该node作为前驱节点
(1)、所以还应该有个tail变量,并且每个线程使用的时候要求安全的获取并替换所以这里使用原子引用类型。
图:
java实现
CLH队列中的节点QNode中含有一个locked字段,该字段若为true表示该线程需要获取锁,且不释放锁,为false表示线程释放了锁。
定义Node类
1 | public class QNode { |
定义Lock接口
1 | public interface Lock { |
定义CLHLock
1 | public class CLHLock implements Lock { |
问题
问题1
this.myNodeThreadLocal.set(predNodeThreadLocal.get());
这句话的作用。
答:
(1)、this.myNodeThreadLocal.set()
防止某线程连续两次获取锁,发生死锁问题。
(2)、set该值predNodeThreadLocal.get()
保证连续两次竞争到锁时,第二次会重复使用第一次获取到锁设置的preNode对象,防止被GC掉。充分利用node提高GC效率和节省内存空间。
对于回答2中,如果this.myNodeThreadLocal.set(new QNode;
第二次获取到锁lock()时会设置新的preNode,导致旧的preNode没有引用存在,只能等待gc。
问题2
解释: CLH是一个基于链表(队列)非线程饥饿的自旋(公平)锁。
公平就是每个线程来了排队一个一个使用锁。
非饥饿:保证每个线程都会执行到
自旋:
1 | while (pred.locked) { |
链表:每个线程保存前驱节点,从tail可以遍历整个链表。
扩展知识
SMP(Symmetric Multi-Processor)
对称多处理器结构,指服务器中多个CPU对称工作,每个CPU访问内存地址所需时间相同。其主要特征是共享,包含对CPU,内存,I/O等进行共享。
SMP能够保证内存一致性,但这些共享的资源很可能成为性能瓶颈,随着CPU数量的增加,每个CPU都要访问相同的内存资源,可能导致内存访问冲突,
可能会导致CPU资源的浪费。常用的PC机就属于这种。
NUMA(Non-Uniform Memory Access)
非一致存储访问,将CPU分为CPU模块,每个CPU模块由多个CPU组成,并且具有独立的本地内存、I/O槽口等,模块之间可以通过互联模块相互访问,
访问本地内存的速度将远远高于访问远地内存(系统内其它节点的内存)的速度,这也是非一致存储访问的由来。NUMA较好地解决SMP的扩展问题,
当CPU数量增加时,因为访问远地内存的延时远远超过本地内存,系统性能无法线性增加。
CLH 的缺点
CLH唯一的缺点是在NUMA系统结构下性能很差,但是在SMP系统结构下该法还是非常有效的。解决NUMA系统结构的思路是MCS队列锁
1 | https://cloud.tencent.com/developer/article/1690060 |
- 本文作者: 初心
- 本文链接: http://funzzz.fun/2021/05/19/CLH锁/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!