One atomic instruction
Test and set is a hardware primitive that atomically writes one to a memory word and returns its old value, all in a single uninterruptible step. That atomicity is exactly what software locks struggled to achieve.
Building a lock
A lock is one word, zero means free. To acquire, a thread repeatedly runs test and set on it. If the returned old value was zero, the lock was free and this thread just claimed it, so it enters. If the old value was one, someone else holds it, so the thread loops and tries again. To release, the holder simply stores zero.
Why it is correct
Because test and set is atomic, two threads can never both read zero and both set one. Exactly one sees the old zero and wins. The losers spin, which is why this is a spinlock.
The downsides
- It busy waits, burning CPU while spinning
- Every spin is a write, so the cache line bounces between cores causing heavy bus traffic
- It gives no fairness, a thread can be starved by luckier peers
Key idea
A test and set lock spins on an atomic swap of a flag, simple and correct but wasteful and unfair.