An introduction to lockless algorithms

An introduction to lockless algorithms

Using Lamport's approach when reasoning about concurrency is very powerful. It's much more rigorous and applicable than you might expect, and it can explain many behaviors easily at a glance that you might struggle over. For instance, in a lockless memory allocator, you need to grab a pointer from a freelist head and claim it for the caller (in the implementation of alloc), and then you need to update the freelist pointer to point to the next free block before you're done (very simplified).

Therefore the allocation is split into two distinct actions. The system however, may preempt your thread after a block is claimed, but before the freelist head is updated. Then another thread could also allocate and erroneously pull the same block, which can't be allowed.

The traditional, simplistic solution to this is to pack a counter value together with every freelist address. When you perform any operation on the freelist, including claiming blocks or updating pointers, you use a CAS2 operation ("Compare-and-swap, for two words of memory") to both update a value, and also increment the counter by one next to it. You can then check the counter value against a known value, to check preemption. If the counter value is g at the beginning and no thread interrupted you, then the result you get back at the end of everything, when you read the counter, should be g+1, i.e. no other threads performed any actions between your own, and so what you did was seen as atomic. If it's any other value, you've been preempted, the address you have in your hand is claimed by someone else, and you must start over.

But this can all be stated another way: every object needs a lamport counter associated with it. By examining the counter, you can determine if you are responsible for a casual action identified by the counter n, as well as n+1. If you are in fact responsible for both of these actions, then n by definition occurred before n+1, and thus no other threads were able to see the indeterminate state of the object. In this way, a Lamport counter is a kind of concrete algorithm for ensuring atomic broadcast amongst threads.

Frankly I consider "Time, Clocks, and Ordering of Events in a Distributed System" is a mandatory text for any modern software engineer. Actually, practically every text written by Lamport is extremely important to read...