Write It Only If Nobody Moved It, and Try Again If They Did

Last timeThe Only Ordering You Are Promised

One instruction compares and writes in a single step and tells you whether it worked. Built into a retry loop it removes blocking, and puts a different failure in its place.

The one primitive

The previous lesson ended on the question of which of two competing writes

wins, and noted that an operation reporting what it replaced would settle it.

That operation exists and almost every processor has it.

Compare-and-swap takes three things: a location, the value you believe is

there, and the value you want to put there. It writes the new value only if the

location currently holds the expected one, performs the whole comparison and

write as one indivisible step, and reports whether it wrote.

The report is what makes it more than an atomic store. Failure is information:

it tells you that somebody else changed the location since you read it, which

is precisely the thing a plain read-modify-write can never discover.

FIG 1An increment with no lock

plaintext

to add one to a shared counter:

  repeat:
    old = read the counter
    new = old + 1
    if compare-and-swap counter, old, new
      succeeded, stop
    otherwise
      somebody changed it, go round again

compare-and-swap counter, old, new means:
  if the counter still holds old,
  replace it with new and report success.
  otherwise change nothing and report failure.
  all of that as one indivisible step.

Five lines, no waiting and no lock. The loop looks like busy work and is not: the only way round the loop a second time is if another thread succeeded, which means the system as a whole moved forward.

The retry loop

The pattern generalises to any update at all, and it is worth stating in its

general form because the same four steps recur everywhere.

FIG 2The shape of every lock-free update

The loop back is not a retry after an error. It happens exactly when another thread succeeded, so every pass that fails is evidence that the system progressed. That distinction is what separates this from spinning.

FIG 3Two threads incrementing the same counter

step	step	thread one	thread two	counter	what happened
1	1	reads 5, computes 6	reads 5, computes 6	5	Both threads have the same stale plan. Under a plain read-modify-write this is the lost update from lesson two.
2	2	swaps 5 for 6, succeeds	about to attempt	6	Thread one got there first. The counter is now six and thread one is finished.
3	3	finished	swaps 5 for 6, fails	6	Thread two finds 6 where it expected 5. Nothing is written and it is told so, which is exactly the information the plain version lacked.
4	4	finished	reads 6, computes 7, succeeds	7	It starts again from what is actually there. Two increments, final value seven, nothing lost.

4 steps

Compare this with the trace in lesson two, which is the same interleaving step for step. The only difference is that the second write asked a question before writing, and the answer sent it round again.

What replaces blocking

Nothing here waits. No thread holds anything, so no thread can be blocked by

another, and the entire deadlock chapter stops applying: there are no locks to

order, no cycles to form, and a thread that is suspended by the scheduler

midway through blocks nobody at all. That last point is the strongest practical

argument for the technique, because a thread holding a lock when it gets

preempted stops everybody for a whole scheduling quantum.

What you get in exchange is a different shape of failure.

The system always progresses: whenever an attempt fails, some other attempt

succeeded, so somebody is always moving forward. That property is what the word

lock-free means, and it is a guarantee about the system rather than about any

particular thread.

An individual thread has no such guarantee. A slow thread on a busy location

can lose every race it enters, go round the loop indefinitely, and complete

nothing while burning a core. The system is healthy and that thread is starving.

It is rare, it is real, and it is the thing to watch for rather than deadlock.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents