Problem 13 Synchronization of Dual Threads

The problem

Two threads run concurrently. One thread can only print "foo"; the other can only print "bar". They must cooperate so that the combined output is exactly foobar repeated n times — never barfoo, never foofoo, never barbar. The threads have no idea about each other's progress on their own; left alone, the OS scheduler interleaves them arbitrarily and the output is garbage. The whole task is to impose a strict, alternating order on two threads that would otherwise race.

This is the smallest possible ordering (or signaling) problem. There is no shared data to protect from corruption here — the only thing being coordinated is whose turn it is to act. That distinction matters: a mutex alone gives you mutual exclusion (only one thread in the critical section at a time) but says nothing about order. To get order you need a second ingredient — a condition the threads wait on and signal each other through.

The mechanism: one boolean turn flag, guarded by a monitor

The clean solution uses a single shared boolean — call it fooTurn — plus Java's intrinsic monitor (synchronized + wait()/notify()). The flag is the protocol: when it is true, foo is allowed to print; when it is false, bar is allowed to print. Each thread, after printing, flips the flag to hand the turn to the other and calls notify() to wake it.

Both methods are synchronized on the same object, so only one thread holds the monitor lock at any instant. The guard is a while loop, not an if:

• foo loops while (!fooTurn) wait(); — "as long as it is not my turn, release the lock and sleep."
• bar loops while (fooTurn) wait(); — the exact mirror.

The two pieces that make this correct:

1. wait() atomically releases the monitor lock and suspends the thread. Without releasing the lock, the other thread could never enter its synchronized method to flip the flag — that would be a true deadlock. wait() is the escape hatch that lets the sleeping thread step aside.
2. The guard is a while, re-checked after every wake-up. A thread that wakes from wait() must re-test the condition, because notify() only makes the thread eligible to run — it does not guarantee the condition is still true (and the JVM permits spurious wake-ups). An if here would be a real bug; a while is the standard defensive form.

When a thread sits in wait(), the JVM is no longer scheduling it — it consumes no CPU and is woken only by a matching notify()/notifyAll() (or an interrupt, or a spurious wake-up). On a typical HotSpot deployment with platform threads this maps down to blocking the underlying OS thread; with virtual threads (Project Loom) the carrier thread is freed instead. Either way the practical point holds: a waiting thread is parked, not spinning.

Worked trace (n = 2)

Start state: fooTurn = true. Suppose the scheduler happens to run bar first — this is the interesting case, because it shows the guard doing its job.

Final output: foobar foobar. Notice that even though bar got the CPU first, the flag forced it to wait its turn — the output order is determined by the flag, not by which thread the scheduler happened to start.

Why the naive versions are wrong

Three tempting shortcuts each break in an instructive way. Tracing them is the fastest way to internalize what each piece of the correct solution is buying you.

1. No coordination at all

Drop the flag, the synchronized, and the wait()/notify() — just let each thread loop and print. The two threads now race freely, and the scheduler interleaves them however it likes: foofoobar, barbarfoo, anything. The output is non-deterministic garbage. Lesson: concurrency without coordination gives no ordering guarantee at all.

2. Using if instead of while on the guard

Replace while (!fooTurn) wait(); with if (!fooTurn) wait();. Now a thread that wakes from wait() does not re-check the condition — it just falls through and prints. A spurious wake-up, or a notify() that races with the flag, can let a thread print out of turn. Lesson: always re-test the wait condition in a loop; a wake-up means "recheck," not "proceed."

3. Initializing the flag wrong

The correct start is fooTurn = true, so foo goes first and the output begins with foo. Suppose instead you start with fooTurn = false. Trace it carefully: bar's guard is while (fooTurn) = while (false), so bar does not wait — it prints bar immediately, sets fooTurn = true, and notifies foo. foo, whose guard is while (!fooTurn), was the one parked, and now wakes and prints. The program runs to completion and both threads exit normally; there is no deadlock. What you get instead is the wrong order: barfoobarfoo… (bar-first) rather than foobarfoobar…. Lesson: the flag's initial value is the protocol's opening move — it decides who acts first, and getting it wrong corrupts the ordering even though the synchronization machinery itself still works.

Putting the three together: coordination (the flag + monitor) gives you ordering at all; the while loop makes that ordering robust against spurious and racing wake-ups; and the initial flag value sets which symbol leads. Each is load-bearing.

Complexity and takeaways

Time: O(n) printed pairs; the work is dominated by 2n hand-offs. Space: O(1) — a single boolean flag and the monitor, regardless of n. There is no busy-waiting in the correct version: a thread that cannot proceed parks on wait() and is woken by the partner's notify().

The transferable pattern here is the turn variable guarded by a monitor: a small piece of shared state that encodes "whose turn it is," a while-guarded wait that re-checks that state after every wake-up, and a flip-then-notify hand-off. The same shape scales to round-robin among k threads (replace the boolean with an integer turn counter mod k) and underlies print-in-order, zig-zag, and FizzBuzz-style signaling problems. The three failure modes — no coordination (no order), if-guard (fragile order), wrong initial value (correct machinery, wrong leading symbol) — are the checklist to run any signaling solution against.

Source

Adapted and corrected from the Knowledge Guide lesson "Problem 13 Synchronization of Dual Threads" (Concurrency › Concurrency Problems), reference solution in site/concurrency/concurrency-problems/018-problem-13-synchronization-of-dual-threads.html. The behavior of the fooTurn = false initialization (runs to completion, prints barfoo…, both threads exit, no deadlock) was verified by compiling and running the lesson's Java solution.