The Value Came Back

Compare-and-swap asks whether the value is still what you read. Something can change and change back, the comparison succeeds, and everything you concluded from it is wrong. Reading the code more carefully will not help.

Core19 min read4 exercises

Previously on

Section 14.8 ended on a retry loop:

do {
    head = top.get();
    next.next = head;
} while (!top.compareAndSet(head, next));

The compare asks whether the top is still the object you read. If it is, the reasoning goes, nothing has changed, so it is safe to swap.

That reasoning has a hole in it.

The problem

Compare-and-swap compares a value. You have been reading it as though it compares a history.

String seen = ref.get();          // reads A
// ... another thread does its work ...
ref.compareAndSet(seen, "C");     // succeeds if the value is still A

Between those two lines, another thread can set the reference to B and then back to A.

Verified:

plain CAS after A->B->A : true   <- it could not tell

The value is A. The comparison passes. Your swap goes through, and everything you assumed because it passed is wrong.

Why that matters for the stack. Take the lock-free stack from last section, and imagine popping:

Node<T> head = top.get();
// I will swap top from head to head.next

How a pop can corrupt the stack

Thread 1 reads the topThe stack is A, then B, then C. It reads head = A and plans to set top to B.
Thread 1 is descheduledRight there, before its compare-and-swap.
Thread 2 pops A and pops BThe stack is now just C. B is no longer part of anything.
Thread 2 pushes A backThe stack is A, then C. The same A object, reused.
Thread 1 wakes and swapsIt expected top to be A. It is. So the swap succeeds and top becomes B, which was removed two steps ago.

The stack now claims its top is a node that was popped, and whatever B still points at comes back with it. C has been lost.

Every instruction was correct. The comparison did exactly what it promises. The gap is between “the value is the same” and “nothing has happened”, and only one of those is what you needed.

And you cannot find it by reading. The code is right. The bug lives in a window of a few nanoseconds and needs a particular interleaving. It will not happen while you are watching, and it will happen under load.

The idea

Compare a version, not just a value.

A value can return to what it was. A number that only ever goes up cannot.

AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);

int[] stampHolder = new int[1];
String seen = ref.get(stampHolder);         // value, and the stamp comes back in the array
int seenStamp = stampHolder[0];             // 0

// another thread: A -> B (stamp 1), then B -> A (stamp 2)

ref.compareAndSet(seen, "C", seenStamp, seenStamp + 1);

stamped CAS after same  : false  <- version moved 0 -> 2
value is still          : A, stamp 2

The value is A, exactly as before. The stamp is 2 and you expected 0, so the swap fails. Your thread goes back round the loop, reads the current state, and tries again with what is actually there.

The odd int[] parameter is Java’s way of returning two things from one call, which is one of the places the absence of tuples shows.

	Class	What it carries
AtomicReference<T>	a reference	cannot tell a change-and-change-back from no change
AtomicStampedReference<T>	a reference and an int	the stamp catches it. You increment it yourself
AtomicMarkableReference<T>	a reference and a boolean	for one bit of state, like "logically deleted"

When you do not need any of this. ABA needs a value to come back, which usually means an object being reused.

For a counter it cannot happen in any way that matters. AtomicInteger going 5, 6, 5 is a real sequence of increments, and adding one to 5 is correct whichever 5 it is. Values that are only ever added to are safe.

It bites when a reference identifies a position in a structure, which is exactly what a lock-free stack, queue or list does. Java’s garbage collector helps here in a way C does not: a node still referenced by your thread cannot be freed and reallocated as something else, so the worst version of the bug is not possible. Reuse by your own code still is.

Now the other failure of retry loops. They cannot deadlock, and they can spin.

Eight threads, 200,000 increments each:

value 1600000, failed attempts 2894619

The answer is right. It took nearly three million failed attempts to get 1.6 million successes, so most of the work was thrown away.

	Failure	What it looks like
Deadlock	locks only	everything stops. Threads sit in BLOCKED. Visible in a dump
Livelock	lock-free	threads run hard, retry, and finish nothing. Looks busy
Starvation	both	one thread keeps losing while the others get through

Deadlock at least announces itself by stopping. A retry loop that keeps losing looks like a program working hard, and every measurement agrees that the processor is busy.

Under the hood

Going deeper

The stamped reference allocates. There is no processor instruction that swaps a reference and an int together, so AtomicStampedReference holds one object containing both, and swaps that object.

Every successful change allocates a new pair. Lock-free code chose this path partly to avoid the cost of blocking. Now it allocates on every update, and the garbage collector in Phase XIII has to clean that up. A real trade rather than a free fix.

Backing off helps a losing loop. A thread that keeps failing can wait a moment before its next attempt:

int attempts = 0;
while (!ref.compareAndSet(seen, next)) {
    if (++attempts > 10) {
        Thread.onSpinWait();          // tell the processor we are spinning
    }
    seen = ref.get();
}

Thread.onSpinWait() arrived in Java 9. It compiles to a pause instruction. That tells the processor this is a spin loop, so it can save power and give the other hardware thread on that core more room. It does not release anything and it does not sleep.

For heavier contention, waiting a little longer after each failure spreads threads out so they stop colliding, which is the same idea networks use for collisions.

Sometimes the answer is a lock. The eight thread row in Section 14.8 already said it: ReentrantLock beat AtomicInteger at 326 ms against 179. A lock parks the losers, so they stop competing for the cache line, and the winner finishes faster.

Lock-free is right when contention is low to moderate and the operation is short. It is also right when a thread being descheduled while holding a lock would be a real problem. It is not automatically better, and it is much harder to get right.

What it costs

The stamp is bookkeeping you have to maintain by hand. Increment it on every change, everywhere, and one place that forgets reopens the hole with nothing to warn you.

It also costs an allocation per update, which was one of the things lock-free code was meant to avoid. On a hot path that pressure shows up as garbage collection rather than as contention, so the cost moves somewhere else rather than going away.

The bug it fixes is close to untestable. It needs a specific interleaving in a window of nanoseconds, so a test that passes ten million times proves very little. Most ABA bugs are found by reasoning or by a rare production failure that nobody can reproduce.

Livelock is worse to diagnose than deadlock. A deadlocked program stops, and the thread dump names the locks. A livelocked one runs at full speed, reports healthy processor usage, and gets through less work than a single thread would.

And the general problem stands: single variable atomicity does not compose. Two atomic operations are still two, and building a correct structure out of them takes more care than almost any codebase can afford.

Check yourself

Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.

What is the ABA problem, in one sentence, and why can you not see it by reading the code?
Show the answer
A value changes from A to B and back to A, so a compare-and-swap expecting A succeeds even though the world has moved on.

Verified: read A, then let another thread set B and then A again, then compare-and-swap expecting A. It returned true. The comparison is doing exactly what it promises, which is to compare the value.

You cannot see it in the code because the code is correct. The bug is a gap between two instructions, and it needs a specific interleaving that will not happen while you are looking.

The mistake is in the reasoning around it. "Still A" was taken to mean "nothing has happened", and those are two different statements.
How does `AtomicStampedReference` fix it?
Show the answer
By comparing a version number as well as the value, and increasing the version on every change.

A value can return to A. A version that only ever goes up cannot. So a swap expecting A at version 0 fails once the version has reached 2, even though the value looks identical.

Verified: the same A to B to A sequence, with stamps. The plain reference said true. The stamped one said false, because the stamp had moved from 0 to 2.

The cost is an extra object holding the pair, allocated on every change, which is exactly the allocation lock-free code was trying to avoid.
Lock-free code cannot deadlock. What can go wrong instead?
Show the answer
Starvation and livelock. Nothing is stuck, and one thread may make no progress at all.

A thread whose compare-and-swap keeps failing keeps retrying. It is running, using a core, and finishing nothing. Under enough contention a slow or unlucky thread can lose every race for a long time.

Measured: eight threads doing 200,000 increments each got the right answer, 1,600,000, and took 2,894,619 failed attempts to get there. Nearly two wasted tries for every one that counted.

Deadlock at least stops and shows up in a thread dump. This looks like a healthy busy program that is slower than it should be.

Exercises

Write each solution in VS Code, predict its result, and then run the checks. Reading an example does not replace implementing it.

4 exercises105 pointsabout 110 minutes

The Layers of Logic VS Code extension runs the checks for exercises marked checked. For a manual exercise, run the program and compare its behaviour with the stated requirements and sample output.

Change It and Change It Back

Real work·25 min·25 points

ex-14-9-a

Predict the plain result before you run it. Most people say false.

It returns true, and nothing is broken. The comparison did exactly what it promises, which is to compare the value. The mistake is one level up, in reading “still A” as “nothing has happened”.

The stamped version costs an extra object and one number you have to remember to increment. That is the whole fix, and the last question tells you when you can skip it entirely.

What your program must do

Predict the plain compareAndSet result after A to B to A, then check
Do the same with a stamped reference and compare
Say what the plain compare concluded and why it was wrong
Say why a counter is unaffected by this problem

CameBack.java

import java.util.concurrent.atomic.*;

public class CameBack {
    public static void main(String[] args) throws Exception {
        // TODO: an AtomicReference holding "A". Read it into a variable.
        //       Then set it to "B" and back to "A".
        //       Then compareAndSet(seen, "C"). Predict the answer first.
        // TODO: do the same with AtomicStampedReference, incrementing the stamp
        //       on every change. Predict again.
        // TODO: say in one sentence what the plain version concluded, and why
        //       that conclusion was wrong
        // TODO: say why an AtomicInteger counter does not care about any of this
    }
}

Hint 1

The plain one returns true. The value is A, so the comparison passes, exactly as documented.

Hint 2

The stamped version returns false, because the stamp moved from 0 to 2 even though the value came home.

Hint 3almost the answer

For a counter, 5 to 6 to 5 is a real sequence of increments, and adding one to 5 is correct whichever 5 it is. ABA bites when a reference identifies a POSITION in a structure rather than a value.

Corrupt Your Own Stack

Hard·30 min·30 points

ex-14-9-b

Widen the window on purpose. This bug will not show up on its own while you are watching.

The pause inside pop is what makes it reproducible, and it is not cheating. In production that pause is the operating system descheduling your thread for a few microseconds, which happens constantly.

When it corrupts, account for every node. B comes back from the dead and C disappears, and no line of your code was wrong.

What your program must do

Force the ABA interleaving with a deliberate pause inside pop
Predict what the paused thread's compare-and-swap does, then check
Print the resulting stack and account for every node
Fix it with a stamped reference and confirm the corruption is gone

Corrupt.java

import java.util.concurrent.atomic.*;

public class Corrupt {
    // TODO: take your lock-free stack from Section 14.8.
    //       Add a pause hook inside pop, between reading the top and the CAS.

    public static void main(String[] args) throws Exception {
        // TODO: push A, B, C. Start a pop on thread 1 and pause it after the read.
        // TODO: from thread 2: pop A, pop B, push A back.
        // TODO: let thread 1 finish its compareAndSet. Predict the result.
        // TODO: print the whole stack afterwards. Where did C go?
        // TODO: fix it with AtomicStampedReference and repeat
    }
}

Hint 1

A CountDownLatch or a simple sleep inside pop, between reading the top and calling compareAndSet, makes the window as wide as you like.

Hint 2

Thread 1 expected the top to be A. It is A, because thread 2 pushed the same object back. So the swap succeeds and the top becomes B, which was popped two steps ago.

Hint 3almost the answer

After that, C is unreachable and B is back in a stack it had left. Nothing threw, and every individual operation was correct.

Count the Wasted Work

Real work·25 min·25 points

ex-14-9-c

Count what gets thrown away.

The answer is always right, so nothing suggests a problem. The only evidence is that most of the attempts were discarded, and the proportion grows sharply with threads.

The last question is the practical one. Deadlock announces itself by stopping. This announces itself by looking busy, and telling the two apart from the outside is a skill worth having before you need it.

What your program must do

Record successes and failures at four different thread counts
Express the wasted work as a percentage at each
Compare with LongAdder
Say what this failure would look like on a production dashboard

Wasted.java

import java.util.concurrent.atomic.*;

public class Wasted {
    static final AtomicInteger value = new AtomicInteger();
    static final AtomicLong failures = new AtomicLong();

    public static void main(String[] args) throws Exception {
        // TODO: a retry loop with a failure counter, run at 1, 2, 4 and 8 threads.
        //       Keep the total number of increments the same.
        // TODO: record successes and failures at each thread count
        // TODO: work out the wasted work as a percentage
        // TODO: do the same with LongAdder and compare
        // TODO: say how you would notice this in production
    }
}

Hint 1

At eight threads one run gave 1,600,000 successes and 2,894,619 failures. Nearly two thirds of the attempts were discarded.

Hint 2

The failure count does not grow gently with threads. Plot it and the shape is the point.

Hint 3almost the answer

On a dashboard this looks like healthy high processor usage and lower throughput than expected. There is no error, no exception and nothing in the logs, which is what makes it harder to find than a deadlock.

Read Somebody Else's Lock-Free Code

Hard·30 min·25 points

ex-14-9-d

Go and read the real thing.

You now have everything you need to follow it: compare-and-swap, retry loops, the memory model, ABA, and why the bucket matters. Six sections ago none of this would have parsed.

Read the comments as carefully as the code. The ratio is the message: these classes are mostly explanation, because the reasoning behind each line cannot be recovered by looking at it. That is also the strongest argument for using them rather than writing your own.

What your program must do

Find the retry loop in ConcurrentLinkedQueue and describe it
Find a comment covering a case you would not have anticipated
Find what ConcurrentHashMap locks on a put, and say why it is not one lock
Compare both with the stack you wrote yourself

ReadIt.java

import java.util.concurrent.*;

public class ReadIt {
    public static void main(String[] args) throws Exception {
        // TODO: open the source of ConcurrentLinkedQueue.offer from src.zip
        //       and find the retry loop
        // TODO: find the compareAndSet call and say what it is comparing
        // TODO: find a comment explaining a case you would not have thought of
        // TODO: now open ConcurrentHashMap.putVal and find where it locks.
        //       What exactly does it lock, and why is that not one big lock?
        // TODO: compare both against your own stack from Section 14.8
    }
}

Hint 1

The JDK source is in lib/src.zip inside your Java installation. Unzip it and read java.base/java/util/concurrent/.

Hint 2

ConcurrentHashMap locks the first node of the bucket, not the whole map. Two threads writing to different buckets never meet, which is why it scales the way it does.

Hint 3almost the answer

Look at how much of the code is comment. These classes are mostly explanation, because the reasoning cannot be recovered from the instructions.

After the credits

Nine sections in, and you are still writing this:

Thread t = new Thread(job);
t.start();

Every one costs a stack of around a megabyte before it does anything, from Section 13.1. It cannot be restarted. It cannot return a value, because Runnable.run() returns void. It cannot throw a checked exception. And if it fails, the failure goes nowhere.

Section 14.10 replaces all of it. An ExecutorService holds a pool of threads and takes work, so threads are made once and reused. Callable returns a value and is allowed to throw. Future is a receipt you can wait on, which is where a worker’s exception finally reaches the thread that started it.

It also answers the sizing question raised by the two kinds of work in Section 14.1, and explains why Executors.newFixedThreadPool is the wrong way to build one.

The ABA problem will return in Phase XIV. Concurrency