Atomic Operations

Atomic operations provide synchronization by ensuring that a read-modify-write operation occurs as a single, indivisible (hence atomic) step, so other threads cannot observe the operation as a partially completed.

CPU and Cache

Multiple CPU cores can execute instructions at the same time (TODO:SMT). Each core has its own registers and usually its own L1 and L2 caches. A larger L3 cache is often shared between the cores. The same memory location can exist in more than one cache.

The CPU uses cache coherence, a system used by multiple CPU cores to keep their cached copies of the same memory consistent. MESI is one such protocol, that describes the state of a cache line in each CPU cache. States from:

• Modified: this cache has the only copy, and it was changed.
• Exclusive: this cache has the only copy, and it was not changed.
• Shared: multiple caches have the same clean copy.
• Invalid: this cache's copy cannot be used.

When one core writes to a cache line, copies in other cores are typically invalidated. The core that wants to write must first get exclusive access to that cache line.

Cache coherence keeps copies of memory consistent. It does not make a sequence of normal loads and stores atomic, and it does not decide the order in which normal operations become visible to other cores.

Atomic Instructions

CPUs provide instructions for atomic operations. On x86, LOCK XADD can add a value to memory atomically. Other CPUs can use a single atomic instruction or a retry loop built from a pair of instructions.

LOCK XADD [address], register

The LOCK prefix does not normally lock the entire memory bus. The CPU usually uses the cache coherence system to get exclusive access to the relevant cache line. The important part is that another core cannot perform a conflicting operation halfway through the XADD.

Compare-and-Swap

Conceptually, CAS changes a value only if it still equals an expected old value:

old = load(address)
if *address == old:
    *address = new
    return true
return false

If another thread changes the value first, the operation fails. The code can load the new value and try again. This is useful for building lock-free data structures, but those data structures are hard to implement correctly.

Memory Ordering

Atomicity and memory ordering are different things. Atomicity means that another thread cannot observe an atomic operation halfway through. Memory ordering controls the ordering and visibility relationships between the atomic operation and other memory operations

The compiler and CPU can reorder normal operations when the result for a single thread stays the same. Atomic operations add ordering constraints:

writer: data = 42
        release_store(ready, true)

reader: if acquire_load(ready) == true:
            read(data)

The writer first sets data to 42, then performs a release store to ready. The reader performs an acquire load of ready. If it observes true, the earlier write to data is guaranteed to be visible to the reader. The exact syntax depends on the programming language and its memory model.

Performance Under Multiple Threads

An atomic value can become a performance bottleneck when many cores update it repeatedly. Every write needs exclusive access to the cache line. The cache line can move between cores after every update:

Core 1 writes -> cache line moves to Core 1
Core 2 writes -> cache line moves to Core 2
Core 3 writes -> cache line moves to Core 3

One way to reduce this is to split a counter into several counters and let each core update a different one. The final value is the sum of all counters.

Unrelated values can also become slower when they share the same cache line. Adding padding between them can prevent false sharing.

Glossary

Cache line

The block of memory that a CPU cache moves and tracks as one unit. It is usually larger than one variable, often 64 bytes on modern CPUs.

False sharing

A performance problem where unrelated variables share one cache line and writes to one variable invalidate the line for the other variable.

Lock-free

An algorithm where the system as a whole always makes progress: even if one thread is paused or delayed, other threads can still complete their operations.