Test and test-and-set
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.
Given a lock:
boolean locked := false // shared lock variable
Entry protocol is:
procedure EnterCritical() { do { while ( locked == true ) skip // spin until the lock seems free } while ( TestAndSet(locked) == true ) // attempt actual atomic locking using the test-and-set instruction }
Exit protocol is:
procedure ExitCritical() { locked := false }
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 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 }
Caveat[]
Although this optimization is useful in system programming, it should be avoided in high-level concurrent programming when constraints are unclear and misunderstood. One example of bad usage is a similar idiom called double-checked locking, which is unsafe without special precautions and can be an anti-pattern.[1]
See also[]
- Parallel processor
- Parallel programming
- Mutual exclusion
- Test-and-set
- Fetch-and-add
References[]
- ^ David Bacon et al. The "Double-Checked Locking is Broken" Declaration.
- 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