Java AQS核心数据结构

在并发编程中，锁是一种常用的保证线程安全的方法。Java中常用的锁主要有两类，一种是Synchronized修饰的锁，被称为Java内置锁或监视器锁。另一种就是J2SE 1.5版本之后的java.util.concurrent包中的各类同步器，包括ReentrantLock（可重入锁），ReentrantReadWriteLock（可重入读写锁），Semaphore（信号量），CountDownLatch等。这些同步器都是基于AbstractQueueSynchronizer这个简单的框架来构建的，而AQS的核心数据结构是一种名叫Craig，Landin，and Hagersten locks（下称CLH锁）的变体。
CLH锁是对自旋锁的一种改良。在介绍CLH锁前，我先简单介绍一下自旋锁。

自旋锁是互斥锁的一种实现，Java实现如下方所示。

public class SpinLock {
    private AtomicReference owner = new AtomicReference<>();

    public void lock() {
        Thread thread = Thread.currentThread();
        while (!owner.compareAndSet(null, thread)) {
        }
    }

    public void unlock() {
        Thread thread = Thread.currentThread();
        while (!owner.compareAndSet(thread, null)) {
        }
    }
}

如代码所示，获取锁时，线程会对一个原子变量循环执行compareAndSet方法，直到该方法返回成功时即为成功获取锁。compareAndSet方法底层是通用的compare-and-swap（下称CAS）实现的。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。该操作原子的。该操作时原子操作，原子性保证了根据最新信息计算新值，如果于此同时值已由另一个线程更新，则写入将失败。因此，这段代码可以实现互斥锁的功能。

自旋锁实现简单，同时避免了操作系统进程调度和线程上下文切换的开销，但它有两个缺点：

• 第一是锁饥饿的问题。在锁竞争激烈的情况下，可能存在一个线程一直被其他线程“插队”而一直获取不到锁的情况（因为没有机制保证谁能抢到锁）。
• 第二个是性能问题。在实际的多处理上运行的自旋锁在锁竞争激烈时性能较差。
  下图是引用自《多处理器编程的艺术》的 n 个线程固定地执行一段临界区所需的时间。
  TASLock 和 TTASLock 与上文代码类似，都是针对一个原子状态变量轮询的自旋锁实现，最下面的曲线表示线程在没有干扰的情况下所需的时间。
  
  显然，自旋锁的性能和理想情况相距甚远。这是因为自旋锁锁状态中心化，在竞争激烈的情况下，锁状态变更会导致多个CPU的高速缓存频繁同步主存锁状态，从而拖慢CPU效率。

自旋锁适用于锁竞争不激烈、锁持有时间短的场景。

CLH锁是对自旋锁的一种改进，有效的解决了以上的两个缺点。首先它将线程组织成一个队列，保证先请求的线程先获得锁，避免了饥饿问题。其次锁状态去中心化，让每个线程在不同的状态变量中自旋，这样当一个线程释放它的锁时，只能使其直接后续线程的高速缓存失效，缩小了影响范围，从而减少了CPU的开销。
CLH锁结构很简单，类似一个链表队列，所有请求获取锁的线程会排队在链表队列中，自旋访问队列中前一个节点的状态。当一个节点释放锁时，只有它的后一个节点才可以得到锁。CLH锁本身有一个队尾指针Tail，它是一个原子变量，指向队列最末端的CLH节点。每个CLH节点有两个属性：所代表的线程和标识是否持有锁的状态变量。当一个线程要获取锁时，它会对Tail进行一个getAndSet的原子操作。该操作会返回Tail当前指向的节点，也就是当前队尾节点，然后使Tail指向这个线程对应的CLH节点，成为新的队尾节点。入队成功后，该线程会轮询上一个队尾节点的状态变量，当上一个节点释放锁后，它将得到这个锁。
下面用图来展示CLH锁从获取到释放锁的全过程。

1. CLH锁初始化时，Tail会指向一个状态为false的空节点。
2. 当Thread1请求获取锁时，Tail节点指向T1对应的节点，同时返回空节点。T1检查上一个节点状态为false，就成功获取到锁，可以执行相应的逻辑。
3. 当Thread2请求获取锁，Tail节点执行T2对应的节点，同时返回T1对应的节点。T2检查到上一个节点状态为True，无法获取到锁，于是开始轮询上一个节点的状态。
4. 当T1释放锁时，会将状态变量设置为false，T2轮询检查上一个节点状态为false，获取锁成功。
5. T2释放锁。

通过上面的图形象的展示了CLH的数据结构以及初始化、获取 、释放锁的全过程，编译大家理解CLH锁的原理。但是就是理解了原理，也不一定能够实现一个线程安全的CLH互斥锁。在并发编程领域，“细节是魔鬼”这一格言同样适用。下面讲解读CLH锁Java实现源码并分享并发编程的一些细节。

public class CLH {
    private final ThreadLocal node = ThreadLocal.withInitial(Node::new);
    private final AtomicReference tail = new AtomicReference<>(new Node());
    private static class Node {
        private volatile boolean locked;
    }
    public void lock() {
        Node node = this.node.get();
        node.locked = true;
        Node pre = tail.getAndSet(node);
        while (pre.locked) {
        }
    }
    public void unLock() {
        Node node = this.node.get();
        node.locked = false;
        this.node.set(new Node());
    }
}

1. 节点中的状态变量为什么用volatile修饰？可以不用volatile么？
   如果不用volatile变量，会导致线程1释放锁，但是线程2这是一直忙碌中（空转），导致线程2的工作内存中的pre.locked变量副本一直无法同步主存，因此一直拿不到锁。
   如果使用了volatile变量，volatile变量的一写多度特性，能够让线程2的工作内存失效，再次读取时会同步主存中的变量，其实就是利用了volatile的可见性。
2. CLH锁时一个链表队列，为什么Node节点没有执行前驱或后继指针呢？
   CLH锁是一种隐式的链表队列，没有显示的维护前驱或后继指针。因为每个等待获取锁的线程只需要轮询前一个节点的状态就够了，而不需要遍历整个队列。在这种情况下，只需要使用一个局部变量保存前驱节点，而不需要显示的维护前驱后后继指针。
   当Node节点无变量引用后，GC会自动回收。
3. this.node.set(new Node())这行代码有何意义？
   如果没有这行代码，Node可能被复用，导致死锁，如下图所示：
   

• 一开始，T1持有锁，T2自旋等待，如图1开始。
• 当T1释放锁（设置为false），但此时T2尚未抢占到锁，如图2。
• 此时如果T1再次调用lock()请求获取锁，会将状态设置为true，同时自旋等待T2释放锁。而T2也自旋等待前驱节点状态变为false，这样就造成了死锁，如图3。

CLH锁作为自旋锁的改进，有以下几个优点：

1. 性能优异，获取和释放锁开销小。CLH的锁状态不再是单一的原子变量，而是分散在每个节点的状态中，降低了自旋锁在竞争激烈是频繁同步的开销。在释放锁的开销也因为不需要使用CAS指令而降低了。
2. 公平锁。先入队列的线程会得到锁。
3. 实现简单，易于理解。
4. 扩展性强。下面会提到AQS如何扩展CLH锁实现了j.u.c包下各类丰富的同步器。

当然，它也有两个缺点：

1. 因为有自旋操作，当锁持有时间长时会带来较大的CPU开销。
2. 基本的CLH锁功能单一，不改造不能支持复杂的功能。

Java AQS 核心数据结构 -CLH 锁