Optimistic Locking: Internals, CAS Semantics, and Hardware Execution

Writing multi-threaded applications is essential for unlocking the performance of modern multi-core processors. However, managing shared mutable state across threads requires synchronization to maintain data correctness.

While wrapping a critical section with mutual exclusion locks (pessimistic locking) is the standard approach, it introduces performance bottlenecks that degrade throughput. Optimistic locking offers an alternative paradigm that avoids mutual exclusion locks by relying on atomic hardware primitives.

---

1. The Bottleneck of Pessimistic Locking

In standard multi-threaded programming, the default mechanism for thread safety is pessimistic locking (e.g., using mutexes or synchronized blocks).

sequenceDiagram
    autonumber
    participant T1 as Thread 1
    participant Mutex as Mutex Lock
    participant T2 as Thread 2
    participant CS as Critical Section

    T1->>Mutex: Acquire Lock (Success)
    T2->>Mutex: Acquire Lock (Blocked / Sleeps)
    T1->>CS: Execute operations
    T1->>Mutex: Release Lock
    Mutex->>T2: Grant Lock (Woken up)
    T2->>CS: Execute operations
    T2->>Mutex: Release Lock

How Pessimistic Locking Works

1. Before entering a critical section, a thread must acquire an exclusive lock.
2. If $N$ threads attempt to access the critical section simultaneously, exactly one thread acquires the lock and enters.
3. The remaining $N-1$ threads are suspended (or spin-wait), waiting for the lock to be released.
4. Once the active thread finishes, it releases the lock, allowing one waiting thread to resume.

The Problem: Throughput Degradation

Pessimistic locking assumes conflicts are frequent and preemptively restricts access. Under heavy concurrency:

• Thread Contention: Even with dozens of CPU cores available, execution serializes through the critical section choke point.
• OS Overhead: Threads that fail to acquire a lock often transition from user-space to kernel-space, entering sleep states that incur costly OS context switches and cache thrashing.

---

2. Core Intuition Behind Optimistic Locking

Optimistic locking operates under the assumption that data conflicts are rare. Instead of locking access before performing an update, threads proceed optimistically without acquiring a lock.

Core Rule: Allow multiple threads to calculate and attempt their update concurrently. Guarantee that if a conflict occurs, exactly one thread succeeds and all conflicting threads fail cleanly, returning control to application logic.

flowchart TD
    A[Read Current Value: V_old] --> B[Compute New Value: V_new]
    B --> C{Atomic Compare-And-Swap\nValue == V_old?}
    C -- Yes --> D[Update Value to V_new\nReturn Success]
    C -- No --> E[Value Changed by Another Thread\nReturn Failure]
    E --> F{Handle Conflict}
    F -->|Retry Loop| A
    F -->|Fail Fast| G[Throw Error / Abort]
    F -->|Ignore| H[Discard Update]

When an operation fails, the thread is alerted explicitly. This provides fine-grained control to:

• Retry: Re-read the updated state, recompute, and try again.
• Fail fast: Throw an error to the caller or user.
• Ignore: Drop the update safely if it is obsolete.

---

3. Compare-And-Swap (CAS) Semantics

The fundamental building block of optimistic locking is the Compare-And-Swap (CAS) (or Compare-And-Exchange) operation.

Logical Specification

Instead of a direct assignment count = new_value, CAS requires three operands:

1. The memory location of the variable (&variable).
2. The expected current value (old_value).
3. The target new value (new_value).

// Conceptual representation (must execute atomically)
bool compare_and_swap(int *target, int expected_old, int new_val) {
    if (*target == expected_old) {
        *target = new_val;
        return true;  // Succeeded
    }
    return false;     // Failed, target was modified concurrently
}

Concurrency Trace Example

Assume count = 10:

1. Thread A wants to update count to 11. It evaluates CAS(&count, 10, 11).
2. Thread B wants to update count to 15. It evaluates CAS(&count, 10, 15).
3. If both threads execute at virtually the same instant, hardware arbitration ensures one evaluates first.
4. If Thread A wins, count becomes 11, and Thread A receives true.
5. When Thread B executes, the actual memory value is 11, which does not match Thread B’s expected value of 10. The swap is rejected, leaving count = 11, and Thread B receives false.

Because CAS evaluates and writes conditionally in an indivisible, atomic step, no two threads can interleave in between the comparison and the assignment.

---

4. Implementation Walkthrough (C / C11 Atomics)

In standard environments, developers use language-level atomic primitives (such as stdatomic.h in C, java.util.concurrent.atomic in Java, or sync/atomic in Go).

Thread-Safe Counter Using Optimistic Retries

#include <stdio.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <pthread.h>

// Shared counter
atomic_int count = 0;

void* increment_count_optimistic(void* arg) {
    int old_val;
    int new_val;
    bool success = false;

    // Retry loop until the atomic swap succeeds
    while (!success) {
        // 1. Read the old value atomically
        old_val = atomic_load(&count);
        
        // 2. Compute the new state locally
        new_val = old_val + 1;
        
        // 3. Attempt conditional atomic swap
        // atomic_compare_exchange_weak updates old_val on failure
        success = atomic_compare_exchange_strong(&count, &old_val, new_val);
        
        // If success is false, count was modified by another thread.
        // Loop re-runs with the freshly updated old_val.
    }
    
    return NULL;
}

int main() {
    pthread_t t1, t2;
    
    pthread_create(&t1, NULL, increment_count_optimistic, NULL);
    pthread_create(&t2, NULL, increment_count_optimistic, NULL);
    
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    
    printf("Final Count: %d\n", atomic_load(&count));
    return 0;
}

Contrasting Code Complexity

• Mutex approach: Simple to read (lock() -> count++ -> unlock()), but introduces contention under heavy thread load.
• Optimistic approach: More verbose; requires explicit handling for read-compute-swap cycles and conflict loops, but runs lock-free in user space without thread descheduling.

---

5. Hardware Internals: How the CPU Guarantees Atomicity

How can software execute if (*target == expected) { *target = new; } without another thread preempting it mid-execution?

The answer lies in compilation down to dedicated CPU instructions.

Assembly Deep-Dive (x86_64)

Compiling C code containing atomic_compare_exchange via GCC (gcc -S main.c) reveals the underlying assembly instruction:

# Inside increment_count_optimistic
movl    -4(%rbp), %eax       # Load old_val into %eax register
movl    -8(%rbp), %edx       # Load new_val into %edx register
lock cmpxchgl   %edx, count(%rip)   # Atomic Compare-and-Exchange

Key Assembly Primitives

1. cmpxchgl (Compare and Exchange):
   • Compares the value in register %eax with the memory operand (count).
   • If equal, sets the ZF (zero flag) in the status register and writes the contents of %edx to count.
   • If not equal, clears ZF and loads the current value of count back into %eax.
2. lock Prefix:
   • In multi-core systems, multiple CPU cores share a memory bus and L3 cache.
   • The lock prefix asserts hardware-level cache line locking (via protocols like MESI/MOESI), guaranteeing that the current core has exclusive modification access to that memory line across the entire bus for the duration of that instruction.
3. Indivisibility & Context Switching:
   • The OS kernel executes context switches using timer interrupts.
   • The CPU will only service an interrupt between instructions, never midway through a single atomic instruction. Thus, lock cmpxchgl cannot be interrupted by the operating system.

Hardware Fallbacks

If an underlying CPU architecture does not provide native atomic CAS instructions, compilers and runtimes fall back to internal spinlocks or mutexes, simulating optimistic semantics via pessimistic locks under the hood.

---

6. Trade-Off Analysis: Optimistic vs. Pessimistic Locking

Attribute	Pessimistic Locking (Mutexes)	Optimistic Locking (CAS / Lock-Free)
Core Philosophy	Expect conflicts; block all other threads preemptively.	Expect no conflicts; detect conflicts at write-time.
Cost per Conflict	High (thread sleeping, OS context switch, kernel involvement).	Low (failed CPU instruction, local branch/retry).
Cost under Low Contention	Overhead of acquiring/releasing lock structures.	Extremely low; fast single CPU cycle instructions.
Cost under High Contention	Constant serialization delay, but bounded retries.	Live-lock risk; high CPU burn due to continuous retry loops.
Implementation Complexity	Simple, intuitive block scope.	Complex loops, memory order parameters, ABA problem awareness.
Supported Operations	Complex, multi-step critical sections (I/O, network, database updates).	Single primitive memory locations or versioned structs.

---

7. When to Use Which Pattern

Choose Optimistic Locking When:

• Contention is low to moderate: Conflicts are infrequent, allowing the majority of operations to succeed on the first attempt.
• Operations are brief and memory-bound: Tasks such as incrementing counters, state transitions, toggling flags, or lock-free data structure nodes (queues, stacks).
• High read-to-write ratio: Many threads read state, while writes are sporadic.

Choose Pessimistic Locking When:

• Contention is severe: Continuous CAS failures cause excessive CPU cycles to be wasted inside busy-spin retry loops.
• Critical sections are heavy: If the operation involves disk I/O, network calls, RPCs, or updates spanning multiple unrelated resources, rollback logic is non-trivial and CAS is impractical.

---

8. Summary

• Pessimistic locking ensures correctness by enforcing exclusivity, but penalizes throughput when multiple threads contend for the lock.
• Optimistic locking delegates synchronization down to atomic CPU instructions (like lock cmpxchgl), enabling lock-free state transitions.
• In systems with infrequent collisions, optimistic concurrency delivers superior performance, lower latency, and higher resource utilization across modern multi-core processors.