Skip to main content
Java

Java Multithreading Programs for Interviews: Odd-Even Printing, Ping-Pong, Ordered Threads, Deadlock

The four classic multithreading programs in Java, solved with wait/notify, Semaphore, ReentrantLock + Condition and virtual threads: odd-even printing, ping-pong, ordered threads and a deadlock detected with ThreadMXBean and fixed by lock ordering and tryLock. Every program is runnable with asserted output.

Ankur 20 min read
If you search for multithreading programs in Java, you are almost always looking for the same four questions, because exams, viva rounds and first-round coding interviews keep asking them: print odd and even numbers with two threads, print “ping” and “pong” alternately, make three threads run in a fixed order, and write a deadlock (then fix it). Most pages show you a snippet that works on the author’s laptop. This one gives you programs that were run, asserted and repeated hundreds of times, so you can trust the output. You do not need to know anything about concurrency beyond one idea: a thread is a separate line of execution inside your program, and two threads touching the same variable at the same time can step on each other. Everything below is a different way of making threads wait their turn.
Versions tested. JDK 25.0.5+8 (Temurin, LTS), compiled with --release 25; JUnit Jupiter 6.1.3; Maven 3.9.11. Every program, test and console block below comes from the multithreading module of the java-interview-lab repository (module README). All 25 tests pass; after I fixed one wrong assumption in a test (described in the deadlock section), the full suite passed 8 consecutive runs.

Every one of these questions is the same question: whose turn is it?

Odd-even printing, ping-pong and “run these three threads in order” look like three different puzzles. They are one puzzle. You need two things: a piece of shared state that says whose turn it is, and a way for the thread whose turn it is not to sleep until that state changes (and for the other thread to wake it). The mechanisms in this post — wait/notifyAll, Semaphore, ReentrantLock with Condition — are three ways of doing exactly that.
thread “odd”needs next == 1, 3, 5 …else: sleep thread “even”needs next == 2, 4, 6 …else: sleep shared statenext = 7 print, change next, wake the other thread Every program in this post is this picture. Only the “sleep and wake” mechanism changes: wait/notifyAll, a Semaphore permit, or a Condition. The shared state is the part people forget.
The diagram shows the picture to keep in your head. The amber box is the one people forget: if there is no shared “next” value, you have nothing to check when you wake up, and you will print out of order or hang forever. In every program below, find that value first (next, a permit count, a boolean) and the rest follows.
Going deeper: what the module contains and how it is organised

The module has one class per technique, all taking a ThreadKind (platform or virtual) so the identical code runs on both. Each returns a list of events such as odd:1, so a test can assert both the order and which thread did the work. Start with the module README for the map.

Odd-even printing with wait() and notifyAll()

This is the answer interviewers expect first, because it uses only what the language gives you. Two threads share one lock object (the monitor) and one counter next. A thread enters synchronized, and if it is not its turn it calls wait(), which releases the monitor and sleeps. When it is its turn it prints, bumps next and calls notifyAll() to wake the other thread. The code is in OddEvenWaitNotify.java. 
    private void worker(String name, int first, int max) throws InterruptedException {
        for (int n = first; n <= max; n += 2) {
            synchronized (monitor) {
                while (next != n) {            // a LOOP, never an if: guards against spurious wake-ups
                    monitor.wait();
                }
                events.add(name + ":" + n);
                next++;
                monitor.notifyAll();           // notifyAll, not notify: see the post for why
            }
        }
    }
Running all three odd-even versions for 1 to 10 gives the same list every time (transcript: 01-odd-even.txt): 
OddEvenWaitNotify (platform threads), max=10
  [odd:1, even:2, odd:3, even:4, odd:5, even:6, odd:7, even:8, odd:9, even:10]
OddEvenSemaphore (platform threads), max=10
  [odd:1, even:2, odd:3, even:4, odd:5, even:6, odd:7, even:8, odd:9, even:10]
OddEvenLockCondition (platform threads), max=10
  [odd:1, even:2, odd:3, even:4, odd:5, even:6, odd:7, even:8, odd:9, even:10]
Use while, never if. A thread can wake up when nothing changed for it (a spurious wake-up), and with more than two threads it can be woken by a notification meant for someone else. A while loop re-checks next != n after every wake-up; an if trusts the wake-up and can print out of order. The notifyAll() is deliberate for the same reason: notify() wakes one arbitrary waiter, which may be the wrong one.
Notice also that the program starts the even thread first on purpose. A correct solution must not depend on which thread the operating system happens to schedule first. If your version only works when “odd” starts first, it works by luck.
Going deeper: why wait() needs the lock, and what a lost wake-up looks like

You can only call wait() or notifyAll() while holding the monitor, otherwise the JVM throws IllegalMonitorStateException. That rule exists to prevent a lost wake-up: if checking the condition and going to sleep were two separate steps, the other thread could change the state and notify in between, and you would sleep forever on a notification that already happened. Holding the monitor makes “check, then sleep” one atomic step, because wait() releases the monitor only as it goes to sleep.

The tests in OddEvenTest.java run each implementation 200 times with an odd upper limit. A lost wake-up would hang, and the hang would turn into a test failure through the timeout described in the testing section below.

The same program with a Semaphore, and with Lock + Condition

A Semaphore is a counter of permits: acquire() takes one (sleeping if none are left) and release() gives one back. Give “odd” one permit and “even” zero, and the turn becomes a permit passed back and forth. There is no shared next variable because the permit is the turn. Source: OddEvenSemaphore.java. 
        Semaphore oddTurn = new Semaphore(1);    // odd goes first
        Semaphore evenTurn = new Semaphore(0);
        List<String> events = Collections.synchronizedList(new ArrayList<>());

        Group group = new Group(kind);
        group.start("odd", () -> {
            for (int n = 1; n <= max; n += 2) {
                oddTurn.acquire();
                events.add("odd:" + n);
                evenTurn.release();
            }
        });
        group.start("even", () -> {
            for (int n = 2; n <= max; n += 2) {
                evenTurn.acquire();
                events.add("even:" + n);
                oddTurn.release();
            }
        });
The third version uses ReentrantLock with two Condition objects, one per thread. It looks like wait/notify, but each thread signals exactly the other one, so nobody is woken needlessly. Source: OddEvenLockCondition.java. 
            lock.lock();
            try {
                while (next != n) {
                    mine.await();
                }
                events.add(name + ":" + n);
                next++;
                other.signal();
            } finally {
                lock.unlock();
            }
        }
All three print the identical sequence (see the transcript above). Which one should you write in an interview? Start with whichever you can explain line by line, then mention the others:
TechniqueShared stateWake-upEasy to get wrong
synchronized + wait/notifyAlla counterwakes every waiterif instead of while; notify instead of notifyAll
Semaphorethe permits themselvesone release = one thread can gowrong initial permits (both 0 = instant hang)
ReentrantLock + Conditiona counter or flagsignals one named waiterforgetting unlock() in finally
Going deeper: Semaphore ordering and why the list is safe to read afterwards

The event list is a synchronizedList, and the semaphore hand-off already gives a happens-before edge between one thread’s release() and the next thread’s acquire(), so the list contents are visible in order. In the lock version the list is guarded by the same lock as next. The test asserts the exact list, which would expose a reordering.

One more interview follow-up: the semaphore version has no loop around acquire() because the re-checking loop lives inside acquire() itself: it returns only once a permit was actually taken.

Ping-pong is odd-even with a boolean

Print “ping” from one thread and “pong” from another, for a fixed number of rounds. Here the shared state is a boolean pingsTurn instead of a counter, and the same Lock + Condition pattern applies. Source: PingPong.java. 
    private void side(String word, boolean isPing, int rounds, Condition mine, Condition other)
            throws InterruptedException {
        for (int i = 0; i < rounds; i++) {
            lock.lock();
            try {
                while (pingsTurn != isPing) {
                    mine.await();
                }
                events.add(word);
                pingsTurn = !isPing;
                other.signal();
            } finally {
                lock.unlock();
            }
        }
    }
Output for four rounds (02-ping-pong.txt): 
PingPong, 4 rounds
  [ping, pong, ping, pong, ping, pong, ping, pong]
The test runs 500 rounds, twenty times each, on both platform and virtual threads, and asserts the full 1,000-word sequence every time. Zero rounds must print nothing, which catches an off-by-one at the loop boundary, a favourite follow-up question.
  • Test source: PingPongTest.java
  • Variation interviewers ask: add a third word (“pang”) — change the boolean to an int turn index, or use the ring from the next section.

Running threads in a fixed order: T1, then T2, then T3

The question: three threads are started in the order T3, T2, T1, yet the output must be T1, T2, T3. The trick is to stop thinking about start order and think about who waits for whom. A CountDownLatch starts closed; threads calling await() sleep until some thread calls countDown(). Chain two latches and the order is fixed no matter how the scheduler behaves.
T1runs at once T2await(latch 1) T3await(latch 2) latch 1 latch 2 Start order does not matter: T3 starts first and simply sleeps on latch 2. Each thread opens the next latch when it finishes, so the order is carried by the latches, not by timing.
Read the diagram left to right: T1 never waits, T2 waits for latch 1, T3 waits for latch 2, and each thread opens the next latch as its last action. Code from OrderedThreads.java: 
    public static List<String> withLatches(ThreadKind kind) throws Exception {
        List<String> events = Collections.synchronizedList(new ArrayList<>());
        CountDownLatch t1Done = new CountDownLatch(1);
        CountDownLatch t2Done = new CountDownLatch(1);

        Group group = new Group(kind);
        group.start("T3", () -> { t2Done.await(); events.add("T3"); });
        group.start("T2", () -> { t1Done.await(); events.add("T2"); t2Done.countDown(); });
        group.start("T1", () -> { events.add("T1"); t1Done.countDown(); });
        group.awaitAll(Duration.ofSeconds(10));
        return List.copyOf(events);
    }
The other classic answer is a join() chain: T2 calls t1.join(), T3 calls t2.join(). It needs the earlier thread object to exist before the later one starts, which is why the code creates T1 first. For N threads taking turns (thread 1 prints 1, 4, 7, thread 2 prints 2, 5, 8 …) use a ring of semaphores: thread k acquires its own permit and releases the next thread’s. Output for all three (03-ordered-threads.txt): 
Started T3, T2, T1 (in that order). Execution order:
  latches:     [T1, T2, T3]
  join chain:  [T1, T2, T3]
Round robin, 3 threads, max=10:
  [worker-1:1, worker-2:2, worker-3:3, worker-1:4, worker-2:5, worker-3:6, worker-1:7, worker-2:8, worker-3:9, worker-1:10]
Going deeper: the same ring with 1,000 threads

The ring code is not limited to three threads. A test in OrderedThreadsTest.java runs 1,000 virtual threads printing 1 to 5,000 and asserts the exact sequence; the demo in 05-virtual-single-carrier.txt runs 1,000 virtual threads and 3,000 numbers on a single carrier thread. With 1,000 platform threads the same program also works but costs 1,000 operating-system threads; that gap is the point of the virtual-thread section below.

How to test threads without sleep()

The usual way to “test” a threaded program is to run it, eyeball the output and add Thread.sleep(1000) so the main thread waits long enough. That proves nothing: it passes on a fast machine and fails on a slow one. Every program here is built so a test can wait for a fact instead of a duration. A small helper, Group.java, starts named threads and joins them against a hard deadline; if the deadline passes, it interrupts the stragglers and throws. 
    public void awaitAll(Duration timeout) throws InterruptedException, TimeoutException {
        long deadline = System.nanoTime() + timeout.toNanos();
        for (Thread t : threads) {
            long left = deadline - System.nanoTime();
            if (left <= 0 || !t.join(Duration.ofNanos(left))) {
                threads.forEach(Thread::interrupt);
                throw new TimeoutException("thread still running after " + timeout + ": " + t.getName());
            }
        }
        if (!failures.isEmpty()) {
            throw new IllegalStateException("worker failed", failures.get(0));
        }
    }
}
Combined with JUnit’s @Timeout on the test classes, a lost wake-up or a deadlock becomes a red test within seconds rather than a hung build. The assertions compare the full event list, so order is checked, not just “it finished”. Full test list (06-test-results.txt): 
PASS DeadlockTest.naiveLockingDeadlocksAndTheJvmSaysSo
PASS DeadlockTest.consistentLockOrderingRemovesTheCycle
PASS DeadlockTest.fixesAlsoWorkOnVirtualThreads
PASS DeadlockTest.tryLockWithBackOffTurnsDeadlockIntoCountedRetries
PASS DeadlockTest.deadlockedVirtualThreadsAreInvisibleToFindDeadlockedThreads

… and the last line of the file:

25 tests, 0 failures
Honest limits. Two places do use short sleeps, and neither synchronises a result. The deadlock detector polls findDeadlockedThreads() every 5 ms until the JVM reports a deadlock (detection is the thing being tested), and the tryLock fix backs off 0 or 25 ms between retries (a retry policy, not a test wait). A passing run does not prove there is no race in general; the 200-repetition loops make a race very likely to show, not impossible.

Writing a deadlock on purpose, and getting the JVM to confirm it

A deadlock is a cycle: thread 1 holds lock A and wants lock B, thread 2 holds lock B and wants lock A. Neither can move, and neither will ever let go. The classic example is transferring money between two bank accounts in opposite directions, each transfer locking “from” first and “to” second.
transfer-A-to-Bthread 1 transfer-B-to-Athread 2 lock of account A lock of account B holds holds wants (blocked) A cycle of “holds” and “wants” means nobody can ever move. Break any one edge and it is gone.
Dashed red lines are the blocked requests, solid lines are locks already held. The cycle exists only because the two transfers lock in opposite orders; that observation is the whole fix, as the next section shows. The naive code, from Transfers.java: 
    public static void naive(Account from, Account to, long amount, Runnable afterFirstLock)
            throws InterruptedException {
        from.lock.lockInterruptibly();          // interruptible only so the demo can clean up afterwards
        try {
            afterFirstLock.run();
            to.lock.lockInterruptibly();
            try {
                from.withdraw(amount);
                to.deposit(amount);
            } finally {
                to.lock.unlock();
            }
        } finally {
            from.lock.unlock();
        }
    }
The unlucky interleaving usually appears once in thousands of runs, which makes a demo useless. So the scenario inserts a hook (a CyclicBarrier) that makes both threads wait until both hold their first lock, and the deadlock then happens every time. Next, detection. The JVM can report deadlocks itself through ThreadMXBean.findDeadlockedThreads(), which covers both synchronized monitors and java.util.concurrent locks and returns null when there is none. From DeadlockDetector.java: 
    static List<String> describe(long[] ids) {
        List<String> lines = new ArrayList<>();
        for (ThreadInfo info : MX.getThreadInfo(ids, true, true)) {
            String lockType = info.getLockInfo() == null ? "?" : info.getLockInfo().getClassName();
            lines.add(info.getThreadName() + " is " + info.getThreadState()
                    + " on " + lockType + " owned by " + info.getLockOwnerName());
        }
        lines.sort(null);       // thread-id order is not stable; name order is
        return lines;
    }
Real output of the naive run (04-deadlock.txt): 
== NAIVE ==
  findDeadlockedThreads: DEADLOCK
    transfer-A-to-B is WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync owned by transfer-B-to-A
    transfer-B-to-A is WAITING on java.util.concurrent.locks.ReentrantLock$NonfairSync owned by transfer-A-to-B
  after interrupting both threads: total balance = 2000
Each thread is WAITING on a lock that the other owns. That is the cycle in the diagram, reported by the JVM and not by my code. To clean up, the demo calls lockInterruptibly() instead of lock(), so interrupting both threads breaks the deadlock.
Breaking a deadlock by interrupting is not atomic. This showed up while writing the tests: a demo run ended with balances A=1030 and B=970 instead of 1000/1000, and the test that asserted 1000/1000 then failed intermittently. The first interrupt freed a lock, the other thread grabbed it before its own interrupt arrived, and one transfer completed. Money is conserved either way, so the output prints the total (2000) and the test asserts that, not a specific split. In real systems the lesson is the same: you cannot reliably recover from a deadlock, you can only prevent it.
Going deeper: what findDeadlockedThreads can and cannot see

It reports cycles of platform threads waiting for object monitors or ownable synchronizers (this includes ReentrantLock). It does not find deadlocks on wait()/notify() or latches: a thread waiting for a notification nobody will send is just stuck, not “deadlocked” in the JVM’s sense. There is also a similarly named findMonitorDeadlockedThreads() that only sees synchronized monitors, so it would have missed this example, which uses ReentrantLock. I used ReentrantLock here (rather than synchronized) because only an interruptible lock lets the demo recover and finish; I did not run a synchronized variant.

Two fixes: lock ordering and tryLock

Fix 1: always lock in the same global order. Give every account an id and always lock the smaller id first, whichever direction the money moves. Now both threads reach for account 1 first, so one waits at the very first lock and no cycle can form. This is the answer to give first, because it removes the deadlock rather than recovering from it. 
    public static void ordered(Account from, Account to, long amount, Runnable afterFirstLock)
            throws InterruptedException {
        Account first = from.id < to.id ? from : to;
        Account second = first == from ? to : from;
        first.lock.lockInterruptibly();
        try {
            afterFirstLock.run();
            second.lock.lockInterruptibly();
            try {
                from.withdraw(amount);
                to.deposit(amount);
            } finally {
                second.lock.unlock();
            }
        } finally {
            first.lock.unlock();
        }
    }
Fix 2: tryLock with a timeout. Lock the first account, then try the second for 50 ms. If you cannot get it, release everything, back off and retry. A deadlock becomes a counted retry. This is useful when you cannot impose a global order (for example the locks come from different libraries). 
            from.lock.lockInterruptibly();
            boolean done = false;
            try {
                if (firstAttempt) {
                    afterFirstLock.run();
                    firstAttempt = false;
                }
                if (to.lock.tryLock(50, TimeUnit.MILLISECONDS)) {
                    try {
                        from.withdraw(amount);
                        to.deposit(amount);
                        done = true;
                    } finally {
                        to.lock.unlock();
                    }
                }
            } finally {
                from.lock.unlock();
            }
            if (done) {
                return;
            }
            retries.incrementAndGet();
            // Asymmetric back-off so two retrying threads cannot stay in lock-step forever.
            Thread.sleep(from.id < to.id ? 0 : 25);
        }
Both transfers complete in both fixes (04-deadlock.txt): 
== ORDERED ==
  both transfers completed, no deadlock to detect
  balances A=930 B=1070
== TRY_LOCK ==
  both transfers completed, no deadlock to detect
  balances A=930 B=1070 retries>0=true
The balances are 930 and 1070: A paid 100 and received 30, B the reverse. The line retries>0=true comes from the barrier forcing both threads to hold their first lock; at least one tryLock must therefore have failed. The tests check the balances 100 times for the ordered version.
A harness trap I hit. My first run hung. I had put the same barrier hook in the lock-ordering fix, but with ordered locking the second thread cannot even take its first lock until the first thread is finished, so neither thread ever reached the barrier. The fix has no unlucky interleaving to force, so DeadlockScenario.java passes a no-op hook for it. If you build your own demo harness, expect the same.
Going deeper: the livelock risk in tryLock

If both threads fail, release, and retry at the same instant, they can repeat the failure indefinitely: a livelock, where the threads are busy but make no progress. The code avoids this with an asymmetric back-off (the thread locking the lower id retries at once, the other waits 25 ms). Random jitter is the more general answer. Other prevention options interviewers mention: hold only one lock at a time, use a single coarse lock, or use lock-free structures such as AtomicLong for the balance.

The same programs on virtual threads

A virtual thread (Java 21 and later) is a cheap thread scheduled by the JVM onto a small pool of real operating-system threads called carriers. You switch by changing one line: Thread.ofVirtual() instead of Thread.ofPlatform(). That is the only difference inside ThreadKind.java, so every program above already runs on both, and the tests are parameterised over both kinds. Two things are worth knowing for interviews, and both were checked by running code. First, wait/notify used to be a problem on virtual threads, because blocking inside synchronized pinned the carrier. Since JEP 491 (Java 24) a virtual thread waiting in Object.wait() unmounts and frees its carrier. To prove it, the demo runs in a child JVM with exactly one carrier thread, and the odd-even wait/notify program still finishes (05-virtual-single-carrier.txt): 
carrier parallelism = 1
OddEvenWaitNotify on virtual threads, max=10
  [odd:1, even:2, odd:3, even:4, odd:5, even:6, odd:7, even:8, odd:9, even:10]
Round robin: 1000 virtual threads, max=3000 -> 3000 events
  first 3: [worker-1:1, worker-2:2, worker-3:3]
  last 3:  [worker-998:2998, worker-999:2999, worker-1000:3000]
With one carrier, the 1,000-thread ring completing means the threads really are parking and resuming, not occupying 1,000 OS threads. The test SingleCarrierVirtualThreadTest.java starts that child JVM with -Djdk.virtualThreadScheduler.parallelism=1 and maxPoolSize=1 and asserts the output. Second, and this is the surprise: deadlocked virtual threads are invisible to findDeadlockedThreads(). The Javadoc says cycles that include virtual threads are not found, and the run confirms it: both virtual threads are WAITING in a real deadlock, and the MXBean reports nothing (04-deadlock.txt): 
== NAIVE on virtual threads ==
  thread states: [WAITING, WAITING]
  findDeadlockedThreads: none (virtual threads are invisible to it)
Do not rely on ThreadMXBean for virtual-thread deadlocks. A clean “no deadlock” from findDeadlockedThreads() proves nothing if your threads are virtual. I did not run a thread dump here; the JDK documents jcmd <pid> Thread.dump_to_file for dumping virtual threads, but treat that as a pointer to the docs, not something verified in this module.
Going deeper: pinning is not completely gone

JEP 491 states that synchronized no longer pins virtual threads, and that pinning still happens in a few other cases, such as native code calling back into blocking Java code. The jdk.VirtualThreadPinned event remains for diagnosing those. On Java 21 to 23, the same wait/notify program would have pinned its carrier; this module targets Java 25 only and I did not test older releases.

Should you write any of this by hand?

Almost never in production. These programs are exercises in the primitives. Real code that passes work between threads uses a BlockingQueue, an Exchanger, a Phaser or CompletableFuture, which have the waiting logic already written and tested. In an interview, write the primitive version, then say that out loud. That sentence is often what the interviewer is listening for.

Also remember what this module does not cover: memory visibility (volatile, happens-before), thread pools, and the producer-consumer problem, which is a sibling of the programs above and deserves its own post.

Further reading

No Comments yet!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.