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. The main idea is to reduce writeback that can create resource contention when two separate threads want the same lock. If n threads are competing for the lock, they will attempt to acquire it as soon as it is released if only using test and set, causing each thread to invalidate the lock flag, meaning it must be propagated through the cache of the remaining processors n times, before any one thread may safely read it. By adding the check-yield step, only the first thread of execution to notice the lock is free will attempt to obtain it, eliminating the writeback.

boolean locked := false // shared lock variable
procedure EnterCritical() {
  do {
    while (locked == true) yield(); // lock looks busy so yield to scheduler
  } while TestAndSet(locked) // actual atomic locking
}
procedure TestAndSet(lock) {
   boolean initial = lock;
   lock = true;
   return initial;
 }

Exit protocol is:

procedure ExitCritical() {
  locked := false
}

The entry protocol uses normal memory reads to spin, waiting 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 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
 }