CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 2 of 6 · 3 min read

Races

Check-then-act and read-modify-write.

Think of two clerks selling the last cinema ticket for seat 7. Each looks at the chart, sees the seat free, and sells it. Both looked before either wrote. The seat is sold twice.

JCIP defines a race condition as a bug where the answer is right only if the threads happen to interleave kindly, so success rests on lucky timing. The most common form is check-then-act: a decision is made from an observation that may already be stale. A second form is read-modify-write, such as n++, which reads the value, adds one and writes it back as three separate steps.

A counter shows the second form. Four threads each add 1 a hundred thousand times to three counters: a plain int, an object with a synchronized method, and an AtomicInteger.

static class Unsafe { int n; void inc() { n++; } }
static class Locked { private int n; synchronized void inc() { n++; } synchronized int get() { return n; } }
// AtomicInteger at;  at.incrementAndGet()

After the run, the locked and atomic counters both read 400000. The plain counter reads less than 400000, because two threads sometimes read the same old value and both write the same new one, so one update is lost. The exact shortfall varies from run to run, which is what makes such bugs hard to find.

The first fix is to make the compound action atomic: it runs as one indivisible step that no other thread can interleave with. JCIP says that compound actions on shared state must be made atomic to avoid race conditions. Two tools do this. A lock (synchronized) makes a whole block atomic. An atomic class, such as AtomicInteger, makes a single variable's update atomic with no explicit lock, and ConcurrentHashMap.merge does the same for a map entry.

The seat problem is check-then-act, so the check and the write must sit under one lock.

class SeatMap {
    private final Set<Integer> taken = new HashSet<>();
    synchronized boolean reserve(int seat) {
        if (taken.contains(seat)) return false;
        taken.add(seat);
        return true;
    }
}

Eight threads all call reserve(7). Exactly one gets true, and the set holds one seat. A version that keeps the set thread-safe but checks and then adds in two separate calls, with a pause between, is still wrong. In a repeat of that experiment, two threads sometimes both won. Making each call safe does not make a pair of calls safe.

Atomic

An action is atomic if it happens as one unbroken step, so no other thread can see or change the state halfway through it.

Example: reserve(7) under a lock, which checks and adds as one step.

Check yourself: 1. Why does the plain counter lose updates? 2. Why is a thread-safe set not enough for the seat problem? 3. Name two tools that make an update atomic.