Test and test-and-set: Difference between revisions

Revision as of 00:11, 16 February 2008

Latest revision as of 17:17, 27 April 2024

(33 intermediate revisions by 28 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 [[memoryresource contention]] in busy lock (caused by bus locking, andespecially [[cache invalidationcoherence when| test-and-setcache operationcoherency needsprotocol]] tooverhead accesson memorycontended [[atomic (computer science)|atomic]]ally)locks.

To lower the overhead a more elaborate locking protocol '''test and test-and-set'''

is used. The main idea is ''not'' to [[Busy waiting|spin]] in test-and-set but increase the likelihood of successful test-and-set by using following entry protocol to the lock:

Given a lock:

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

the entry protocol is:

'''procedure''' EnterCritical() {

'''do''' {

'''while''' ( locked == true ) skip ''// spin until lock '''''seems''''' free

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

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

}

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 its free. Thus the expensive atomic memory operations happens 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.

If the [[programming language]] used supports [[minimal evaluation]], the entry protocol could be implemented as:

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 [[minimalshort-circuit evaluation]], the entry protocol could be implemented as:

'''procedure''' EnterCritical() {

Line 27 ⟶ 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]].: Onespinning examplein ofapplications baddeprives usagethe ofoperating thissystem [[idiom]] is [[double-checked locking]], which is listed as an [[anti-pattern]].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==

Line 34 ⟶ 43:

*[[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.

{{reflist}}

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

[[Category:Concurrency control]]