Synchronization Primitives • Compare-and-Swap & Atomic OperationsMedium⏱️ ~2 min
Building Algorithms with CAS
Key Insight
Most lock-free algorithms follow the same pattern: read current value, compute new value, CAS to update. If CAS fails (someone else updated), retry with the fresh value.
Lock vs CAS Pattern
The CAS Retry Loop
1) Read the current value. 2) Compute what you want to write. 3) CAS with expected=what you read. 4) If CAS fails, someone changed it: go to step 1.
Why This Works
CAS fails only if the value changed since you read it. By retrying with the new value, you guarantee your update is based on current data. No lost updates, no stale data.
Example: Atomic Counter
do {
old = counter.load();
new = old + 1;
} while (!counter.CAS(old, new));
old = counter.load();
new = old + 1;
} while (!counter.CAS(old, new));
Contention Concern
If many threads CAS the same location, most fail and retry. Under extreme contention, a lock might be faster. CAS shines when conflicts are rare.
Pattern: Read, compute, CAS, retry on failure. This is the backbone of lock-free programming.
💡 Key Takeaways
✓CAS retry loop: read, compute, CAS, repeat on failure. Standard lock free pattern.
✓No blocking: failed CAS just retries. Other threads can make progress independently.
✓Good for low contention: when conflicts are rare, most CAS succeed on first try.
✓Bad for high contention: many failing CAS waste CPU spinning. Locks let threads sleep.
✓Progress guarantee: at least one thread always succeeds (lock free property).
📌 Examples
1Lock free counter: widely used for metrics/statistics where precision matters but locking would hurt throughput.
2Lock free stack push: new.next = top; while (!CAS(&top, new.next, new)) { new.next = top; }