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
    }
}

Go

atomic_counter.go

package main

import (
  "fmt"
  "sync"
  "sync/atomic"
)

var counter int64

func increment() {
  atomic.AddInt64(&counter, 1) // atomic increment (uses CAS internally)
}

func main() {
  var wg sync.WaitGroup

  for i := 0; i < 10; i++ {
    wg.Add(1)
    go func() {
      defer wg.Done()
      for j := 0; j < 1000; j++ {
        increment()
      }
    }()
  }

  wg.Wait()
  fmt.Println("Counter:", atomic.LoadInt64(&counter)) // 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;
        }
    }
}

Go

atomic_reference.go

package main

import (
  "fmt"
  "sync/atomic"
  "unsafe"
)

type Node struct {
  value int
  next  unsafe.Pointer // *Node stored as unsafe.Pointer for CAS
}

var head unsafe.Pointer // *Node

func push(value int) {
  newNode := &Node{value: value}
  for {
    oldHead := atomic.LoadPointer(&head)
    newNode.next = oldHead
    if atomic.CompareAndSwapPointer(&head, oldHead, unsafe.Pointer(newNode)) {
      return // CAS succeeded
    }
    // CAS failed — another goroutine changed head; retry
  }
}

func main() {
  push(1)
  push(2)
  push(3)

  current := (*Node)(atomic.LoadPointer(&head))
  for current != nil {
    fmt.Println(current.value)
    current = (*Node)(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!)
    }
}

Go

aba_solution.go

package main

import (
  "fmt"
  "sync/atomic"
)

// Versioned value: pack version (upper 32 bits) + value (lower 32 bits) into int64
// This is Go's idiomatic way to solve ABA without generics overhead.

func pack(version, value int32) int64 {
  return int64(version)<<32 | int64(uint32(value))
}

func unpack(n int64) (version int32, value int32) {
  return int32(n >> 32), int32(n)
}

func main() {
  // Initial: version=0, value=1 (representing "A")
  var ref int64 = pack(0, 1)

  // Thread 1: read version and value
  ver1, val1 := unpack(atomic.LoadInt64(&ref))
  fmt.Printf("Thread 1 read: version=%d value=%d\n", ver1, val1)

  // Thread 2: change 1→2→1 with bumped version each time
  atomic.CompareAndSwapInt64(&ref, pack(0, 1), pack(1, 2)) // 1→2
  atomic.CompareAndSwapInt64(&ref, pack(1, 2), pack(2, 1)) // 2→1

  // Thread 1: CAS with original version (fails — version mismatch!)
  success := atomic.CompareAndSwapInt64(&ref, pack(ver1, val1), pack(ver1+1, 3))
  fmt.Println("CAS succeeded:", success) // false (version 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;
    }
}

Go

lock_free_stack.go

package main

import (
  "fmt"
  "sync/atomic"
  "unsafe"
)

type StackNode[T any] struct {
  value T
  next  unsafe.Pointer // *StackNode[T]
}

type LockFreeStack[T any] struct {
  head unsafe.Pointer // *StackNode[T]
}

func (s *LockFreeStack[T]) Push(value T) {
  newNode := &StackNode[T]{value: value}
  for {
    oldHead := atomic.LoadPointer(&s.head)
    newNode.next = oldHead
    if atomic.CompareAndSwapPointer(&s.head, oldHead, unsafe.Pointer(newNode)) {
      return // CAS succeeded
    }
    // retry
  }
}

func (s *LockFreeStack[T]) Pop() (T, bool) {
  for {
    oldHead := atomic.LoadPointer(&s.head)
    if oldHead == nil {
      var zero T
      return zero, false
    }
    node := (*StackNode[T])(oldHead)
    newHead := node.next
    if atomic.CompareAndSwapPointer(&s.head, oldHead, newHead) {
      return node.value, true // CAS succeeded
    }
    // retry
  }
}

func main() {
  stack := &LockFreeStack[int]{}
  stack.Push(1)
  stack.Push(2)
  stack.Push(3)

  for {
    val, ok := stack.Pop()
    if !ok {
      break
    }
    fmt.Println(val)
  }
}

---

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! 🚀