Problem 17 Traffic-Light-Controlled Intersection Synchronization

Mutual exclusion across directions — read the state under the lock

An intersection must never let conflicting directions move at once. The shared "which direction is green" state is read by every vehicle thread and written by the controller, so every access must be synchronized. The earlier version read a plain (non-volatile) array without the lock, so a vehicle could act on a stale or torn value and two directions could cross together — the exact accident the lock exists to prevent. The fix: guard the state with a lock and let vehicles wait on a condition until their direction is green.

Correct Java

import java.util.concurrent.locks.*;

class Intersection {
    private final Lock lock = new ReentrantLock();
    private final Condition changed = lock.newCondition();
    private int green = 0;                 // 0 = North-South, 1 = East-West

    // controller flips the light atomically
    public void switchLight() {
        lock.lock();
        try { green = 1 - green; changed.signalAll(); }
        finally { lock.unlock(); }
    }
    // a vehicle is *admitted* only when its direction is green; state read UNDER the lock
    public void cross(int direction, Runnable drive) throws InterruptedException {
        lock.lock();
        try {
            while (green != direction) changed.await();
            // Intentional model A: hold lock through drive → single-car intersection
            // (even same-direction cars fully serialized). Simple and safe for the puzzle.
            drive.run();
        } finally { lock.unlock(); }
    }

    // Model B: concurrent same-direction flow — release before long drive
    public void crossParallelSameDir(int direction, Runnable drive) throws InterruptedException {
        lock.lock();
        try {
            while (green != direction) changed.await();
            // light is green for us; do NOT hold lock during slow drive
        } finally { lock.unlock(); }
        drive.run(); // many NS cars may drive together; EW still blocked until switch
        // Caveat: a switchLight during drive may open the other direction while we still move —
        // real systems use "all red" clearance time or a generation counter checked under lock.
    }
}

Both the read (green != direction) and the write (green = 1 - green) happen while holding the same lock, so there is a single, consistent view for the decision. Trade-off: holding the lock for the entire drive models a single-car intersection (safe, easy). Releasing before drive allows same-direction parallelism but needs a clearance protocol so a switch cannot green the other way mid-cross.

Worked schedule (NS waits, EW drives, then switch)

The mid-cross hazard, and the drain protocol that closes it

Model B trades safety for throughput, and the caveat in the comment is a real accident, not a footnote. Because the green check and the drive are no longer in the same critical section, a switch can land between them. Trace it:

The hazard is a check-then-act race across a state change: A's admission decision was valid when made and stale by the time it acted. Widening the lock (Model A) removes it by making admission and drive one atomic step — at the cost of serializing everyone. To keep same-direction parallelism and stay safe you need a drain protocol: the switch must wait for every car admitted under the old green to clear before it greens the other direction. That is exactly what a real intersection's all-red clearance interval is — a fixed gap long enough for the longest legal crossing. In software you make it precise with an in-flight counter instead of a guessed time:

private int green = 0;
private final int[] inFlight = new int[2];   // cars currently crossing, per direction

public void cross(int direction, Runnable drive) throws InterruptedException {
    lock.lock();
    try {
        while (green != direction) changed.await();
        inFlight[direction]++;               // registered while still green, under the lock
    } finally { lock.unlock(); }
    drive.run();                             // many same-dir cars overlap here
    lock.lock();
    try { inFlight[direction]--; changed.signalAll(); }
    finally { lock.unlock(); }
}

public void switchLight() throws InterruptedException {
    lock.lock();
    try {
        int old = green;
        while (inFlight[old] > 0) changed.await();  // DRAIN: wait out everyone still crossing
        green = 1 - green;                          // only now is the flip safe
        changed.signalAll();
    } finally { lock.unlock(); }
}

Why this is correct: a car increments inFlight[dir] under the lock while its direction is still green, and the switch cannot flip until inFlight[old] == 0. So the set of cars crossing under green g is fully drained before any car is ever admitted under the perpendicular green — the two directions can never overlap on the road, yet same-direction cars still drive concurrently. The generation-counter variant is the same idea keyed differently: stamp each admitted car with the current green generation and refuse to flip while any car of the outgoing generation is unfinished. The cost is a throughput ceiling: while draining, the intersection is effectively all-red, so a stream of long crossings in one direction delays the switch — the same starvation-vs-safety tension real signals resolve with a maximum green time.

When each model is correct

• Model A (lock through drive) — when a "crossing" is short and cheap (updating a shared cell, touching a small critical region) so full serialization costs nothing, or when you want the simplest provably-safe code. This is the right default for the interview puzzle.
• Model B + drain — when a crossing is long relative to switch frequency and same-direction throughput matters (real traffic, or a resource where many same-class users can proceed together). You accept the extra in-flight bookkeeping and the drain latency to unlock concurrency.
• Model B without a drain — never in anything that must be safe. It is only acceptable when a stale admission is harmless (e.g. best-effort metrics), which the "two cars must not collide" invariant is precisely not.

Correct Go (mutex + cond)

type Intersection struct { mu sync.Mutex; cv *sync.Cond; green int }
func New() *Intersection { x := &Intersection{}; x.cv = sync.NewCond(&x.mu); return x }
func (x *Intersection) Switch() { x.mu.Lock(); x.green = 1 - x.green; x.cv.Broadcast(); x.mu.Unlock() }
func (x *Intersection) Cross(dir int, drive func()) {
    x.mu.Lock()
    for x.green != dir { x.cv.Wait() }
    drive() // model A: serialize under lock
    x.mu.Unlock()
}

Alternative: controller owns the light (CSP)

// One goroutine owns green; cars request permission via channels
// req := make(chan int); grant := make(chan struct{})
// controller: for { select { case d := <-req: if d==green { grant<-struct{}{} }; case <-tick: green=1-green }}
// car: req <- dir; <-grant; drive()
// No shared mutable flag — ownership replaces the condition variable.

When NOT shared mutable green: if you already have an event loop / actor for the intersection, channel grants are clearer. Use the lock+cond form when mapping directly from the Java monitor solution.

Pitfalls

• Reading shared state without the lock (the original bug): even a single int/array read can see a stale value without proper synchronization; volatile fixes visibility but not the check-then-act atomicity you need here — use the lock.
• Guard the wait in a while loop, not an if: after signalAll, only the threads whose direction is now green should proceed; the rest must re-check and wait again.
• Lock held for entire drive serializes same-direction traffic — state the model deliberately.

Takeaways

• Read and write shared state under the same lock — a one-sided guard is no guard.
• Vehicles wait on a condition for their green; signalAll on every switch wakes the right ones.
• volatile/atomics give visibility but not check-then-act atomicity; here the lock is required.
• Choose: serialize under lock (simple) vs release-before-drive (same-dir parallelism + clearance rules).

Re-authored for correctness for this guide (the prior version read unsynchronized state and lacked cross- direction exclusion). See also: Mutex Lock, Condition Variables, Critical Section & Race Condition.