Multithreading: a mental model

These are my notes on multithreading, with a diagram and a small Java example. The example is a counter. It works with one thread, but several threads can make it return the same value twice.

The mental model

A counter shared by three threads

Each call to getNextValue() adds one to currentValue and returns it:

public class SequenceGenerator {

    private int currentValue = 1;

    public int getNextValue() {
        currentValue += 1;
        return currentValue;
    }
}

This test submits 1,000 calls to a pool of three threads. It collects the results in a set, so duplicates count only once:

@Test
public void givenUnsafeSequenceGenerator_whenRaceCondition_thenUnexpectedBehavior() throws Exception {
    int count = 1000;
    Set<Integer> uniqueSequences = getUniqueSequences(new SequenceGenerator(), count);
    Assert.assertEquals(count, uniqueSequences.size());
}

private Set<Integer> getUniqueSequences(SequenceGenerator generator, int count) throws Exception {
    ExecutorService executor = Executors.newFixedThreadPool(3);
    Set<Integer> uniqueSequences = new LinkedHashSet<>();
    List<Future<Integer>> futures = new ArrayList<>();

    try {
        for (int i = 0; i < count; i++) {
            futures.add(executor.submit(generator::getNextValue));
        }

        for (Future<Integer> future : futures) {
            uniqueSequences.add(future.get());
        }
    } finally {
        executor.shutdown();
    }

    return uniqueSequences;
}

An unsafe run can produce this result:

java.lang.AssertionError: expected:<1000> but was:<994>

There were 1,000 calls, but only 994 distinct results. currentValue += 1 looks like one operation in the source code, but it reads a value, adds one and writes the result back. Two threads can both read 9 and both write 10. One increment is lost.

That's the race condition here. The result depends on how the threads' operations overlap. The test might also pass, so a green run doesn't prove the counter is safe.

The critical section is getNextValue(). Only one thread should be able to read, increment and return the value at a time.

Using a lock

Every Java object has an intrinsic lock. Adding synchronized to an instance method makes it acquire the lock on this before running. Another thread calling the same method on the same object has to wait.

Java releases the lock when the method exits, including if it throws an exception.

For this counter, the change is small:

public class SequenceGeneratorUsingSynchronizedMethod extends SequenceGenerator {

    @Override
    public synchronized int getNextValue() {
        return super.getNextValue();
    }
}

A synchronized block also lets me choose which object to lock and which code belongs inside the critical section. Here, the private lock protects the same operation:

public class SequenceGeneratorUsingSynchronizedBlock extends SequenceGenerator {

    private final Object mutex = new Object();

    @Override
    public int getNextValue() {
        synchronized (mutex) {
            return super.getNextValue();
        }
    }
}

Using a semaphore

A semaphore keeps a count of available permits. A thread takes one before entering and gives it back when it leaves. With one permit, it can protect this counter too. With two permits, two threads could enter together and we'd still have the race.

This version waits for a permit before touching the counter:

public class SequenceGeneratorUsingSemaphore extends SequenceGenerator {

    private final Semaphore mutex = new Semaphore(1);

    @Override
    public int getNextValue() {
        try {
            mutex.acquire();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            throw new IllegalStateException("Interrupted while waiting for the counter", e);
        }

        try {
            return super.getNextValue();
        } finally {
            mutex.release();
        }
    }
}

The two try blocks matter. If waiting is interrupted, the thread never gets a permit, so it mustn't release one. Otherwise, we'd accidentally allow an extra thread into the critical section. The Semaphore documentation covers that behavior.

Replacing new SequenceGenerator() in the test with any of these protected versions gives each call a distinct result. For this example, I'd use the synchronized method. The semaphore adds interruption handling without making the counter easier to read.