ARTICLE AD BOX
I’m debugging a solution for LeetCode Fizz Buzz Multithreaded:
https://leetcode.com/problems/fizz-buzz-multithreaded/
The implementation below appears logically safe to me, but on LeetCode it produces different outputs across runs for n = 50. Locally, my tests do not reproduce the issue consistently.
My intended invariant is:
only the thread whose id matches turn can proceed
all other threads block on their semaphore
after printing, the active thread releases exactly the next expected thread
So I’m looking for one of two things:
a concrete interleaving that breaks this invariant, or
an explanation of why the invariant itself is false
I’m not looking for alternative implementations yet, I specifically want to understand what is wrong with the synchronization logic in this version.
One design constraint I chose intentionally was to compute the next action only once per output step rather than re-evaluating divisibility independently in each worker.
The main method supposedly creates 4 threads that call a single time one of the public methods.
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(); } }