Multithreading — A Mental Model

This post will (hopefully) be part of a series of personal notes that illustrate various concepts that I'll be trying to deep dive into in my spare time. I might be revisiting/changing the content as my understanding deepens and my breadth of reading widens.

A Broad Picture

A Practical Example

Let's take a sequence generator that increments the currentValue by one whenever its getNextValue method is called:

public class SequenceGenerator {

    private int currentValue = 1;

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

Now, let's see how this method behaves when multiple threads try to access it concurrently:

@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<>();

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

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

    executor.awaitTermination(1, TimeUnit.SECONDS);
    executor.shutdown();

    return uniqueSequences;
}

Once we execute this test case, we can see that it fails most of the time:

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

What we have here is a race condition: the three threads are accessing getNextValue() concurrently.

Let's use our mental model: we need to identify the critical section (getNextValue() in this case), and use a synchronization mechanism to make sure that only one thread can execute the method at a time.

Using a Mutex

Every object in Java has an intrinsic lock associated with it. The synchronized method and the synchronized block use this intrinsic lock to restrict the access of the critical section to only one thread at a time.

Therefore, when a thread invokes a synchronized method or enters a synchronized block, it automatically acquires the lock. The lock releases when the method or block completes or an exception is thrown from them.

Let's change getNextValue to have a mutex, simply by adding the synchronized keyword:

public class SequenceGeneratorUsingSynchronizedMethod extends SequenceGenerator {

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

The synchronized block is similar to the synchronized method, with more control over the critical section and the object we can use for locking:

public class SequenceGeneratorUsingSynchronizedBlock extends SequenceGenerator {

    private Object mutex = new Object();

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

Using a Sempahore

While a mutex only allows one thread to access a critical section, a semaphore allows a fixed number of threads to access a critical section. Therefore, we can also implement a mutex by setting the number of allowed threads in a Semaphore to one.

Let's now create another thread-safe version of SequenceGenerator using Semaphore:

public class SequenceGeneratorUsingSemaphore extends SequenceGenerator {

    private Semaphore mutex = new Semaphore(1);

    @Override
    public int getNextSequence() {
        try {
            mutex.acquire();
            return super.getNextSequence();
        } catch (InterruptedException e) {
            // exception handling code
        } finally {
            mutex.release();
        }
    }
}

If we now modify our test to instantiate SequenceGeneratorUsingSynchronizedMethod, SequenceGeneratorUsingSynchronizedBlock or SequenceGeneratorUsingSemaphore, it will pass.