Test-and-Set Instruction
Test-and-set atomically reads a memory location and writes a fixed value (CLOSED) into it, returning the old value. It is the simplest atomic read-modify-write primitive and enough, on its own, to build a working spinlock. Described as a software routine, but implemented in hardware as a single uninterruptible instruction.
Why isn't a plain read + write enough for mutex?
Because between the read (check lock is OPEN) and the write (set lock CLOSED), another task can run and acquire the same lock. Two tasks both read OPEN, both write CLOSED, and both enter the critical section together. Atomicity across read-and-write is exactly what test-and-set adds.
The failed naive attempt
int Lock = OPEN;
while ( Lock == CLOSED ); // read
Lock = CLOSED; // write
// critical section
Lock = OPEN;The gap between the read and the write admits a race. Two tasks can both pass the loop and both enter the critical section.
Test-and-set
int TestSet( int & b ) { // atomic
int temp = b;
b = CLOSED;
return temp;
}
while ( TestSet( Lock ) == CLOSED ); // spin until we see OPEN
// critical section
Lock = OPEN;If TestSet returns OPEN, this task observed the lock free and atomically closed it. If it returns CLOSED, the loop retries. The read and write happen as one uninterruptible step.
Works for N threads
The algorithm does not require knowing the number of tasks. It depends only on one shared lock variable, which makes it a big improvement over software solutions like Dekker or Peterson that track per-thread state.
Multi-CPU requirement
On a multiprocessor the hardware bus must prevent two CPUs from interleaving their atomic read-writes on the same address. Modern ISAs give this via LOCK prefixes on x86 or cache-line reservations on ARM.
Limitation: rule 5 broken
No bounded waiting. A contending task can spin indefinitely while others repeatedly acquire and release the lock. In practice, starvation is rare but possible.