Test and test-and-set: Difference between revisions

Revision as of 09:47, 21 June 2005

Latest revision as of 17:17, 27 April 2024

(41 intermediate revisions by 36 users not shown)

Line 1:

{{Short description|CPU Instruction}}

The [[test-and-set]] [[Central processing unit|CPU]] instruction is used to implement

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

[[mutual exclusion]] in [[multiprocessor]] environments. Although a correct [[Locklock (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 coherency protocol]] operationoverhead needson tocontended access memory [[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 spin in [[test-and-set]] but increase the likelihood of successfull [[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

'''while''' TestAndSet( locked) ''//== actualtrue atomic locking'')

'''whileskip''' (locked = true) skip ''// ifspin test-and-setusing failed,normal waitinstructions foruntil the lock to becomeis free again''

} '''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]] and wait for the lock to come 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 [[Lazy evaluation#Minimal evaluation|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 [[Lazy evaluation#Minimal evaluation|minimalshort-circuit evaluation]], the entry protocol could be implemented as:

'''procedure''' EnterCritical() {

'''while''' ( locked == true or TestAndSet(locked) == true )

'''skip''' ''// spin until locked''

}

==Caveat==

Although this [[Optimization (computer science)|optimization]] is usefulluseful in [[system programming]], ittest-and-set is shouldto 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 36 ⟶ 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]]

[[Category:Computer sciencearithmetic]]