Lock-Free Programming

What is Lock-Free Programming?

Lock-free programming achieves thread-safety without using locks, using atomic operations and CAS (Compare-And-Swap) instead.

Visual: Lock-Based vs Lock-Free

---

CAS (Compare-And-Swap)

CAS is an atomic operation that updates a value only if it matches an expected value.

Visual: How CAS Works

CAS Pseudocode

CAS(memory_location, expected_value, new_value):
    if memory_location.value == expected_value:
        memory_location.value = new_value
        return true  # Success
    else:
        return false  # Failure, retry needed

---

Java Atomic Variables

Java provides atomic variables that use CAS internally.

AtomicInteger

Java

AtomicIntegerExample.java

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicIntegerExample {
    private static AtomicInteger counter = new AtomicInteger(0);

    public static void increment() {
        // Atomic increment (uses CAS internally)
        counter.incrementAndGet();
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] threads = new Thread[10];

        for (int i = 0; i < 10; i++) {
            threads[i] = new Thread(() -> {
                for (int j = 0; j < 1000; j++) {
                    increment();
                }
            });
            threads[i].start();
        }

        for (Thread thread : threads) {
            thread.join();
        }

        System.out.println("Counter: " + counter.get());  // Always 10000
    }
}

AtomicReference

Java

AtomicReferenceExample.java

import java.util.concurrent.atomic.AtomicReference;

public class AtomicReferenceExample {
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    private static AtomicReference<Node> head = new AtomicReference<>();

    public static void push(int value) {
        Node newHead = new Node(value);
        Node oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));  // CAS
    }

    public static void main(String[] args) {
        push(1);
        push(2);
        push(3);

        Node current = head.get();
        while (current != null) {
            System.out.println(current.value);
            current = current.next;
        }
    }
}

---

The ABA Problem

The ABA problem occurs when a value changes from A → B → A, making CAS think nothing changed.

Visual: ABA Problem

Solution: AtomicStampedReference

Java

ABASolution.java

import java.util.concurrent.atomic.AtomicStampedReference;

public class ABASolution {
    public static void main(String[] args) {
        String initialRef = "A";
        int initialStamp = 0;

        AtomicStampedReference<String> ref =
            new AtomicStampedReference<>(initialRef, initialStamp);

        // Thread 1: Read reference and stamp
        int[] stampHolder = new int[1];
        String ref1 = ref.get(stampHolder);
        int stamp1 = stampHolder[0];

        // Thread 2: Change A → B → A (with different stamp)
        ref.compareAndSet("A", "B", 0, 1);  // A → B, stamp 0 → 1
        ref.compareAndSet("B", "A", 1, 2);  // B → A, stamp 1 → 2

        // Thread 1: CAS with original stamp (fails!)
        boolean success = ref.compareAndSet(ref1, "C", stamp1, stamp1 + 1);
        System.out.println("CAS succeeded: " + success);  // false (stamp mismatch!)
    }
}

---

Lock-Free Stack

A lock-free stack using CAS:

Java

LockFreeStack.java

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeStack<T> {
    static class Node<T> {
        T value;
        Node<T> next;

        Node(T value) {
            this.value = value;
        }
    }

    private AtomicReference<Node<T>> head = new AtomicReference<>();

    public void push(T value) {
        Node<T> newHead = new Node<>(value);
        Node<T> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));  // CAS
    }

    public T pop() {
        Node<T> oldHead;
        Node<T> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) {
                return null;
            }
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead, newHead));  // CAS
        return oldHead.value;
    }
}

---

Trade-offs: Lock-Free vs Locked

Aspect	Lock-Free	Locked
Performance	Higher (no blocking)	Lower (contention)
Complexity	Higher	Lower
Correctness	Harder to verify	Easier to reason about
Use When	High contention, performance critical	Most cases

When to Use Lock-Free

• Use: High-performance scenarios, lock contention bottleneck
• Don’t use: Most applications (locks are simpler and sufficient)
• Consider: Complexity vs performance gain

---

Interview Questions

Q1: “What is CAS and how does it work?”

Answer: CAS (Compare-And-Swap) is an atomic operation that:

1. Compares a memory location’s value with an expected value
2. If they match, updates to a new value
3. Returns success/failure
4. Used for optimistic locking without blocking

Q2: “Explain the ABA problem and how to solve it.”

Answer: ABA occurs when value changes A→B→A, making CAS think nothing changed. Solutions:

• AtomicStampedReference: Add version/stamp to detect changes
• Tagged pointers: Add metadata to pointer
• Hazard pointers: Advanced technique for memory management

---

Key Takeaways

Remember

• Lock-free uses CAS instead of locks
• Atomic variables provide lock-free operations
• ABA problem can occur with CAS (use versioning)
• Trade-off: Higher performance but more complexity
• Use sparingly: Only when performance is critical

---

Next Steps

• Concurrency Hazards - Deadlocks, livelocks, and other pitfalls

Lock-free programming is powerful but complex—use wisely! 🚀