Editing Test-and-set (section)

{{short description|CPU instruction to set a memory location to 1 and return its prior value}}

In [[computer science]], the '''test-and-set''' [[Instruction set architecture|instruction]] is an instruction used to write (set) 1 to a [[memory location]] and return its old value as a single [[atomic (computer science)|atomic]] (i.e., non-[[Interrupt|interruptible]]) operation. The caller can then "test" the result to see if the state was changed by the call. 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 [[central processing unit]] (CPU) may use a test-and-set instruction offered by another electronic component, such as [[DPRAM|dual-port RAM]]; a CPU itself may also offer a test-and-set instruction.

A [[Lock (computer science)|lock]] can be built using an atomic test-and-set<ref>{{Cite journal|last=Anderson|first=T. E.|date=1990-01-01|title=The performance of spin lock alternatives for shared-money multiprocessors|journal=IEEE Transactions on Parallel and Distributed Systems|volume=1|issue=1|pages=6–16|doi=10.1109/71.80120|issn=1045-9219}}</ref> instruction as follows:

This code assumes that the memory location was initialized to 0 at some point prior to the first test-and-set.  The calling process obtains the lock if the old value was 0, otherwise the while-loop spins waiting to acquire the lock. This is called a [[spinlock]].  At any point, the holder of the lock can simply set the memory location back to 0 to release the lock for acquisition by another--this does not require any special handling as the holder "owns" this memory location. "[[Test and test-and-set]]" is another example.

[[Maurice Herlihy]] (1991) proved that test-and-set (1-bit comparand) has a finite [[Consensus (computer science)|consensus number]] and can solve the wait-free [[Consensus (computer science)|consensus problem]] for at-most two concurrent processes.<ref>{{cite journal|last=Herlihy|first=Maurice|date=January 1991|title=Wait-free synchronization|url=http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf|journal=ACM Trans. Program. Lang. Syst.|volume=13|issue=1|pages=124–149|doi=10.1145/114005.102808|access-date=2007-05-20|citeseerx=10.1.1.56.5659|s2cid=2181446 }}</ref> In contrast, [[compare-and-swap]] (32-bit comparand) offers a more general solution to this problem, and in some implementations wider compare-and-swap (64- or 128-bit comparand) is also available for extended utility.