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队列锁