7. 并发工具之锁原理 - 《JUC》

7.1 AbstractQueuedSynchronizer
- 7.1.1 AQS概述
- 7.1.2 获取与释放资源
7.2 ReentrantLock
7. 3 ReentrantReadWriteLock
7.4 StampedLock

全程高能，源码解读，拜读Doug Lea前辈的并发理念和玄妙设计。

分析并不完全透彻，只能大概梳理出大致流程，有时间再深入吧。

（我只是Javadoc的搬运工罢了。）

7.1 AbstractQueuedSynchronizer

7.1.1 AQS概述

AbstractQueuedSynchronizer(抽象同步队列)，是阻塞式锁和相关的同步器工具的框架。

使用state属性来表示资源的状态（分独占模式和共享模式），子类需要定义如何维护这个状态，控制如何获取锁和释放锁。
- getState：获取state状态
- setState：设置state状态
- compareAndSetState：乐观锁机制设置state状态
- 独占模式是只有一个线程能够访问资源，而共享模式可以允许多个线程访问资源
提供了基于FIFO的等待队列，在其内部通过节点head和tail记录对手和队尾元素，队列的元素类型为Node
- SHARED：用来标记该线程是是否是获取共享资源时被阻塞挂起后放入AQS队列的
- EXCLUSIVE：用来标记线程是获取独占资源时被挂起后放入AQS队列的
- waitStatus：记录当前线程等待状态
  - 1：CANCELLED，线程结点已释放（超时、中断），已取消的节点不会再阻塞
  - -1：SIGNAL，该线程的后续线程需要阻塞，即只要前驱结点释放锁，就会通知标识为SIGNAL状态的后继结点的线程
  - -2：CONDITION，该线程在condition队列中阻塞
  - -3：PROPAGATE，释放共享资源时需要通知其他节点
- prev记录当前节点的前驱结点，next记录当前阶段的后继结点
内部类ConditionObject，用来结合锁实现线程同步，是条件变量，每个条件变量对应一个条件队列（单向链表队列），用来存放调用条件变量的await方法后被阻塞的线程，队列的头、尾元素分别是firstWaiter和lastWaiter。

7.1.2 获取与释放资源

对于AQS来说，线程同步的关键是对状态值state进行操作。根据state是否属于一个线程，操作state的方式分为独占方式和共享方式。

独占方式：void acquire(int arg) void acquireInterruptibly(int arg) boolean release(int arg)
共享方式：void acquireShared(int arg) void acquireSharedInterruptibly(int arg) boolean releaseShared(int arg)

使用独占方式获取的资源是与具体线程绑定的，就是说如果一个线程获取到了资源，就会标记到是这个线程获取到了，其他线程再尝试操作state获取资源时会发现当前该资源不是自己持有的，就会在获取失败后被阻塞。比如独占锁ReentrantLock的实现，当一个线程获取了ReentrantLock的锁后，在AQS内部会首先使用CAS操作把state状态值从0变为1，然后设置当前锁的持有者exclusiveOwnerThread为当前线程，当该线程再次获取锁时发现它就是锁的持有者，则会把状态值state从1变为2，即设置可重入次数，而当另外一个线程获取锁时发现自己并不是该锁的持有者就会被放入AQS阻塞队列后挂起。

对应共享方式的资源与具体线程是不相关的，当多个线程去请求资源时通过CAS方式竞争获取资源，当一个线程获取到了资源后，另外一个线程再次去获取时如果当前资源还能满足它的需要，则当前线程只需要使用CAS方式进行获取即可。比如Semaphore信号量，当一个线程通过acquire()方法获取信号量时，会首先看当前信号量个数是否满足需要，不满足则把当前线程放入阻塞队列，如果满足则通过自旋CAS获取信号量。

7.1.2.1 独占方式

（1）当一个线程调用acquire(int arg)方法获取独占资源时，会首先使用tryAcquire方法尝试获取资源，具体是设置状态变量state的值，成功则直接返回，失败则将当前线程封装为类型为Node.EXCLUSIVE的Node节点后插入到AQS阻塞队列的尾部，并调用LockSupport.park(this)方法挂起自己。

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

（2）当一个线程调用release(int arg)方法时会尝试使用tryRelease操作释放资源，这里是设置状态变量state的值，然后调用LockSupport.unpark(thread)方法激活AQS队列里面被阻塞的一个线程（thread）。被激活的线程则使用tryAcquire尝试，看当前状态变量state的值是否能满足自己的需要，满足则该线程被激活，然后继续向下运行，否则还是会被放入AQS队列并被挂起。

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

需要注意的是，AQS类并没有提供可用的tryAcquire和tryRelease方法，正如AQS是锁阻塞和同步器的基础框架一样，tryAcquire和tryRelease需要由具体的子类来实现。子类在实现tryAcquire和tryRelease时要根据具体场景使用CAS算法尝试修改state状态值，成功则返回true，否则返回false。子类还需要定义，在调用acquire和release方法时state状态值的增减代表什么含义。

7.1.2.2 共享方式

（1）当线程调用acquireShared(int arg)获取共享资源时，会首先使用tryAcquireShared尝试获取资源，具体是设置状态state的值，成功则直接返回，失败则将当前线程封装为类型为Node.SHARED的Node节点后插入到AQS阻塞队列的尾部，并使用LockSupport.park(this)方法挂起自己。

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0)
        doAcquireShared(arg);
}

（2）当一个线程调用releaseShared(int arg)时会尝试使用tryReleaseShared操作释放资源，这里是设置状态变量state的值，然后使用LockSupport.unpark(thread)激活AQS队列里面被阻塞的一个线程（thread）。被激活的线程则使用tryReleaseShared查看当前状态变量state的值是否能满足自己的需要，满足则该线程被激活，然后继续向下运行，否则还是会被放入AQS队列并被挂起。

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        doReleaseShared();
        return true;
    }
    return false;
}

同样需要注意的是，AQS类并没有提供可用的tryAcquireShared和tryReleaseShared方法，正如AQS是锁阻塞和同步器的基础框架一样，tryAcquire和tryRelease需要由具体的子类来实现。子类在实现tryAcquireShared和tryReleaseShared时要根据具体场景使用CAS算法尝试修改state状态值，成功则返回true，否则返回false。

7.1.2.3 入队操作

当一个线程获取锁失败后该线程会被转换为Node节点，然后就会使用enq(final Node node)方法将该节点插入到AQS的阻塞队列。

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;                          // (1)
        if (t == null) { // 初始化
            if (compareAndSetHead(new Node()))  // (2)
                tail = head;
        } else {
            node.prev = t;                      // (3)
            if (compareAndSetTail(t, node)) {   // (4)
                t.next = node;
                return t;
            }
        }
    }
}

在第一次循环中，在队列尾部插入元素时，队列状态如图（default）所示，队列头尾节点都指向null；

执行代码（1）后节点t指向了尾部节点，此时队列状态如图（I）所示；

执行代码（2），使用CAS设置一个哨兵节点为头结点，如果设置成功，则让尾部节点也指向哨兵节点，此时队列状态如图（II）所示。

第一次循环之后只插入了一个哨兵节点，还需要插入node节点。

在第二次循环中，执行代码（1）后节点t指向了哨兵节点，此时队列状态如图（III）所示；

执行代码（3），设置node的前驱结点为哨兵节点，此时队列状态如图（IV）所示；

执行代码（4），通过CAS设置node节点为尾部节点，如果设置成功，则队列状态如图（V）所示；

然后设置哨兵节点的后继结点为node结点，此时队列状态如图（VI）所示。

7.1.2.4 补充

基于AQS实现的锁除了需要重写上面方法以外，还需要重写isHeldExclusively方法，来判断是被当前线程独占还是被共享。

此外，与acquire和release对应的都有一个带有Interruptibly关键字的函数。

区别如下：

不带interruptibly关键字的方法的意思是不对中断进行响应，也就是线程在调用不带interruptibly关键字的方法获取资源时或者获取资源失败被挂起时，其他线程中断了该线程，那么该线程不会因为被中断而抛出异常，它还是继续获取资源或者被挂起，也就是说不对中断进行响应，忽略中断。

而带interruptibly关键字的方法要对中断进行响应，也就是线程在调用带interruptibly关键字的方法获取资源时或者获取资源失败而被挂起时，其他线程中断了该线程，那么该线程会抛出InterruptedException异常而返回。

7.2 ReentrantLock

7.2.1 概述与应用

ReentrantLock是可重入的独占锁，同时只能有一个线程可以获取该锁，其他获取该锁的线程会被阻塞而被放入该锁的AQS阻塞队列中。

示例1：基于AQS实现的不可重入的独占锁

import java.io.Serializable;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
/**
 * @author KHighness
 * @since 2021-05-02
 * @apiNote 不可冲入独占锁
 */
public class ParaKLock implements Lock, Serializable {
    private static final long serialVersionUID = 7379874578553124018L;
    // 独占锁同步器
    private static class ParaKSync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = 6278547169976524823L;
        @Override // 是否锁已经被持有
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }
        @Override // 如果state为0，则尝试获取锁
        protected boolean tryAcquire(int arg) {
            if (Thread.currentThread() == this.getExclusiveOwnerThread())
                throw new IllegalMonitorStateException("不支持锁重入");
            if (compareAndSetState(0, 1)) {
                // 设置独占者线程
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }
        @Override // 尝释放锁，设置state = 0
        protected boolean tryRelease(int arg) {
            assert arg == 1;
            if (getState() == 0)
                throw new IllegalMonitorStateException("当前state不为0");
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }
        // 提供条件变量接口
        Condition newCondition() {
            return new ConditionObject();
        }
    }
    private final ParaKSync sync = new ParaKSync();
    @Override // 一直尝试，失败进入AQS队列
    public void lock() {
        sync.acquire(1);
    }
    @Override // 尝试一次
    public boolean tryLock() {
        return sync.tryAcquire(1);
    }
    @Override // 超时尝试
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return sync.tryAcquireNanos(1, unit.toNanos(time));
    }
    @Override // 解锁
    public void unlock() {
        sync.release(1);
    }
    // 是否被占有
    public boolean isLocked() {
        return sync.isHeldExclusively();
    }
    @Override // 可被打断式加锁
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }
    @Override
    public Condition newCondition() {
        return sync.newCondition();
    }
}

示例2：基于上面自定义独占锁实现生产-消费模型

import lombok.extern.slf4j.Slf4j;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
/**
 * @author KHighness
 * @since 2021-05-03
 * @apiNote 生产-消费模型
 */
@Slf4j(topic = "ProducerConsumerModel")
public class ProducerConsumerModel {
    /** 不可重入独占锁 */
    private final static ParaKLock LOCK = new ParaKLock();
    /** 已满：生产者条件变量 */
    private final static Condition FULL = LOCK.newCondition();
    /** 已空：消费者者条件变量 */
    private final static Condition EMPTY = LOCK.newCondition();
    /** 产品队列 */
    private final static Queue<Character> QUEUE = new LinkedBlockingDeque<>();
    /** 最大容量 */
    private final static int QUEUE_MAX_SIZE = 5;
    /** 随机变量 */
    private final static Random RANDOM = new Random();
    /**
     * 生成随机数字/字母字符
     * ascii  char
     * 48-57  0~9
     * 65-90  A~Z
     * 97-122 a~z
     * @return ascii码字符
     */
    private static Character randomChar() {
        int choice = RANDOM.nextInt(3);
        if (choice == 0)
            return (char) (RANDOM.nextInt(10) + 48);
        else if (choice == 1)
            return (char) (RANDOM.nextInt(26) + 65);
         else
            return (char) (RANDOM.nextInt(26) + 97);
    }
    /**
     * 生产者线程
     */
    static class Producer extends Thread {
        public Producer() {
            super.setName("Producer");
        }
        @Override
        public void run() {
            while (true) {
                // 获取独占锁
                LOCK.lock();
                try {
                    // (1) 如果队列已满，等待
                    while (QUEUE.size() == QUEUE_MAX_SIZE) {
                        FULL.await();
                    }
                    // (2) 生产一个元素到队列
                    Character character = randomChar();
                    TimeUnit.SECONDS.sleep(1);
                    log.debug("生产 => [{}]", character);
                    QUEUE.add(character);
                    // (3) 唤醒消费者线程
                    EMPTY.signalAll();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    // 释放独占锁
                    LOCK.unlock();
                }
            }
        }
    }
    /**
     * 消费者线程
     */
    static class Consumer extends Thread {
        public Consumer() {
            super.setName("Consumer");
        }
        @Override
        public void run() {
            while (true) {
                // 获取独占锁
                LOCK.lock();
                try {
                    // (1) 如果队列为空，等待
                    while (QUEUE.isEmpty()) {
                        EMPTY.await();
                    }
                    // (2) 消费一个元素
                    Character character = QUEUE.poll();
                    TimeUnit.SECONDS.sleep(1);
                    log.debug("消费 => [{}]", character);
                    // (3) 唤醒生产者线程
                    FULL.signalAll();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    LOCK.unlock();
                }
            }
        }
    }
    public static void main(String[] args) {
        Producer producer = new Producer();
        Consumer consumer = new Consumer();
        producer.start();
        consumer.start();
    }
}

7.2.2 非公平锁实现原理

先结合ReentrantLock的内部类Sync 、NonfailSync和AbstractQueuedSynchronizer中的方法进行分析。

对于Sync中的抽象方法lock，公平锁与非公平锁分别有不同的实现：

abstract void lock();

非公平锁NonfairSync的实现如下：

// (一)
final void lock() {
    if (compareAndSetState(0, 1))        
        // 直接CAS，而不去阻塞队列中检查，体现非公平性
        // 成功则设置独占线程为当前线程
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1); // 这个方法在AQS中已经实现好了
}
// (三)
protected final boolean tryAcquire(int acquires) {
    return nonfairTryAcquire(acquires); // 这个方法在Sync中已经实现好了
}

Sync中的nonfairTryAcquire方法：

// (四)
final boolean nonfairTryAcquire(int acquires) {
    // 获取当前进入方法的线程
    final Thread current = Thread.currentThread();
    // 获取state状态值
    int c = getState();
    // 如果还未获得锁
    if (c == 0) {
        // 不去AQS队列检查，直接尝试用CAS获得锁，体现了不公平性
        if (compareAndSetState(0, acquires)) {
            // 成功获取到锁，官宣独占
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    // 如果已经获得了锁并且当前线程是独占线程，表示发生了锁重入
    else if (current == getExclusiveOwnerThread()) {
        // state++
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    // 获取失败，回到调用处
    return false;
}

AbstractQueuedSynchronizer中涉及到的主要方法：

// (二) 
// 以独占模式获取，忽略中断。通过至少调用一次tryAcquire返回成功。
// 否则线程会排队，可能会反复阻塞和解除阻塞，调用tryAcquire直到成功。
public final void acquire(int arg) {
    if (!tryAcquire(arg) && 
        // 尝试直接获取锁，看名字就知道，只是试一试
        // 有可能直接成功了，就不需要进队列排队了
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) 
        // Java编译器会优化，&&前面已经为false，后面的条件不再进行判断
        // 走到这一步说明，获取锁失败，然后执行addWaiter方法，节点设置为独占模式
        // 节点添加完毕后，执行acquireQueued方法，这个方法才是最终的BOSS
        // 这个方法一直循环到返回结果为true，进入if块内的代码执行
        selfInterrupt(); 
}
// (五)
// 添加等待节点至队列末尾
private Node addWaiter(Node mode) {
    // 创建新节点node，模式为EXCLUSIVE(独占)
    Node node = new Node(Thread.currentThread(), mode);
    // 获取尾部节点
    Node pred = tail;
    // 尾部节点非空
    if (pred != null) {
        // 先将node的前驱节点设置为当前尾部节点
        node.prev = pred;
        // 通过CAS操作将node节点设置为tail尾部节点
        if (compareAndSetTail(pred, node)) {
            // 如果CAS成功，则将原tail节点的后继结点设置为当前尾部节点node
            pred.next = node;
            return node;
        }
    }
    // 尾部节点为空，说明没有哨兵节点
    // 这个方法在7.1.2.3已经详述过
    // 需要创建新的哨兵节点，然后插入当前节点
    enq(node); 
    return node;
}
// (六)
// 在队列中循环尝试获取锁
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        // 线程获取锁的过程中是否产生了中断
        boolean interrupted = false;
        for (;;) {
            // 获取当前节点的前驱节点
            final Node p = node.predecessor();
            // 如果前驱节点为head哨兵节点，说明当前节点为第二节点
            // 拥有尝试获取锁的资格
            // 获取锁成功则进入if代码块，剔除当前节点
            if (p == head && tryAcquire(arg)) {
                // 将当前节点设置为头节点，属性thread和prev都设置为null
                // 直接使用setHead而非compareAndSetHead，没有使用CAS
                // 是因为此时已经成功获取到独占锁
                setHead(node);
                // 辅助GC
                p.next = null; 
                failed = false;
                return interrupted;
            }
            // 执行到这里，只有两种情况
            // (1)不符合获取锁的前提，即当前节点不是第二节点
            // (2)tryAcquire失败，即没有抢占到锁
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true; // 产生了中断，设置后永久保留
        }
    } finally {
        // 当tryAcquire为抛出异常的时候，failed为true
        if (failed)
            cancelAcquire(node);
    }
}
// (七)
// 获取失败后应该挂起
// 寻找node的有效前驱，并且将有效前驱状态设置为SIGNAL，返回true代表马上可以阻塞
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    // 前驱节点的等待状态
    int ws = pred.waitStatus;
    // 前驱节点的状态为SIGNAL，状态正常，当前线程需要挂起，自己的唤醒依赖于前驱节点。
    // 如果前驱节点变成了head，并且head的代表线程释放了锁，就会根据这个SIGNAL唤醒自己。
    if (ws == Node.SIGNAL)
        // 返回true，则进入parakAndCheckInterrupt挂起当前线程
        return true;
    // 前驱节点的状态为CANCELLED，说明前驱节点因为超时或者响应了中断而取消排队。
    // 因此需要跨越这些CANCELLED结点，直到找到一个状态<0的节点做自己的前驱。
    if (ws > 0) {
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } 
    // 前驱节点的状态为0，通过CAS将其状态设置为SIGNAL(-1)
    else {
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    // 返回false则不进入parakAndChecKInterrupt继续在acquireQueeud中循环
    // 再次进入这个方法时，便会从第一个if分支返回true
    return false;
}
// (八)
// 挂起并检查中断状态
private final boolean parkAndCheckInterrupt() {
    // 挂起当前线程
    // 唤醒方式：unpark/interrupt/return
    LockSupport.park(this);
    // 返回中断状态，并且清除中断标记
    return Thread.interrupted();
}
// (九)
// 补充中断标记
static void selfInterrupt() { 
    Thread.currentThread().interrupt();
}

非公平抢锁过程总结：

调用ReentrantLock的lock方法，会执行AQS的acquire方法，先执行NonFairSync的tryAcquire方法尝试获取锁，失败则执行AQS的acquireQueued方法在队列中循环获取锁。

tryAcquire：检查state状态值，为0说明还未有线程获取锁，那么自己就直接尝试通过CAS操作将state设置为1，成功则官宣自己独占；不为0且当前线程是独占线程，表示锁重入，那么state+1。以上两种情况成功都返回true，从而结束抢锁过程，其他情况都代表获取失败，返回false。

获取失败后，先执行addWaiter方法将当前线程封装为节点添加到队列末尾，然后进入acquireQueued方法，循环获取直到成功，执行selfInterrupt方法。

acquireQueued：设置一个标志interrupted = false，代表线程获取锁的过程中是否产生了中断，第一个if分支，判断当前节点的前驱节点是否为哨兵节点，是则拥有获取锁的资格，执行tryAcquire尝试获取锁，成功则将前驱节点剔除，并且返回interrupted；往下执行，第二个if分支，说明当前节点不是第二节点，没有获取锁的资格，或者是tryAcquire失败，没有抢占到锁，执行shouldParkAfterFailedAcquire和parkAndCheckInterrupt，执行成功后将interrupted设置为true。shouldParkAfterFailedAcquire返回true则说明获取锁的过程中产生了中断，但是这个中断标记在parkAndCheckInterrupt中清除了，所以需要填补中断标记。

shouldParkAfterFailedAcquire：顾名思义，获取失败后应该挂起，如果当前节点的前驱节点的状态为SIGNAL，那么前驱节点释放锁后会通知自己，自己就可以安心阻塞，并返回true；如果当前节点的前驱节点的状态为CANCELLED即取消排队，那么需要寻找当前节点的有效前驱，即跳过状态为CANCELLED的节点，找到一个状态为SIGNAL的节点；否则当前节点的前驱节点的状态为0，则通过CAS操作将前驱节点的状态设置为SIGNAL，后两种都会返回false，那么会在acquireQueued的for循环中进行下一轮，第二次会按照第一种情况返回true。返回true后，执行parkAndCheckInterrupt。

parkAndCheckInterrupt：先调用LockSupport.park挂起当前线程（有三种唤醒方式：①unpark ②interrupt ③return），那么当前线程等待唤醒（被唤醒的时候会进入acquireQueued的第一个if分支），后调用Thread.interrupted方法返回并重置中断状态。

这里为什么需要清除中断状态呢？知乎： https://www.zhihu.com/question/399039232/answer/1260843911

如果不清除中断状态，也就是返回Thread.currentThread.isInterrupt()方法，那么当前线程挂起后依然是中断状态，那么下一轮循环的时候LockSupport.lock()方法将会失效，使得当前线程持续运行，在acquireQueued()的for循环中空转，导致CPU100%。

下面开始图示详解：

没有竞争时

第一个竞争出现时

Thread-1执行了

CASC尝试将state由0改为1，结果失败
进入tryAcquire逻辑，这时state已经是1，结果仍然失败
接下来进入addWaiter逻辑，构造Node队列
- 图中黄色三角表示该Node的waitStatus状态，其中0为默认正常状态
- Node的创建是懒惰的
- 其中第一个Node称为Dummy（哑元）或哨兵，用来占位，并不关联线程

进入acquireQueued逻辑

acquireQueued会在一个死循环中不断尝试获得锁，失败后进入park阻塞
如果自己是紧邻着head（排第二位），那么再次tryAcquire尝试获取锁，当然这时state仍为1，失败
进入shouldParkAfterFailedAcquire逻辑，将前驱node，即head的waitStatus改为-1，这次返回false

shouldParkAfterFailedAcquire执行完毕回到acquireQueued，再次tryAcquire尝试获取锁，当然这时state仍然为1，失败
当再次进入shouldParkAfterFailedAcquire时，这时因为其前驱node的waitStatus已经是-1，这次返回true
进入parkAndCheckInterrupt，Thread-1 park（灰色表示）

再次有多个线程经历上述过程竞争失败，变成这个样子

Thread-0释放锁

设置exclusiveOwnerThread为null
state = 0

当前队列不为null，并且head的waitStatus，进入unparkSuccessor流程

找到队列中离head最近的一个node（没取消的），unpark恢复其运行，本例中即为Thread-1。

回到Thread-1的acquireQueued流程

如果加锁成功（没有竞争），会设置

exclusiveOwnerThread为Thread-1，state = 1
head指向刚刚Thread-1所在的Node，该node清空Thread
原本的head因为从链表断开，而可被垃圾回收

如果这时候有其他线程来竞争（非公平的体现），例如这时有Thrtead-4来了

如果不巧又被Thread-4占了先

Thread-4被设置为exclusiveOwnerThread，state = 1
Thread-1再次进入acquireQueued流程，获取锁失败，重新进入park阻塞

7.2.3 公平锁实现原理

ReentrantLock-Fair的Sync覆盖方法tryAcquire：

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        // 先检查AQS队列中是否有前驱节点，没有才去竞争
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

AbstractQueuedSynchronizer中涉及到的方法：

// 查询是否有线程等待获取的时间超过当前线程，即查询等待队列中的线程
public final boolean hasQueuedPredecessors() {
    Node t = tail; // 尾节点要么为空，要么为等待
    Node h = head; // 头节点要么为空，要么为哨兵节点
    Node s;
    return h != t && // 头尾节点不同说明队列中有其他节点
        ((s = h.next) == null || //表示队列中没有第二节点
         s.thread != Thread.currentThread()); // 或者队列中第二线程不是此线程
}

7.2.4 可重入原理

ReentrantLock的内部类Sync

// 获取锁
final boolean nonfairTryAcquire(int acquires) {
    // 获取当前线程
    final Thread current = Thread.currentThread();
    // 获取state状态值
    int c = getState();
    // 如果未获得锁
    if (c == 0) {
        // CAS成功后设置独占线程为当前线程即可
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    // 如果已经获得锁，当前线程是独占线程，表示发生了锁重入
    else if (current == getExclusiveOwnerThread()) {
        // state在当前基础上加acquires
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    // 如果已经获得锁，当前线程非独占线程，因为是独占锁，其他线程只能阻塞
    return false;
}
// 释放锁
protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    // 当前线程非独占线程则抛出异常
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    // 当state减为0时锁才释放成功
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

7.2.5 可打断原理

不可打断模式：

// 线程无法获得锁时，进入这个方法
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                // 还是需要获得锁后，才能返回打断状态
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                // 如果是因为interrupt被唤醒，返回打断状态为true
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}
private final boolean parkAndCheckInterrupt() {
    // 如果打断标记已经是true，则park会失效
    LockSupport.park(this);
    // interrupted会清除打断标记
    return Thread.interrupted();
}
// 重新产生一次中断
static void selfInterrupt() {
    Thread.currentThread().interrupt();
}

可打断模式：

public final void acquireInterruptibly(int arg)
    throws InterruptedException {
    if (Thread.interrupted())
        throw new InterruptedException();
    // 如果没有获得到锁，进入
    if (!tryAcquire(arg))
        doAcquireInterruptibly(arg);
}
// 可打断锁的获取流程
private void doAcquireInterruptibly(int arg)
    throws InterruptedException {
    final Node node = addWaiter(Node.EXCLUSIVE);
    boolean failed = true;
    try {
        for (;;) {
            final Node p = node.predecessor();
            if (p == head && tryAcquire(arg)) {
                setHead(node);
                p.next = null; // help GC
                failed = false;
                return;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                // 在park过程中如果被interrupt会进入此
                // 这时候抛出异常，而不会再次进入for循环
                throw new InterruptedException();
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

7.2.6 条件变量实现原理

每个条件变量其实就对应着一个等待队列，其实现类是ConditionObject。

内部属性：

// 成员变量
private transient Node firstWaiter; // 首节点
private transient Node lastWaiter;  // 尾节点
// 常量
private static final int REINTERRUPT =  1; // 从等待状态切换为中断状态
private static final int THROW_IE    = -1; // 抛出异常标识

await流程

// 向队列中添加节点并返回
private Node addConditionWaiter()
// 释放节点持有的锁
final int fullyRelease(Node node)
// 判断节点是否在同步队列中
final boolean isOnSyncQueue(Node node)
// 检查线程是否中断，如果是则终止Condition状态并加入到同步队列
private int checkInterruptWhileWaiting(Node node)
// 操作节点去申请锁
final boolean acquireQueued(final Node node, int arg)
// 清理等待队列中无效节点
private void unlinkCancelledWaiters()
// 处理线程中断情况
private void reportInterruptAfterWait(int interruptMode)

开始Thread-0持有锁，调用await，进入ConditionObject的addConditionWaiter流程。

创建新的Node状态为-2（Node.CONDITION），关联Thread-0，加入等待队列尾部。

接下来进入AQS的fullRelease流程，释放同步器上的锁

unpark AQS队列中的下一个节点，竞争锁，假设没有其他竞争线程，那么Thread-1竞争成功

park阻塞Thread-0

signal流程

// 唤醒线程入口
public final void signal()
// 判定当前线程是否持有锁
protected boolean isHeldExclusively()
// 唤醒first节点
private void doSignal(Node first) 
// 转换节点状态
final boolean transferForSignal(Node node)

假设Thread-1要来唤醒Thread-0

进入ConditionObject的doSignal流程，取得等待队列中第一个Node，Thread-0所在Node

执行transferForSignal流程，将该Node加入到AQS队列尾部，将Thread-0的waitStatus改为0，Thread-3的waitStatus改为-1

Thread-1释放锁，进入unlock流程。

7. 3 ReentrantReadWriteLock

7.3.1 概述与应用

当读操作远远高于写操作时，这时候使用读写锁让读-读可以并发，提高性能。

读锁不支持条件变量
重入时升级不支持：持有读锁的情况下去获取写锁，会导致写锁永久等待
重入时降级支持：持有写锁的情况下去获取读锁

示例1：数据容器

import lombok.extern.slf4j.Slf4j;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
 * @author KHighness
 * @since 2021-05-05
 */
@Slf4j(topic = "DataContainer")
class DataContainer {
    private Object data;
    private final static Random RANDOM = new Random();
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final ReentrantReadWriteLock.ReadLock readLock = lock.readLock();
    private final ReentrantReadWriteLock.WriteLock writeLock = lock.writeLock();
    private static Character randomChar() {
        int choice = RANDOM.nextInt(3);
        if (choice == 0)
            return (char) (RANDOM.nextInt(10) + 48);
        else if (choice == 1)
            return (char) (RANDOM.nextInt(26) + 65);
        else
            return (char) (RANDOM.nextInt(26) + 97);
    }
    public void read() {
        log.debug("获取读锁...");
        readLock.lock();
        try {
            log.debug("读取数据 => [{}]", data);
        } finally {
            log.debug("释放读锁...");
            readLock.unlock();
        }
    }
    public void write() {
        log.debug("获取写锁...");
        writeLock.lock();
        try {
            log.debug("写入数据 => [{}]", data = randomChar());
        } finally {
            log.debug("释放写锁...");
            writeLock.unlock();
        }
    }
}

示例2：文档中的应用示例

import java.util.Random;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
 * @author KHighness
 * @since 2021-05-05
 */
class CachedData {
    Object data;
    // 是否有效，如果失效，需要重新计算data
    volatile boolean cacheValid;
    final static Random RANDOM = new Random();
    final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    void processCachedData() {
        lock.readLock().lock();
        if (!cacheValid) {
            // 不支持锁升级，获取写锁钱必须释放读锁
            lock.readLock().unlock();
            lock.writeLock().lock();
            try {
                // 双重检查，判断是否其他线程已经获取了读锁更新缓存，避免重复更新
                if (!cacheValid) {
                    data = write();
                    cacheValid = true;
                }
                // 降为读锁，释放写锁，让其他线程读取缓存
                lock.readLock().lock();
            } finally {
                lock.writeLock().unlock();
            }
        }
        // 使用数据，释放读锁
        try {
            use(data);
        } finally {
            lock.readLock().unlock();
        }
    }
}

示例3：Redis的Java缓存

import lombok.extern.slf4j.Slf4j;
import redis.clients.jedis.Jedis;
import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.locks.ReentrantReadWriteLock;
/**
 * @author KHighness
 * @since 2021-05-05
 */
@Slf4j(topic = "GenericRedisDemo")
public class GenericRedisDemo {
    public static void main(String[] args) {
        GenericCached cached = new GenericCached();
        cached.update(new User(1, "KHighness", "parakovo@gmail.com"));
        cached.update(new User(2, "RubbishK", "rubbish@gmail.com"));
        cached.update(new User(3, "FlowerK", "flower@gmail.com"));
        log.debug(cached.query(User.class, 1).toString());
        log.debug(cached.query(User.class, 1).toString());
        log.debug(cached.query(User.class, 2).toString());
    }
}
class User {
    private Integer id;
    private String name;
    private String email;
    public User(Integer id, String name, String email) {
        this.id = id;
        this.name = name;
        this.email = email;
    }
}
interface Generic {
    String update(Object obj);
    Map<String, String> query(Class<?> clazz, Integer id);
}
class GenericRedis implements Generic {
    private final Jedis jedis = new Jedis("127.0.0.1", 6379);
    public String update(Object obj) {
        Class<?> clazz = obj.getClass();
        Field[] declaredFields = clazz.getDeclaredFields();
        Map<String, String> map = new HashMap<>();
        Integer id = null;
        try {
            Field idField = clazz.getDeclaredField("id");
            idField.setAccessible(true);
            id = (Integer) idField.get(obj);
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
        }
        for (Field field : declaredFields) {
            field.setAccessible(true);
            try {
                map.put(field.getName(), field.get(obj).toString());
            } catch (IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        return jedis.hmset(clazz.getSimpleName() + ":" + id, map);
    }
    public Map<String, String> query(Class<?> clazz, Integer id) {
        return jedis.hgetAll(clazz.getSimpleName() + ":" + id);
    }
}
// 装饰器模式，强化
@Slf4j(topic = "GenericCached")
class GenericCached implements Generic {
    private final GenericRedis redis = new GenericRedis();
    private final Map<Key, Map<String, String>> cache = new HashMap<>();
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    static class Key {
        Class<?> clazz;
        Integer id;
        public Key(Class<?> clazz, Integer id) {
            this.clazz = clazz;
            this.id = id;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Key key = (Key) o;
            return Objects.equals(clazz, key.clazz) && Objects.equals(id, key.id);
        }
        @Override
        public int hashCode() {
            return Objects.hash(clazz, id);
        }
        @Override
        public String toString() {
            return "Key[" + "clazz=" + clazz + ", id=" + id + ']';
        }
    }
    // 先更新redis再清除缓存，需要加写锁
    @Override
    public String update(Object obj) {
        String res = null;
        lock.writeLock().lock();
        try {
            // 更新redis
            res = redis.update(obj);
            // 清除缓存
            Field idField = obj.getClass().getDeclaredField("id");
            idField.setAccessible(true);
            Key key = new Key(obj.getClass(), (int) idField.get(obj));
            if (cache.remove(key) != null) {
                log.debug("清除缓存: {}", key);
            }
        } catch (IllegalAccessException | NoSuchFieldException e) {
            e.printStackTrace();
        } finally {
            lock.writeLock().unlock();
        }
        return res;
    }
    // 先查询缓存，需要加读锁；
    // 没有则查询redis添加到缓存，需要加写锁
    @Override
    public Map<String, String> query(Class<?> clazz, Integer id) {
        Key key = new Key(clazz, id);
        Map<String, String> res = null;
        lock.readLock().lock();
        // 查询缓存
        try {
            if (cache.containsKey(key)) {
                log.debug("缓存查询: {}", res = cache.get(key));
                return res;
            }
        } finally {
            lock.readLock().unlock();
        }
        lock.writeLock().lock();
        // 查询数据库，添加到缓存
        try {
            // 双重检查
            if (cache.containsKey(key)) {
                log.debug("缓存查询: {}", res = cache.get(key));
                return res;
            }
            cache.put(key, res = redis.query(clazz, id));
            log.debug("添加缓存: {}", key);
        } finally {
            lock.writeLock().unlock();
        }
        return res;
    }
}

7.3.2 内部类Sync概述

读写锁的内部维护了一个ReadLock和一个WriteLock，它们依赖Sync实现具体功能，Sync继承自AQS，并且也提供了公平锁和非公平锁的实现。

AQS中只维护了一个state状态，那么如何表示读和写两种状态呢？

Sync巧妙地使用state的高16位表示读获取到读锁的次数，低16位表示获取到写锁的线程的可重入次数。

static final int SHARED_SHIFT   = 16;
// 共享锁（读锁）状态单位值65536
static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
// 共享锁线程最大个数65535
static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
// 排它锁（写锁）掩码
static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
/** 返回读锁线程数  */
static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
/** 返回写锁可重入个数 */
static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }

Sync的成员：

firstReader：记录第一个获取到读锁的线程
firstReaderHoldCount：记录第一个获取到读锁的线程获取读锁的可重入次数
cacheHoldCounter：记录最后一个获取读锁的线程获取读锁的可重入次数
readHolds：存放除去第一个获取锁线程外的其他线程获取读锁的可重入次数。

static final class HoldCounter {
    int count = 0;
    // 线程ID
    final long tid = getThreadId(Thread.currentThread());
}
static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> {
    public HoldCounter initialValue() {
        return new HoldCounter();
    }
}

7.3.3 写锁的获取与释放

在ReentrantReadWriteLock中写锁使用WriteLock实现。

获取

写锁是个独占锁，某时只有一个线程可以获取该锁。

如果当前没有线程获取到读锁和写锁，则当前线程可以获取到写锁然后返回。

如果当前已经有线程获取到读锁和写锁，则当前请求写锁的线程会被阻塞挂起。

另外，写锁是可重入锁，再次获取只是简单地把可重入次数加1后直接返回。

（1）WriteLock的lock方法：

public void lock() {
    sync.acquire(1);  // 继承自AQS
}

（2）AbstractQueuedSynchronizer的acquire方法：

public final void acquire(int arg) {
    if (!tryAcquire(arg) && // Sync重写
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

（3）Sync重写的tryAcquire方法：

protected final boolean tryAcquire(int acquires) {
    Thread current = Thread.currentThread();
    int c = getState();
    int w = exclusiveCount(c);
    // (1) c != 0说明读锁或者写锁已经被某线程获取
    if (c != 0) {
        // (2) w = 0说明已经有线程获取了读锁，w != 0并且当前线程不是写锁拥有者，则返回false
        if (w == 0 || current != getExclusiveOwnerThread())
            return false;
        // (3) 说明当前线程获取了写锁，判断可重入次数
        if (w + exclusiveCount(acquires) > MAX_COUNT)
            throw new Error("Maximum lock count exceeded");
        // （4）设置可重入次数(+1)
        setState(c + acquires);
        return true;
    }
    // (5) c == 0说明第一个写线程获取写锁
    if (writerShouldBlock() ||
        !compareAndSetState(c, c + acquires))
        return false;
    setExclusiveOwnerThread(current);
    return true;
}

（4）writerShouldBlock方法：

公平锁NonfairSync实现：return false，即抢占式执行CAS尝试获取写锁，获取成功则设置当前锁的持有者为当前线程并返回true。
非公平锁FairSync的实现：return hashQueuedPredecessors()，判断当前线程节点是否有前驱结点，有则放弃获取写锁的权限，直接返回false。

释放

如果当前线程持有该所，unlock会让该线程对该线程持有的AQS状态值减1，如果减1后当前状态值为0则当前线程会释放该锁，否则仅仅减1而已。

如果当前线程没有持有该锁而调用unlock抛出IllegalMonitorStateException异常。

（1）WriteLock的unlock方法：

public void unlock() {
    sync.release(1);  // 继承自AQS
}

（2）AbstractQueuedSynchronizer的release方法：

public final boolean release(int arg) {
    if (tryRelease(arg)) { // Sync重写
        Node h = head;
        // 激活阻塞队列中的一个线程
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

（3）Sync重写的tryRelease方法：

protected final boolean tryRelease(int releases) {
    // (1) 检查当前线程是否为锁拥有者
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    // (2) 获取可重入值，这里没有考虑高16位，因为获取写锁时读锁状态值肯定为0
    int nextc = getState() - releases;
    boolean free = exclusiveCount(nextc) == 0;
    // (3) 如果写锁可重入值为0则释放锁，否则只是简单更新状态值
    if (free)
        setExclusiveOwnerThread(null);
    setState(nextc);
    return free;
}

7.3.4 读锁的获取与释放

在ReentrantReadWriteLock中读锁使用ReadLock实现。

获取

如果当前没有线程持有写锁，则当前线程可以获取锁，AQS的状态值state的高16位的值会加1，然后方法返回。

如果其他一个线程持有锁，则当前线程会阻塞。

（1）Read的lock方法：

public void lock() {
    sync.acquireShared(1); // 继承自AQS
}

（2）AbstractQueuedSynchronizer的acquireShared方法：

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0) // Sync重写
        doAcquireShared(arg);
}

（3）Sync重写的tryAcquireShared方法：

protected final int tryAcquireShared(int unused) {
    // (1) 获取当前线程
    Thread current = Thread.currentThread();
    // (2) 获取当前状态值
    int c = getState();
    // (3) 判断当前写锁是否被占用
    if (exclusiveCount(c) != 0 && getExclusiveOwnerThread() != current)
        return -1;
    // (4) 获取读锁计数
    int r = sharedCount(c);
    // (5) 尝试获取锁，多个度线程只有一个会成功，失败的进入fullTryAcquireShared进行重试
    if (!readerShouldBlock() &&
        r < MAX_COUNT &&
        compareAndSetState(c, c + SHARED_UNIT)) {
        // (6) 如果当前线程是第一个获取锁的线程
        if (r == 0) {
            firstReader = current;
            firstReaderHoldCount = 1;
        } 
        // (7) 如果当前线程是第一个获取读锁的线程
        else if (firstReader == current) {
            firstReaderHoldCount++;
        } else {
            // (8) 记录最后一个获取读锁的线程或者记录其他线程读锁的可重入个数
            HoldCounter rh = cachedHoldCounter;
            if (rh == null || rh.tid != getThreadId(current))
                cachedHoldCounter = rh = readHolds.get();
            else if (rh.count == 0)
                readHolds.set(rh);
            rh.count++;
        }
        return 1;
    }
    // (9) 自旋获取
    return fullTryAcquireShared(current);
}

（4）readerShouldBlock方法：

公平锁NonfairStnc实现：return apparentlyFirstQueuedIsExclusive()，实现如下：
上述代码的作用是，如果队列里面存在一个元素，咋判断第一个元素是不是正在尝试获取写锁，如果不是，则当前线程判断当前获取读锁的线程是否到达了最大值，最后执行CAS操作将AQS状态值的高16位值加1。
```
final boolean apparentlyFirstQueuedIsExclusive() {
 Node h, s;
 return (h = head) != null &&
     (s = h.next)  != null &&
     !s.isShared()         &&
     s.thread != null;
}
```
非公平锁FairSync的实现：return hashQueuedPredecessors()，判断当前线程节点是否有前驱结点，有则放弃获取读锁的权限。

（5）Sync的fullTryAcquireShared方法：

final int fullTryAcquireShared(Thread current) {
    HoldCounter rh = null;
    for (;;) {
        int c = getState();
        if (exclusiveCount(c) != 0) {
            if (getExclusiveOwnerThread() != current)
                return -1;
            // else we hold the exclusive lock; blocking here
            // would cause deadlock.
        } else if (readerShouldBlock()) {
            // Make sure we're not acquiring read lock reentrantly
            if (firstReader == current) {
                // assert firstReaderHoldCount > 0;
            } else {
                if (rh == null) {
                    rh = cachedHoldCounter;
                    if (rh == null || rh.tid != getThreadId(current)) {
                        rh = readHolds.get();
                        if (rh.count == 0)
                            readHolds.remove();
                    }
                }
                if (rh.count == 0)
                    return -1;
            }
        }
        if (sharedCount(c) == MAX_COUNT)
            throw new Error("Maximum lock count exceeded");
        if (compareAndSetState(c, c + SHARED_UNIT)) {
            if (sharedCount(c) == 0) {
                firstReader = current;
                firstReaderHoldCount = 1;
            } else if (firstReader == current) {
                firstReaderHoldCount++;
            } else {
                if (rh == null)
                    rh = cachedHoldCounter;
                if (rh == null || rh.tid != getThreadId(current))
                    rh = readHolds.get();
                else if (rh.count == 0)
                    readHolds.set(rh);
                rh.count++;
                cachedHoldCounter = rh; // cache for release
            }
            return 1;
        }
    }
}

释放

（1）ReadLock的unlock方法：

public void unlock() {
    sync.releaseShared(1); // 继承自AQS
}

（2）AbstractQueuedSynchronizer的releaseShared方法：

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        doReleaseShared();
        return true;
    }
    return false;
}

（3）Sync的tryReleaseShared方法：

protected final boolean tryReleaseShared(int unused) {
    Thread current = Thread.currentThread();
    // (1) 判断当前线程是否为第一个获取读锁的线程
    if (firstReader == current) {
        // 可保证firstReaderHoldCount > 0
        // 可重入次数为1，清空读锁第一线程
        if (firstReaderHoldCount == 1) 
            firstReader = null;
        // 否则，可重入次数减一
        else
            firstReaderHoldCount--;
    } 
    // (2) 那么维护最后一个获取读锁的线程的可重入次数
    else {
        // 最后一个获取读锁的线程的可重入次数
        HoldCounter rh = cachedHoldCounter;
        // 初始化ch
        if (rh == null || rh.tid != getThreadId(current))
            rh = readHolds.get();
        int count = rh.count;
        // 如果可重入次数小于等于1，说明当前线程没有持有读锁，ch是get()成的
        if (count <= 1) {
            readHolds.remove();
            if (count <= 0)
                throw unmatchedUnlockException();
        }
        // 执行到这里，说明当前线程持有读锁中，可重入次数减一
        --rh.count;
    }
    // (3) 修改同步状态，循环直到自己的读计数-1，CAS更新成功
    for (;;) {
        int c = getState();
        int nextc = c - SHARED_UNIT;
        if (compareAndSetState(c, nextc))
            // 状态值=0释放成功
            return nextc == 0;
    }
}

7.4 StampedLock

StampedLock是JDK1.8新增的一个锁，该锁提供了三种模式的读写控制，但是不支持条件变量和锁重入。

当调用获取锁的系列函数时，会返回一个long型的变量，称为戳记(stamp)，代表了锁的状态。其中try系列获取锁的函数，当获取失败后会返回为0的stamp值。当调用释放锁和转换锁的方法时需要传入获取锁时返回的stamp值。

StampedLock提供了三种读写模式的锁：

写锁writeLock：是一个独占锁，任意时刻只有一个线程可以获取到该锁，当一个线程获取该锁后，其他请求读锁和写锁的线程必须等待，这类似于ReentrantReadWriteLock的写锁（不同的是这里的写锁是不可重入锁）；当目前没有线程持有读锁或者写锁时才可以获取到该锁。请求该锁成功后会返回一个stamp变量用来表示该锁的版本，当解释该锁时需要调用unlockWrite方法并传递获取锁时的stamp参数。并且它提供了非阻塞的tryWriteLock方法。
```
long stamp = lock.writeLock();
lock.unlockWrite(stamp);
```
悲观读锁readLock：是一个共享锁，在没有线程获取独占写锁的情况下，多个线程可以同时获取该锁。如果已经有线程持有写锁，则其他线程请求获取该锁会被阻塞，这类似于ReentrantReadWriteLock的读锁（不同的是这里的读锁是不可重入锁）。这里说的悲观是指具体操作数据前会悲观地认为其他线程可以要对自己操作的数据进行修改，所以需要先对数据加锁，这是在读少写多的情况下的一种考虑。请求该所成功后会返回一个stamp变量用来表示该锁的版本，当释放该锁时需要调用unlockRead方法并传递stamp参数。并且它提供了非阻塞的tryReadLock方法。
```
long stamp = lock.readLock();
lock.unlockRead(stamp);
```
乐观读锁tryOptimisticRead：它是相对于悲观锁来说的，在操作数据前并没有通过CAS设置锁的状态，仅仅通过位运算测试。如果当前没有线程持有写锁，则简单地返回一个非0的stamp值。获取该stamp后在具体操作数据前还需要调用validate方法验证该stamp是否已经不可用，也就是看当调用tryOptimisticRead返回stamp后到当前时间期间是否有其他线程持有了写锁，如果是则validate会返回0，否则就可以使用该stamp版本的锁对数据进行操作。由于tryOptimisticRead并没有使用CAS设置锁状态，所以不需要显式地释放该锁。该锁的一个特点是适用于读多写少的场景，因为获取读锁只是使用位操作进行检验，不涉及CAS操作，所以效率上会高很多，但是同时由于没有使用真正的锁，在保证数据一致性上需要复制一份要操作的变量到方法栈，并且在操作数据时可能其他写线程已经修改了数据，而我们操作的是方法栈里面的数据，也就是一个快照，所以最多返回的不是最新的数据，但是一致性还是得到保障的。
```
long stamp = lock.tryOptimisticRead();
if (!lock.validate(stamp)) {
// 锁升级
}
```

示例：笛卡尔二维点

import java.util.concurrent.locks.StampedLock;
/**
 * @author KHighness
 * @since 2021-05-05
 */
public class Point {
    /**
     * 横坐标
     */
    private double x;
    /**
     * 纵坐标
     */
    private double y;
    /**
     * 锁实例
     */
    private final StampedLock lock = new StampedLock();
    /**
     * 移动点到新位置
     * <p>使用排它锁-写锁</p>
     * @param deltaX 横坐标变化值
     * @param deltaY 纵坐标变化值
     */
    void move(double deltaX, int deltaY) {
        long stamp = lock.writeLock();
        try {
            x += deltaX;
            y += deltaY;
        } finally {
            lock.unlockWrite(stamp);
        }
    }
    /**
     * 计算当前位置到原点的距离
     * <p>使用乐观锁读</p>
     * @return 距离原点的距离
     */
    double distanceFromOrigin() {
        long stamp = lock.tryOptimisticRead();
        double currentX = x, currentY = y;
        // 检查获取stamp后，锁是否被其他写线程排他性抢占
        if (!lock.validate(stamp)) {
            // 如果被抢占则进行锁升级，获取悲观读锁
            stamp = lock.readLock();
            try {
                currentX = x;
                currentY = y;
            } finally {
                lock.unlockRead(stamp);
            }
        }
        return Math.sqrt(currentX * currentX + currentY * currentY);
    }
    /**
     * 如果当前位置在原点则移动至新位置
     * <p>使用悲观锁获取读锁，并尝试转换为写锁</p>
     * @param newX 新位置的横坐标
     * @param newY 新位置的纵坐标
     */
    void moveIfAtOrigin(double newX, double newY) {
        // 这里可以用乐观锁读替换
        long stamp = lock.readLock();
        try {
            while (x == 0.0 && y == 0.0) {
                // 尝试将读锁升级为写锁
                long ws = lock.tryConvertToWriteLock(stamp);
                // 升级成功，则更换戳记，更新坐标，退出循环
                if (ws != 0L) {
                    stamp = ws;
                    x = newX;
                    y = newY;
                    break;
                } 
                // 升级失败，则释放读锁，显式获取写锁，循环重试
                else {
                    lock.unlockRead(stamp);
                    stamp = lock.writeLock();
                }
            }
        } finally {
            // 释放锁
            lock.unlockWrite(stamp);
        }
    }
}