Problem 11 Palindrome Multithreaded Investigator

The problem

You are given a fixed sequence of numbers. Two threads cooperate to classify and print every number, in input order, with no number printed twice and none skipped:

• Thread A — palindrome detector: prints the number at the current index only if it reads the same forward and backward (e.g. 121, 45654).
• Thread B — non-palindrome detector: prints the number at the current index only if it is not a palindrome.

A shared currentIndex says which number is up next. Exactly one of the two threads is qualified to print each number; the other must step aside. The output must respect input order, so the two threads cannot both barrel ahead independently — they have to take turns around the shared index. That ordering constraint is the whole reason synchronization is needed here; the palindrome check itself is trivial.

The shape of the solution

Wrap the shared state (currentIndex plus the array) in a single ReentrantLock, and give it one Condition. Each thread runs the same loop: take the lock, look at the number under currentIndex, and decide.

• If this thread is the one qualified to print it (A on a palindrome, B on a non-palindrome): print it, advance currentIndex, and signal the condition to release the peer.
• If it is not qualified: this number belongs to the peer, so this thread must await() on the condition — releasing the lock and parking until woken.

The lock guarantees mutual exclusion on currentIndex; the condition is what hands the turn from one thread to the other. Because every number is either a palindrome or not, exactly one thread prints each number and the other waits, so the two alternate as dictated entirely by the data — not by a fixed A-B-A-B rhythm.

Walkthrough on [123, 121, 3223, 4554, 1234]

Trace the shared currentIndex (i) and which thread acts. "waits" means the thread found the number was not its job and called await(); "prints" means it was qualified, printed, did i++, and signaled.

Note rows 1–3: A printed three numbers in a row while B stayed parked the whole time. The turn order is dictated by the data, not by strict alternation. When i reaches the array length, the qualified thread is the one running; the parked peer must still be released so it can re-check the loop guard and exit — see the termination note below.

The real question: signal() vs signalAll() here

The interesting design point on this problem is which wakeup primitive to use — and the honest answer is the opposite of the common scare story.

signal() is sufficient and correct for this program. There is exactly one Condition and exactly two threads. At any instant at most one thread is blocked in await(), and it is necessarily the peer of the thread currently holding the lock. There is no pool of waiters and no "wrong waiter" to accidentally wake — the only thread that can possibly be parked on this condition is the one you want to wake. A bare signal() wakes that single peer deterministically. (Running a signal()-only version of this exact two-thread program thousands of times produces zero deadlocks, which matches the analysis.)

So why does the sample use signalAll()? Habit and defensiveness, not a correctness requirement on this problem. signalAll() is the safe default that earns its keep only when more than one thread can be waiting on the same condition — for example if you generalized this to N detector threads sharing one condition, where signal() might wake an unqualified waiter and leave the qualified one asleep. With N>1 waiters and a single condition, signalAll() (inside the mandatory while re-check loop) is what guarantees the right thread eventually proceeds. With exactly two threads, that failure mode cannot arise, so the two primitives are interchangeable for correctness.

What about cost? The famous "thundering herd" objection to signalAll() — waking O(threads) waiters so all but one immediately re-block — is real only in that many-threads-on-one-condition design. It does not apply here: there is only ever a single waiter, so signalAll() and signal() wake the same one thread. The extra cost on this two-thread program is essentially nil, not "one wasted wakeup per number." The reason to still prefer signal() here is clarity of intent ("hand off to the one peer"), not measurable performance.

A subtlety worth stating precisely: signal() can only ever wake a thread that is currently blocked in await(). The thread that calls signal() is the running thread holding the lock — it is not itself a waiter, so the runtime cannot "wake the signaler instead of the peer." Spurious wakeups are a separate phenomenon: await() may return without a matching signal(), which is exactly why the body must re-test the condition in a while loop rather than an if — but a spurious wakeup only causes a harmless re-check and re-park, never a lost handoff in this design.

Reference implementation (Java)

Single lock, single condition, two threads. Note the loop guard and the use of while around await().

import java.util.List;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Solution {
  private static final List<Integer> numbers =
      List.of(123, 121, 3223, 4554, 1234);

  private int currentIndex = 0;
  private final Lock lock = new ReentrantLock();
  private final Condition turn = lock.newCondition();

  private static boolean isPalindrome(int n) {
    String s = Integer.toString(n);
    return s.equals(new StringBuilder(s).reverse().toString());
  }

  // qualified == true for the palindrome thread, false for the other
  private void run(boolean qualifiedOnPalindrome) throws InterruptedException {
    while (true) {
      lock.lock();
      try {
        if (currentIndex >= numbers.size()) {
          turn.signal();   // release the parked peer so it can exit too
          return;
        }
        boolean pal = isPalindrome(numbers.get(currentIndex));
        if (pal == qualifiedOnPalindrome) {
          System.out.println(numbers.get(currentIndex)
              + (pal ? " is a palindrome." : " is not a palindrome."));
          currentIndex++;
          turn.signal();   // exactly one peer can be waiting: deterministic
        } else {
          turn.await();    // while-guarded by the surrounding loop
        }
      } finally {
        lock.unlock();
      }
    }
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    Runnable a = () -> { try { s.run(true); }  catch (InterruptedException e) { Thread.currentThread().interrupt(); } };
    Runnable b = () -> { try { s.run(false); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } };
    new Thread(a).start();
    new Thread(b).start();
  }
}

The loop re-checks currentIndex >= numbers.size() every time it holds the lock, so the structure also satisfies the while-loop-around-await() rule: any wakeup (real or spurious) re-evaluates the guard before acting. The original sample used cond.signalAll(); swapping it for signal() as above is a correctness-neutral, intent-clarifying change for this two-thread case.

Pitfalls

• Using if instead of while around await(). A thread woken by a spurious wakeup (or any wakeup) must re-test its predicate. With an if, it would proceed on a stale assumption; the while/loop re-check makes it park again harmlessly. In this solution the surrounding while(true) plus the guard re-read provides that re-check.
• Forgetting to release the parked peer at termination. When the running thread sees currentIndex has reached the end, its peer may still be parked in await(). Without a final signal() (or signalAll()) before returning, that peer hangs forever and the JVM never exits. This, not the steady-state handoff, is the genuine liveness hazard in this design.
• Reading or mutating currentIndex outside the lock. Every read, the print, and the increment must happen while holding the lock, or two threads can act on the same index and double-print or skip.
• Calling await()/signal() without holding the lock. Both throw IllegalMonitorStateException if the current thread does not own the lock; keep them inside the lock()/unlock() block.
• Reaching for signalAll() as a reflex "to be safe." It is the correct default when more than one thread can wait on one condition, but here it buys nothing over signal() and slightly obscures the intent. Match the primitive to the actual waiter count.

Source

Adapted and corrected from the Knowledge Guide lesson "Problem 11 Palindrome Multithreaded Investigator" (Concurrency › Concurrency Problems), with the Condition signaling analysis revised to reflect the two-thread, single-condition semantics verified against the JDK java.util.concurrent.locks.Condition contract.