Lock-Free Programming
High-performance concurrency without locks.
What is Lock-Free Programming?
Section titled “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
Section titled “Visual: Lock-Based vs Lock-Free”CAS (Compare-And-Swap)
Section titled “CAS (Compare-And-Swap)”CAS is an atomic operation that updates a value only if it matches an expected value.
Visual: How CAS Works
Section titled “Visual: How CAS Works”CAS Pseudocode
Section titled “CAS Pseudocode”1CAS(memory_location, expected_value, new_value):2 if memory_location.value == expected_value:3 memory_location.value = new_value4 return true # Success5 else:6 return false # Failure, retry neededJava Atomic Variables
Section titled “Java Atomic Variables”Java provides atomic variables that use CAS internally.
AtomicInteger
Section titled “AtomicInteger”1import java.util.concurrent.atomic.AtomicInteger;2
3public class AtomicIntegerExample {4 private static AtomicInteger counter = new AtomicInteger(0);5
6 public static void increment() {7 // Atomic increment (uses CAS internally)8 counter.incrementAndGet();9 }10
11 public static void main(String[] args) throws InterruptedException {12 Thread[] threads = new Thread[10];13
14 for (int i = 0; i < 10; i++) {15 threads[i] = new Thread(() -> {16 for (int j = 0; j < 1000; j++) {17 increment();18 }19 });20 threads[i].start();21 }22
23 for (Thread thread : threads) {24 thread.join();25 }26
27 System.out.println("Counter: " + counter.get()); // Always 1000028 }29}AtomicReference
Section titled “AtomicReference”1import java.util.concurrent.atomic.AtomicReference;2
3public class AtomicReferenceExample {4 static class Node {5 int value;6 Node next;7
8 Node(int value) {9 this.value = value;10 }11 }12
13 private static AtomicReference<Node> head = new AtomicReference<>();14
15 public static void push(int value) {16 Node newHead = new Node(value);17 Node oldHead;18 do {19 oldHead = head.get();20 newHead.next = oldHead;21 } while (!head.compareAndSet(oldHead, newHead)); // CAS22 }23
24 public static void main(String[] args) {25 push(1);26 push(2);27 push(3);28
29 Node current = head.get();30 while (current != null) {31 System.out.println(current.value);32 current = current.next;33 }34 }35}The ABA Problem
Section titled “The ABA Problem”The ABA problem occurs when a value changes from A → B → A, making CAS think nothing changed.
Visual: ABA Problem
Section titled “Visual: ABA Problem”Solution: AtomicStampedReference
Section titled “Solution: AtomicStampedReference”1import java.util.concurrent.atomic.AtomicStampedReference;2
3public class ABASolution {4 public static void main(String[] args) {5 String initialRef = "A";6 int initialStamp = 0;7
8 AtomicStampedReference<String> ref =9 new AtomicStampedReference<>(initialRef, initialStamp);10
11 // Thread 1: Read reference and stamp12 int[] stampHolder = new int[1];13 String ref1 = ref.get(stampHolder);14 int stamp1 = stampHolder[0];15
16 // Thread 2: Change A → B → A (with different stamp)17 ref.compareAndSet("A", "B", 0, 1); // A → B, stamp 0 → 118 ref.compareAndSet("B", "A", 1, 2); // B → A, stamp 1 → 219
20 // Thread 1: CAS with original stamp (fails!)21 boolean success = ref.compareAndSet(ref1, "C", stamp1, stamp1 + 1);22 System.out.println("CAS succeeded: " + success); // false (stamp mismatch!)23 }24}Lock-Free Stack
Section titled “Lock-Free Stack”A lock-free stack using CAS:
1import java.util.concurrent.atomic.AtomicReference;2
3public class LockFreeStack<T> {4 static class Node<T> {5 T value;6 Node<T> next;7
8 Node(T value) {9 this.value = value;10 }11 }12
13 private AtomicReference<Node<T>> head = new AtomicReference<>();14
15 public void push(T value) {16 Node<T> newHead = new Node<>(value);17 Node<T> oldHead;18 do {19 oldHead = head.get();20 newHead.next = oldHead;21 } while (!head.compareAndSet(oldHead, newHead)); // CAS22 }23
24 public T pop() {25 Node<T> oldHead;26 Node<T> newHead;27 do {28 oldHead = head.get();29 if (oldHead == null) {30 return null;31 }32 newHead = oldHead.next;33 } while (!head.compareAndSet(oldHead, newHead)); // CAS34 return oldHead.value;35 }36}Trade-offs: Lock-Free vs Locked
Section titled “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 |
Interview Questions
Section titled “Interview Questions”Q1: “What is CAS and how does it work?”
Section titled “Q1: “What is CAS and how does it work?””Answer: CAS (Compare-And-Swap) is an atomic operation that:
- Compares a memory location’s value with an expected value
- If they match, updates to a new value
- Returns success/failure
- Used for optimistic locking without blocking
Q2: “Explain the ABA problem and how to solve it.”
Section titled “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
Section titled “Key Takeaways”Next Steps
Section titled “Next Steps”- Concurrency Hazards - Deadlocks, livelocks, and other pitfalls
Lock-free programming is powerful but complex—use wisely! 🚀