为何基于数组队列的ALock锁表现出非公平性？

问题背景 #

在Herlihy等人所著《多处理器编程艺术》（第2版，2020）的§7.5.1中，提出了一种基于数组队列实现FIFO锁定的简单锁ALock，其代码如下：

public class ALock {
    ThreadLocal<Integer> mySlotIndex = new ThreadLocal<>() {
        @Override protected Integer initialValue() { return 0; }
    };
    AtomicInteger tail;
    volatile boolean[] flag;
    int size;

    public ALock(int capacity) {
        size = capacity;
        tail = new AtomicInteger(0);
        flag = new boolean[capacity];
        flag[0] = true;
    }

    public void lock() {
        int slot = tail.getAndIncrement() % size;
        mySlotIndex.set(slot);
        while (!flag[slot]) {};
    }

    public void unlock() {
        int slot = mySlotIndex.get();
        flag[slot] = false;
        flag[(slot + 1) % size] = true;
    }
}

为验证该锁的公平性，编写了如下测试程序：创建NUM_THREADS个线程，每个线程获取锁后递增全局COUNT及对应线程的RUNS_PER_THREAD[id]。若锁正确，COUNT应等于RUNS_PER_THREAD元素之和；若锁公平，RUNS_PER_THREAD的元素应大致相等。测试代码如下：

public class Main {
    static long COUNT = 0;
    static int NUM_THREADS = 16;
//    static Lock LOCK = new ReentrantLock(true);
    static ALock LOCK = new ALock(NUM_THREADS);
    static long[] RUNS_PER_THREAD = new long[NUM_THREADS];
    static Map<Long, Integer> THREAD_IDS = new HashMap<>();

    public static void main(String[] args) {
        var threads = IntStream.range(0, NUM_THREADS).mapToObj(Main::makeWorker).toArray(Thread[]::new);
        for (int i = 0; i < threads.length; i++) THREAD_IDS.put(threads[i].getId(), i);
        for (var thread: threads) thread.start();
        try { Thread.sleep(300L); } catch (InterruptedException e) {}
        for (var thread: threads) thread.interrupt();
        try { Thread.sleep(100L); } catch (InterruptedException e) {}
        for (int i = 0; i < NUM_THREADS; i++) System.out.printf("Thread %d:\t%12d%n", i, RUNS_PER_THREAD[i]);
        System.out.println("Counted up to: \t\t\t" + COUNT);
        System.out.println("Sum for all threads: \t" + Arrays.stream(RUNS_PER_THREAD).sum());
    }

    private static Thread makeWorker(int i) {
        return new Thread(() -> {
            while (true) {
                if (Thread.interrupted()) return;
                LOCK.lock();
                try {
                    COUNT++;
                    var id = THREAD_IDS.get(Thread.currentThread().getId());
                    RUNS_PER_THREAD[id]++;
                } finally {
                    LOCK.unlock();
                }}});
    }
}

测试结果显示：使用公平ReentrantLock(true)时，16个线程的RUNS_PER_THREAD结果近乎均等；但使用ALock时，前几个线程获取锁的次数约为后几个线程的10倍。

由此提出问题：该ALock是否确实非公平？若如此，原因是什么？或是测试程序存在缺陷？为何该测试能验证ReentrantLock的公平性？

问题解答 #

1. ALock确实存在非公平性 #

ALock的非公平性源于其锁调度逻辑的设计缺陷：

• 线程调用lock()时，通过tail.getAndIncrement() % size获取一个槽位，随后自旋等待该槽位的flag变为true。
• 在unlock()阶段，当前线程会将自身槽位的flag置为false，并激活下一个槽位（(slot+1)%size）的flag。
• 关键问题在于：当某个槽位的flag被激活后，所有等待该槽位的线程都会无差别竞争，而非严格按照线程获取槽位的先后顺序（也就是请求锁的顺序）来分配锁。
• 早期启动的线程可能因为操作系统调度优先级、CPU缓存局部性等优势，反复抢占到刚被激活的槽位，导致后启动的线程难以获得执行机会，最终出现前几个线程获取锁次数远多于后几个的倾斜情况。

2. 测试程序不存在缺陷 #

该测试的逻辑完全符合公平锁的验证标准：

• 公平锁的核心定义是线程获取锁的顺序与请求锁的顺序严格一致，在足够长的测试周期内，每个线程获取锁的次数应该大致均等。
• 通过统计每个线程的锁获取次数，能够直观反映锁的调度是否公平——公平锁会让各线程的执行次数趋近平衡，而非公平锁则会出现明显的次数差异。

3. 测试能验证ReentrantLock公平性的原因 #

公平模式下的ReentrantLock(true)内部维护了一个严格的FIFO等待队列：

• 当线程请求锁时，如果锁已被占用，会进入等待队列的尾部排队；
• 当锁被释放时，会唤醒队列头部的线程，严格按照请求顺序分配锁资源。
• 这种有序的调度机制确保了每个线程获取锁的机会均等，因此测试中RUNS_PER_THREAD的结果会近乎均等。

内容的提问来源于stack exchange，提问作者aas