Compare-and-Swap in OS Synchronization

Introduction

Compare-and-swap is usually called CAS. It is an atomic hardware operation, meaning the compare and possible update happen as one indivisible action.

CAS is more flexible than test-and-set because it updates a value only when the current value still matches what the caller expected. This makes it useful for locks, atomic updates, and lock-free synchronization.

Core Idea

CAS works on a memory location. It reads the current value, compares it with an expected value, and writes a new value only if both values match.

• Read: CAS reads the value currently stored at the memory location

• Compare: It checks whether the current value equals the expected value

• Update on match: If both match, CAS writes the new value

• No update on mismatch: If they do not match, CAS fails and leaves memory unchanged

The compare and possible write are atomic. No other thread can slip between the comparison and the update.

Pseudocode Meaning

A common form is CAS(address, expected, new). It means: update the value at address to new only if the current value is still expected.

CAS(address, expected, new):
    if *address == expected:
        *address = new
        return success
    else:
        return failure

This pseudocode explains the meaning, but the real hardware operation must perform the check and update indivisibly. Some APIs also update expected with the actual current value when CAS fails.

Lock Using CAS

CAS can be used to build a simple lock. Suppose 0 means unlocked and 1 means locked.

A thread can try: CAS(lock, 0, 1)

This means: change the lock from 0 to 1 only if it is still 0.

• Success: The lock was free, CAS changes it to 1, and the thread enters the critical section.

• Failure: The lock was already 1, so the thread retries, waits, or blocks depending on the design.

• Release: After the critical section, the thread sets the lock back to 0.

Only one thread can successfully change the lock from 0 to 1, because the compare-and-update step is atomic.

CAS vs Test-and-Set

Test-and-set and CAS are both hardware atomic operations, but they are not the same.

ABA Problem

The ABA problem happens when a value changes from A to B and then back to A. CAS sees the current value as A, so it may succeed, even though the state changed in between.

For example, Thread 1 reads a shared pointer as A and pauses. Thread 2 changes the pointer from A to B, then later back to A. When Thread 1 resumes, CAS(head, A, C) may succeed because the current value is again A.

The problem is that CAS checks the current value, not the full history. The value looks unchanged, but the logical state may no longer be the same.

Common ways to reduce this risk include version numbers, tagged pointers, hazard pointers, garbage collection, or safer memory-reclamation techniques.

Limitations

CAS is powerful, but it is not a complete synchronization solution by itself.

• Retry cost: Under contention, many failed CAS attempts can waste CPU.

• Complex design: Lock-free structures using CAS are harder to reason about than simple locks.

• Starvation possibility: Some threads may repeatedly fail while others succeed.

For application-level code, higher-level synchronization tools are often safer unless lock-free behavior is truly needed.

Summary

Compare-and-swap is an atomic hardware operation that reads a memory location, compares it with an expected value, and writes a new value only if the comparison succeeds.

CAS is more general than test-and-set and supports locks, optimistic updates, reference counters, atomic state transitions, and lock-free data structures. Its main caution is that failed retries, memory ordering, and the ABA problem must be handled carefully.