Ordered Three-Thread Execution (Print in Order)
Three threads start in arbitrary order; ensure first() runs before second() runs before third(). The minimal solution: two binary semaphores starting at 0, where each method releases the next's semaphore on completion. Same pattern with CountDownLatch.
The setup
This shows up on LeetCode as "Print in Order". Three threads start at roughly the same time. Each one is supposed to print one word: the first thread prints "first", the second prints "second", the third prints "third". The output has to come out as firstsecondthird no matter which thread the operating system happens to schedule first.
The trap is that you cannot control thread start order. The OS may run thread 3 before thread 1. The job is to write first(), second(), and third() so that even if the threads start in the wrong order, each one waits its turn before printing.
A picture of the timing
The threads start in any order. What we want is the printing to come out in the right order, regardless.
The trick is that second() and third() do nothing at first. They sit at a closed door waiting for a "go ahead" signal. first() does its work, then opens the door for second(). second() does its work, then opens the door for third(). The door-opening is what forces the order.
The pattern: pass a baton
Think of it like a relay race with three runners. Runner 2 is at the starting line but cannot move until runner 1 hands them the baton. Runner 3 cannot move until runner 2 hands it over. The act of handing the baton is what enforces the order.
In code, the "baton" is whatever signaling primitive your language gives you:
- In Java, a
Semaphorethat starts at 0, or aCountDownLatchof 1. - In Python, a
threading.Event. - In Go, a channel that gets closed when the previous step is done.
All of them behave the same way: a thread can wait on the baton, and another thread can pass it. The waiter blocks until the baton is passed; from then on it is free to run.
One baton per gap, not one per step
For three steps in order you need two batons, not three. Baton 1 sits between first() and second(). Baton 2 sits between second() and third(). first() does not wait on anything; third() does not pass anything. In general, N steps in order need N-1 batons.
A small note on which primitive to pick
A semaphore that starts at 0 and a countdown latch with count 1 do exactly the same thing here. The difference is only in style:
- A countdown latch is one-shot. Once it counts down to 0, it stays open forever. This reads naturally as "wait for this thing to happen, once".
- A semaphore holds a count of tokens. You can release more than one and you can acquire repeatedly. This reads naturally as "pass turns back and forth".
For Print in Order, where each step happens exactly once, the countdown latch reads better. For a problem where turns repeat (alternating between two threads, for example), the semaphore is the cleaner fit.
What goes wrong if you try to skip the primitive
The shortcut answer is "I will use a boolean flag and have second() loop until the flag becomes true". That looks like it works in toy tests but has two real problems. It busy-waits, burning CPU for no reason, and without the right memory ordering the second thread may never see the flag flip at all. Reach for a real signaling primitive: semaphore, countdown latch, event, channel. Each one handles both the waiting and the memory visibility for free.
Where this pattern shows up later
The same shape appears any time one step depends on another finishing first.
- Build systems. A package step waits for compile, which waits for codegen. The build tool is just walking a dependency graph and using the same "wait for the previous step to signal done" mechanism.
- Promise chains in JavaScript.
.then()is exactly "do this when the previous promise has resolved", which is the same baton pass. - Pipelines in data systems. Stage 3 cannot start a record until stages 1 and 2 have finished it.
Once you have written Print in Order with two batons, every "do these N things in this order, no matter when each thread starts" problem solves the same way.
Implementations
Both start at 0. first() releases s1 when done. second() waits on s1, then releases s2. third() waits on s2. Order forced regardless of which thread starts running first.
1 import java.util.concurrent.Semaphore;
2
3 class Foo {
4 private final Semaphore s1 = new Semaphore(0);
5 private final Semaphore s2 = new Semaphore(0);
6
7 public void first(Runnable printFirst) {
8 printFirst.run();
9 s1.release();
10 }
11
12 public void second(Runnable printSecond) throws InterruptedException {
13 s1.acquire();
14 printSecond.run();
15 s2.release();
16 }
17
18 public void third(Runnable printThird) throws InterruptedException {
19 s2.acquire();
20 printThird.run();
21 }
22 }Two latches, each starting at count 1. first() counts down latch1; second() waits on latch1, then counts down latch2; third() waits on latch2. Reads more like the requirement.
1 import java.util.concurrent.CountDownLatch;
2
3 class Foo {
4 private final CountDownLatch latch1 = new CountDownLatch(1);
5 private final CountDownLatch latch2 = new CountDownLatch(1);
6
7 public void first(Runnable printFirst) {
8 printFirst.run();
9 latch1.countDown();
10 }
11 public void second(Runnable printSecond) throws InterruptedException {
12 latch1.await();
13 printSecond.run();
14 latch2.countDown();
15 }
16 public void third(Runnable printThird) throws InterruptedException {
17 latch2.await();
18 printThird.run();
19 }
20 }Key points
- •Two semaphores both start at 0 → first method must signal before second can proceed
- •first() prints, then releases s1; second() acquires s1, prints, releases s2; third() acquires s2
- •CountDownLatch (Java) is a clean alternative, semantically more obvious
- •Generalizes to N-stage pipelines via N-1 semaphores or N-1 latches