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[]

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