Part 2 of 7 · 2 min read
Atomic
Think of it this way. A bank counter window handles one customer from the first word to the last coin. Nobody else is served halfway. The analogy stops in one place: a window serves customers for minutes, while an atomic instruction takes a few nanoseconds.
In plain words: An atomic operation is an operation that appears to the rest of the system to happen in a single step. No other thread can see it half done, or can change the data in the middle. The processor guarantees it, usually by locking the cache line of the data for the duration of the instruction (Level 2, page 6).
Three atomic operations are enough for almost all synchronisation. Written as ordinary code for clarity (the real instruction does all of it at once):
/* fetch-and-add: add and return the old value */
int fetch_add(int *p, int v) { int old = *p; *p = old + v; return old; }
/* test-and-set (exchange): store a value and return the old one */
int test_and_set(int *p, int v) { int old = *p; *p = v; return old; }
/* compare-and-swap: store new only if the value still equals expected */
int cas(int *p, int expected, int new) {
if (*p == expected) { *p = new; return 1; }
return 0;
}
With fetch-and-add, the lost-update counter of Level 2, page 4 becomes safe with no lock. Four threads each adding 1 two million times with __atomic_fetch_add (the GCC built-in) reach the exact total, where a plain counter++ loses updates. On x86 the compiler uses a lock-prefixed instruction. The cost is higher than a plain increment: in one test, a million plain increments took 0.003 s on one thread and a million atomic ones 0.007 s.
Page 1 showed that Peterson's lock needed sequentially consistent ordering. An atomic read-modify-write also acts as a barrier on x86, which is part of why the following locks work.
Atomic operation
An atomic operation is an operation on memory that the hardware carries out as one indivisible step, so that no other processor or thread can observe it half finished or change the data in its middle.
Example: __atomic_fetch_add(&counter, 1, ...) reads and increases counter in one step, so two threads that run it cannot both read the same old value.
Check yourself: 1. What does test-and-set return? 2. Why does fetch-and-add remove the lost-update problem? 3. Why is an atomic increment slower than a plain one?