并发编程 AQS 思想之CLH 队列锁的原理使用（十四）

旧城等待， 2022-12-28 00:50 141阅读 0赞

今天分享并发编程 AQS 思想之CLH 队列锁的 原理使用：

CLH  队列锁即  Craig, Landin, and Hagersten (CLH) locks 。 CLH 队列锁也是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程 仅仅在本地变量上自旋，它不断轮询前驱的状态，假设发现前驱释放了锁就结束 自旋。当一个线程需要获取锁时：

1.  创建一个的 QNode ，将其中的 locked 设置为 true 表示需要获取锁， myPred 表示对其前驱结点的引用

![20201212223951167.png][]

2.  线程  A  对  tail  域调用  getAndSet  方法，使自己成为队列的尾部，同时获取 一个指向其前驱结点的引用 myPred

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

线程  B  需要获得锁，同样的流程再来一遍：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

3. 线程就在前驱结点的  locked  字段上旋转，直到前驱结点释放锁 ( 前驱节点 的锁值 locked == false)

4. 当一个线程需要释放锁时，将当前结点的  locked  域设置为  false ，同时回收 前驱结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

如上图所示，前驱结点释放锁，线程  A  的  myPred  所指向的前驱结点的  locked 字段变为 false ，线程  A  就可以获取到锁。 CLH 队列锁的优点是空间复杂度低（如果有  n  个线程， L  个锁，每个线程每 次只获取一个锁，那么需要的存储空间是 O （ L+n ）， n  个线程有  n  个  myNode ， L 个锁有  L  个  tail ）。 CLH  队列锁常用在  SMP  体系结构下。Java 中的  AQS  是  CLH  队列锁的一种变体实现，也是学习AQS的基础。

***扩展知识点***

*SMP(Symmetric Multi-Processor)* *。即对称多处理器结构，指*  *server*  *中多个*  *CPU*  *对称工作，*  *每一个*  *CPU*  *訪问内存地址所需时间同样。其主要特征是共享，包括对*  *CPU* *，内存，* *I/O*  *等进*  *行共享。* *SMP*  *的长处是可以保证内存一致性。缺点是这些共享的资源非常可能成为性能瓶*  *颈。随着*  *CPU*  *数量的添加，每一个*  *CPU*  *都要訪问同样的内存资源，可能导致内存訪问冲突，*  *可能会导致*  *CPU*  *资源的浪费。经常使用的*  *PC*  *机就属于这样的。*

![20201212224103304.png][]

*非一致存储访问，将*  *CPU*  *分为*  *CPU*  *模块，每个*  *CPU*  *模块由多个*  *CPU*  *组成，并且具有独*  *立的本地内存、* *I/O*  *槽口等，模块之间可以通过互联模块相互访问，访问本地内存（本*  *CPU*  *模块的内存）的速度将远远高于访问远地内存* *(* *其他*  *CPU*  *模块的内存* *)* *的速度，这也是非一致*  *存储访问的由来。* *NUMA*  *较好地解决*  *SMP*  *的扩展问题，当*  *CPU*  *数量增加时，因为访问远地*  *内存的延时远远超过本地内存，系统性能无法线性增加。*

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3][]

*CLH*  *唯一的缺点是在*  *NUMA*  *系统结构下性能很差，但是在*  *SMP*  *系统结构下该法还是非*  *常有效的。解决*  *NUMA*  *系统结构的思路是*  *MCS*  *队列锁。*

*今天分享到处结束，明天我们开始分享AQS具体的原理和实现。*

[20201212223951167.png]: /images/20221120/e0aeb827115e48f9bdbc8db786903a6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221120/a3760036159142aeb93d96a21b801d06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201212224026371.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201212224040940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA==,size_16,color_FFFFFF,t_70
[20201212224103304.png]: https://img-blog.csdnimg.cn/20201212224103304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201212224117530.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA==,size_16,color_FFFFFF,t_70