What is the Compare-and-Swap (CAS) Instruction?
Learn what compare-and-swap (CAS) is, how it enables lock-free synchronization, and the ABA problem, with OS interview questions answered.
Expected Interview Answer
Compare-and-swap (CAS) is an atomic CPU instruction that reads a memory location, compares it to an expected value, and only writes a new value if the comparison succeeds, all as one indivisible hardware operation that lets software build lock-free synchronization primitives.
CAS takes three operands: the memory address, an expected old value, and a desired new value. The hardware guarantees that reading the current value, comparing it to the expected value, and conditionally writing the new value happen as a single atomic step, so no other core can interleave a write in between, even on a multi-core system with a shared memory bus or cache-coherence protocol. Software uses CAS to implement lock-free data structures and higher-level primitives such as spinlocks, atomic counters, and mutexes: a thread reads the current value, computes a new value locally, then calls CAS to commit only if nobody else changed the value in the meantime, retrying in a loop otherwise. Because CAS never blocks the caller in a kernel sense, it avoids the overhead of putting a thread to sleep for short critical sections, but naive CAS loops are vulnerable to the ABA problem, where a value changes from A to B and back to A between the read and the CAS, fooling the check into succeeding incorrectly.
- Enables lock-free and wait-free concurrent data structures
- Avoids kernel-level blocking overhead for short updates
- Forms the atomic building block for spinlocks and atomic counters
- Understanding it explains why the ABA problem must be guarded against
AI Mentor Explanation
Compare-and-swap is like a scorer updating the total only if the ball count on the board still matches what they last saw: they check the displayed number, and only if it still equals their expected value do they atomically overwrite it with the new total in one motion. If another scorer already changed the number in between, the update is rejected and the first scorer must re-read the board and retry. This single check-then-write motion, with no gap for interference, is exactly what a CAS instruction guarantees in hardware.
Step-by-Step Explanation
Step 1
Read expected value
A thread reads the current value of a memory location and computes a desired new value locally.
Step 2
Issue CAS
The thread calls the CAS instruction with the address, the expected old value, and the new value.
Step 3
Atomic compare
The CPU atomically checks whether the memory still holds the expected value; if it does not, no write happens and CAS reports failure.
Step 4
Retry or succeed
On success the new value is committed; on failure the thread re-reads the current value and retries the whole cycle.
What Interviewer Expects
- A precise definition of CAS as a single atomic hardware instruction
- Explanation of how a CAS retry loop implements lock-free updates
- Awareness of the ABA problem and why it matters
- A concrete example — spinlock, atomic counter, or lock-free stack
Common Mistakes
- Thinking CAS blocks the calling thread like a mutex does
- Forgetting that a failed CAS requires the caller to retry, not just fail silently
- Not knowing what the ABA problem is or how to mitigate it
- Confusing CAS with a simple non-atomic read-then-write sequence
Best Answer (HR Friendly)
“Compare-and-swap is a special CPU instruction that lets a thread say, in one uninterruptible step, 'update this value, but only if nobody else has changed it since I last looked.' It is the building block behind lock-free programming, letting threads coordinate without the overhead of a traditional lock, though the code using it must loop and retry when the check fails.”
Code Example
#include <stdatomic.h>
atomic_int counter = 0;
void atomic_increment(void) {
int expected, desired;
do {
expected = atomic_load(&counter);
desired = expected + 1;
} while (!atomic_compare_exchange_weak(&counter, &expected, desired));
/* loop retries only if another thread changed counter first */
}Follow-up Questions
- What is the ABA problem and how can it be avoided?
- How does CAS differ from a test-and-set instruction?
- How would you build a spinlock using CAS?
- What is the difference between lock-free and wait-free algorithms?
MCQ Practice
1. What does a compare-and-swap instruction guarantee?
CAS atomically checks whether a memory location still equals an expected value and, only if so, writes a new value, with no possibility of interleaving.
2. What happens when a CAS call fails because the value changed?
A failed CAS does not write anything; the caller is expected to re-read the current value and retry its update loop.
3. What is the ABA problem in the context of CAS?
If a value returns to its original state between a thread's read and its CAS call, the CAS succeeds even though the value was modified in between, which can corrupt lock-free data structures.
Flash Cards
What is compare-and-swap (CAS)? — An atomic CPU instruction that writes a new value only if the memory still holds an expected old value.
What does software do when CAS fails? — Re-read the current value and retry the update in a loop.
What is the ABA problem? — A value changes A to B to A between read and CAS, causing a stale check to incorrectly succeed.
What does CAS enable? — Lock-free data structures and primitives like spinlocks and atomic counters, without kernel-level blocking.