Test and test-and-set

From Wikipedia, the free encyclopedia
  (Redirected from Test and Test-and-set)
Jump to navigation Jump to search

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

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

References[edit]

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