为何Anderson队列锁表现出非公平性？基于Java测试的技术问询

DevOps 小满

2026-8-16

Anderson队列锁的公平性问题分析

Anderson等人（1990）提出了一种教学上简洁的自旋锁，它使用长度为N的数组来实现互斥的FIFO机制。在Herlihy等人所著《多处理器编程艺术》（第二版，2020）的§7.5.1节中，该锁的实现如下（原文照搬）：

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;
    }
}

我编写了一个简单的Java测试程序，创建N个线程，这些线程获取锁后递增一个全局计数器和一个线程本地计数器。测试结束时，我会对比全局计数器与所有线程本地计数器的总和（以验证正确性）。此外，如果锁是公平的，各线程的计数器数值应大致相等。

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（注释行）进行测试时，该锁既正确又公平。但当我使用Herlihy书中描述的Anderson队列锁时，锁的正确性得以保证，但前几个线程获取锁的次数比后几个线程多一个数量级。考虑到该锁的实现方式，这种情况为何会发生？

测试设备：搭载M1 Max（10核）的MBP，使用Java 17。

问题原因分析

这种现象的核心是Anderson锁的理论公平性依赖理想的线程调度环境，而实际的CPU资源限制和调度策略打破了这种公平性，具体原因如下：

自旋锁的调度依赖限制
Anderson锁是自旋锁，等待锁的线程需要不断循环检查flag[slot]的值才能获取锁。你的测试设备是10核CPU，但启动了16个线程，意味着有6个线程会处于调度等待状态（无法占用CPU执行自旋循环）。当这些线程的slot对应的flag被设置为true时，它们因为没被调度，根本无法执行检查逻辑，自然无法进入临界区。

而先被调度的前10个线程，在解锁后会立刻重新调用lock()，此时它们处于运行状态，能立即获取新的slot（通过tail.getAndIncrement()），并持续自旋等待对应的flag被激活。一旦前面的线程解锁时设置了该slot的flag为true，它们能第一时间进入临界区，形成“运行线程持续抢占锁”的循环。

与公平ReentrantLock的实现差异
公平ReentrantLock基于阻塞队列实现：等待锁的线程会被挂起，放入等待队列，锁释放时会按顺序唤醒队列头部的线程。即使线程未被调度，也能在被唤醒后获得执行机会，保证了严格的FIFO顺序。而Anderson锁没有这种调度层面的队列机制，完全依赖线程主动自旋检查，一旦线程被调度器挂起，就彻底失去了竞争能力。
循环slot的利用加剧了不平衡
当线程持续循环lock-unlock时，会不断获取新的slot（tail原子递增后取模）。运行中的线程会不断占据新的slot，而这些slot的flag会被后续的解锁操作依次激活，进一步巩固了它们的运行优势；未被调度的线程则一直卡在首次获取的slot上，无法推进。

总结来说，Anderson锁的“FIFO公平性”是理论上的、基于线程能被公平调度的前提，在实际核数不足、线程需要竞争CPU资源的场景下，自旋锁的特性会导致严重的获取次数不平衡。

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

为何Anderson队列锁表现出非公平性？基于Java测试的技术问询

问题原因分析 #

问题原因分析