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

1. ↑ 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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Test and test-and-set. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Test_and_test-and-set&oldid=82225"