the test-and-set instruction

We saw that pure-software locks are fragile because ordinary reads and writes are not atomic and can be reordered. The hardware fix is to provide a single machine instruction that does a tiny read-and-write as one indivisible step. Test-and-set is the classic one. In one uninterruptible action it reads the old value of a memory location and writes true into it, and hands you back the old value. The name is literal: it tests (reads) and sets (writes) at the same instant, with no gap for another core to slip into.

From this one primitive you can build a lock almost trivially. Keep a shared boolean locked, starting false. To acquire the lock, repeatedly do old = test_and_set(locked) until the old value comes back false. The first thread to call it reads false (lock was free) and simultaneously writes true (now taken), so it returns false and enters. Every other thread that calls test_and_set now reads back true (already taken) and keeps looping. To release, the holder simply writes locked = false. Because the read-and-write is atomic, two threads cannot both see false — exactly one wins. This is the heart of a spinlock.

The catch is fairness and waste. A test-and-set lock gives mutual exclusion, but it does not by itself guarantee bounded waiting: under contention the same lucky thread can keep winning the race while another spins indefinitely. And the waiting thread is busy-waiting — burning CPU cycles in a tight loop doing nothing useful. Real implementations soften this (for example, test-and-test-and-set first reads the flag with a cheap plain load and only attempts the atomic write when it looks free, reducing cache-line contention), but the fundamental lesson stands: one small atomic instruction is enough to build mutual exclusion, and everything richer is built on top of it.