Locks Using Compare-And-Swap (CAS)

1. What is Compare-And-Swap?

Compare-And-Swap (CAS) is a hardware-supported atomic instruction used to safely update shared variables in concurrent systems.

It is called:

• compare-and-swap on SPARC

• compare-and-exchange on x86

What CAS Does (in simple words)

CAS checks a memory location and updates it only if it has not changed.

“Update this value only if it is what I expect it to be.”

Because CAS is atomic, no other thread can interfere while it is executing.

---

2. CAS Pseudocode (Conceptual View)

int CompareAndSwap(int *ptr, int expected, int new) {
    int original = *ptr;
    if (original == expected)
        *ptr = new;
    return original;
}

Meaning:

• Read the current value at ptr

• If it equals expected, replace it with new

• Always return the original value

This return value tells the calling thread whether the operation succeeded.

---

3. Building a Lock with Compare-And-Swap

Using CAS, we can build a spin lock.

Lock Representation

• A shared integer variable flag

• flag = 0 → lock is free

• flag = 1 → lock is held

---

Lock Acquisition Using CAS

void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ; // spin
}

How This Works Step-by-Step

1. Thread tries to change flag from 0 → 1

2. If flag was 0:

   • CAS succeeds

   • Thread acquires the lock

3. If flag was already 1:

   • CAS fails

   • Thread spins (busy waits)

4. Thread keeps retrying until the lock is released

---

Lock Release

lock->flag = 0;

Once the thread exits the critical section, it sets the flag back to 0,
allowing another thread to acquire the lock.

---

4. Why CAS Works for Locks

Key Properties

✔ Atomicity
CAS executes as one uninterruptible operation.

✔ Mutual Exclusion
Only one thread can successfully change flag from 0 to 1.

✔ Correctness
No two threads can enter the critical section simultaneously.

---

5. Comparison with Test-And-Set

Feature	Test-And-Set	Compare-And-Swap
Atomic	Yes	Yes
Checks expected value	No	Yes
More flexible	❌	✅
Used in lock-free algorithms	❌	✅

👉 CAS is more powerful because it allows conditional updates, not just blind setting.

---

6. Behavior of CAS-Based Spin Locks

If we use CAS only to build a simple spin lock, its behavior is:

✔ Correct

• Provides mutual exclusion

❌ Unfair

• No guarantee that waiting threads will eventually get the lock

• Starvation is possible

⚠ Performance

• Poor on single-CPU systems (busy waiting wastes CPU time)

• Good on multicore systems when:

  • Critical sections are short

  • Threads ≈ number of CPUs

In practice, CAS-based spin locks behave identically to test-and-set spin locks.

---

7. Why CAS Is Important Beyond Locks

Although simple locks built with CAS behave like test-and-set locks, CAS is more powerful and enables:

• Lock-free data structures

• Non-blocking algorithms

• High-performance concurrent systems

These ideas are used in:

• Modern operating systems

• Databases

• High-performance servers

---

8. Key Takeaway 

Compare-And-Swap is an atomic hardware instruction that allows a thread to update a shared variable only if it has an expected value. Using CAS, we can build spin locks that ensure mutual exclusion, but such locks are unfair and rely on busy waiting. CAS is more powerful than test-and-set and forms the foundation of advanced lock-free synchronization techniques.