computer science

Test and test-and-set

Test and test-and-set is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Test and test-and-set rather than just read about it. In short: In computer architecture, the test-and-set CPU instruction (or instruction sequence) is designed to implement mutual exclusion in multiprocessor environments. Although a correct lock can be implemented with test-and-set, the test and test-and-set optimization lowers resource contention caused by bus locking, especially cache coherency protocol overhead on contended locks.

Key takeaways

Test and test-and-set belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Test and test-and-set to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Test and test-and-set from memory before moving on to harder problems.

Reference excerpt

In computer architecture, the test-and-set CPU instruction (or instruction sequence) is designed to implement mutual exclusion in multiprocessor environments. Although a correct lock can be implemented with test-and-set, the test and test-and-set optimization lowers resource contention caused by bus locking, especially cache coherency protocol 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 test-and-set 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 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. 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:

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

Caveat Although this optimization is useful in system programming, test-and-set is to be avoided in high-level concurrent programming: spinning in applications deprives the operating system 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 Parallel processor Parallel programming 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.

Worked examples

Example 1 — a first encounter with Test and test-and-set

Start with the simplest possible case. Write down what Test and test-and-set claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Test and test-and-set before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Test and test-and-set ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Test and test-and-set

In research: Test and test-and-set appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Test and test-and-set in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Test and test-and-set is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computer arithmetic, Concurrency control, so understanding it makes those chapters shorter.
In everyday life: Look for Test and test-and-set outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Test and test-and-set” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Test and test-and-set in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Test and test-and-set means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Test and test-and-set out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Test and test-and-set in simple terms?

Why does Test and test-and-set matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Test and test-and-set?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Test and test-and-set.