LockFree Algorithms & Data Structures

The Concept: While AtomicInteger works for primitives, AtomicReference<V> allows you to update a reference to an entire object as a single atomic unit. This is the foundation of “Immutable State” updates. import java.util.concurrent.atomic.AtomicReference; public class ConfigManager { // A shared configuration object that many threads read private final AtomicReference<Config> currentConfig = new AtomicReference<>(new Config("v1")); public void updateConfig(String newVersion) { Config oldConfig; Config newConfig = new Config(newVersion); do { oldConfig = currentConfig.get(); // Snapshot of the pointer // We don't modify oldConfig; we create a whole new one! } while (!currentConfig.compareAndSet(oldConfig, newConfig)); System.out.println("Config updated to: " + newVersion); } } class Config { final String version; Config(String v) { this.version = v; } } Explanation: ...

1. The “Why” In an e-commerce platform, the “Inventory Count” is the most contested variable. The Problem with Locks: If 10,000 users try to buy an item, synchronized puts 9,999 threads to sleep while 1 thread works. The overhead of waking them all up is higher than the actual work of subtracting 1 from the inventory. The Atomic Solution: AtomicInteger uses the CPU’s native ability to “reserve” a memory address for a nanosecond, update it, and release it without ever suspending a thread. 2. Comparison: Synchronized vs. AtomicInteger Feature synchronized int AtomicInteger Mechanism Blocking (Pessimistic). Lock-Free (Optimistic CAS). Thread State Threads become BLOCKED. Threads stay RUNNABLE (Spinning). Performance High contention = slow. High contention = fast (until CPU saturation). Operations Manual count++ (3 steps). Atomic decrementAndGet() (1 step). 3. The “Golden” Snippet: High-Traffic Inventory This example simulates a flash sale where multiple threads attempt to decrease stock. It ensures we never sell more items than we have (Overselling) without using a single synchronized block. ...

1. The “Why” If you want to update a complex object (like a User profile or a Node in a list) across multiple threads, you usually have to lock the entire object. AtomicReference allows you to swap an entire object reference atomically. It says: “Only change the pointer from Object A to Object B if the pointer is still pointing at Object A.” 2. Comparison: Synchronized Object vs. AtomicReference Feature synchronized (obj) AtomicReference<T> Safety Prevents multiple threads from entering. Prevents “stale” updates via CAS. Blocking Yes (Threads sleep). No (Threads “spin” and retry). Granularity Locks the whole block of code. Only protects the reference (the pointer). Performance High overhead for small updates. Extremely fast for “pointer swapping.” 3. The “Golden” Snippet: A Lock-Free Stack A standard Stack uses synchronized on push and pop. In this high-performance version, we use AtomicReference to manage the “Head” of the stack without any locks. ...

1. The “Why” Traditional locks (synchronized, ReentrantLock) have major downsides: Deadlocks: Threads waiting for each other forever. Priority Inversion: A low-priority thread holding a lock prevents a high-priority thread from running. Performance Overhead: Suspending and resuming a thread (context switching) is expensive for the OS. Lock-Free operations use hardware-level atomic instructions to ensure that at least one thread always makes progress, even if others are interrupted or fail. 2. Comparison: Blocking vs. Lock-Free (Non-Blocking) Feature Blocking (Locks) Lock-Free (Non-Blocking) Philosophy “Pessimistic” - Assume trouble and lock the door. “Optimistic” - Assume success and retry if failed. Hardware Tool Mutex / Monitors. CAS (Compare-And-Swap) instructions. Deadlock Risk High. Zero. Throughput Limited by lock contention. High (Scales better with more CPU cores). Complexity Simple to write and reason about. Extremely difficult to design correctly. 3. The “Golden” Snippet: Atomic Compare-And-Swap (CAS) The heart of every lock-free algorithm is the CAS operation. It is a single CPU instruction that says: “If the value in memory is X, change it to Y. If it’s not X anymore, don’t do anything and tell me I failed.” ...