In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, 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 stat ...
CPU
instruction is used 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 concurrent ...
in
multiprocessor
Multiprocessing 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. There ar ...
environments. Although a correct
lock
Lock(s) 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 entertainment
* ''Lock ...
can be implemented with test-and-set, it can lead to
resource contention in busy lock (caused by bus locking and cache invalidation when test-and-set operation needs to access memory
atomically).
To lower the overhead a more elaborate locking protocol test and test-and-set is used.
Given a lock:
''boolean'' locked := false ''// shared lock variable''
Entry protocol is:
procedure EnterCritical()
Exit protocol is:
procedure ExitCritical()
The entry protocol uses normal memory reads to wait for the lock to become free. Test-and-set is only used to try to get the lock when normal memory read says it's free. Thus the expensive atomic memory operations happen less often than in a simple
spin around test-and-set.
If the
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming l ...
used supports
short-circuit evaluation
A short circuit (sometimes abbreviated to short or s/c) is an electrical circuit that allows a current to travel along an unintended path with no or very low electrical impedance. This results in an excessive current flowing through the circuit ...
, 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 criterion, from some set of available alternatives. It is generally divided into two subfi ...
is useful in
system programming Systems programming, or system programming, is the activity of programming computer system software. The primary distinguishing characteristic of systems programming when compared to application programming is that application programming aims to ...
, it should 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 ...
when constraints are unclear and misunderstood. One example of bad usage is a similar
idiom
An idiom is a phrase or expression that typically presents a figurative, non-literal meaning attached to the phrase; but some phrases become figurative idioms while retaining the literal meaning of the phrase. Categorized as formulaic language, ...
called
double-checked locking, which is
unsafe without special precautions and can be an
anti-pattern
An anti-pattern in software engineering, project management, and business processes is a common response to a recurring problem that is usually ineffective and risks being highly counterproductive. The term, coined in 1995 by computer programmer An ...
.
[David Bacon et al]
The "Double-Checked Locking is Broken" Declaration
See also
*
Parallel processor
Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different for ...
*
Parallel programming
Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different f ...
*
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 concurrent ...
*
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 stat ...
*
Fetch-and-add In computer science, the fetch-and-add CPU instruction (FAA) atomically increments the contents of a memory location by a specified value.
That is, fetch-and-add performs the operation
:increment the value at address by , where is a memory locat ...
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