Course contentsShow
← Computer Science
Lesson 2567 of 2,87257. Concurrency FundamentalsFree lesson

Atomic Operations and Compare-and-Swap

Learning hardware-level atomic operations, particularly CAS (compare-and-swap), as the foundation of lock-free algorithms.

Atomic Operations and Compare-and-Swap

You'll learn how hardware-level atomic operations, especially compare-and-swap (CAS), enable lock-free algorithms by guaranteeing indivisible memory updates.

The Foundation of Lock-Free Programming

In lock-free programming, you can't use locks or synchronized blocks—yet you still need to safely update shared data. This is where hardware-level atomic operations come in. These operations are guaranteed by your CPU to execute completely without interruption, as if they were a single, indivisible instruction.

The most powerful atomic operation is compare-and-swap (CAS). It performs three steps atomically:

  1. Read a value from memory
  2. Compare it to an expected value
  3. If they match, swap in a new value; otherwise, do nothing

All three steps happen as one uninterruptible unit.

How CAS Works

Imagine you're updating a shared counter. With CAS, you say: "I last saw this counter at 42. If it's still 42, change it to 43. If someone else changed it, tell me it failed."

This lets you detect and handle interference from other threads. If CAS fails, you simply retry with the updated value—no locks needed.

while (true) {
    current = counter.get()
    next = current + 1
    if (CAS(counter, current, next)) {
        break  // Success!
    }
    // Failed—someone modified counter, retry
}

Why CAS Matters

CAS is the building block for lock-free data structures. It avoids the overhead and blocking of locks while still ensuring correctness. Modern CPUs provide CAS instructions (like CMPXCHG on x86), making it efficient at the hardware level.

Key Takeaway: Compare-and-swap is a hardware-supported atomic operation that reads, compares, and conditionally updates memory in one indivisible step, forming the foundation of lock-free algorithms.