What is the Test-and-Set Instruction?
Learn how the atomic test-and-set instruction builds spinlocks, why it scales beyond two processes, and its tradeoffs.
Expected Interview Answer
Test-and-set is a hardware-atomic CPU instruction that reads a memory location, sets it to true, and returns the old value, all as one indivisible operation, which is enough to build a correct lock without relying on software tricks like Peterson's algorithm.
The atomicity guarantee is the entire point: no other core or thread can observe or interleave with the read-then-write, because the CPU (and cache-coherence protocol) executes it as a single uninterruptible step. A lock built on test-and-set works by looping — 'while (test_and_set(&lock) == true) { }' — so a thread only exits the loop when it is the one that flipped the lock from false to true; every other thread sees the lock already true and keeps spinning. This scales to any number of threads or processes, unlike Peterson’s two-process software solution, and it works correctly regardless of memory reordering because the instruction itself is a hardware synchronization point. The tradeoff is that it implements a spinlock: threads busy-wait consuming CPU cycles instead of sleeping, so test-and-set locks are best for very short critical sections, and production systems often combine it with backoff or fall back to OS-level blocking (futex) for longer waits.
- Atomic at the hardware level, eliminating software race conditions entirely
- Works for any number of competing threads or processes, not just two
- Forms the primitive building block for spinlocks and higher-level mutexes
- Immune to compiler/CPU reordering issues that plague pure software algorithms
AI Mentor Explanation
Test-and-set is like a single indivisible action where a fielder both checks if the stumps are already broken and breaks them in one motion, so no other fielder can sneak in between the check and the break. If the fielder finds the stumps already broken, they know someone else got there first and must accept the old result. This one atomic action is what prevents two fielders from both claiming a clean run-out simultaneously.
Step-by-Step Explanation
Step 1
Atomic read
The instruction reads the current value of the target memory location.
Step 2
Atomic write
In the same indivisible step, it writes true into that memory location.
Step 3
Return old value
The instruction returns the value the location held before the write.
Step 4
Lock loop
A caller loops calling test-and-set until it receives false, meaning it was the one to acquire the lock.
What Interviewer Expects
- Correct description of the atomic read-modify-write semantics
- How a spinlock is built from a test-and-set loop
- Awareness it works for N threads/processes, not just two
- Understanding of the busy-wait cost and when it is appropriate
Common Mistakes
- Describing test-and-set as two separate operations instead of one atomic one
- Forgetting it produces a spinlock, which wastes CPU while waiting
- Confusing it with Peterson’s solution, which is pure software
- Not knowing compare-and-swap is a more general, often preferred, alternative
Best Answer (HR Friendly)
“Test-and-set is a special CPU instruction that checks and flips a value in a single, uninterruptible step, so it is impossible for two threads to both think they grabbed the same lock. It is the hardware building block behind spinlocks, and while it is very fast for short waits, threads using it burn CPU cycles busy-waiting rather than sleeping, so it is best kept for brief critical sections.”
Code Example
volatile int lock = 0;
int test_and_set(volatile int *target) {
int old = *target; /* conceptually atomic on real hardware */
*target = 1;
return old;
}
void acquire(volatile int *lock) {
while (test_and_set(lock) == 1) {
/* busy-wait: another thread holds the lock */
}
}
void release(volatile int *lock) {
*lock = 0;
}Follow-up Questions
- How does compare-and-swap differ from test-and-set?
- Why is test-and-set atomicity guaranteed by hardware, not software?
- When should you prefer a spinlock over a blocking mutex?
- How does cache-coherence traffic affect test-and-set performance under contention?
MCQ Practice
1. What makes test-and-set useful for building locks?
The atomicity of the combined read-and-write is exactly what prevents two threads from both acquiring the lock simultaneously.
2. A lock built purely on test-and-set is best described as a?
Threads loop (busy-wait) calling test-and-set until they succeed, which is the definition of a spinlock.
3. Unlike Peterson's solution, test-and-set works for?
Because it is a hardware-atomic primitive, test-and-set generalizes to any number of contenders without special-casing.
Flash Cards
What is test-and-set? — An atomic CPU instruction that reads and writes a memory location in one indivisible step, returning the old value.
What structure does it build? — A spinlock — callers busy-wait looping on the instruction until they acquire it.
Advantage over Peterson's solution? — Works for any number of processes and is immune to software memory-reordering issues.
Main downside of test-and-set locks? — Busy-waiting wastes CPU cycles, so it suits only short critical sections.