我在调试一个LeetCode的 Fizz Buzz多线程解法：

https://leetcode.com/problems/fizz-buzz-multithreaded/

下面的实现对我来说在逻辑上看起来是安全的，但在LeetCode上，它对 n = 50 在不同运行之间会产生不同的输出。在本地测试中，我也无法稳定复现这个问题。

我设定的不变量是：

• 只有其 id 与 turn 匹配的线程才能继续执行
• 所有其他线程都在各自的信号量上阻塞
• 打印后，活动线程恰好释放下一个被期望的线程的信号量

因此我在寻求两种可能中的一种：

1. 给出一个具体的交错执行序列，能够破坏这个不变量，或
2. 解释为什么这个不变量本身是错误的

我暂时不寻求替代实现，我希望具体理解这个版本的同步逻辑哪里出了问题。

我有意选择的一个设计约束是：在每个输出步骤只计算下一步的动作一次，而不是在每个工作线程中独立地重新评估是否可被整除。

主方法据说创建了4 个线程，这些线程对公开方法中的其中一个只调用一次。

class FizzBuzz {
    private final Semaphore sFizz = new Semaphore(0, false);
    private final Semaphore sBuzz = new Semaphore(0, false);
    private final Semaphore sFizzBuzz = new Semaphore(0, false);
    private final Semaphore sNumber = new Semaphore(0, false);
    private volatile int index = 1;
    private final int max;
    private volatile Id turn;
    private final Object mutex = new Object();

    public FizzBuzz(int n) {
        this.max = n;
        turn = calculateTurn(index);
    }

    private enum Id {
        FIZZ, BUZZ, FIZZBUZZ, NUMBER
    }

    private Integer markReady(Id id) throws InterruptedException {
        if (id != turn) {
            switch (id) {
                case NUMBER -> sNumber.acquire();
                case BUZZ -> sBuzz.acquire();
                case FIZZ -> sFizz.acquire();
                case FIZZBUZZ -> sFizzBuzz.acquire();
            }
        }

        synchronized (mutex) {
            if (index > max) {
                return null;
            }
            int turnIndex = index++;
            if (index <= max) {
                turn = calculateTurn(index);
            }
            return turnIndex;
        }
    }

    private Id calculateTurn(int _index) {
        if (_index % 3 == 0 && _index % 5 == 0) {
            return Id.FIZZBUZZ;
        } else if (_index % 3 == 0) {
            return Id.FIZZ;
        } else if (_index % 5 == 0) {
            return Id.BUZZ;
        } else {
            return Id.NUMBER;
        }
    }

    private void releaseWaiting(Id id) {
        if (id != turn) {
            switch (turn) {
                case FIZZBUZZ -> sFizzBuzz.release();
                case FIZZ -> sFizz.release();
                case BUZZ -> sBuzz.release();
                case NUMBER -> sNumber.release();
            }
        }
    }

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        while (index <= max) {
            try {
                var num = markReady(Id.FIZZ);
                if (num == null) return;
                printFizz.run();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                releaseWaiting(Id.FIZZ);
            }
        }
        releaseAll();
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        while (index <= max) {
            try {
                var num = markReady(Id.BUZZ);
                if (num == null) return;
                printBuzz.run();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                releaseWaiting(Id.BUZZ);
            }
        }
        releaseAll();

    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        while (index <= max) {
            try {
                var num = markReady(Id.FIZZBUZZ);
                if (num == null) return;
                printFizzBuzz.run();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                releaseWaiting(Id.FIZZBUZZ);
            }
        }

        releaseAll();
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        while (index <= max) {
            try {
                var num = markReady(Id.NUMBER);
                if (num == null) return;
                printNumber.accept(num);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } finally {
                releaseWaiting(Id.NUMBER);
            }
        }
        releaseAll();
    }

    private void releaseAll() {
        sFizzBuzz.release();
        sFizz.release();
        sBuzz.release();
        sNumber.release();
    }
}

解决方案

下面给出一个示例的交错执行，错误地输出 1, 2, 4, fizz 而不是 1, 2, fizz, 4。

初始状态是除了 number() 线程已经打印了1 和2 并且刚刚释放了 fizz() 线程的信号量外，其他所有线程都在它们的信号量上阻塞。

在它为自己的轮次输出之前，fizz() 线程将 turn 更新为NUMBER，这使得 number() 线程可以先输出，因为它不需要等待自己的信号量。