Test and Test-and-set

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 memory 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-setis used. The main idea is "not" to spin in test-and-set but increase the likelihood of successful test-and-set by using following entry protocol to the lock:

"boolean" locked := false "// shared lock variable" procedure EnterCritical() { do { while (locked = true) skip "// spin until lock "seems" free } while TestAndSet(locked) "// actual atomic locking" }

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 happens 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" }

Caveat

Although this optimization is useful in system programming it should be avoided in high level concurrent programming. One example of bad usage of this idiom is double-checked locking, which is listed as an anti-pattern.

ee also

*Parallel processor
*Parallel programming
*Mutual exclusion
*Test-and-set

References

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


Wikimedia Foundation. 2010.

Нужно сделать НИР?

Look at other dictionaries:

  • Test-and-set — Test and set  простая неразрывная (атомарная) процессорная инструкция, которая копирует значение переменной в регистр, и устанавливает некое новое значение. Во время исполнения данной инструкции процессор не может прервать её выполнение и… …   Википедия

  • Test-and-set — In computer science, the test and set instruction is an instruction used to both test and (conditionally) write to a memory location as part of a single atomic (i.e. non interruptible) operation. This means setting a value, but first performing… …   Wikipedia

  • Test-and-set lock — TSL son las siglas de Test and set lock, una instrucción hardware utilizada por ciertos procesadores para facilitar la creación de semáforos y otras herramientas necesarias para la programación concurrente en computadores. TSL es una instrucción… …   Wikipedia Español

  • SET 3 — NOTOC Infobox Aircraft name=SET 3 and SET 4 caption= type=Trainer aircraft manufacturer=SET designer=Grigore Zamfirescu first flight=1928 introduced= retired= status= primary user= more users= produced= number built= variants with their own… …   Wikipedia

  • set — {{Roman}}I.{{/Roman}} noun 1 group of similar things ADJECTIVE ▪ complete, entire, full, whole ▪ broad, comprehensive, huge, large …   Collocations dictionary

  • Test (Unix) — test is a Unix command that evaluates conditional expressions.yntax test expression or [ expression ] DescriptionThe test command evaluates the expression parameter. In the second form of the command, the [ ] (brackets) must be surrounded by… …   Wikipedia

  • Test fixture — refers to the fixed state used as a baseline for running tests in software testing. The purpose of a test fixture is to ensure that there is a well known and fixed environment in which tests are run so that results are repeatable. Some people… …   Wikipedia

  • Test-driven development — (TDD ) is a software development technique consisting of short iterations where new test cases covering the desired improvement or new functionality are written first, then the production code necessary to pass the tests is implemented, and… …   Wikipedia

  • Test and tagging — is a generic name given to the process of visually inspecting and electrically testing in service electrical equipment for personal use and/or safety. Colloquially, it is also referred to as; tagging, test tag, test and tag, electrical tagging,… …   Wikipedia

  • Test — Test, n. [OE. test test, or cupel, potsherd, F. t[^e]t, from L. testum an earthen vessel; akin to testa a piece of burned clay, an earthen pot, a potsherd, perhaps for tersta, and akin to torrere to patch, terra earth (cf. {Thirst}, and… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”