Test and test-and-set
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 memory 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 successfull test-and-set by using following entry protocol to the lock:
boolean locked := false // shared lock variable
procedure EnterCritical() {
while (locked = true) skip // spin until lock seems free
while TestAndSet(locked) // actual atomic locking
while (locked = true) skip // if test-and-set failed, wait for lock to become free again
}
Exit protocol is:
procedure ExitCritical() {
locked := false
}
The entry protocol uses normal memory reads to spin and wait for the lock to come free. Test-and-set is only used to try to get the lock when normal memory read says its free. Thus the expensive atomic memory operations happens less often than in simple spin around Test-and-set.
Caveat
Although this optimization is usefull in system programming it should be avoided in high level concurrent programming. One example of bad usage of this idiom is double-checked locking, which is listed as an anti-pattern.
See also
References
- Gregory R. Andrews, Foundations of Multithreaded, Parallel, and Distributed Programming, pp. 100-101. Addison-Wesley, 2000. ISBN 0-201-35752-6.