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 unless all constraints are clear and understood. 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.

See also

• Parallel processor
• Parallel programming
• Mutual exclusion
• Test-and-set
• Fetch-and-add

References

• Gregory R. Andrews, Foundations of Multithreaded, Parallel, and Distributed Programming, pp. 100–101. Addison-Wesley, 2000. ISBN 0-201-35752-6.