Test and test-and-set

In <a href="/facts/Computer_architecture/tHtwxgR2">computer architecture</a>, the <a href="/facts/Test-and-set/KyR6bYFo">test-and-set</a> CPU <a href="/facts/Instruction_(computer_science)/8p8vwUeE">instruction</a> (or instruction sequence) is designed to implement 
<a href="/facts/Mutual_exclusion/1dwvCxDW">mutual exclusion</a> in <a href="/facts/Multiprocessor/aDCfehDQ">multiprocessor</a> environments. Although a correct <a href="/facts/Lock_(computer_science)/e3a9gnJT">lock</a> can be implemented with test-and-set, the test and test-and-set optimization lowers <a href="/facts/Resource_contention/eAh3Rtrs">resource contention</a> caused by bus locking, especially <a href="/facts/Cache_coherence/MhUD576q"> cache coherency protocol</a> overhead on contended locks.
Given a lock:

boolean locked := false // shared lock variable

the entry protocol is:

procedure EnterCritical() {
 do {
 while ( locked == true )
 skip // spin using normal instructions until the lock is free
 } while ( TestAndSet(locked) == true ) // attempt actual atomic locking using the <a href="/facts/Test-and-set/KyR6bYFo">test-and-set</a> instruction
}

and the exit protocol is:

procedure ExitCritical() {
 locked := false
}

The difference to the simple test-and-set protocol is the additional spin-loop (the test in test and test-and-set) at the start of the entry protocol, which utilizes ordinary load instructions. The load in this loop executes with less overhead compared to an atomic operation (resp. a <a href="/facts/Load-link%2fstore-conditional/owLXpjeu"> load-exclusive</a> instruction). E.g., on a system utilizing the <a href="/facts/MESI/BUCBWvtS">MESI</a> cache coherency protocol, the cache line being loaded is moved to the Shared state, whereas a test-and-set instruction or a load-exclusive instruction moves it into the Exclusive state.
This is particularly advantageous if multiple processors are contending for the same lock: whereas an atomic instruction or load-exclusive instruction requires a coherency-protocol transaction to give that processor exclusive access to the cache line (causing that line to ping-pong between the involved processors), ordinary loads on a line in Shared state require no protocol transactions at all: processors spinning in the inner loop operate purely locally.
Cache-coherency protocol transactions are used only in the outer loop, after the initial check has ascertained that they have a reasonable likelihood of success.
If the <a href="/facts/Programming_language/cWTYbgWa">programming language</a> used supports <a href="/facts/Short-circuit_evaluation/GYhompFd">short-circuit evaluation</a>, the entry protocol could be implemented as:

 procedure EnterCritical() {
 while ( locked == true or TestAndSet(locked) == true )
 skip // spin until locked
 }

Test and test-and-set open-in-new

Test and test-and-set