非阻塞算法-ReentrantLock代码剖析之ReentrantLock.lock

ReentrantLock是java.util.concurrent.locks中的一个可重入锁类。在高竞争条件下有更好的性能，且可以中断。深入剖析ReentrantLock的源码有助于我们了解线程调度，锁实现，中断，信号触发等底层机制，实现更好的并发程序。

以下代码出自JDK1.6

先来看ReentrantLock最常用的代码lock

public void lock() {
        sync.lock();
    }

public void lock() {
        sync.lock();
    }

很简单，直接调用了成员变量sync的lock方法。以下是sync的声明

/** Synchronizer providing all implementation mechanics */
    private final Sync sync;

/** Synchronizer providing all implementation mechanics */
    private final Sync sync;

从注释中我们可以看出sync提供了所有的实现机制，ReentrantLock只是简单执行了转发而已。

下图是Sync的层次结构，Sync,FairSync和NonFairSync都是ReentrantLock的静态内部类。Sync 是一个抽象类，而FairSync和NonFairSync则是具体类，分别对应了公平锁和非公平锁。实际中公平锁吞吐量比非公平锁小很多，所以以下讨论若非特别说明均以非公平锁为例。



在上图的类层次中，最核心的类当属 AbstractQueuedSynchronizer ,最重要的两个数据成员当前锁状态和等待链表都是由它来实现的。

/**
     * Head of the wait queue, lazily initialized.  Except for
     * initialization, it is modified only via method setHead.  Note:
     * If head exists, its waitStatus is guaranteed not to be
     * CANCELLED.
     */
    private transient volatile Node head;

    /**
     * Tail of the wait queue, lazily initialized.  Modified only via
     * method enq to add new wait node.
     */
    private transient volatile Node tail;
    /**
     * The synchronization state.
     */
    private volatile int state;

/**
     * Head of the wait queue, lazily initialized.  Except for
     * initialization, it is modified only via method setHead.  Note:
     * If head exists, its waitStatus is guaranteed not to be
     * CANCELLED.
     */
    private transient volatile Node head;

    /**
     * Tail of the wait queue, lazily initialized.  Modified only via
     * method enq to add new wait node.
     */
    private transient volatile Node tail;
    /**
     * The synchronization state.
     */
    private volatile int state;

state记录了当前锁被锁定的次数。如果为0则未被锁定。加锁通过更改状态实现，而更改状态主要由函数compareAndSetState实现。调用cas原语以保证操作的原子性，如果state值为expect,则更新为update值且返回true,否则不更改state且返回false.

/**
     * Atomically sets synchronization state to the given updated
     * value if the current state value equals the expected value.
     * This operation has memory semantics of a <tt>volatile</tt> read
     * and write.
     *
     * @param expect the expected value
     * @param update the new value
     * @return true if successful. False return indicates that the actual
     *         value was not equal to the expected value.
     */
protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

/**
     * Atomically sets synchronization state to the given updated
     * value if the current state value equals the expected value.
     * This operation has memory semantics of a <tt>volatile</tt> read
     * and write.
     *
     * @param expect the expected value
     * @param update the new value
     * @return true if successful. False return indicates that the actual
     *         value was not equal to the expected value.
     */
protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

其中unsafe的类Unsafe为sun的非公开类sun.misc.Unsafe，有兴趣的可以反编译该类查看代码。
而另一个重要的数据当前线程则是在 AbstractOwnableSynchronizer中。

/**
     * The current owner of exclusive mode synchronization.
     */
    private transient Thread exclusiveOwnerThread;

/**
     * The current owner of exclusive mode synchronization.
     */
    private transient Thread exclusiveOwnerThread;

了解这些基本的数据结构后让我们来一探上面提到的 sync.lock()之究竟。以下是NonFairSync的lock函数。代码里中文注释均为本文作者添加。

/**
         * Performs lock.  Try immediate barge, backing up to normal
         * acquire on failure.
         */
final void lock() {
            // 如果锁没有被任何线程锁定且加锁成功则设定当前线程为锁的拥有者
            // 如果锁已被当前线程锁定，则在acquire中将状态加1并返回
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                // 加锁失败,再次尝试加锁，失败则加入等待队列，禁用当前线程，直到被中断或有线程释放锁时被唤醒
                acquire(1);
        }

/**
         * Performs lock.  Try immediate barge, backing up to normal
         * acquire on failure.
         */
final void lock() {
            // 如果锁没有被任何线程锁定且加锁成功则设定当前线程为锁的拥有者
            // 如果锁已被当前线程锁定，则在acquire中将状态加1并返回
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                // 加锁失败,再次尝试加锁，失败则加入等待队列，禁用当前线程，直到被中断或有线程释放锁时被唤醒
                acquire(1);
        }

acquire方法在AbstractQueuedSynchronizer中定义。

/**
     * Acquires in exclusive mode, ignoring interrupts.  Implemented
     * by invoking at least once {@link #tryAcquire},
     * returning on success.  Otherwise the thread is queued, possibly
     * repeatedly blocking and unblocking, invoking {@link
     * #tryAcquire} until success.  This method can be used
     * to implement method {@link Lock#lock}.
     *
     * @param arg the acquire argument.  This value is conveyed to
     *        {@link #tryAcquire} but is otherwise uninterpreted and
     *        can represent anything you like.
     */
public final void acquire(int arg) {
    // 首先尝试获取锁，成功则直接返回
    // 否则将当前线程加入锁的等待队列并禁用当前线程
    // 直到线程被中断或者在锁为其它线程释放时唤醒
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

/**
     * Acquires in exclusive mode, ignoring interrupts.  Implemented
     * by invoking at least once {@link #tryAcquire},
     * returning on success.  Otherwise the thread is queued, possibly
     * repeatedly blocking and unblocking, invoking {@link
     * #tryAcquire} until success.  This method can be used
     * to implement method {@link Lock#lock}.
     *
     * @param arg the acquire argument.  This value is conveyed to
     *        {@link #tryAcquire} but is otherwise uninterpreted and
     *        can represent anything you like.
     */
public final void acquire(int arg) {
    // 首先尝试获取锁，成功则直接返回
    // 否则将当前线程加入锁的等待队列并禁用当前线程
    // 直到线程被中断或者在锁为其它线程释放时唤醒
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

被tryAcquireNonFairSync override,直接调用 Sync.nonfairTryAcquire,代码如下

/**
         * Performs non-fair tryLock.  tryAcquire is
         * implemented in subclasses, but both need nonfair
         * try for trylock method.
         */
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                // 如果锁空闲则尝试锁定，成功则设当前线程为锁拥有者
                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;
        }

/**
         * Performs non-fair tryLock.  tryAcquire is
         * implemented in subclasses, but both need nonfair
         * try for trylock method.
         */
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                // 如果锁空闲则尝试锁定，成功则设当前线程为锁拥有者
                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;
        }

在tryAcquire失败后则进行如下操作

第一步调用AbstractQueuedSynchronizer.addWaiter将当前线程加入等待队列尾部，其中也涉及一些细微的同步操作及逻辑判断，就不详述了。有兴趣者可自行查看源码。

/**
     * Creates and enqueues node for given thread and mode.
     *
     * @param current the thread
     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
     * @return the new node
     */
    private Node addWaiter(Node mode) {
        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;
    }

/**
     * Creates and enqueues node for given thread and mode.
     *
     * @param current the thread
     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
     * @return the new node
     */
    private Node addWaiter(Node mode) {
        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;
    }

第二步调用AbstractQueuedSynchronizer.acquireQueued让线程进入禁用状态，并在每次被唤醒时尝试获取锁，失败则继续禁用线程。

/**
     * Acquires in exclusive uninterruptible mode for thread already in
     * queue. Used by condition wait methods as well as acquire.
     *
     * @param node the node
     * @param arg the acquire argument
     * @return {@code true} if interrupted while waiting
     */
    final boolean acquireQueued(final Node node, int arg) {
        try {
            boolean interrupted = false;
            for (;;) {
                // 如果当前线程是head的直接后继则尝试获取锁
                // 这里不会和等待队列中其它线程发生竞争，但会和尝试获取锁且尚未进入等待队列的线程发生竞争。这是非公平锁和公平锁的一个重要区别。
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    return interrupted;
                }
                // 如果不是head直接后继或获取锁失败，则检查是否要禁用当前线程
                // 是则禁用，直到被lock.release唤醒或线程中断
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
    }

/**
     * Acquires in exclusive uninterruptible mode for thread already in
     * queue. Used by condition wait methods as well as acquire.
     *
     * @param node the node
     * @param arg the acquire argument
     * @return {@code true} if interrupted while waiting
     */
    final boolean acquireQueued(final Node node, int arg) {
        try {
            boolean interrupted = false;
            for (;;) {
                // 如果当前线程是head的直接后继则尝试获取锁
                // 这里不会和等待队列中其它线程发生竞争，但会和尝试获取锁且尚未进入等待队列的线程发生竞争。这是非公平锁和公平锁的一个重要区别。
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    return interrupted;
                }
                // 如果不是head直接后继或获取锁失败，则检查是否要禁用当前线程
                // 是则禁用，直到被lock.release唤醒或线程中断
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } catch (RuntimeException ex) {
            cancelAcquire(node);
            throw ex;
        }
    }

AbstractQueuedSynchronizer. shouldParkAfterFailedAcquire做了一件很重要的事：根据状态对等待队列进行清理，并设置等待信号。

这里需要先说明一下waitStatus，它是AbstractQueuedSynchronizer的静态内部类Node的成员变量，用于记录Node对应的线程等待状态.等待状态在刚进入队列时都是0，如果等待被取消则被设为Node.CANCELLED,若线程释放锁时需要唤醒等待队列里的其它线程则被置为Node.SIGNAL,还有一种状态Node.CONDITION这里先不讨论。

/** 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 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;

AbstractQueuedSynchronizer.shouldParkAfterFailedAcquire实现如下

/**
     * Checks and updates status for a node that failed to acquire.
     * Returns true if thread should block. This is the main signal
     * control in all acquire loops.  Requires that pred == node.prev
     *
     * @param pred node's predecessor holding status
     * @param node the node
     * @return {@code true} if thread should block
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int s = pred.waitStatus;
        if (s < 0)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park
             */
            // 如果前置结点waitStatus已经被置为SIGNAL,则返回true,可以禁用线程
            return true;
        if (s > 0) {
            // 如果前置结果已被CALCEL,则移除。
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
        do {
        node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    }
        else
            /*
             * Indicate that we need a signal, but don't park yet. Caller
             * will need to retry to make sure it cannot acquire before
             * parking.
             */
            // 原子性将前置结点waitStatus设为SIGNAL
            compareAndSetWaitStatus(pred, 0, Node.SIGNAL);
        // 这里一定要返回false,有可能前置结点这时已经释放了锁，但因其 waitStatus在释放锁时还未被置为SIGNAL而未触发唤醒等待线程操作，因此必须通过return false来重新尝试一次获取锁
        return false;
    }

/**
     * Checks and updates status for a node that failed to acquire.
     * Returns true if thread should block. This is the main signal
     * control in all acquire loops.  Requires that pred == node.prev
     *
     * @param pred node's predecessor holding status
     * @param node the node
     * @return {@code true} if thread should block
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int s = pred.waitStatus;
        if (s < 0)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park
             */
            // 如果前置结点waitStatus已经被置为SIGNAL,则返回true,可以禁用线程
            return true;
        if (s > 0) {
            // 如果前置结果已被CALCEL,则移除。
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
        do {
        node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    }
        else
            /*
             * Indicate that we need a signal, but don't park yet. Caller
             * will need to retry to make sure it cannot acquire before
             * parking.
             */
            // 原子性将前置结点waitStatus设为SIGNAL
            compareAndSetWaitStatus(pred, 0, Node.SIGNAL);
        // 这里一定要返回false,有可能前置结点这时已经释放了锁，但因其 waitStatus在释放锁时还未被置为SIGNAL而未触发唤醒等待线程操作，因此必须通过return false来重新尝试一次获取锁
        return false;
    }

AbstractQueuedSynchronizer.parkAndCheckInterrupt实现如下，很简单，直接禁用线程，并等待被唤醒或中断发生。对java中Thread.interrupted()都作了什么不甚了解的要做功课。

这里线程即被堵塞，醒来时会重试获取锁，失败则继续堵塞。即使Thread.interrupted()也无法中断。那些想在等待时间过长时中断退出的线程可以调用ReentrantLoc.lockInterruptibly().其原理后继文章中会剖析。 

/**
     * Convenience method to park and then check if interrupted
     *
     * @return {@code true} if interrupted
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

/**
     * Convenience method to park and then check if interrupted
     *
     * @return {@code true} if interrupted
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

关于线程的更多知识可以参考：http://www.ibm.com/developerworks/cn/java/j-concurrent/

该文章为Agrael转帖，并在转帖的内容上做了一定的更改和注释，版权属于原作者拥有。红色字体为Agarel添加的注释。