The idea: a lock needs one indivisible step
Threads that share a variable need a critical section: a piece of code only one thread runs at a time. The obvious lock is a shared word, lock: 0 means free, 1 means taken. A thread waits until it reads 0, then writes 1. The catch is that "read 0" and "write 1" are two separate memory operations, and another thread can run between them.
Test-and-set is a CPU instruction that does both in one step: it writes 1 into a memory word and returns the value the word had before. No other CPU can touch the word in between. If it returns 0, the lock was free and you now own it. If it returns 1, someone else owns it, and writing 1 over 1 changed nothing.
int TestAndSet(int *p) { // done by the hardware, atomically
int old = *p;
*p = 1;
return old;
}
while (TestAndSet(&lock)) ; // spin until it returns 0
// critical section
lock = 0; // release: a plain store
How to use the animation
Every thread runs on its own CPU and executes the listing in a loop: take the lock, add 1 to counter through its register tmp, release the lock. A coloured marker shows the line each thread runs next. Every step runs one line, and between any two steps any thread may run. Choose a thread and press Step Thread to build a schedule by hand, or let the round-robin or random scheduler choose. Every load or store flies between the thread and the shared word; during a test-and-set the bus is marked as locked by that thread. The lines under the separator check after every step that no update was lost and that at most one thread is inside.
Why test, then set does not work
Open the Bug: test, then set tab and run Demo: both get in. T1 reads lock = 0 and is preempted before its store. T2 also reads 0. Now both store 1 and both enter: the lock protected nothing. Inside, both read counter = 0 and both write 1, so two increments leave counter = 1. This is a race condition: the result depends on the order the scheduler picks, and most orders are fine, which is why such bugs pass tests.
Software alone can fix this with plain loads and stores (Peterson's and Dekker's algorithms), but those need one flag per thread and break on modern CPUs that reorder memory accesses unless fences are added. Every real lock is built on an atomic instruction instead.
Test-and-set makes it work
The Test-and-set spinlock tab's Demo: same schedule runs the same order of threads. T1's test-and-set returns 0; T2's returns 1 because T1's write was part of the same step as its read. Exactly one thread sees 0 for every time the lock is released, so at most one is inside. Release is an ordinary store of 0: only the owner writes it, so no atomic step is needed there.
| Where | Test-and-set |
|---|---|
| x86 | XCHG reg, [mem] with 1 in reg (always locked), or LOCK BTS |
| ARM | SWP (old), LDXR/STXR loop or SWPAL (ARMv8.1) |
| C / C++ | atomic_flag_test_and_set, std::atomic_flag::test_and_set, atomic_exchange |
| Java | AtomicBoolean.getAndSet(true) |
| GCC | __sync_lock_test_and_set / __atomic_test_and_set |
How is it atomic? Old CPUs asserted a LOCK# signal and held the memory bus for the read and the write. Today the CPU takes the word's cache line in exclusive state (the MESI protocol) and refuses to give it to another core until both halves are done. The animation draws this as "bus locked".
Spinning and its cost
A thread that does not get the lock spins: it runs test-and-set again and again. Each spin uses the CPU and does nothing useful. That is fine when the lock is held for a few instructions, and it avoids the cost of putting a thread to sleep and waking it, which is why kernels use spinlocks for short sections. It is bad when the owner stops running while holding the lock. Demo: holder preempted: T1 is interrupted inside the critical section, and T2 spends six steps spinning. On one CPU it is worse still: the spinner can burn its whole time slice while the owner cannot run at all.
So kernel spinlocks disable preemption (and sometimes interrupts) while held, and user-space locks such as a Linux pthread_mutex spin briefly and then sleep in the kernel with futex. See Bounded buffer for locks and semaphores that sleep instead of spinning.
A plain test-and-set lock is also not fair: whoever happens to run test-and-set right after the release wins, and an unlucky thread can lose every time. Ticket locks and queue locks (MCS) hand the lock over in order.
Test-and-test-and-set
Every test-and-set is a write, so every spinning CPU keeps pulling the cache line away from the others, even though the lock stays 1. With many spinners that traffic slows down the owner too. The usual fix spins on a plain read, which can be served from each CPU's own cache, and only tries test-and-set when the lock looks free:
for (;;) {
while (lock == 1) ; // read-only spin, stays in the cache
if (!TestAndSet(&lock)) break; // looked free: try for real
}
The first loop is exactly the broken test of the bug tab, but now it is only a hint: the test-and-set after it still decides. Add a short pause (PAUSE on x86) or an exponential back-off between attempts and you have the spinlock most libraries use.
Test-and-set and compare-and-swap
Test-and-set always writes 1. Compare-and-swap writes a new value only if the word still holds an expected one, so it can do more than locks: it can update a counter or a pointer directly, with no lock at all. A test-and-set lock is CAS(&lock, 0, 1). See Compare-and-swap.
What the page leaves out
- Memory ordering. Taking a lock must be an acquire and releasing it a release, so the CPU and the compiler do not move the critical section's loads and stores outside it. The page treats memory as sequentially consistent.
- Caches and the coherence protocol are drawn as one bus.
- Sleeping: threads here never block; a real mutex would put T2 to sleep after a few spins.
- Priority inversion: a high-priority thread spinning on a lock held by a low-priority one that never gets to run.