What is "test-and-set"

In computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. Typically, the value 1 is written to the memory location. If multiple processes may access the same memory location, and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process's test-and-set is finished. A CPU may use a test-and-set instruction offered by another electronic component, such as dual-port RAM; a CPU itself may also offer a test-and-set instruction.

A lock can be built using an atomic test-and-set instruction as follows:

function Lock(boolean *lock)
{
while (test_and_set(lock) == 1)
;
}

The calling process obtains the lock if the old value was 0; it " spins", writing 1 to the variable until this occurs.

Maurice Herlihy (1991) proved that test-and-set has a finite consensus number, in contrast to the compare-and-swap operation. The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes. However, more than two decades before Herlihy's proof, IBM had already replaced test-and-set with compare-and-swap, which is a more general solution to this problem.