详解AQS一：CLH队列锁

Published on 2024-11-24 17:10 in 分类: 博客 with 狂盗一枝梅
分类: 博客

AQS（AbstractQueuedSynchronizer）抽象队列同步器是Java中用于构建同步器（synchronizer）的框架，提供了一种基于FIFO等待队列的抽象框架，JAVA中的很多显式锁底层实现都使用了该框架：ReentrantLock、Semaphore、CountDownLatch等。可以说掌握了AQS，就几乎掌握了这些众多的显式锁底层实现原理，AQS对JAVA开发的重要性不言而喻。

一、CAS的弊端和解决方案

在争用激烈的场景下，使用基于CAS自旋实现的轻量级锁有两个大的问题：

（1）CAS恶性空自旋会浪费大量的CPU资源。

（2）在SMP架构的CPU上会导致“总线风暴”。

解决CAS恶性空自旋的有效方式之一是以空间换时间，较为常见的方案有两种：分散操作热点和使用队列削峰。

分散操作热点： 这种方式比较经典的是读写锁以及分段锁。读写锁相关的类有ReentrantReadWriteLock，分段锁相关的类有ConcurrentHashMap、LongAdder、LongAccumulator等。

使用队列削峰： AQS就是使用队列削峰的典范。相关的类有ReentrantLock、Semaphore、CountDownLatch等。说到底synchronized内置锁其实也是使用了队列进行了削峰。实际上使用队列削峰并不能提高程序性能，甚至远远不如CAS自旋的效率高。

看下分别使用AtomicLong、LongAdder、synchcronized内置锁、ReentrantLock显式锁在八线程环境下自增1,0000,0000 次所耗费的时间

类名 耗费时间（秒）
AtomicLong 22.240
LongAdder 4.615
synchcronized 194.573
ReentrantLock 203.570

从表格中可以看到内置锁和显式锁的效率几乎是相同的，效率最高的LongAdder由于使用了分段锁最大程度的减少了竞争，只用了不到5秒的时间就完成了任务，这比内置锁和显式锁效率高四五十倍，也比纯CAS无分段锁的AtomicLong效率高五倍。可见分散热点，最大程度的减少线程竞争是提高效率的最好方式，而无论内置锁的偏向锁、轻量级锁、自旋锁再怎么优化，在竞争激烈的场景下很快都会膨胀成重量级锁，其优化手段几乎没什么用。

而显式锁ReentrantLock内部使用了AQS，AQS比较复杂，它是CLH队列的变种，为此本篇文章先讲解CLH队列的相关知识，为理解AQS做好准备。

二、CLH锁原理

CLH锁其实就是一种基于队列（具体为单向链表）排队的自旋锁，由于是Craig、Landin和Hagersten三人一起发明的，因此被命名为CLH锁，也叫CLH队列锁。

简单的CLH锁可以基于单向链表实现，申请加锁的线程首先会通过CAS操作在单向链表的尾部增加一个节点，之后该线程只需要在其前驱节点上进行普通自旋，等待前驱节点释放锁即可。由于CLH锁只有在节点入队时进行一下CAS的操作，在节点加入队列之后，抢锁线程不需要进行CAS自旋，只需普通自旋即可。因此，在争用激烈的场景下，CLH锁能大大减少CAS操作的数量，以避免CPU的总线风暴。

CLH队列是一种先进先出的队列（FIFO），所以CLH锁是一种公平锁。

起初，CLH队列只有一个初始化的节点Tail表示尾部节点

image-20241122215554559

这时，线程0和线程1同时尝试进入临界区，触发了竞态条件，它们需要排队进入CLH队列，为了防止发生线程安全性问题，这里需要使用CAS自旋操作入队，进入队列后的示意图如下

image-20241122221229658

每个入队之后的节点都会轮询前一个节点是否已经释放锁，如果已经释放锁，那意味着自己可以获取到锁了

image-20241122221703999

Tail节点默认是释放锁状态，所以Thread0立即会获取到锁并进入临界区执行任务，同时Thread1也会轮询Thread0的持有锁状态，Thread0如果未释放锁，Thread1会一直做普通自旋轮询Thread0持有锁的状态

image-20241122222343727

依次类推，如果有N个线程，其数据结构会变成如下所示，线程从队尾开始依次获取锁，获取不到锁的线程将会依次在队尾排队。

a0a523ec-8089-4bf9-8809-270c235a48dd.png

以上是获取锁的过程，那释放锁呢？

每个CLH节点都维护了持有锁的状态，只需要将持有锁的状态标记为false，则后继结点在轮询锁状态的时候就会察觉到前一个节点已经释放了锁，它会将自己持有锁的状态标记为true，并进入临界区执行任务；可以顺便切断和preNode的联系，加速GC。

三、CLH锁案例

1、节点类Node

首先定义一个Node类用来描述CLH队列中排队的节点

//虚拟等待队列的节点
@Data
static class Node {
    public Node(boolean locked, Node prevNode) {
        this.locked = locked;
        this.prevNode = prevNode;
    }

    // true：当前线程正在抢占锁，或者已经占有锁
    // false：当前线程已经释放锁，下一个线程可以占有锁了
    volatile boolean locked;

    // 前一个节点，需要监听其locked字段
    Node prevNode;

    // 空节点
    public static final Node EMPTY = new Node(false, null);
}

该节点类有两个字段：

  • locked：标志当前节点是否持有锁
  • prevNode：前一个节点的指针

2、CLH锁类

模仿ReentrantLock，自定义一个锁类CLHLock，让它实现Lock接口

public class CLHLock implements Lock {
    /**
     * 当前节点的线程本地变量
     */
    private static ThreadLocal<Node> curNodeLocal = new ThreadLocal();
    /**
     * CLHLock队列的尾部指针，使用AtomicReference，方便进行CAS操作
     */
    private AtomicReference<Node> tail = new AtomicReference<>(null);

    public CLHLock() {
        //设置尾部节点
        tail.getAndSet(Node.EMPTY);
    }
    ......省略其它方法
}

CLH队列是一个虚拟队列，它们前后是通过指针串联起来的。Node节点类中并没有Thread类型的成员变量，这是因为Node节点和线程是通过ThreadLocal进行绑定。

CLH锁初始化的时候就使用了空节点作为队列尾部节点，每个Node都应当使用CAS方式入队，所以这里使用了AtomicReference类来包装尾部Node。

3、获取锁方法：lock

//加锁操作：将节点添加到等待队列的尾部
@Override
public void lock() {
    Node curNode = new Node(true, null);
    Node preNode = tail.get();
    //CAS自旋：将当前节点插入队列的尾部
    while (!tail.compareAndSet(preNode, curNode)) {
        preNode = tail.get();
    }
    //设置前驱节点
    curNode.setPrevNode(preNode);

    // 自旋，监听前驱节点的locked变量，直到其值为false
    // 若前驱节点的locked状态为true，则表示前一个线程还在抢占或者占有锁
    while (curNode.getPrevNode().isLocked()) {
        //让出CPU时间片，提高性能
        Thread.yield();
    }
    // 能执行到这里，说明当前线程获取到了锁
    // Print.tcfo("获取到了锁！！！");

    //将当前节点缓存在线程本地变量中，释放锁会用到
    curNodeLocal.set(curNode);
}

获取锁是CLH锁最核心的方法，这个过程分为两步：

第一步：CAS自旋将当前节点插入队尾

由于创建节点和将节点插入队尾是两个操作，不具备原子性，所以这里要使用CAS操作一直重试

//CAS自旋：将当前节点插入队列的尾部
while (!tail.compareAndSet(preNode, curNode)) {
    preNode = tail.get();
}

直到CAS设置成功，队尾节点就变成了新创建的Node，再将前驱节点设置为上一个队尾节点即可

//设置前驱节点
curNode.setPrevNode(preNode);

第二步：普通自旋等待前驱节点释放锁

每个Node入CLH队列之后，都会立马开始自旋轮询前驱节点持有锁的状态，如果前驱节点一直持有锁，则让出cpu时间片，一直等待；如果前驱节点释放了锁，则结束循环，获取到了锁。

// 自旋，监听前驱节点的locked变量，直到其值为false
// 若前驱节点的locked状态为true，则表示前一个线程还在抢占或者占有锁
while (curNode.getPrevNode().isLocked()) {
    //让出CPU时间片，提高性能
    Thread.yield();
}

最后，使用ThreadLocal绑定当前线程和Node的关联关系

//将当前节点缓存在线程本地变量中，释放锁会用到
curNodeLocal.set(curNode);

4、释放锁方法：unlock

//释放锁
@Override
public void unlock() {
    Node curNode = curNodeLocal.get();
    curNode.setLocked(false);
    curNode.setPrevNode(null);     //help for GC
    curNodeLocal.set(null);                //方便下一次抢锁
}

释放锁的方法比较简单了，一方面将持有锁的状态设置为false表示已经释放了锁，后继结点判断前驱节点释放了锁之后就可以获取锁进入临界区了；另一方面将前驱节点指针设置为null，可以在GC的时候释放先关的内存。

5、完整CLHLock源码

import lombok.Data;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

/**
 * @author kdyzm
 * @date 2024/11/8
 */
public class CLHLock implements Lock {
    /**
     * 当前节点的线程本地变量
     */
    private static ThreadLocal<Node> curNodeLocal = new ThreadLocal();
    /**
     * CLHLock队列的尾部指针，使用AtomicReference，方便进行CAS操作
     */
    private AtomicReference<Node> tail = new AtomicReference<>(null);

    public CLHLock() {
        //设置尾部节点
        tail.getAndSet(Node.EMPTY);
    }

    //加锁操作：将节点添加到等待队列的尾部
    @Override
    public void lock() {
        Node curNode = new Node(true, null);
        Node preNode = tail.get();
        //CAS自旋：将当前节点插入队列的尾部
        while (!tail.compareAndSet(preNode, curNode)) {
            preNode = tail.get();
        }
        //设置前驱节点
        curNode.setPrevNode(preNode);

        // 自旋，监听前驱节点的locked变量，直到其值为false
        // 若前驱节点的locked状态为true，则表示前一个线程还在抢占或者占有锁
        while (curNode.getPrevNode().isLocked()) {
            //让出CPU时间片，提高性能
            Thread.yield();
        }
        // 能执行到这里，说明当前线程获取到了锁
        // Print.tcfo("获取到了锁！！！");

        //将当前节点缓存在线程本地变量中，释放锁会用到
        curNodeLocal.set(curNode);
    }



    //释放锁
    @Override
    public void unlock() {
        Node curNode = curNodeLocal.get();
        curNode.setLocked(false);
        curNode.setPrevNode(null);     //help for GC
        curNodeLocal.set(null);                //方便下一次抢锁
    }

    //虚拟等待队列的节点
    @Data
    static class Node {
        public Node(boolean locked, Node prevNode) {
            this.locked = locked;
            this.prevNode = prevNode;
        }

        // true：当前线程正在抢占锁，或者已经占有锁
        // false：当前线程已经释放锁，下一个线程可以占有锁了
        volatile boolean locked;

        // 前一个节点，需要监听其locked字段
        Node prevNode;

        // 空节点
        public static final Node EMPTY = new Node(false, null);
    }
    // 省略其他代码

    @Override
    public void lockInterruptibly() throws InterruptedException {

    }

    @Override
    public boolean tryLock() {
        return false;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return false;
    }

    @Override
    public Condition newCondition() {
        return null;
    }
}

6、CLHLock性能

CLHLock是自定义的锁，它的性能如何呢？还是按照文章一开始的自增1,0000,0000 次的测试方法，和JDK自带的内置锁、显示锁、以及原子类它们相比，CLHLock的执行效率如何？

类名 耗费时间（秒）
AtomicLong 18.908
LongAdder 4.141
synchcronized 182.696
ReentrantLock 178.925
CLHLock 37890.644

好吧，自定义的CLHLock性能实在太差了。。。。



END.


注意：本文归作者所有，未经作者允许，不得转载

#java #多线程编程
阅读全部
目录
复制 复制成功