In
computer architecture, the
test-and-set
In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non- interruptible) operation. The caller can then "test" the result to see if the ...
CPU
instruction (or instruction sequence) is designed to implement
mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurr ...
in
multiprocessor
Multiprocessing (MP) is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. The ...
environments. Although a correct
lock
Lock(s) or Locked may refer to:
Common meanings
*Lock and key, a mechanical device used to secure items of importance
*Lock (water navigation), a device for boats to transit between different levels of water, as in a canal
Arts and entertainme ...
can be implemented with test-and-set, the ''test and test-and-set'' optimization lowers
resource contention caused by bus locking, especially
cache coherency protocol overhead on contended locks.
Given a lock:
''boolean'' locked := false ''// shared lock variable''
the entry protocol is:
procedure EnterCritical()
and the exit protocol is:
procedure ExitCritical()
The difference to the simple test-and-set protocol is the additional spin-loop (the ''test'' in ''test and test-and-set'') at the start of the entry protocol, which utilizes ordinary load instructions. The load in this loop executes with less overhead compared to an atomic operation (resp. a
load-exclusive instruction). E.g., on a system utilizing the
MESI cache coherency protocol, the cache line being loaded is moved to the Shared state, whereas a test-and-set instruction or a load-exclusive instruction moves it into the Exclusive state.
This is particularly advantageous if multiple processors are contending for the same lock: whereas an atomic instruction or load-exclusive instruction requires a coherency-protocol transaction to give that processor exclusive access to the cache line (causing that line to ping-pong between the involved processors), ordinary loads on a line in Shared state require no protocol transactions at all: processors spinning in the inner loop operate purely locally.
Cache-coherency protocol transactions are used only in the outer loop, after the initial check has ascertained that they have a reasonable likelihood of success.
If the
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
used supports
short-circuit evaluation
Short-circuit evaluation, minimal evaluation, or McCarthy evaluation (after John McCarthy) is the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argumen ...
, the entry protocol could be implemented as:
procedure EnterCritical()
Caveat
Although this
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
is useful in
system programming, test-and-set is to be avoided in high-level
concurrent programming
Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to:
Law
* Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea''
* Concurring opinion (also called a "concurrence"), a ...
: spinning in applications deprives the operating system scheduler
the knowledge of who is blocking on what. Consequently, the scheduler will have to guess on how to allocate CPU time among the threads -- typically just allowing the threads to use up their timing quota. Threads will end up spinning unproductively, waiting for threads that are not scheduled.
By using operating-system provided lock objects, such as mutexes, the OS can schedule exactly the unblocked threads.
See also
*
Parallel processor
*
Parallel programming
Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...
*
Mutual exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurr ...
*
Test-and-set
In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non- interruptible) operation. The caller can then "test" the result to see if the ...
*
Fetch-and-add
In computer science, the fetch-and-add (FAA) CPU instruction atomically increments the contents of a memory location by a specified value.
That is, fetch-and-add performs the following operation: increment the value at address by , where is ...
References
* Gregory R. Andrews, ''Foundations of Multithreaded, Parallel, and Distributed Programming'', pp. 100–101. Addison-Wesley, 2000. {{ISBN, 0-201-35752-6.
Concurrency control
Computer arithmetic