Problem 10 Leap Year Detector Multithreading Problem

The problem

You are given a sequence of years. Two threads cooperate to print a classification for every year, in input order:

• Thread A prints the leap years.
• Thread B prints the non-leap years.

A year is a leap year when it is divisible by 4, except centuries (divisible by 100), which are leap only when also divisible by 400. So 2000 is a leap year (divisible by 400) but 1900 is not (divisible by 100, not by 400).

The hard part is not the arithmetic — it is the ordering. The two threads share one cursor into the sequence, and only the thread whose classification matches the current year is allowed to print and advance. For [2000, 2001, 2002, 2003, 2004] the required output is exactly:

2000: Leap Year
2001: Non-Leap Year
2002: Non-Leap Year
2003: Non-Leap Year
2004: Leap Year

Without coordination the lines interleave or duplicate. The job is to make the two threads take strict turns on a single shared index.

The coordination idea

Keep one shared cursor currentIndex and one lock. At any fixed index the year is a leap year or it is not — never both. So for each index exactly one thread is the rightful printer (the consumer) and the other is a no-op for that index.

The protocol under the lock is:

• Look at years[currentIndex].
• If it is my kind: print it, do currentIndex++, and signal the partner's condition so it can re-evaluate the new index.
• If it is not my kind: await on my own condition — park and release the lock until the partner advances the cursor and wakes me.

This gives a clean ping-pong: the consumer always advances the cursor and always signals the partner; the non-matching thread always parks. Because exactly one thread matches each index, you never get both threads trying to print, and you never get both parked at the same index.

Walkthrough on [1999, 2000, 2001]

Cursor starts at currentIndex = 0. All reads, prints, increments, and signals below happen under the single lock.

1. idx 0 → 1999 (non-leap). If A runs first it sees a non-leap year, so it awaits on isLeap (releasing the lock). B runs, sees a non-leap year, prints 1999: Non-Leap Year, does currentIndex++ to 1, and signals isLeap.
2. idx 1 → 2000 (leap). B loops, sees a leap year (not its kind), so it awaits on isNotLeap. A — woken by the earlier isLeap signal, or arriving fresh — sees a leap year, prints 2000: Leap Year, increments to 2, and signals isNotLeap.
3. idx 2 → 2001 (non-leap). A loops, sees a non-leap year, awaits on isLeap. B — woken by the isNotLeap signal — sees a non-leap year, prints 2001: Non-Leap Year, increments to 3, and signals isLeap.
4. Termination. currentIndex is now 3 = years.length. B's loop guard is false, so B exits. The isLeap signal B just fired wakes the parked A; A re-checks its guard, finds currentIndex < length false, and exits too. Both threads return.

Output, every time:

1999: Non-Leap Year
2000: Leap Year
2001: Non-Leap Year

The mechanism that retires the last index — the consumer signals the partner before the partner re-checks its guard — is exactly the mechanism that lets a parked partner wake up and exit. That is why this terminates rather than hangs.

Does the textbook Java version actually deadlock? No — and here is why

It is tempting to look at the two await() calls and worry that both threads could end up parked forever. They cannot, and it is worth seeing precisely why, because the reasoning is the whole point of the problem.

Both-parked is impossible

At any fixed index years[i] is either leap or non-leap, never both. So of the two threads, exactly one finds "my kind" and takes the consume branch (print, currentIndex++, signal partner); the other finds "not my kind" and parks. You never reach a state where both threads have decided to await on the same index.

The last index cannot strand a parked partner

The only code path that advances currentIndex is the consume path, and that path always signals the partner's condition before releasing the lock. So at the moment the cursor reaches years.length, the consumer that advanced it has already issued isLeap.signal() / isNotLeap.signal(). A parked partner is therefore woken; when it re-acquires the lock and re-tests while (currentIndex < years.length), the guard is now false and it exits.

The scenario "B parks just after A's last signal" cannot occur

A natural-but-wrong worry: B parks on index i after A has already incremented the cursor past i. That state is unreachable. B can only arrive at await() by first passing its loop guard and reading years[currentIndex] under the lock. Once A has advanced the cursor (which A did under the same lock), B's next guard test reads the new value: if the sequence is exhausted the guard is false and B never enters the body to park; if not, B reads the new index, not the stale one. There is no interleaving in which B parks against an index A has already retired. Traced under adversarial scheduling, [2004], [2001, 2004], and [1999, 2000, 2001] all terminate cleanly.

The real latent defect: an unsynchronized read of shared state

The textbook code is correct on ordering and termination, but it does contain a genuine bug — just not a deadlock. Look at where the loop guard lives:

public void detectLeapYears() {
  while (currentIndex < years.length) {   // <-- read OUTSIDE the lock
    lock.lock();
    try {
      if (isLeapYear(years[currentIndex])) { ... currentIndex++; ... }
      else { isLeap.await(); }
    } finally { lock.unlock(); }
  }
}

currentIndex is shared mutable state written under the lock by the other thread, but the while condition reads it before lock.lock() and after lock.unlock() — outside any synchronization. That read has no happens-before edge to the writes the partner makes under the lock. Under the Java Memory Model this is a data race: the reading thread may observe a stale value of currentIndex indefinitely, because nothing forces its cached view to be refreshed. In practice it usually works (the lock operations inside the loop tend to flush visibility), which is exactly what makes it dangerous — it is the kind of bug that passes a thousand test runs and then hangs in production on a different JVM or CPU.

The fix: read the guard under the same lock

Move the termination test inside the critical section so every read of currentIndex is ordered with respect to every write:

public void detectLeapYears() {
  while (true) {
    lock.lock();
    try {
      if (currentIndex >= years.length) return;        // guarded read
      if (isLeapYear(years[currentIndex])) {
        System.out.println(years[currentIndex] + ": Leap Year");
        currentIndex++;
        isNotLeap.signal();
      } else {
        isNotLeap.signal();                            // wake partner first...
        if (currentIndex >= years.length) return;       // ...re-check before parking
        isLeap.await();
      }
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
      return;
    } finally {
      lock.unlock();
    }
  }
}

Two real improvements here, neither of which is "repairing a deadlock": (1) the loop guard and the year read now happen under the lock, closing the visibility race; (2) signalling the partner before await on the no-op branch makes the wake-up obligation explicit rather than relying on the consume path of a later iteration — a defensive habit that pays off the moment you generalize to more than two threads or use signalAll. Mirror the same change in detectNonLeapYears().

Go translation (mutex + two condition variables)

The faithful Go version mirrors the Java structure exactly: one sync.Mutex, two sync.Cond built on it, and a guarded loop. It is not a channel hand-off — routing each index to the wrong-kind goroutine over channels is how a naive Go port both prints nothing and deadlocks. With condition variables the logic is a line-for-line analogue of the corrected Java. This program was compiled and run; on [1999, 2000, 2001] it prints the three lines in order and terminates.

type detector struct {
    years        []int
    currentIndex int
    mu           sync.Mutex
    isLeap       *sync.Cond
    isNotLeap    *sync.Cond
}

func isLeapYear(y int) bool {
    return y%4 == 0 && (y%100 != 0 || y%400 == 0)
}

func (d *detector) detectLeapYears() {
    d.mu.Lock()
    defer d.mu.Unlock()
    for d.currentIndex < len(d.years) {
        if isLeapYear(d.years[d.currentIndex]) {
            fmt.Printf("%d: Leap Year\n", d.years[d.currentIndex])
            d.currentIndex++
            d.isNotLeap.Signal()
        } else {
            d.isNotLeap.Signal()                 // wake partner first
            if d.currentIndex >= len(d.years) {
                return
            }
            d.isLeap.Wait()                      // releases mu while parked
        }
    }
    d.isNotLeap.Signal()                         // release a parked partner at the end
}

func (d *detector) detectNonLeapYears() {
    d.mu.Lock()
    defer d.mu.Unlock()
    for d.currentIndex < len(d.years) {
        if !isLeapYear(d.years[d.currentIndex]) {
            fmt.Printf("%d: Non-Leap Year\n", d.years[d.currentIndex])
            d.currentIndex++
            d.isLeap.Signal()
        } else {
            d.isLeap.Signal()
            if d.currentIndex >= len(d.years) {
                return
            }
            d.isNotLeap.Wait()
        }
    }
    d.isLeap.Signal()
}

Driver: build the detector, start both methods as goroutines, and wg.Wait() on a sync.WaitGroup of 2. Three points make this terminate where the broken channel version did not. First, sync.Cond.Wait() atomically releases mu while parked and re-acquires it on wake, so the guard re-test after waking is correct. Second, both goroutines hold and release the same mutex, so every read of currentIndex — including the loop guard — is ordered; there is no Go data race (verify with go run -race). Third, the trailing Signal() after the loop, plus the Signal() before each Wait(), guarantee that whichever goroutine finishes last wakes any partner still parked, so neither blocks forever on its condition.

Takeaways

• Two-thread turn-taking on one cursor: the consumer of an index always advances the cursor and signals the partner; the non-matching thread parks. Mutual exclusion on the index does the ordering work.
• Termination falls out of the same signal: because the consume path signals before releasing the lock, the act of retiring the final index is also the act of waking a parked partner so it can re-test its guard and exit. There is no termination deadlock.
• The real bug is a visibility race, not a hang: reading the shared currentIndex in the while guard outside the lock has no happens-before edge to the partner's writes. Pull every read of shared mutable state inside the critical section.
• Don't confuse "usually works" with "correct": a data race that the lock incidentally papers over is still a latent defect — it is the class of bug that survives heavy testing and then fails on a new JVM, CPU, or scheduler.
• Translate the synchronization shape, not just the syntax: the Java mutex+condition design maps directly onto Go's sync.Mutex+sync.Cond. A channel-routing port of this particular problem is where correctness quietly breaks.

Source

Adapted and corrected from the Knowledge Guide lesson "Problem 10 Leap Year Detector Multithreading Problem" (Concurrency → Concurrency Problems). The leap-year rule and the lock/condition-variable approach follow standard Java java.util.concurrent.locks (ReentrantLock, Condition) semantics and the Java Memory Model's happens-before rules; the Go translation follows the sync.Mutex/sync.Cond contract from the Go standard library documentation. The Go program in this page was compiled and executed on Go 1.25 to confirm correct, ordered output and clean termination on [1999, 2000, 2001].