What is Compare-and-Swap?

Definition
Compare-and-Swap (CAS) is a hardware instruction that atomically compares a memory location to an expected value and, only if they match, replaces it with a new value. Returns whether the swap succeeded.
The Basic Operation
CAS(address, expected, new_value)
// If *address == expected:
//   *address = new_value, return true
// Else:
//   return false (value unchanged)
CAS Operation Flow
Memory: 5CAS(addr, 5, 10)Expected: 5, New: 10Match! Memory = 10, return trueCAS(addr, 7, 10)Expected: 7, New: 10No match! No change, return false
Why It Matters
CAS is the foundation of lock-free programming. Instead of locking, you try to make your change. If someone else changed the data first (CAS fails), you see the new value, recalculate, and try again. No blocking, no waiting.
Hardware Support
x86 has CMPXCHG. ARM has LDREX/STREX pairs. These are single instructions that are atomic at the hardware level. No other thread can see an intermediate state.
Key Point: CAS is optimistic: assume no conflict, detect if wrong, retry. Locks are pessimistic: assume conflict, prevent it upfront.

💡 Key Takeaways

✓CAS compares memory to expected value, swaps only if match. Returns success or failure.

✓Entire operation is atomic in hardware. No other thread can intervene between compare and swap.

✓Returns false if value changed since you read it. You can then retry with the new value.

✓Foundation of lock free algorithms. Updates without blocking other threads.

✓Available on all modern CPUs: x86 (CMPXCHG), ARM (LDREX/STREX), etc.

📌 Examples

1Atomic increment: do { old = value; } while (!CAS(&value, old, old+1)); Retry until success.

2Set flag once: CAS(&initialized, false, true). Returns true only for the first thread.

← Back to Compare-and-Swap & Atomic Operations Overview