Test-and-Set in OS Synchronization

Introduction

Test-and-set is a hardware atomic instruction used to build simple mutual-exclusion locks. Atomic means the operation behaves as one indivisible step.

Its main purpose is to remove the unsafe gap between checking whether a lock is free and marking that lock as acquired. Without this atomic step, two threads may both believe they acquired the same lock.

Core Idea

Test-and-set works on a shared lock variable. It reads the old value of the lock, sets the lock to true, and returns the old value it read.

The important point is that this full sequence behaves like one hardware operation. Other threads cannot observe the lock halfway through the read-and-set action.

So test-and-set combines checking and acquiring into one indivisible operation.

Why Normal Check-Then-Set Fails

Suppose false means unlocked and true means locked. A normal check-then-set idea may look like this:

if lock == false:
    lock = true
    enter critical section

This is unsafe because the check and update are separate. Thread A may see lock == false, and before it sets the lock, Thread B may also see lock == false.

Now both threads can believe the lock is free. Test-and-set fixes this by making the check and update happen together as one atomic hardware action.

Simple Spinlock Using Test-and-Set

A simple spinlock can be built using one shared lock variable.

while test_and_set(lock) == true:
    wait

critical section

lock = false

The working idea is:

• Acquire attempt: A thread calls test_and_set(lock).

• Free result: If it returns false, the thread owns the lock and enters the critical section.

• Busy result: If it returns true, the lock is already held, so the thread keeps trying.

• Release: After the critical section, the thread sets lock = false.

This lock is called a spinlock because a waiting thread spins in a loop while the lock is busy.

Why Mutual Exclusion Works

Mutual exclusion requires that only one thread enter the critical section at a time. Test-and-set provides this because only one thread can see the old lock value as false.

If Thread A executes test-and-set first and the lock was free, the operation immediately changes the lock to true. When Thread B tries after that, it receives true, meaning the lock was already taken.

The safety comes from indivisibility. The check and update cannot be split, so two threads cannot both acquire the lock from the same free state.

Busy Waiting Problem

A basic test-and-set lock uses busy waiting. The waiting thread repeatedly checks the lock while still using CPU time.

Busy waiting can be acceptable when the lock is held for a very short time. If the critical section is long, or if the lock holder is not currently running, spinning wastes CPU.

Common problems include:

• Long waits: A spinning thread burns CPU without doing useful work.

• Descheduled lock holder: Other threads may spin while the actual lock holder is not running.

• Heavy contention: Many waiting threads may repeatedly hit the same lock variable.

• Cache traffic: Multiple cores spinning on one lock can create extra coherence overhead.

So test-and-set gives correctness for mutual exclusion, but it does not automatically give good performance.

Fairness and Limitations

Basic test-and-set does not guarantee fairness. When the lock becomes free, any waiting thread may win the next test-and-set attempt.

This means one unlucky thread can lose repeatedly while other threads acquire the lock again and again. More advanced locks, such as ticket locks or queue-based locks, are designed to improve fairness and reduce contention.

Summary

Test-and-set is a hardware atomic instruction that reads the old lock value, sets the lock to true, and returns the old value in one indivisible operation.

It is useful for building simple spinlocks and explaining hardware-supported mutual exclusion. Its main limits are busy waiting, possible unfairness, and cache traffic under contention, so real systems often use more advanced lock designs or higher-level synchronization primitives.