Problem 8 ZeroEvenOdd Multithreading Problem

The problem

Three threads cooperate to print the sequence 0102030405… up to 2n characters. One thread prints only zeros, one prints only even numbers, one prints only odd numbers. A zero must precede every number, odds and evens must appear in ascending order, and the three threads must interleave in exactly one legal order. The whole exercise is about turn-taking: at any instant exactly one thread is allowed to print, and printing must hand the turn to the correct next thread.

The shape of the schedule never changes. A zero is always followed by a number; whether that number comes from the odd thread or the even thread alternates. So the state machine has two facts to track: whose turn is it (zero, or a number), and which number thread is pending (odd or even). That is the entire coordination problem.

Walkthrough for n = 2 (target 0102)

Trace the state machine. The pending-number flag starts as odd because the first number to print is 1.

1. ZERO prints 0. Pending is odd, so it wakes the odd thread. Sequence: 0
2. ODD prints 1, flips pending to even, hands the turn back to zero. Sequence: 01
3. ZERO prints 0. Pending is even, so it wakes the even thread. Sequence: 010
4. EVEN prints 2, hands the turn back to zero. Sequence: 0102
5. Every loop has hit its bound (n=2 means two zeros, one odd, one even). All three threads return. Done.

The critical correctness question is step 5: how does the program know it is finished? Completion is reached only when all three threads have run their loops to exhaustion. Any "done" signal that fires before the last number thread has actually printed will truncate the output — and that is precisely the trap in the channel version below.

Version 1 — sync.Cond (Java and Go, same state machine)

This is the direct translation of the turn-taking machine. One mutex protects two boolean fields: zeroTurn (is it zero's turn?) and oddTurn (when it is a number's turn, is the odd thread the pending one?). Each thread loops, waits on the condition until its predicate holds, prints, flips the flags, and broadcasts. There is no separate counter driving the logic — the loop variable of each thread is the count, and the two booleans are the entire shared state. Do not add a spare counter field; it would be dead state that never gets read and only invites confusion.

The Java version (from the source) uses a ReentrantLock with three Condition objects so it can signal() exactly the right thread. The Go version uses a single sync.Cond and Broadcast(); because every thread re-checks its predicate in a for loop after waking, broadcasting the wrong sleepers is harmless — they simply go back to sleep. The for-loop wait (never an if) is also what makes spurious wakeups a non-issue: a spurious return from Wait just re-evaluates the predicate and waits again.

Go — sync.Cond

type ZeroEvenOdd struct {
    n        int
    mu       sync.Mutex
    cond     *sync.Cond
    zeroTurn bool // true => zero prints next
    oddTurn  bool // when !zeroTurn: true => odd pending, false => even pending
}

func New(n int) *ZeroEvenOdd {
    z := &ZeroEvenOdd{n: n, zeroTurn: true, oddTurn: true}
    z.cond = sync.NewCond(&z.mu)
    return z
}

func (z *ZeroEvenOdd) zero(print func(int)) {
    for i := 0; i < z.n; i++ {
        z.mu.Lock()
        for !z.zeroTurn {
            z.cond.Wait()
        }
        print(0)
        z.zeroTurn = false
        z.cond.Broadcast()
        z.mu.Unlock()
    }
}

func (z *ZeroEvenOdd) odd(print func(int)) {
    for i := 1; i <= z.n; i += 2 {
        z.mu.Lock()
        for z.zeroTurn || !z.oddTurn {
            z.cond.Wait()
        }
        print(i)
        z.zeroTurn = true
        z.oddTurn = false // next number is even
        z.cond.Broadcast()
        z.mu.Unlock()
    }
}

func (z *ZeroEvenOdd) even(print func(int)) {
    for i := 2; i <= z.n; i += 2 {
        z.mu.Lock()
        for z.zeroTurn || z.oddTurn {
            z.cond.Wait()
        }
        print(i)
        z.zeroTurn = true
        z.oddTurn = true // next number is odd
        z.cond.Broadcast()
        z.mu.Unlock()
    }
}

Verified: across 300 randomized runs each for n = 0…8, and under the race detector (go run -race), this prints 0102030405… every time with no data race. Caller completion is handled by a sync.WaitGroup over all three goroutines (see below) — the threads themselves carry no done signal.

Version 2 — channels as batons (idiomatic Go), done right

The same turn-taking can be modeled without a mutex at all. Give each thread its own channel; receiving on your channel is "you have the turn," sending on another thread's channel is "you now have the turn." A single token (an empty struct{}{}) circulates: zero → odd → zero → even → zero → … Because only one token is ever in flight, mutual exclusion is automatic and no shared field needs a lock. The channel handoff also establishes the happens-before edge that makes the shared output buffer safe.

The bug to avoid (and why)

A tempting but wrong shortcut is to let the zero goroutine signal completion right after it sends its final baton — for example close(done) at the end of zero, with main doing <-done and returning. This is a real, deterministic race, not a theoretical one. When zero sends its last baton, the matching number thread has not yet printed; it is still waiting to be scheduled. Zero races ahead, closes done, main wakes and returns, and the process exits before that final number is ever appended. Compiled and run, the buggy form produces 010 for n=2 on most runs (the trailing 2 is dropped) and longer garbled prefixes for larger n. The lesson: the done signal must come from completion of all the worker loops, never from the producer immediately after its last send.

The correct version

Two changes make it correct. First, completion is owned by a sync.WaitGroup that all three goroutines call Done on — the program is finished only when every loop has exhausted, which is exactly the "all three threads returned" condition from the walkthrough. Second, the zero channel is given a buffer of one, so the very last hand-back from a number thread lands in the buffer instead of blocking forever on a zero loop that has already finished. (Without the buffer, that orphaned final send deadlocks — also verified.)

type ZeroEvenOdd struct {
    n      int
    zeroCh chan struct{} // buffered(1): absorbs the final hand-back
    oddCh  chan struct{}
    evenCh chan struct{}
}

func New(n int) *ZeroEvenOdd {
    return &ZeroEvenOdd{
        n:      n,
        zeroCh: make(chan struct{}, 1),
        oddCh:  make(chan struct{}),
        evenCh: make(chan struct{}),
    }
}

func (z *ZeroEvenOdd) zero(print func(int)) {
    for i := 1; i <= z.n; i++ {
        <-z.zeroCh        // wait for the baton
        print(0)
        if i%2 == 1 {
            z.oddCh <- struct{}{}  // pass baton to odd
        } else {
            z.evenCh <- struct{}{} // pass baton to even
        }
    }
}

func (z *ZeroEvenOdd) odd(print func(int)) {
    for i := 1; i <= z.n; i += 2 {
        <-z.oddCh
        print(i)
        z.zeroCh <- struct{}{} // hand back to zero
    }
}

func (z *ZeroEvenOdd) even(print func(int)) {
    for i := 2; i <= z.n; i += 2 {
        <-z.evenCh
        print(i)
        z.zeroCh <- struct{}{} // hand back to zero
    }
}

func main() {
    z := New(5)
    var wg sync.WaitGroup
    wg.Add(3)
    p := func(x int) { fmt.Print(x) }
    go func() { defer wg.Done(); z.zero(p) }()
    go func() { defer wg.Done(); z.odd(p) }()
    go func() { defer wg.Done(); z.even(p) }()
    z.zeroCh <- struct{}{} // kick off the first zero
    wg.Wait()              // DONE = all three loops finished
}

Verified: 300 randomized runs each for n = 0…8, race-detector clean, output 0102030405… every time. This is now a faithful port of the same state machine — but only because "done" is the join of all three workers, not a flag flipped by zero after its last send.

Takeaways

• Two facts of state, nothing more. The schedule is fully captured by "whose turn" and "which number is pending." Each thread's loop variable supplies the count; a separate counter field is dead state — leave it out.
• Always wait in a loop. With sync.Cond / Condition, re-check the predicate in a for after every Wait. That makes both spurious wakeups and over-broad broadcasts harmless.
• Channels-as-batons is a real alternative, but completion is separate from handoff. The single circulating token gives you mutual exclusion and ordering for free; it does not tell you when everything has finished. Derive "done" from the join of all worker loops (a WaitGroup), never from the producer right after its last send — that ordering bug deterministically drops the final number.
• Verify ordering empirically. Concurrency correctness is not provable by reading once. Both versions here were compiled, run 300× per size under randomized scheduling, and checked with go run -race before being called correct.

Source

Adapted and corrected from the Knowledge Guide lesson “Problem 8 ZeroEvenOdd Multithreading Problem” (Concurrency → Concurrency Problems), based on the LeetCode 1116 “Print Zero Even Odd” problem statement. The Java ReentrantLock/Condition solution is from the original lesson; the Go sync.Cond and corrected channel-baton solutions were written and verified for this revision (go1.25, 300 randomized runs per size for n = 0…8, race detector clean).