CLH队列锁的原理

img

什么是CLH队列锁

CLH锁是有由Craig, Landin, and Hagersten这三个人发明的锁，取了三个人名字的首字母，所以叫 CLH Lock。

CLH锁是一个自旋锁。能确保无饥饿性。提供先来先服务的公平性。

CLH队列锁也是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程仅仅在本地变量上自旋，它不断轮询前驱的状态，假设发现前驱释放了锁就结束自旋。

就像这样

img

当一个线程需要获取锁时

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

img

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

img

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

img

  1. 线程就在前驱结点的locked字段上旋转，直到前驱结点释放锁(前驱节点的锁值 locked ==
    false)
  2. 当一个线程需要释放锁时，将当前结点的locked域设置为false，同时回收前驱结点

img

如上图所示，前驱结点释放锁，线程A的myPred所指向的前驱结点的locked字段变为false，线程A就可以获取到锁。

CLH队列锁的优点是空间复杂度低（如果有n个线程，L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O（L+n），n个线程有n个myNode，L个锁有L个tail）。CLH队列锁常用在SMP体系结构下。

Java中的AQS是CLH队列锁的一种变体实现。

扩展知识

SMP(Symmetric Multi-Processor)

img

对称多处理器结构，指服务器中多个CPU对称工作，每个CPU访问内存地址所需时间相同。其主要特征是共享，包含对CPU，内存，I/O等进行共享。

SMP能够保证内存一致性，但这些共享的资源很可能成为性能瓶颈，随着CPU数量的增加，每个CPU都要访问相同的内存资源，可能导致内存访问冲突，

可能会导致CPU资源的浪费。常用的PC机就属于这种。

NUMA(Non-Uniform Memory Access)

img

非一致存储访问，将CPU分为CPU模块，每个CPU模块由多个CPU组成，并且具有独立的本地内存、I/O槽口等，模块之间可以通过互联模块相互访问，

访问本地内存的速度将远远高于访问远地内存(系统内其它节点的内存)的速度，这也是非一致存储访问的由来。NUMA较好地解决SMP的扩展问题，

当CPU数量增加时，因为访问远地内存的延时远远超过本地内存，系统性能无法线性增加。

CLH 的缺点

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