LLD Dojo

Designing under pressure · chapter 32 of 33

Two threads, one object

Chapter 4.4 · Part 4, Designing under pressure · about 40 minutes

What you need before this chapter: Parts 1 to 3 of this course, plus chapters 4.1 to 4.3. Nothing before this chapter used more than one thread. This is your first real concurrency, and it is also the last chapter before Part 4 hands you a full graded round.

When you finish this chapter you will be able to:

1. One object, two threads

Here is the whole program. A counter with one field, and a method that adds one to it.

public class Counter {

    private int count = 0;

    public void increment() {
        count++;
    }

    public int get() {
        return count;
    }
}

Nothing here is wrong on its own. Called from one thread, increment() behaves exactly as written, every time, forever. The problem this chapter is about only exists once a second thread starts calling the same method on the same Counter at the same time. Here is that second thread:

int perThread = 1_000_000;
Counter counter = new Counter();

Runnable work = () -> {
    for (int i = 0; i < perThread; i++) {
        counter.increment();
    }
};

Thread t1 = new Thread(work);
Thread t2 = new Thread(work);
t1.start();
t2.start();
t1.join();
t2.join();

int expected = perThread * 2;
System.out.println("expected: " + expected + "  actual: " + counter.get()
    + "  lost: " + (expected - counter.get()));

Two threads, one Counter, one million increments each. Two million increments happen. counter.get() should report two million.

2. Run it, and run it again

Here is the same program, compiled once and run eight times in a row, with nothing changed between runs:

expected: 2000000  actual: 1156595  lost: 843405
expected: 2000000  actual: 1031374  lost: 968626
expected: 2000000  actual: 1866702  lost: 133298
expected: 2000000  actual: 1677930  lost: 322070
expected: 2000000  actual: 1898231  lost: 101769
expected: 2000000  actual: 1496919  lost: 503081
expected: 2000000  actual: 1077966  lost: 922034
expected: 2000000  actual: 1650392  lost: 349608

Every single run lost somewhere between roughly 100,000 and 970,000 increments, and no two runs lost the same number. Nothing here is random in the sense of a coin flip. Both threads did exactly what the code told them to. The number that comes out depends on the exact order the operating system happened to interleave the two threads, on this run, on this machine. That is precisely what a race is: correctness that depends on timing nobody controls. State that honestly rather than quoting one run as if it were the answer. If you build the same program yourself and run it, expect a different spread of numbers, not the same eight.

3. What count++ actually does

count++ reads as one operation. It is not one operation. Compile Counter.java and read the increment() method back with javap -c:

public void increment();
  Code:
     0: aload_0
     1: dup
     2: getfield      #7    // Field count:I
     5: iconst_1
     6: iadd
     7: putfield      #7    // Field count:I
    10: return

Three steps that matter: getfield reads the current value of count. iadd adds one to it. putfield writes the result back. Nothing stops a second thread from running its own getfield between this thread's getfield and its putfield. When that happens, both threads read the same starting value, both compute the same next value, and both write it back. One of the two increments is silently gone, and nothing in the program noticed, because every individual instruction executed correctly. The bug lives entirely in the gap between three instructions that look, from the source code, like a single line.

4. The fix that just works: synchronized

Wrap both methods in a lock, and the three-step read, add, write sequence becomes one step as far as any other thread can tell:

public class Counter {

    private int count = 0;

    public synchronized void increment() {
        count++;
    }

    public synchronized int get() {
        return count;
    }
}

synchronized on a method takes a lock on this before the method body runs, and releases it when the method returns. While one thread holds that lock, a second thread calling increment() on the same object has to wait its turn. The three steps inside increment() can no longer be interleaved with another thread's three steps, because the second thread cannot even begin until the first one has finished all three. Run the same experiment five times with this version:

expected: 2000000  actual: 2000000  lost: 0  time: 25ms
expected: 2000000  actual: 2000000  lost: 0  time: 43ms
expected: 2000000  actual: 2000000  lost: 0  time: 53ms
expected: 2000000  actual: 2000000  lost: 0  time: 42ms
expected: 2000000  actual: 2000000  lost: 0  time: 43ms

Zero lost, every single run. This is not a smaller chance of losing an update. It is a guarantee of never losing one, because the two threads can no longer both be inside increment() at once.

5. A narrower, faster fix: AtomicInteger

synchronized protects a whole method body, which is more than a single counter needs. The JDK ships a class built for exactly one job, adding a number safely under contention, and it does that job without ever taking a lock at all:

import java.util.concurrent.atomic.AtomicInteger;

AtomicInteger counter = new AtomicInteger(0);

Runnable work = () -> {
    for (int i = 0; i < perThread; i++) {
        counter.incrementAndGet();
    }
};

incrementAndGet() is built on a hardware instruction called compare-and-swap: read the current value, compute the new one, and write it back only if nobody else changed the value in between. If somebody did, the whole read-compute-write happens again, automatically, until it succeeds. No thread ever blocks waiting for another one to finish. Run the same experiment five times:

expected: 2000000  actual: 2000000  lost: 0  time: 13ms
expected: 2000000  actual: 2000000  lost: 0  time: 13ms
expected: 2000000  actual: 2000000  lost: 0  time: 14ms
expected: 2000000  actual: 2000000  lost: 0  time: 15ms
expected: 2000000  actual: 2000000  lost: 0  time: 13ms

Zero lost, exactly like the synchronized version, and roughly three times faster on this machine: about 13 to 15 milliseconds against about 25 to 53. Neither number is a promise about your own machine. The comparison between the two is the point, not the milliseconds themselves.

Reach for AtomicInteger, or one of its siblings such as AtomicLong, whenever the whole invariant you need to protect lives in exactly one number. Reach for synchronized, or a Lock, once an operation has to update more than one field as a unit. The same is true once it has to check a condition and act on it without another thread changing the answer first. A single counter is the easy case this chapter used to show the bug clearly. Chapter 4.5's problems, and lesson E1 right after this chapter, both spend most of their time on the harder case: several pieces of state that have to move together.

Going deeper

Everything above was about atomicity: making sure a read-modify-write sequence cannot be split by another thread. There is a second, separate problem that synchronized also solves, and most treatments of this topic skip it. It is called visibility, and it can hang a program forever with no exception and no wrong number anywhere.

public class StopFlag {
    static boolean stop = false;

    public static void main(String[] args) throws InterruptedException {
        Thread worker = new Thread(() -> {
            long iterations = 0;
            while (!stop) {
                iterations++;
            }
            System.out.println("worker stopped after " + iterations + " iterations");
        });
        worker.setDaemon(true);
        worker.start();
        Thread.sleep(1000);
        stop = true;
        worker.join(5000);
        System.out.println("worker still alive after 5s wait: " + worker.isAlive());
    }
}

The main thread sets stop = true after one second. The worker thread reads stop on every pass of a tight loop and should notice within nanoseconds. Run it, and here is the real output, on three separate runs:

worker still alive after 5s wait: true
worker still alive after 5s wait: true
worker still alive after 5s wait: true

The worker never stops. The write genuinely happened, on the main thread, but nothing obliges another thread to ever see it. The loop body never assigns to stop, so the JIT compiler is free to notice that and read the field from a register once, never checking main memory again. On this machine it does exactly that. This is not a lost update. No arithmetic went wrong anywhere. A thread is reading a value that is stale forever, because no rule in the Java Memory Model required the write to become visible to it.

Mark the field volatile, and every write to it happens-before every later read of it, across threads, guaranteed:

static volatile boolean stop = false;

Same program, same loop, three more runs:

worker stopped after 4015461504 iterations
worker still alive after 5s wait: false
worker stopped after 4089736458 iterations
worker still alive after 5s wait: false
worker stopped after 4038922335 iterations
worker still alive after 5s wait: false

The worker now stops within a fraction of a second every time, after around four billion iterations of a loop that does almost nothing per pass. This is the fact worth carrying forward: synchronized was never only about stopping two threads from running the same block at once. Entering and leaving a synchronized block forces this same guarantee too, in both directions. That is why the Counter fix in section 4 was correct for a reason beyond keeping two threads out of the same method. AtomicInteger carries the identical guarantee on every read and write internally, which is one more reason it is the right tool here, and not merely a smaller workaround for the same problem.

Next: chapter 4.5, Your first full round, start to finish — where everything from Parts 1 to 4 comes together in one timed attempt at a real problem.

← 4.3 Drawing a class diagram fast · All chapters · 4.5 Your first full round, start to finish →