Unit 2 · Concurrent Processes

Lecture 7: Test-and-Set, Spinlocks, and Mutex Locks

Learning outcomes

Explain why hardware support is needed for synchronization in modern computer systems.
Define atomic operations and describe the purpose of the test-and-set instruction.
Illustrate how test-and-set can be used to implement mutual exclusion.
Explain the concept of a spinlock and distinguish it from a general mutex lock.
Analyze the advantages and limitations of busy waiting in single-core and multicore systems.
Relate hardware primitives such as test-and-set and compare-and-swap to higher-level synchronization tools.

Prerequisites

Critical section problem and race conditions Basic idea of mutual exclusion Peterson’s solution Concurrent processes and shared variables Single-core vs multicore execution basics

Lecture Notes

Main content

Lecture: Test-and-Set, Spinlocks, and Mutex Locks

Learning Focus

Understand how hardware instructions such as test-and-set help solve the critical-section problem, and how they are used to build spinlocks and mutex locks.

Why hardware support is needed

In concurrent systems, two or more processes may try to access shared data at the same time. If access is not controlled properly, a race condition occurs and the final result becomes unpredictable.

Software-only methods are useful for learning, but modern processors may reorder instructions or delay the visibility of memory updates across cores. Therefore, operating systems use hardware-supported atomic operations for reliable synchronization.

Figure 1: Why a simple software check can fail

Atomic operations and test-and-set

An atomic operation is performed as one indivisible step. No other process can interrupt it halfway. This is important because checking and setting a lock separately can allow two processes to enter together.

The test-and-set instruction atomically reads the old value of a lock, sets it to true, and returns the old value.

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

If the old value is false, the process gets the lock. If the old value is true, another process already holds it.

while (test_and_set(&lock))
    ;   /* busy wait */

/* critical section */

lock = false;

Because test-and-set is atomic, two processes cannot acquire the lock at the same time. So mutual exclusion is maintained.

Figure 2: Test-and-set as one atomic step

Spinlocks and mutex locks

When a process keeps checking a lock in a loop until it becomes free, the lock is called a spinlock. This is also called busy waiting.

A mutex lock is the higher-level locking tool used for mutual exclusion. A process must acquire the lock before entering the critical section and release it after leaving.

acquire(lock)
/* critical section */
release(lock)

A spinlock is one way of implementing a mutex lock. In a blocking mutex, the waiting process sleeps instead of spinning.

Figure 3: Spinlock vs Blocking Mutex

Important points

Spinlocks are fast for short waits but waste CPU time if the wait becomes long.
Blocking mutexes are better for longer waits because the waiting process sleeps.
On multicore systems, spinlocks can be efficient when the critical section is very short.
A practical rule is: use a spinlock when the expected wait is shorter than about two context switches.
Another related atomic primitive is compare-and-swap (CAS).

Worked Example

Worked Example: Two Processes Using Test-and-Set

Let the shared lock variable be initialized as:

boolean lock = false;

Two processes, P1 and P2, want to enter the same critical section.

Step 1: Process P1 tries to enter

P1 executes test_and_set(&lock).

The old value of lock is false.
The instruction sets lock = true.
P1 enters the critical section.

Step 2: Process P2 tries to enter while P1 is inside

P2 also executes test_and_set(&lock).

The old value of lock is now true.
P2 cannot enter the critical section.
P2 keeps waiting in the loop.

while (test_and_set(&lock))
    ;   /* busy wait */

Step 3: P1 exits the critical section

When P1 finishes, it releases the lock by executing:

lock = false;

Step 4: P2 tries again

P2 again executes test_and_set(&lock).

The old value of lock is now false.
The instruction sets lock = true.
P2 enters the critical section.

Conclusion

At no point do both P1 and P2 enter the critical section together. This shows that test-and-set ensures mutual exclusion.

Extension

Since the waiting process repeatedly checks the lock in a loop, this mechanism behaves as a spinlock. If the same idea is provided through higher-level operations such as acquire() and release(), it is commonly described as a mutex lock built using atomic hardware support.

One-Page Summary

In modern systems, software-only synchronization is not always reliable because processors may reorder instructions and memory updates may not become visible immediately to other cores. Therefore, operating systems use hardware support for safe synchronization. One important hardware instruction is test-and-set. It atomically checks the old value of a lock and sets it to busy in one step. Because of this, it can be used to implement mutual exclusion correctly. When a process keeps checking the lock in a loop until it becomes free, the mechanism is called a spinlock. Spinlocks are useful for very short waits, especially on multicore systems, but they waste CPU time if the waiting period becomes long. To make locking easier to use, operating systems provide mutex locks. A process must acquire the lock before entering the critical section and release it after leaving. A spinlock is one way of implementing a mutex lock, while a blocking mutex makes the waiting process sleep. So, test-and-set and compare-and-swap are low-level hardware mechanisms, while spinlocks and mutex locks are synchronization tools built on top of them.