public class TestCondition {

    private int MAX_SIZE = 10;
    private ReentrantLock lock = new ReentrantLock();
    // having multiple wait-sets per object
    private Condition notFull = lock.newCondition();
    private Condition notEmpty = lock.newCondition();
    private LinkedList<Integer> holders = new LinkedList<>();

    @Test
    public void test() {
        new Thread(new Producer()).start();
        new Thread(new Consumer()).start();
        try {
            Thread.currentThread().join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    class Consumer implements Runnable {

        @Override
        public void run() {
            while (true) {
                try {
                    lock.lock();
                    while (holders.isEmpty()) {
                        notEmpty.await();
                    }

                    int x = holders.removeFirst();
                    System.out.println("consumes: " + x);
                    notFull.signal();
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    lock.unlock();
                }
            }
        }
    }

    class Producer implements Runnable {

        @Override
        public void run() {
            Random random = new Random();
            while (true) {
                try {
                    lock.lock();
                    // 在循环中检查条件，处理虚假唤醒的情况
                    while (holders.size() == MAX_SIZE) {
                        notFull.await();
                    }

                    int x = random.nextInt(100);
                    holders.addLast(x);
                    System.out.println("produce: " + x);

                    notEmpty.signal();
                    Thread.sleep(500);

                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    lock.unlock();
                }
            }
        }
    }
}

public class ReentrantLock implements Lock, java.io.Serializable{

    abstract static class Sync extends AbstractQueuedSynchronizer {
        final ConditionObject newCondition() {
            return new ConditionObject();
        }
    }
}

public class ConditionObject implements Condition, java.io.Serializable {
    private static final long serialVersionUID = 1173984872572414699L;
    /** First node of condition queue. */
    private transient Node firstWaiter;
    /** Last node of condition queue. */
    private transient Node lastWaiter;

/**
 * Adds a new waiter to wait queue.
 * @return its new wait node
 */
private Node addConditionWaiter() {
    Node t = lastWaiter;
    // If lastWaiter is cancelled, clean out.
    if (t != null && t.waitStatus != Node.CONDITION) {
        unlinkCancelledWaiters();
        t = lastWaiter;
    }
    Node node = new Node(Thread.currentThread(), Node.CONDITION);
    if (t == null)
        firstWaiter = node;
    else
        t.nextWaiter = node;
    lastWaiter = node;
    return node;
}

private void unlinkCancelledWaiters() {
    Node t = firstWaiter;
    Node trail = null;
    while (t != null) {
        Node next = t.nextWaiter;
        // 因为是条件队列，waitStatus != Node.CONDITION 都认为是取消等待。
        if (t.waitStatus != Node.CONDITION) {
            t.nextWaiter = null;
            if (trail == null)
                firstWaiter = next;
            else
                trail.nextWaiter = next;
            if (next == null)
                lastWaiter = trail;
        }
        else
            trail = t;
        t = next;
    }
}

public final void signal() {
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    Node first = firstWaiter;
    if (first != null)
        doSignal(first);
}

private void doSignal(Node first) {
    do {
        if ( (firstWaiter = first.nextWaiter) == null)
            lastWaiter = null;
        first.nextWaiter = null;
    } while (!transferForSignal(first) &&
             (first = firstWaiter) != null);
}

/**
* Transfers a node from a condition queue onto sync queue.
*/
final boolean transferForSignal(Node node) {
    /*
     * If cannot change waitStatus, the node has been cancelled.
     */
    if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
        return false;

    /*
     * Splice onto queue and try to set waitStatus of predecessor to
     * indicate that thread is (probably) waiting. If cancelled or
     * attempt to set waitStatus fails, wake up to resync (in which
     * case the waitStatus can be transiently and harmlessly wrong).
     */
    // 把节点插入到AQS同步队列的tail，这样线程可以参与竞争锁
    // 并且返回它的前驱
    Node p = enq(node);
    int ws = p.waitStatus;
    // 当前前驱的ws为SIGNAL，才需要唤醒后面的节点。
    if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
        LockSupport.unpark(node.thread);
    return true;
}

public final void await() throws InterruptedException {
    if (Thread.interrupted())
        throw new InterruptedException();
    
    // 释放锁后要再次等待锁，因此加入到Condition等待队列
    Node node = addConditionWaiter();
    // 释放锁
    int savedState = fullyRelease(node);
    int interruptMode = 0;
    // 自旋检查并且阻塞，直到进入sync队列，或者被中断
    while (!isOnSyncQueue(node)) {
        LockSupport.park(this);
        if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
            break;
    }
    // 获取锁
    if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
        interruptMode = REINTERRUPT;
    if (node.nextWaiter != null) // clean up if cancelled
        unlinkCancelledWaiters();
    if (interruptMode != 0)
        reportInterruptAfterWait(interruptMode);
}

final int fullyRelease(Node node) {
    boolean failed = true;
    try {
        // 获取AQS的state字段，保存的是同步状态
        int savedState = getState();
        // release会调用模板方法tryRelease
        if (release(savedState)) {
            failed = false;
            return savedState;
        } else {
            throw new IllegalMonitorStateException();
        }
    } finally {
        if (failed)
            node.waitStatus = Node.CANCELLED;
    }
}

/**
 * Returns true if a node, always one that was initially placed on
 * a condition queue, is now waiting to reacquire on sync queue.
 * @param node the node
 * @return true if is reacquiring
 */
final boolean isOnSyncQueue(Node node) {
    // CONDITION表明在condition队列
    // node.prev == null : 进入sync队列，是在tail入队，且node.prev设置为之前的tail
    //     因此null表明肯定没有进入队列
    if (node.waitStatus == Node.CONDITION || node.prev == null)
        return false;
    // 进入sync队列，则在tail入队，node.next被设置为null
    // 因此next != null 肯定已经在sync队列
    if (node.next != null) // If has successor, it must be on queue
        return true;
    /*
     * node.prev can be non-null, but not yet on queue because
     * the CAS to place it on queue can fail. So we have to
     * traverse from tail to make sure it actually made it.  It
     * will always be near the tail in calls to this method, and
     * unless the CAS failed (which is unlikely), it will be
     * there, so we hardly ever traverse much.
     */

    // 这时候node.next==null & node.prev!=null
    // 可以认为node正处于放入Sync队列的执行CAS操作执行过程中。而这个CAS操作有可能失败
    // 遍历sync队列检查 
    return findNodeFromTail(node);
}

/**
 * Returns true if node is on sync queue by searching backwards from tail.
 * Called only when needed by isOnSyncQueue.
 * @return true if present
 */
private boolean findNodeFromTail(Node node) {
    Node t = tail;
    for (;;) {
        if (t == node)
            return true;
        if (t == null)
            return false;
        t = t.prev;
    }
}