Concurrency
Print FooBar Alternately — Two Approaches
Two threads must alternate printing 'foo' and 'bar' exactly n times each. Compare a synchronized wait/notify approach against a cleaner paired-semaphore solution.
Problem#
One object, two threads. One thread calls foo() n times, the other calls bar() n times. The output must strictly alternate:
foobarfoobarfoobar... (n repetitions each)
foo always prints before the bar that follows it, and the threads hand control back and forth for n rounds — so whatever signaling you use must be reusable across iterations, not a one-shot event.
Think Before Coding#
Work through these before looking at the solutions:
-
What's the minimal shared state to know whose turn it is? A boolean is enough for two threads — true = foo's turn, false = bar's. Guarding it under a lock lets each thread wait until the flag flips their way.
-
Can you solve this with two semaphores instead? Yes. One semaphore per thread: fooSem starts with 1 permit (foo goes first), barSem starts with 0 (bar blocks until foo signals it). After printing, each thread releases the other's semaphore. What initial counts make foo go first? Why does it matter which one starts at 1 vs 0?
-
Why doesn't the semaphore version need an explicit "turn" variable? The permit count itself is the state. A thread can only proceed when its semaphore has a permit — and the only thread that adds a permit to it is the other thread, right after that other thread prints. There's nothing else to check.
Solution 1: synchronized with wait/notifyAll#
package FooBar;
public class FooBar {
private final int n;
private boolean fooTurn = true; // true = foo's turn, false = bar's
private final Object lock = new Object();
public FooBar(int n) { this.n = n; }
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (lock) {
while (!fooTurn) // wait while it's bar's turn
lock.wait();
printFoo.run();
fooTurn = false; // hand off to bar
lock.notifyAll();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (lock) {
while (fooTurn) // wait while it's foo's turn
lock.wait();
printBar.run();
fooTurn = true; // hand off back to foo
lock.notifyAll();
}
}
}
}
Why while not if around wait()? wait() can return spuriously (an OS-level wakeup unrelated to a signal). An if check would let the thread proceed even when the condition still doesn't hold. The while re-checks and goes back to sleep if needed. Always loop around wait().
Why notifyAll() not notify()? With only two threads it doesn't matter — notify() wakes the one other thread, which is always the right one. notifyAll() is the safe default when you aren't certain only one waiter exists.
Solution 2: Two semaphores — cleaner, no shared variable#
package FooBar;
import java.util.concurrent.Semaphore;
public class FooBarSem {
private final int n;
private final Semaphore fooSem = new Semaphore(1); // foo goes first
private final Semaphore barSem = new Semaphore(0); // bar waits initially
public FooBarSem(int n) { this.n = n; }
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
fooSem.acquire(); // block until bar signals foo's turn
printFoo.run();
barSem.release(); // signal bar to go
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
barSem.acquire(); // block until foo signals bar's turn
printBar.run();
fooSem.release(); // signal foo to go next
}
}
}
No lock. No boolean. No while loop. The permit counts are the state. fooSem(1) means foo is allowed to proceed immediately; barSem(0) means bar blocks until foo releases it. After each print, each thread releases exactly the other's semaphore — making turn-taking self-enforcing.
Demo#
package FooBar;
public class Demo {
public static void main(String[] args) throws InterruptedException {
int n = 5;
FooBar fooBar = new FooBar(n);
Thread threadFoo = new Thread(() -> {
try { fooBar.foo(() -> System.out.print("foo")); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
Thread threadBar = new Thread(() -> {
try { fooBar.bar(() -> System.out.print("bar")); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
threadBar.start(); // start bar first — proves ordering is enforced, not lucky
threadFoo.start();
threadFoo.join();
threadBar.join();
System.out.println();
}
}
Expected output (n = 5)#
foobarfoobarfoobarfoobarfoobar
Bar starts first in Demo — it immediately blocks on its semaphore (or its while check), and foo gets to print first regardless. That's the proof that the ordering is enforced by the implementation, not by thread start order.
Which approach to prefer?#
| synchronized + wait/notifyAll | Two semaphores | |
|---|---|---|
| Shared state | fooTurn boolean + lock | Permit counts (implicit in semaphore) |
| Wait condition | while loop re-check | Built into acquire() |
| Code length | More verbose | Minimal |
| Spurious wakeup handling | Explicit while loop required | Not needed — acquire() is atomic |
| Generalizes to N threads | Harder (need more flags) | Harder (need N semaphores in a ring) |
For this problem: the semaphore version is better. It's shorter, the turn order falls directly out of the initial permit counts, and there's no condition variable to re-check. The wait/notify version is the more broadly useful pattern — it scales to arbitrary state machines, as seen in Zero-Odd-Even where a simple semaphore pair isn't sufficient.
Common Mistakes#
| Mistake | Why it breaks |
|---|---|
| if instead of while around wait() | Spurious wakeups cause a thread to proceed when it's not its turn |
| fooSem = new Semaphore(0), barSem = new Semaphore(0) | Both threads block immediately — deadlock |
| fooSem = new Semaphore(1), barSem = new Semaphore(1) | Both proceed simultaneously — prints foo and bar in random order |
| Releasing semaphore before printing | The other thread can acquire and print before this one does — wrong order |
| Not calling notifyAll() after flipping fooTurn | The other thread stays parked in wait() forever |