What is the Test-and-Set instruction and how does it provide mutual exclusion?
Test-and-Set is a hardware instruction that atomically reads a memory flag and sets it to 1. If it returned 0, the caller got the lock; if 1, someone else holds it. Because it is one indivisible step, two threads cannot both see 0.
Explain it simply
Software-only locking has a gap: two threads can both read "lock is free" before either writes "lock is taken". Test-and-Set closes the gap by doing read and write as one step that nothing can interrupt, even on multiple cores.
Its meaning, written as C-like code (the hardware does all of it atomically):
boolean test_and_set(boolean *target):
old = *target
*target = true
return oldExample
Using it to build a lock:
boolean lock = false // shared
enter():
while (test_and_set(&lock))
; // old value true: someone holds it, spin
exit():
lock = falseTrace with threads A and B: A calls test_and_set, gets false (old value), and the flag becomes true; A enters. B calls it, gets true, and spins. When A sets the flag to false, B's next call returns false and B enters.
This guarantees mutual exclusion and progress. It does not guarantee bounded waiting: a thread can be unlucky and keep losing the race, so a ticket-based variant is used when fairness matters.
Related instructions: compare-and-swap (CAS) and fetch-and-add, which most modern lock-free code uses.
What to say in the interview
"Test-and-Set atomically returns the old value of a flag and sets it to true. A thread that gets false owns the lock; others spin. It gives mutual exclusion but no bounded waiting, so a thread could starve. Modern CPUs offer compare-and-swap for similar uses."
Common mistakes
- Thinking the atomicity comes from software. It is guaranteed by the hardware instruction.