Test and Test-and-set
Encyclopedia
In computer science
, the test-and-set
CPU instruction is used to implement
mutual exclusion
in multiprocessor
environments. Although a correct 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. The main idea is not to spin
in test-and-set but increase the likelihood of successful test-and-set by using the following entry protocol to the lock:
boolean locked := false // shared lock variable
procedure EnterCritical {
do {
while (locked true) skip // spin until lock seems free
} while TestAndSet(locked) // actual atomic locking
}
Exit protocol is:
procedure ExitCritical {
locked := false
}
The entry protocol uses normal memory reads to spin, waiting 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 happens less often than in simple spin around test-and-set.
If the programming language
used supports short-circuit evaluation, the entry protocol could be implemented as:
procedure EnterCritical {
while ( locked true or TestAndSet(locked) true )
Caveat
Although this optimization
is useful in system programming
it should be avoided in high level concurrent programming unless all constraints are clear and understood. One example of bad usage is a similar idiom
called double-checked locking
, which is listed as an anti-pattern
.
See also
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the test-and-set
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 operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
CPU instruction is used to implement
mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
in multiprocessor
Multiprocessor
Computer system having two or more processing units each sharing main memory and peripherals, in order to simultaneously process programs.Sometimes the term Multiprocessor is confused with the term Multiprocessing....
environments. Although a correct lock
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
can be implemented with test-and-set, it can lead to resource contention
Resource contention
In computer science, resource contention is a conflict over access to a shared resource such as random access memory, disk storage, cache memory, internal busses or external network devices....
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. The main idea is not to spin
Busy waiting
In software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
in test-and-set but increase the likelihood of successful test-and-set by using the following entry protocol to the lock:
boolean locked := false // shared lock variable
procedure EnterCritical {
do {
while (locked true) skip // spin until lock seems free
} while TestAndSet(locked) // actual atomic locking
}
Exit protocol is:
procedure ExitCritical {
locked := false
}
The entry protocol uses normal memory reads to spin, waiting 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 happens less often than in simple spin around test-and-set.
If the programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
used supports short-circuit evaluation, the entry protocol could be implemented as:
procedure EnterCritical {
while ( locked true or TestAndSet(locked)
true )
skip // spin until locked
}
CaveatAlthough this optimization
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
is useful in system programming
System programming
System programming is the activity of programming system software. The primary distinguishing characteristic of systems programming when compared to application programming is that application programming aims to produce software which provides services to the user System programming (or systems...
it should be avoided in high level concurrent programming unless all constraints are clear and understood. One example of bad usage is a similar idiom
Programming idiom
A programming idiom is a means of expressing a recurring construct in one or more programming languages. Generally speaking, a programming idiom is an expression of a simple task or algorithm that is not a built-in feature in the programming language being used, or, conversely, the use of an...
called double-checked locking
Double-checked locking
In software engineering, double-checked locking is a software design pattern used to reduce the overhead of acquiring a lock by first testing the locking criterion without actually acquiring the lock...
, which is listed as an anti-pattern
Anti-pattern
In software engineering, an anti-pattern is a pattern that may be commonly used but is ineffective and/or counterproductive in practice.The term was coined in 1995 by Andrew Koenig,...
.
See also
- Parallel processor
- Parallel programming
- Mutual exclusionMutual exclusionMutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
- Test-and-setTest-and-setIn 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 operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
- Fetch-and-addFetch-and-addIn computer science, the fetch-and-add CPU instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement mutual exclusion and concurrent algorithms in multiprocessor systems, a generalization of semaphores.In uniprocessor systems, it is...