The Print Zero Even Odd problem takes the simple alternation pattern we saw in FooBar and adds a twist: three threads instead of two, with one thread acting as an interleaver.

What makes this problem interesting is the asymmetry. In FooBar, both threads had the same behavior, just alternating. Here, one thread (zero) runs twice as often as the others, and the odd and even threads must alternate between themselves while both depending on zero.

This mirrors real-world patterns like multiplexing, where one coordinator thread services multiple worker threads in a specific order.

Problem Statement

Three threads are given: zero(), even(), and odd(). Design a mechanism so they cooperate to print the sequence "0102030405...0n" for a given n.

The Setup

Here's what each thread does.

Notice the asymmetry: the zero thread runs n times, but odd and even together also run n times, alternating. For n=5, zero prints 5 times, odd prints 3 times (1, 3, 5), and even prints 2 times (2, 4). This uneven distribution adds complexity to loop bounds and termination.

The Rules

With the roles clear, here are the ordering constraints that define correctness.

The pattern becomes clear when you trace through it: zero always goes, then odd or even takes a turn, then back to zero. The tricky part is that zero must know whether to wake odd or even after each print.

The Goal

Design a synchronization mechanism that:

The diagram shows the three-way coordination. Zero prints, then signals either odd or even depending on which number comes next. After odd or even prints, they signal back to zero. The pattern continues until all numbers are printed.

The Zero-Even-Odd problem teaches multi-party synchronization where threads have different roles and frequencies. This pattern appears throughout systems programming:

Real-World Analogies

Synchronization Challenges

Before jumping into solutions, let's understand what makes this problem tricky. The challenges here are more subtle than in FooBar.

Challenge 1: Three-Way Ordering

Unlike FooBar's simple back-and-forth, this problem has a specific state machine. Zero always goes after odd or even, but zero must decide whether odd or even goes next. This creates four distinct states, not two.

The state machine below shows how the system transitions between states.

Notice that zero has two states: "before odd" and "before even." This is the key complexity. After printing, zero must check which state it's in to know who to signal.

Challenge 2: Conditional Dispatch

After printing "0", thread zero must wake up either odd or even, not both, not neither. Using a single condition variable or semaphore for both odd and even would create a race: both might try to proceed, or the wrong one might win.

Imagine using a single numSemaphore for both odd and even. When zero releases it, either thread might acquire it. If even acquires it when odd should print, the output is wrong. This is why we need separate signaling mechanisms for odd and even.

Challenge 3: Different Iteration Counts

The threads don't run the same number of times. For n=5: zero prints 5 times (0,0,0,0,0), odd prints 3 times (1,3,5), even prints 2 times (2,4). Managing these different loop bounds adds complexity.

What happens when even finishes early? It shouldn't block zero or odd. What happens after the last number? Zero must know not to wait for a signal that will never come. These edge cases trip up many implementations.

Analysis Criteria

When evaluating solutions, we'll check each approach against these properties.

Now let's see how different approaches handle these challenges.

Solution 1: Naive Approach (Busy Waiting with State)

The simplest approach: use a shared state variable and have each thread spin until it's their turn.

Approach

We use a state variable with four possible values, corresponding to our state machine: ZERO_BEFORE_ODD, ODD, ZERO_BEFORE_EVEN, EVEN. Each thread spins checking the state. When it matches their turn, they print and update the state.

The diagram below shows how all three threads poll the shared state.

All threads constantly check the state variable, waiting for it to match their condition. This is simple but wasteful.

Implementation

Analysis

The Problem

Three threads spinning means at least two are always wasting CPU cycles. On a dual-core machine, this is catastrophic: two threads fight for CPU time while the third can't run at all. The spinning threads consume 100% of available cores doing nothing useful.

Even on multi-core systems, this approach generates heat and wastes power. For any non-trivial n, the wasted CPU cycles add up quickly. We need a solution where threads sleep when it's not their turn.

Solution 2: Semaphore-Based Solution

The semaphore solution eliminates busy waiting by having threads block efficiently. The OS puts blocked threads to sleep and wakes them only when signaled.

Key Insight

We need three semaphores, one for each thread. Thread zero needs to decide which semaphore to release after printing. Here's the key insight: we use the loop counter i in the zero thread to determine which semaphore to release.

When i is 1, 3, 5, ... (odd), the next number to print is odd, so we release oddSemaphore. When i is 2, 4, 6, ... (even), we release evenSemaphore. This simple parity check encodes the alternation pattern.

Approach

Here's how the three semaphores coordinate the threads.

The diagram below shows this dispatch pattern for the first few iterations.

The conditional branch after printing "0" is the heart of this solution. Zero looks at i, checks if it's odd or even, and releases the appropriate semaphore.

Implementation

Analysis

Why This Works

The solution uses the loop counter i in the zero thread to determine which semaphore to release. When i is 1, 3, 5, ... (odd), the next number to print is odd, so we release oddSemaphore. When i is 2, 4, 6, ... (even), we release evenSemaphore.

This targeted dispatch ensures the correct thread always gets the signal. There's no ambiguity, no race condition, no chance of waking the wrong thread.

Notice that odd and even always release zeroSemaphore. They don't need to make decisions; after printing their number, they always hand control back to zero. The asymmetry is intentional: zero is the coordinator, odd and even are the workers.

Solution 3: Condition Variable Solution

Condition variables offer flexibility when you want all threads to wait on a single condition with different predicates. This approach is more verbose than semaphores for this problem, but it demonstrates a pattern useful for more complex conditions.

Key Insight

All threads wait on the same condition variable but with different predicates. Zero waits until it's in a "before" state, odd waits until state is ODD, even waits until state is EVEN. After each print, update the state and notify all.

Since we use a single condition variable for all three threads, we must use signalAll() (or notifyAll()) rather than signal(). When the state changes, we don't know which thread should proceed, so we wake them all. Each thread rechecks its predicate and either proceeds or goes back to waiting.

Approach

Here's how the pieces fit together.

The flow diagram below shows the zero thread's logic.

The zero thread checks if the state is one of its two "before" states. If not, it waits. When it wakes, it rechecks. This loop handles spurious wakeups correctly.

Implementation

Code Walkthrough

Let's examine the key synchronization points that make this solution correct.

Analysis

Correctness Argument

Why does this solution work? Let's trace through the logic.

The trade-off compared to semaphores is efficiency: signalAll wakes all three threads, but only one can proceed. The other two wake up, check their predicate, find it false, and go back to sleep. For three threads, this overhead is minimal, but it would scale poorly to many threads.

Solution Comparison

We've seen three approaches to the Zero-Even-Odd problem. Here's how they compare.

Alternative Solutions

Beyond the main approaches, there are variations worth knowing. Let's look at an approach that combines the best of both worlds.

Alternative 1: Using Separate Condition Variables

Instead of notifyAll with one condition, use three separate conditions for targeted wakeups with condition variables.

When to prefer: When you want the efficiency of targeted wakeups with the flexibility of condition variables. This approach combines the best of both worlds: each thread waits on its own condition, so you can use signal() instead of signalAll().

Alternative 2: Lock-Free with Atomics and Yield

For systems where semaphores are expensive, you can use atomics with yield:

When to prefer: When you're on a system with expensive thread blocking, or need lock-free guarantees. Still involves spinning but yields CPU.