Java 公平锁和非公平锁

公平锁：指的是多个线程等待同一个锁时，等待时间最长的线程将会优先获取到锁。但是，这也会导致当线程尝试获取锁时，很大概率会进入阻塞状态，有很高的状态切换成本，因此，会降低吞吐量和执行效率。

非公平锁：不会保证一个特定获取到锁的顺序。当线程尝试获取锁时，会优先通过CAS尝试获取锁，如果失败了才会进入等待队列。非公平锁的执行效率更高，因为线程尝试获取锁的时候，如果能够直接获取到锁，可以节省线程的上下文切换带来的时间和性能上的开销。但是，可能会导致有的线程永远也获取不到锁。

Java中的synchronized是非公平锁，ReentrantLock默认也是非公平锁，并且是可重入的。ReentrantLock则可以通过fair来设置为公平锁。下面是ReentrantLock的类图结构：

公平锁加锁

公平锁加锁过程的方法调用：ReentrantLock#lock() → ReentrantLock.FairSync#lock() → AbstractQueuedSynchronizer#acquire(1)。下面看下acquire的代码实现：

// 【AbstractQueuedSynchronizer.java】
    public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }
// 【ReentrantLock.java】
    static final class FairSync extends Sync {
        ......
        /**
         * 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) { //state为0表示当前是未被锁定状态
                if (!hasQueuedPredecessors() && //判断等待队列是否有排在自己前面的线程
                    compareAndSetState(0, acquires)) { //通过CAS设置锁定状态
                    setExclusiveOwnerThread(current); //独占线程设置为自己
                    return true; //加锁成功
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                // 锁的重入，状态加1
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true; //加锁成功
            }
            return false; //加锁失败
        }
    }
// 【AbstractQueuedSynchronizer.java】
// addWaiter的作用就是将当前线程添加到等待队列的队尾
    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;
    }
    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); //设置为head，所以head是持有锁的线程
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt()) //进入blocked状态
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

有一点需要注意，即使ReentrantLock构造时fair设置为true，使用不带超时的tryLock()加锁时也会使用非公平锁的策略。

非公平锁加锁

调用链路：ReentrantLock#lock() → ReentrantLock.NonfairSync#lock() 。

// 【ReentrantLock.java】
    static final class NonfairSync extends Sync {
        ......
        final void lock() {
            if (compareAndSetState(0, 1)) //直接使用CAS加锁，加锁成功后设置为独占线程
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
    }
// 【AbstractQueuedSynchronizer.java】
    public final void acquire(int arg) {
        if (!tryAcquire(arg) && //调用NonfairSync.tryAcquire()
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) //acquireQueued与公平锁流程相同
            selfInterrupt();
    }
// 【ReentrantLock.java】
        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;
        }

从代码可以看出，公平锁和非公平锁的加锁流程几乎相同，区别是state==0时，非公平锁会直接使用CAS尝试加锁，而公平锁会首先判断等待队列中是否有其他线程在排队，如果没人在排队才会使用CAS加锁。

释放锁

公平锁和非公平锁释放锁的流程是一样的。调用链路ReentrantLock#unlock() → AbstractQueuedSynchronizer#release()。

// 【AbstractQueuedSynchronizer.java】
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h); //唤醒队列中下一个等待线程
            return true;
        }
        return false;
    }

// 【ReentrantLock.java】
        protected final boolean tryRelease(int releases) {
            // 获取state并减一
            int c = getState() - releases;
            // 加锁和解锁线程如果不同就会抛出异常
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) { //为0表示锁被释放，否则，表示锁的多次重入
                free = true;
                setExclusiveOwnerThread(null); //独占线程设置为null
            }
            setState(c); //更新锁状态state
            return free;
        }