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. Call it from one thread and increment() behaves exactly as written, every time, forever.

The problem in this chapter only exists once a second thread calls 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, so counter.get() should report two million.

2. Run it, and run it again

Here is that 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 run lost somewhere between roughly 100,000 and 970,000 increments. No two runs lost the same number.

Nothing here is random in the coin-flip sense. Both threads did exactly what the code told them.

The number you get 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.

Say that plainly rather than quoting one run as if it were the answer. Build the same program yourself and expect a different spread of numbers, not these eight.

3. What count++ actually does

count++ reads as one operation. It is three.

Compile Counter.java and read increment() 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 matter here. getfield reads the current value of count. iadd adds one. putfield writes the result back.

Now find the gap. Nothing stops a second thread 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. 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, in your source, like a single line.

4. The fix that just works: synchronized

Wrap both methods in a lock. The three-step read-add-write 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 body runs and releases it on return.

While one thread holds that lock, a second thread calling increment() on the same object waits its turn. The three steps can no longer interleave with another thread's three steps, because the second thread cannot begin until the first 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 run.

That is not a smaller chance of losing an update. It is a guarantee of never losing one, because two threads can no longer both be inside increment().

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.

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 it in between. If somebody did, the whole read-compute-write happens again, automatically, until it succeeds.

No thread ever blocks waiting for another.

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 machine. The comparison between the two is the point, and not the milliseconds.

So here is how you choose.

Reach for AtomicInteger, or a sibling like 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. Same answer 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, used here 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 synchronized also solves, and most treatments skip it. It is called visibility, and it can hang your 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 reads stop on every pass of a tight loop, so it should notice within nanoseconds.

Run it. 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. Nothing obliges another thread to ever see it.

Here is the mechanism. 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.

Now carry the real point forward. synchronized was never only about stopping two threads running the same block at once. Entering and leaving a synchronized block forces this same visibility guarantee, in both directions.

That is why the Counter fix in section 4 was correct for a reason beyond keeping two threads out of one method.

AtomicInteger carries the identical guarantee on every read and write internally. One more reason it is the right tool here, and not merely a smaller workaround.

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 →