面试官：从源码角度讲讲ReentrantLock及队列同步器(AQS)

static final class Node {
    /** Marker to indicate a node is waiting in shared mode */
    static final Node SHARED = new Node();
    /** Marker to indicate a node is waiting in exclusive mode */
    static final Node EXCLUSIVE = null;

    /** waitStatus value to indicate thread has cancelled */
    static final int CANCELLED =  1;
    /** waitStatus value to indicate successor's thread needs unparking */
    static final int SIGNAL    = -1;
    /** waitStatus value to indicate thread is waiting on condition */
    static final int CONDITION = -2;
    /**
     * waitStatus value to indicate the next acquireShared should
     * unconditionally propagate
     */
    static final int PROPAGATE = -3;
    //等待状态
    volatile int waitStatus;
    //指向前一个结点的指针
    volatile Node prev;
    //指向后一个结点的指针
    volatile Node next;
    //当前结点代表的线程
    volatile Thread thread;
    //等待队列中的后继节点，如果当前节点是共享的，那么这个字段将是SHARED常量，即节点类型（独占和共享）和等待队列中的后继节点共用同一个字段
    Node nextWaiter;

    /**
     * Returns true if node is waiting in shared mode.
     */
    final boolean isShared() {
        return nextWaiter == SHARED;
    }


    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 transient volatile Node head;
//指向队列尾结点
private transient volatile Node tail;
//同步状态变量
private volatile int state;
protected final int getState() {
    return state;
}
protected final void setState(int newState) {
    state = newState;
}
protected final boolean compareAndSetState(int expect, int update) {
    // See below for intrinsics setup to support this
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

public final void acquire(int arg) {
    //tryAcquie()方法具体要交给子类去实现，AbstractQueuedSynchronizer类中不实现
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

private Node addWaiter(Node mode) {
 首先创建一个新节点,并将当前线程实例封装在内部,mode这里为null
    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) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
    ///入队的逻辑
    enq(node);
    return node;
}

/**
 * 队列不空时向尾部添加结点的逻辑在enq(node)方法中也有,之所以会有这部分“重复代码”是对某些特殊情况进行提前处理,牺牲一定的代码可读性换取性能提升。
 */
private Node enq(final Node node) {
    for (;;) {
     //t指向当前队列的最后一个节点,队列为空则为null
        Node t = tail;
        //队列为空
        if (t == null) { 
        //此时链表没有节点，需要初始化让head跟tail都指向一个哨兵节点
        //构造新结点,CAS方式设置为队列首元素,当head==null时更新成功
            if (compareAndSetHead(new Node())) 
                tail = head;//尾指针指向首结点
        } else {  //队列不为空
            node.prev = t;
            if (compareAndSetTail(t, node)) { //CAS将尾指针指向当前结点,当t(原来的尾指针)==tail(当前真实的尾指针)时执行成功
                t.next = node;    //原尾结点的next指针指向当前结点
                return t;
            }
        }
    }
}

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())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL) //状态为SIGNAL

        /*
         * This node has already set status asking a release
         * to signal it, so it can safely park.
         */
        return true;
    if (ws > 0) { //状态为CANCELLED,
        /*
         * Predecessor was cancelled. Skip over predecessors and
         * indicate retry.
         */
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else { //状态为初始化状态(ReentrentLock语境下)
        /*
         * waitStatus must be 0 or PROPAGATE.  Indicate that we
         * need a signal, but don't park yet.  Caller will need to
         * retry to make sure it cannot acquire before parking.
         */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

public final boolean release(int arg) {
    //tryRelease()方法具体要交给子类去实现，AbstractQueuedSynchronizer类中不实现
    if (tryRelease(arg)) {
        Node h = head;
        //当前队列不为空且头结点状态不为初始化状态(0)
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h); //唤醒同步队列中被阻塞的线程
        return true;
    }
    return false;
}

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        //从尾部向头部遍历
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    if (s != null)
        LockSupport.unpark(s.thread);
}

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

private void doAcquireShared(int arg) {
    //当前节点加入同步队列
    final Node node = addWaiter(Node.SHARED);
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            //取当前节点的前驱节点
            final Node p = node.predecessor();
            //前驱节点是头结点，就继续尝试获取同步状态
            if (p == head) {
                int r = tryAcquireShared(arg);
                if (r >= 0) {
                    setHeadAndPropagate(node, r);
                    p.next = null; // help GC
                    if (interrupted)
                        selfInterrupt();
                    failed = false;
                    return;
                }
            }
            //用LockSupport的park方法把当前线程阻塞住
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

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

//实现Lock接口的lock方法，调用本方法当前线程获取锁，拿锁成功后就返回
public void lock() {
 //非公平模式下,sync指向的对象类型是NonfairSync
    sync.lock();
}
//实现Lock接口的tryLock方法，尝试非阻塞的获取锁，调用本方法后立刻返回，如果能获取到锁则返回true,否则返回false
public boolean tryLock() {
    return sync.nonfairTryAcquire(1);
}

static final class NonfairSync extends Sync {
    private static final long serialVersionUID = 7316153563782823691L;

    /**
     * Performs lock.  Try immediate barge, backing up to normal
     * acquire on failure.
     */
    final void lock() {
     //首先CAS尝试下获取锁，先假设每次lock都是非重入
        if (compareAndSetState(0, 1))
            setExclusiveOwnerThread(Thread.currentThread());
        else
         //这里调用的是父类AbstractQueuedSynchronizer的acquire()方法，
         //而acquire()方法中又要调用交由子类去实现的tryAcquiretryAcquire()方法
         //所以会调到下面NonfairSync类的tryAcquire()方法
            acquire(1);
    }

    protected final boolean tryAcquire(int acquires) {
        return nonfairTryAcquire(acquires);
    }
}

//本方法写在Sync类中，而不是FairSync类中
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
     //如果当前锁闲置，就CAS尝试下获取锁
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

public void unlock() {
 //这里调用的是父类AbstractQueuedSynchronizer的release()方法，
 //而release()方法中又要调用交由子类去实现的tryRelease()方法
 //所以会调到Sync类的tryRelease()方法
    sync.release(1);
}

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

static final class FairSync extends Sync {
    private static final long serialVersionUID = -3000897897090466540L;

    final void lock() {
        //这里调用的是父类AbstractQueuedSynchronizer的acquire()方法
        //父类的acquire()方法中会调用tryAcquire()方法，该方法由子类去实现
        //即最终会调用到FairSync实现的tryAcquire()方法
        acquire(1);
    }

    /**
     * Fair version of tryAcquire.  Don't grant access unless
     * recursive call or no waiters or is first.
     */
    protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {
         //在真正CAS获取锁之前加了hasQueuedPredecessors()方法
            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;
    }
}

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());
}