算法：CLH锁的原理及实现

矫情吗；* 2022-04-18 03:10 249阅读 0赞

**一、背景**  
**1.1 SMP(Symmetric Multi-Processor)**  
对称多处理器结构，它是相对非对称多处理技术而言的、应用十分广泛的并行技术。在这种架构中，一台计算机由多个CPU组成，并共享内存和其他资源，所有的CPU都可以平等地访问内存、I/O和外部中断。虽然同时使用多个CPU，但是从管理的角度来看，它们的表现就像一台单机一样。操作系统将任务队列对称地分布于多个CPU之上，从而极大地提高了整个系统的数据处理能力。但是随着CPU数量的增加，每个CPU都要访问相同的内存资源，共享资源可能会成为系统瓶颈，导致CPU资源浪费。  
![SMP：对称多处理器结构][SMP]  
**1.2 NUMA(Non-Uniform Memory Access)**  
非一致存储访问，将CPU分为CPU模块，每个CPU模块由多个CPU组成，并且具有独立的本地内存、I/O槽口等，模块之间可以通过互联模块相互访问，访问本地内存（本CPU模块的内存）的速度将远远高于访问远地内存(其他CPU模块的内存)的速度，这也是非一致存储访问的由来。NUMA较好地解决SMP的扩展问题，当CPU数量增加时，因为访问远地内存的延时远远超过本地内存，系统性能无法线性增加。  
![NUMA：非一致存储访问][NUMA]

**1.3 CLH、MCS命名来源**

*  MCS：John Mellor-Crummey and Michael Scott
 *  CLH：Craig，Landin andHagersten

**二、CLH锁**  
CLH是一种基于单向链表的高性能、公平的自旋锁。申请加锁的线程通过前驱节点的变量进行自旋。在前置节点解锁后，当前节点会结束自旋，并进行加锁。在SMP架构下，CLH更具有优势。在NUMA架构下，如果当前节点与前驱节点不在同一CPU模块下，跨CPU模块会带来额外的系统开销，而MCS锁更适用于NUMA架构。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NsYXJhbQ_size_16_color_FFFFFF_t_70]

> 锁值：我把自旋条件定义为锁值 locked。locked == true 表示节点的处于加锁状态或者等待加锁状态，locked == false 表示节点处于解锁状态。

1.  基于线程当前节点的前置节点的锁值（locked）进行自旋，locked == true 自旋，locked == false 加锁成功。
2.  locked == true 表示节点处于加锁状态或者等待加锁状态。
3.  locked == false 表示节点处于解锁状态。
4.  每个节点在解锁时更新自己的锁值（locked），在这一时刻，该节点的后置节点会结束自旋，并进行加锁。

**2.1 加锁逻辑**

1.  获取当前线程的锁节点，如果为空则进行初始化。
2.  通过同步方法获取尾节点，并将当前节点置为尾节点，此时获取到的尾节点为当前节点的前驱节点。
3.  如果尾节点为空，则表示当前节点为第一个节点，加锁成功。
4.  如果尾节点不为空，则基于前驱节点的锁值（locked==true）进行自旋，直到前驱节点的锁值 locked == false。

**2.2 解锁逻辑**

1.  获取当前线程的锁节点，如果节点为空或者锁值（locked== false）则无需解锁，直接返回。
2.  使用同步方法为尾节点赋空值，赋值不成功则表示当前节点不是尾节点，需要将当前节点的 locked == false 已保证解锁该节点。如果当前节点为尾节点，则无需设置该节点的锁值。因为该节点没有后置节点，即使设置了，也没有实际意义。

**2.3 Java代码**

package org.learn.lock;
    
    import java.util.concurrent.atomic.AtomicReference;
    
    /**
     * MCS：John Mellor-Crummey and Michael Scott
     * CLH：Craig，Landin and Hagersten
     * @author zhibo
     * @version 1.0
     * @date 2018/11/7 10:39
     */
    public class CLHLock implements Lock {
        private AtomicReference<CLHNode> tail;
        private ThreadLocal<CLHNode> threadLocal;
    
        public CLHLock() {
            this.tail = new AtomicReference<>();
            this.threadLocal = new ThreadLocal<>();
        }
    
        @Override
        public void lock() {
            CLHNode curNode = threadLocal.get();
            if(curNode == null){
                curNode = new CLHNode();
                threadLocal.set(curNode);
            }
    
            CLHNode predNode = tail.getAndSet(curNode);
            if(predNode != null){
                while (predNode.getLocked()){
    
                }
            }
        }
    
        @Override
        public void unlock() {
            CLHNode curNode = threadLocal.get();
            threadLocal.remove();
    
            if(curNode == null || curNode.getLocked() == false){
                return;
            }
    
            if(!tail.compareAndSet(curNode, null)){
                curNode.setLocked(false);
            }
        }
    
        public static void main(String[] args) {
            final Lock clhLock = new CLHLock();
    
            for (int i = 0; i < 10; i++) {
                new Thread(new DemoTask(clhLock, i + "")).start();
            }
        }
    
        class CLHNode {
            private volatile boolean locked = true;
    
            public boolean getLocked() {
                return locked;
            }
    
            public void setLocked(boolean locked) {
                this.locked = locked;
            }
        }
    }

package org.learn.lock;
    
    /**
     * @author zhibo
     * @version 1.0
     * @date 2018/11/7 14:22
     */
    public class DemoTask implements Runnable {
        private Lock lock;
        private String taskId;
    
        public DemoTask(final Lock lock, final String taskId){
            this.lock = lock;
            this.taskId = taskId;
        }
    
        @Override
        public void run() {
            try {
                lock.lock();
                Thread.sleep(500);
                System.out.println(String.format("Thread %s Completed", taskId));
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    }

CLH锁就介绍到这里，后续会对MCS锁进行介绍，如有不正之处，欢迎批评指正，谢谢大家。

[SMP]: /images/20220418/a195bf18c546401fbe17d90d1af8aac8.png
[NUMA]: /images/20220418/cb0386d67d0a4c339cd0255ca1b34617.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NsYXJhbQ_size_16_color_FFFFFF_t_70]: /images/20220418/3f76ff1ed3b34ebfb206d791246e17e3.png