static final class Node {
    static final Node SHARED = new Node();
    static final Node EXCLUSIVE = null;
    static final int CANCELLED =  1;
    static final int SIGNAL    = -1;
    static final int CONDITION = -2;
    static final int PROPAGATE = -3;
    volatile int waitStatus;
    // prev和next构建的双向链表
    volatile Node prev;
    volatile Node next;
    // 持有的thread。如果是head节点，这里为null
    volatile Thread thread;
    Node nextWaiter;

    final boolean isShared() {
        return nextWaiter == SHARED;
    }

    // 返回prev节点，如果prev = null，抛出NullPointerException
    final Node predecessor() throws NullPointerException {
        Node p = prev;
        if (p == null)
            throw new NullPointerException();
        else
            return p;
    }

    Node() {    // Used to establish initial head or SHARED marker
    }

    Node(Thread thread, Node mode) {     // Used by addWaiter
        this.nextWaiter = mode; // 设定模式
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { // Used by Condition
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}

private Node addWaiter(Node mode) { // 这里的mode是指资源共享方式，有EXCLUSIVE和SHARED
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) { // 如果pred为空，说明该AQS还没有被初始化
            node.prev = pred;
            if (compareAndSetTail(pred, node)) { // 将Tail移动到新节点成功过后
                pred.next = node; // 接在CLH队尾 
                return node;
            }
        }
        enq(node); // 两种情况会进入到这里
        return node;
    }

private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // 还没有初始化
                if (compareAndSetHead(new Node())) // CAS初始化Head的值，不一定会成功
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) { // CAS更新Tail的值，不一定会成功
                    t.next = node;
                    return t;
                }
            }
        }
    }

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

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

public final boolean hasQueuedPredecessors() {
        // The correctness of this depends on head being initialized
        // before tail and on head.next being accurate if the current
        // thread is first in queue.
        Node t = tail; // Read fields in reverse initialization order
        Node h = head;
        Node s;
        return h != t &&
            ((s = h.next) == null || s.thread != Thread.currentThread());
    }

// 标识Node时SHARED还是1EXCLUSIVE
private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // Try the fast path of enq; backup to full enq on failure
    // 下面这一串enq里都能做，只是这里提供一个快速路径，成功就不用进enq了
    Node pred = tail;
    if (pred != null) { // 如果Tail不为空，直接加在尾部就好
        node.prev = pred;
        if (compareAndSetTail(pred, node)) { // 必须要先保证尾部已经移动成功了，才能进行后续步骤，因为可能发生两个节点同时竞争一个Tail
            pred.next = node; // 满足上面条件后，就可以保证这里只会有本线程会修改了
            return node;
        }
    }
    enq(node); // 两种情况进入这里：1. Tail为null   2. compareAndSetTail竞争Tail失败
    return node;
}

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; // 不然会进入到cancelAcquire
                return interrupted; // 未被打断
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt()) // shouldParkAfterFailedAcquire改变前一个结点的waitStatus；parkAndCheckInterrupt当前线程挂起
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node); // 中断排队后，进入这里，需要将节点从CLH中移除
    }
}

private void cancelAcquire(Node node) {
    // Ignore if node doesn't exist
    if (node == null)
        return;

    node.thread = null; // 先将node中的thread清空

    // Skip cancelled predecessors
    Node pred = node.prev;
    while (pred.waitStatus > 0) // 往上找，找到一个非cancel状态的节点，和他连接起来
        node.prev = pred = pred.prev;

    Node predNext = pred.next;

    // Can use unconditional write instead of CAS here.
    // After this atomic step, other Nodes can skip past us.
    // Before, we are free of interference from other threads.
    node.waitStatus = Node.CANCELLED; // 将自己的waitStatus改成Node.CANCELLED

    // 如果自己是Tail节点的话，只需要将Tail移动到上面一个节点就可以了
    if (node == tail && compareAndSetTail(node, pred)) {
        compareAndSetNext(pred, predNext, null); // 将指向自己的引用设为null
    } else {
        // If successor needs signal, try to set pred's next-link
        // so it will get one. Otherwise wake it up to propagate.
        int ws;
        if (pred != head &&
            ((ws = pred.waitStatus) == Node.SIGNAL ||
            (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
            pred.thread != null) {
            Node next = node.next;
            if (next != null && next.waitStatus <= 0)
                compareAndSetNext(pred, predNext, next); // 将前后节点连接起来
        } else {
            unparkSuccessor(node);
        }
        node.next = node; // help GC
    }
}

public final boolean release(int arg) {
    if (tryRelease(arg)) { // 看看是否能被释放成功
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h); // 唤醒park中的后继者
        return true;
    }
    return false;
}

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0) // 将status改为0，标识已经释放了
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next; // 获取到successor
    if (s == null || s.waitStatus > 0) { // 如果successor为空或者已经被cancel了，需要去寻找最近的未cancel节点
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev) // 从尾往前遍历
            if (t.waitStatus <= 0) // 如果status不是cancel
                s = t; // 记录下来，for循环结束后s就是离head最近的非cancel节点了
    }
    if (s != null)
        LockSupport.unpark(s.thread); // unpark节点
    }

protected final boolean tryRelease(int releases) {
    int c = getState() - releases; // 计算新的state值
    if (Thread.currentThread() != getExclusiveOwnerThread()) // 判断当前线程是不是AQS当中记录的锁拥有者线程，这里一般都不会有问题
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) { // 因为可重入锁的原因，所以只有当state释放到0的时候才能释放成功
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

public final void acquireShared(int arg) {
    if (tryAcquireShared(arg) < 0) // 尝试获取锁，返回小于0，表示没有资源用光了
        doAcquireShared(arg); // 比较类似独占锁的acquireQueue
}

private void doAcquireShared(int arg) {
    final Node node = addWaiter(Node.SHARED); // 添加Shared节点
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();
            if (p == head) { // 需要轮到才有资格
                int r = tryAcquireShared(arg); // 尝试获取，获取成功的话返回的r代表共享锁剩余的资源量。失败的话，为负数。
                if (r >= 0) { // 获取锁成功了，需要对CLH队列操作
                    setHeadAndPropagate(node, r); // 将当前节点设置成head，并要开始进行链式唤醒
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

private void setHeadAndPropagate(Node node, int propagate) {
    Node h = head; // 记录老的head节点，是为了后面对老head的waitStatus进行判断
    setHead(node); // 移动head
    if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0) { // 这里的条件比较复杂，主要是为了判断是否需要唤醒自己的successor
        Node s = node.next;
        if (s == null || s.isShared()) // 需要时SHARED节点才行
            doReleaseShared(); // 这里面定义了对successor进行链式唤醒的具体流程
    }
}

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

private void setHeadAndPropagate(Node node, int propagate) {
    // Node h = head;  切换点一
    setHead(node); 
    if (propagate > 0 && node.waitStatus != 0) { // 切换点二
        Node s = node.next;
        if (s == null || s.isShared())
            unparkSuccessor(node); // 切换点三
    }
}

import java.util.concurrent.Semaphore;

public class TestSemaphore {

   private static Semaphore sem = new Semaphore(0);

   private static class Thread1 extends Thread {
       @Override
       public void run() {
           sem.acquireUninterruptibly();
       }
   }

   private static class Thread2 extends Thread {
       @Override
       public void run() {
           sem.release();
       }
   }

   public static void main(String[] args) throws InterruptedException {
       for (int i = 0; i < 10000000; i++) {
           Thread t1 = new Thread1();
           Thread t2 = new Thread1();
           Thread t3 = new Thread2();
           Thread t4 = new Thread2();
           t1.start();
           t2.start();
           t3.start();
           t4.start();
           t1.join();
           t2.join();
           t3.join();
           t4.join();
           System.out.println(i);
       }
   }
}

private void doReleaseShared() {
        for (;;) {
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            
                    unparkSuccessor(h);
                }
                else if (ws == 0 &&
                         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE)) // 主要是这里
                    continue;                
            }
            if (h == head)                   
                break;
        }
    }

Node h = head; // 在更新Head之前，先将老Head保留下来
setHead(node); // 移动head
if (propagate > 0 || h == null || h.waitStatus < 0 // 判断老Head的状态，是否在我被唤醒的时候，有别的线程在老Head上释放了资源，Node.Propagate值为-3，满足 < 0 的条件，进入链式唤醒。 
    ......

if (propagate > 0 || h == null || h.waitStatus < 0 ||
        (h = head) == null || h.waitStatus < 0)

(h = head) == null || h.waitStatus < 0

class BoundedBuffer {

    final Lock lock = new ReentrantLock();
    // condition 实例依赖于 lock 实例
    final Condition notFull = lock.newCondition();
    final Condition notEmpty = lock.newCondition();

    final Object[] items = new Object[100];

    int putPtr, takePtr, count;

    public void put(Object x) throws InterruptedException {
        lock.lock();
        try {
            //  put 时判断是否已经满了
            // 则线程在 notFull 条件上排队阻塞
            while (count == items.length) {
                notFull.await();
            }
            items[putPtr] = x;
            if (++putPtr == items.length) {
                putPtr = 0;
            }
            ++count;
            // put 成功之后，队列中有元素
            // 唤醒在 notEmpty 条件上排队阻塞的线程
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    public Object take() throws InterruptedException {
        lock.lock();
        try {
            // take 时，发现为空
            // 则线程在 notEmpty 的条件上排队阻塞
            while (count == 0) {
                notEmpty.await();
            }
            Object x = items[takePtr];
            if (++takePtr == items.length) {
                takePtr = 0;
            }
            --count;
            // take 成功，队列不可能是满的
            // 唤醒在 notFull 条件上排队阻塞的线程
            notFull.signal();
            return x;
        } finally {
            lock.unlock();
        }
    }
}

public final void await() throws InterruptedException {
    // 响应中断
    if (Thread.interrupted())
        throw new InterruptedException();
    // 添加到条件队列尾部（等待队列）
    // 内部会创建 Node.CONDITION 类型的 Node
    Node node = addConditionWaiter();
    // 释放当前线程获取的锁（通过操作 state 的值）
    // 释放了锁就会被阻塞挂起
    int savedState = fullyRelease(node);
    int interruptMode = 0;
    // 节点已经不在同步队列中，则调用 park 让其在等待队列中挂着
    while (!isOnSyncQueue(node)) {
        // 调用 park 阻塞挂起当前线程
        LockSupport.park(this);
        // 说明 signal 被调用了或者线程被中断，校验下唤醒原因
        // 如果因为终端被唤醒，则跳出循环
        if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
            break;
    }
    // while 循环结束， 线程开始抢锁
    if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
        // 如果没有标记中断，acquireQueued是不会返回true的
        interruptMode = REINTERRUPT;
    if (node.nextWaiter != null) // clean up if cancelled
        unlinkCancelledWaiters();
    // 统一处理中断的
    if (interruptMode != 0)
        reportInterruptAfterWait(interruptMode);
}

private Node addConditionWaiter() {
    Node t = lastWaiter; // 获取到lastWaiter
    
    // 如果lastWaiter是一个Cancel节点，那么需要去清除掉所有的Cancel节点
    if (t != null && t.waitStatus != Node.CONDITION) {
        unlinkCancelledWaiters();
        t = lastWaiter;
    }
    Node node = new Node(Thread.currentThread(), Node.CONDITION);
    if (t == null) // 队列还是空的
        firstWaiter = node; // 直接赋给firstWaiter
    else
        t.nextWaiter = node; // 直接加在尾部就行了
    lastWaiter = node; // 更新lastWaiter
    return node;
}

private void unlinkCancelledWaiters() {
    Node t = firstWaiter;
    Node trail = null;
    while (t != null) {
        Node next = t.nextWaiter;
        if (t.waitStatus != Node.CONDITION) { // 如果当前节点不是Condition节点了
            t.nextWaiter = null; // 把t的关联清空
            if (trail == null) // 如果trail为空
                firstWaiter = next; // 那么把firstWaiter移动到next去
            else
                trail.nextWaiter = next; // 如果trail不为空，那么把trail和next连接起来
            if (next == null) // 如果next是空，那么trail才是tail
                lastWaiter = trail;
        }
        else
            trail = t; // 当前节点是Condition的话，往下移动，trail移动到t
        
        /* 
        上面需要注意的是，为啥发现了Cancel节点并处理后，不需要将trail移动。以为A -> B -> C，如果B是需要Cancel的，我们将B Cancel后，就会使A -> C，这时候的trail(A)其实就是C的trail，就不需要移动了，只需要把t移动到C去就行了
        */

        t = next; // t移动到next
    }
}

final int fullyRelease(Node node) {
    boolean failed = true;
    try {
        int savedState = getState();
        if (release(savedState)) {
            failed = false;
            return savedState;
        } else {
            throw new IllegalMonitorStateException();
        }
    } finally {
        if (failed)
            node.waitStatus = Node.CANCELLED; // 直接标记CANCELLED就行了，signal的时候会处理它。
    }
}

public final void signal() {
    // 是否为当前持有线程，需要子类去实现
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    // 获取Condition队列里的第一个
    Node first = firstWaiter;
    if (first != null)
        doSignal(first);
}

private void doSignal(Node first) {
    do {
        // 将first从Condition队列里面移除
        if ( (firstWaiter = first.nextWaiter) == null)
            lastWaiter = null;
        first.nextWaiter = null;
    } while (!transferForSignal(first) &&
             (first = firstWaiter) != null); // 如果first是Cancel的节点，那么需要继续往下找节点来唤醒
}

final boolean transferForSignal(Node node) {
    // 判断节点是否已经在之前被取消了
    if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
        return false;

    // 调用 enq 添加到 同步队列的尾部
    Node p = enq(node);
    int ws = p.waitStatus;
    // node 的上一个节点 修改为 SIGNAL 这样后续就可以唤醒自己了
    if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
        LockSupport.unpark(node.thread);
    return true;
}

final int fullyRelease(Node node) {
    boolean failed = true;
    try {
        int savedState = getState();
        if (release(savedState)) {
            failed = false;
            return savedState;
        } else {
            throw new IllegalMonitorStateException();
        }
    } finally {
        if (failed)
            node.waitStatus = Node.CANCELLED;
    }
}