Test and test-and-set: Difference between revisions

Revision as of 13:32, 5 December 2018

Latest revision as of 17:17, 27 April 2024

(10 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|CPU Instruction}}

In [[computer sciencearchitecture]], the [[test-and-set]] CPU [[instruction (computer science)|instruction]] (or instruction sequence) is useddesigned to implement

[[mutual exclusion]] in [[multiprocessor]] environments. Although a correct [[lock (computer science)|lock]] can be implemented with test-and-set, itthe can''test leadand totest-and-set'' optimization lowers [[resource contention]] in busy lock (caused by bus locking, andespecially [[cache invalidationcoherence when| test-and-setcache operationcoherency needsprotocol]] tooverhead accesson memorycontended [[atomic (computer science)|atomically]])locks.

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.

Given a lock:

''boolean'' locked := false ''// shared lock variable''

the entry protocol is:

'''procedure''' EnterCritical() {

'''do''' {

'''while''' ( locked == true) yield(); //Lock looks busy so yield to scheduler

'''skip''' ''// spin using normal instructions until the lock is free''

} '''while''' ( ''TestAndSet''(locked) == true ) ''// attempt actual atomic locking using the [[test-and-set]] instruction''

}

'''procedure''' TestAndSet(lock) {

boolean initial = lock;

lock = true;

return initial;

}

Exitand 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 [[Load-link/store-conditional | load-exclusive]] instruction). E.g., on a system utilizing the [[MESI]] 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.

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.

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 [[programming language]] used supports [[short-circuit evaluation]], the entry protocol could be implemented as:

Line 31 ⟶ 33:

==Caveat==

Although this [[Optimization (computer science)|optimization]] is useful in [[system programming]], ittest-and-set shouldis to be avoided in high -level [[concurrent programming]]: unlessspinning allin constraintsapplications aredeprives clearthe andoperating understood.system One example of bad usage is a similar [[programming idiom|idiom]] called [[double-checked locking]], which, under certain conditions, can be an [[anti-pattern]].<ref>David Bacon et al. [http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html The "Double-Checked Locking is Broken" Declaration].</ref>scheduler

the knowledge of who is blocking on what. Consequently, the scheduler will have to guess on how to allocate CPU time among the threads -- typically just allowing the threads to use up their timing quota. Threads will end up spinning unproductively, waiting for threads that are not scheduled.

By using operating-system provided lock objects, such as mutexes, the OS can schedule exactly the unblocked threads.

==See also==