Atomic Operations and Compare-and-Swap
You'll learn how hardware-level atomic operations, especially compare-and-swap (CAS), enable lock-free algorithms by guaranteeing indivisible memory updates.
The Foundation of Lock-Free Programming
In lock-free programming, you can't use locks or synchronized blocks—yet you still need to safely update shared data. This is where hardware-level atomic operations come in. These operations are guaranteed by your CPU to execute completely without interruption, as if they were a single, indivisible instruction.
The most powerful atomic operation is compare-and-swap (CAS). It performs three steps atomically:
- Read a value from memory
- Compare it to an expected value
- If they match, swap in a new value; otherwise, do nothing
All three steps happen as one uninterruptible unit.
How CAS Works
Imagine you're updating a shared counter. With CAS, you say: "I last saw this counter at 42. If it's still 42, change it to 43. If someone else changed it, tell me it failed."
This lets you detect and handle interference from other threads. If CAS fails, you simply retry with the updated value—no locks needed.
while (true) {
current = counter.get()
next = current + 1
if (CAS(counter, current, next)) {
break // Success!
}
// Failed—someone modified counter, retry
}
Why CAS Matters
CAS is the building block for lock-free data structures. It avoids the overhead and blocking of locks while still ensuring correctness. Modern CPUs provide CAS instructions (like CMPXCHG on x86), making it efficient at the hardware level.
Key Takeaway: Compare-and-swap is a hardware-supported atomic operation that reads, compares, and conditionally updates memory in one indivisible step, forming the foundation of lock-free algorithms.