ReentrantLock的公平锁解析

前置概念

park和unpark

unpark函数为线程提供“许可(permit)”，线程调用park函数则等待“许可”。

		Thread thread = Thread.currentThread();
        LockSupport.park(); //park()是不可重入的，如果连续调用两次park(),会发生线程阻塞
        LockSupport.unpark(thread); //和wait和notify相比，unpark()可以放在park之前

这个有点像信号量，但是这个“许可”是不能叠加的，“许可”是一次性的。

• 比如线程B连续调用了三次unpark函数，当线程A调用park函数就使用掉这个“许可”，如果线程A再次调用park，则进入等待状态。注意，unpark函数可以先于park调用。比如线程B调用unpark函数，给线程A发了一个“许可”，那么当线程A调用park时，它发现已经有“许可”了，那么它会马上再继续运行。
• 详细参考：lock详解

多线程执行逻辑

一般分两种情况，一种是阻塞抢占式 ，一种是线程交替执行（顺序可以控制）

这里对AQS类做一个介绍

1. 里面有一个静态内部类Node,我们主要关注四个属性：prev，next，thread，waitStatus

		volatile Node prev;
        /**
         * Link to the successor node that the current node/thread
         * unparks upon release. Assigned during enqueuing, adjusted
         * when bypassing cancelled predecessors, and nulled out (for
         * sake of GC) when dequeued.  The enq operation does not
         * assign next field of a predecessor until after attachment,
         * so seeing a null next field does not necessarily mean that
         * node is at end of queue. However, if a next field appears
         * to be null, we can scan prev's from the tail to
         * double-check.  The next field of cancelled nodes is set to
         * point to the node itself instead of null, to make life
         * easier for isOnSyncQueue.
         */
        volatile Node next;

        /**
         * The thread that enqueued this node.  Initialized on
         * construction and nulled out after use.
         */
        volatile Thread thread;
         /**
         * The synchronization state.
         */
        private volatile int state;

2. 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;

公平锁源码分析

以如下源码作为例子：

	    ReentrantLock reentrantLock = new ReentrantLock(true);
        reentrantLock.lock();

深入分析

首先调用ReentrantLock 的lock()方法:

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

然后按ctrl+鼠标左键，点击sync.lock()方法，进入如下方法：

abstract static class Sync extends AbstractQueuedSynchronizer {
        private static final long serialVersionUID = -5179523762034025860L;

        /**
         * Performs {@link Lock#lock}. The main reason for subclassing
         * is to allow fast path for nonfair version.
         */
        abstract void lock();
        ...

因为我们讨论的是非公平锁，所以点击lock()方法，按ctrl+alt+b,点击fairSysc进入：

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

        final void lock() {
            acquire(1);
        }

继续往下看，就来到了AbstractQueuedSynchronizer类，就是通常说的AQS：

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

调用了tryAcquire（）方法，acquireQueued（）方法，selfInterrupt（）方法

下面我们关注tryAcquire()方法在公平锁里面的实现：

		/**
         * 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) {
                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;
        }

下一步主要看hasQueuedPredecessors（）方法：

 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;
        //null != null -> false,到了!hasQueuedPredecessors()方法就变成了true
        return h != t &&
            ((s = h.next) == null || s.thread != Thread.currentThread());
   }

公平锁的实现

主要是利用AQS维护了一个链表，一个头结点和一个尾节点，利用这两个节点来设置线程的执行操作

细节点

head节点

只要维护队列，就会产生一个哨兵节点，head指针指向哨兵节点，
每次更新的时候是把哨兵节点进行替换，不是直接修改指针