对ReentrantLock的公平性进行测试

ReentrantLock公平性实现原理

在ReentrantLock类内部定义了一个内部类Sync以及两个实现NonfairSync和FairSync，它们内部定义了锁获取和释放的逻辑，下面我列出了两种同步类的代码，通过观察两个代码的差异就可以看到公平性是如何实现的。
NonfairSync和FairSync的差异如下：
差异1：非公平锁在获取锁时增加一条shortcut尝试快速获取锁
差异2：公平锁在尝试获取锁前需保证当前线程位于AQS队列的头部

  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() {if (compareAndSetState(0, 1))     // 差异1：非公平锁在一开始可以直接尝试获取锁，而不需要再经过acquire->tryAcquire->nonfairTryAcquire这样长的路径setExclusiveOwnerThread(Thread.currentThread());elseacquire(1);}protected final boolean tryAcquire(int acquires) {return nonfairTryAcquire(acquires);}final boolean nonfairTryAcquire(int acquires) {final Thread current = Thread.currentThread();int c = getState();if (c == 0) {// 差异2：非公平锁在获取锁时，不需要判断当前线程是否处在队头if (compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);return true;}}else if (current == getExclusiveOwnerThread()) {int nextc = c + acquires;if (nextc < 0) // overflowthrow new Error("Maximum lock count exceeded");setState(nextc);return true;}return false;}
}

static final class FairSync extends Sync {private static final long serialVersionUID = -3000897897090466540L;final void lock() {// 差异1：公平锁不能在一开始直接获取锁，否则可能先于队列中的等待线程获取到锁，破坏了公平性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) {// 差异2：公平锁实现中，线程处于队头才有资格获取锁，保证了公平性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方法检查当前线程是否在队头，只有在队头的线程才能获取到锁，这样，如果新来一个线程，在它入队前是不会拿到锁的，从而保证了线程获取锁的顺序 = 线程申请锁的顺序，也就是说实现了公平性。

ReentrantLock公平性测试

在上一节，说到了ReentrantLock的公平性，如果是公平锁，线程获取锁的顺序 = 线程访问锁的顺序，如果是非公平锁，线程获取锁的顺序 ≠ 线程访问锁的顺序，那也就是说，如果使用非公平锁，一个还没有被加入到队列的新线程可能会抢走早已在队列中等待的线程的锁。基于这个思路，我们来写一个程序来验证ReentrantLock的公平性。
具体步骤如下：

• 主线程获取锁但不释放；
• 创建若干打印线程（打印字符p）并运行，这些线程不能拿到锁，因而被依次放到队列中等待；
• 主线程释放锁，同时立即创建几个新打印线程（打印字符s）运行。

假如是公平锁，那么新打印线程必定会入队等待，按序获取锁，那么最终打印的字符s永远不可能出现在字符p之前；但如果是非公平锁，新打印线程有机会与旧打印线程同时竞争锁，那么这时候字符s可能会出现在字符p之前。
最终的程序如下：

import org.junit.jupiter.api.Test;import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.ReentrantLock;import static org.junit.jupiter.api.Assertions.*;class ReentrantLockTest {@Testpublic void test() throws InterruptedException {ReentrantLock lock = new ReentrantLock(true);final int threadNum = 50;// 主线程先获取锁lock.lock();// 将几个线程在锁队列中排队List<Thread> threads = new ArrayList<>();for (int i = 0; i < threadNum; i++) {Thread thread = new Thread(() -> {try {lock.lock();System.out.printf(Thread.currentThread().getName() + " ");} catch (Exception e) {e.printStackTrace();} finally {lock.unlock();}}, "p");thread.start();threads.add(thread);}// 主线程释放锁，再创建几个线程竞争锁Thread.sleep(200);lock.unlock();List<Thread> threads1 = new ArrayList<>();for (int i = 0; i < threadNum * 2; i++) {Thread thread = new Thread(() -> {try {lock.lock();System.out.printf(Thread.currentThread().getName() + " ");} catch (Exception e) {e.printStackTrace();} finally {lock.unlock();}}, "s");thread.start();threads.add(thread);}for (Thread thread : threads) {thread.join();}// 预计successor-number可能输出在number之前}
}

fair为true时输出结果为：

p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s 

fair为false时输出结果为：

p p p p p s p s s p p s p s s s p p p p p s s p p p s p s p p p s p s p p p s p s p p p s p p p s p p p p p p p s p p p s p s p s s p p s p s p p p s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s