Concurrency & Multithreading: Complete Low-Level Design (LLD) & Systems Engineering Manual

Concurrency and multithreading are foundational pillars of modern, high-throughput software architecture. In low-level design (LLD) and system engineering, mastering execution models, synchronization primitives, thread management, and lock-free data structures is essential for constructing robust, production-grade applications that scale reliably across multi-core processors.

1. Fundamentals of Concurrency: Processes vs. Threads

Core Mental Model & Conceptual Premise

At the operating system level, execution is split into Processes and Threads. A Process is an isolated execution environment created by the OS, possessing its own allocated memory space (heap, stack, data, file descriptors). A Thread, frequently termed a lightweight process, is the smallest unit of CPU execution that resides within a process. Multiple threads under the same process share that process's address space and system resources.

Real-Life Analogy: Baking Cookies

Imagine the overall goal of Baking Cookies as a Process:

Process (Independent Activity): Baking cookies requires gathering ingredients, preparing dough, preheating the oven, and placing trays inside. If your mother bakes cookies entirely by herself, she acts as a single thread performing every step sequentially.
Multithreading (Parallel Collaboration): To speed up the cookie-baking process, your mother (Thread 1), your sister (Thread 2), and you (Thread 3) work together inside the same kitchen (Shared Memory Space). Your mother preheats the oven, your sister mixes the dough, and you place the dough onto the tray. Because you share the same kitchen space, you can coordinate instantly with zero communication overhead.
Multi-Process (Distributed Isolation): If your mother asks a friend living in a different house to bake a portion of the cookies, that friend operates in her own kitchen (Separate Memory Space). Communicating updates requires making phone calls (Inter-Process Communication / Sockets), introducing significant context and coordination overhead.

Architectural Execution Hierarchy

Structure & Concept Flow

Machine (OS Kernel)

+-- Process A (Chrome Browser - Memory Space A)

| |

| +-- Thread 1 (UI Renderer)

| +-- Thread 2 (Network Fetcher)

| +-- Thread 3 (JS Engine)

+-- Process B (Spring Boot Server - Memory Space B)

+-- Thread 1 (Embedded Tomcat Request Handler 1)

+-- Thread 2 (Embedded Tomcat Request Handler 2)

+-- Thread 3 (Background Metrics Flusher)

Process vs. Thread Comparison

Feature / Dimension	Process	Thread
Memory Allocation	Dedicated, isolated virtual memory space.	Shares heap, static data, and code with sibling threads.
Creation Overhead	High (allocates page tables, file descriptors).	Low (allocates only a lightweight call stack & registers).
Context Switching	Expensive (requires invalidating CPU TLB and cache).	Inexpensive (switches execution stack within the same address space).
Communication	Complex (Requires IPC: Sockets, Pipes, Shared Memory).	Direct & Fast (Reads/Writes to shared object references on the Heap).
Fault Isolation	High (If Process A crashes, Process B is unaffected).	Low (An unhandled exception in one thread can crash the entire process).
Primary Use Case	Chrome tabs, isolated microservices, media players.	Asynchronous IO, UI background processing, Web Server Request handling.

2. Thread Creation Models: `Thread`, `Runnable`, and `Callable`

In Java, threads can be instantiated directly or managed abstractions can be executed via interface task contracts.

1. Extending the `Thread` Class (Naive Approach)

Subclassing Thread requires overriding its run() method.

JAVA

class CustomThread extends Thread {
    @Override
    public void run() {
        System.out.println("Thread executing: " + Thread.currentThread().getName());
    }
}

public class Application {
    public static void main(String[] args) {
        CustomThread t1 = new CustomThread();
        CustomThread t2 = new CustomThread();
        t1.start(); // Spawns a new native OS thread and invokes run()
        t2.start();
    }
}

Warning: Never call run() directly instead of start(). Calling run() executes the method synchronously within the caller's thread (e.g., main), without spawning a new execution thread.

2. Implementing the `Runnable` Interface (Idiomatic Approach)

Because Java does not support multiple class inheritance, extending Thread prevents a domain class from inheriting from any other base class. Implementing Runnable decouples the execution task from the thread object.

JAVA

class TaskRunner implements Runnable {
    @Override
    public void run() {
        System.out.println("Task running on: " + Thread.currentThread().getName());
    }
}

public class Application {
    public static void main(String[] args) {
        TaskRunner task = new TaskRunner();
        Thread thread1 = new Thread(task, "Worker-1");
        Thread thread2 = new Thread(task, "Worker-2");
        thread1.start();
        thread2.start();
    }
}

3. The `Callable<V>` Interface & `Future<V>`

The Runnable.run() signature returns void and cannot throw checked exceptions. The Callable<V> interface resolves both limitations by defining a generic call() method:

JAVA

@FunctionalInterface
public interface Callable<V> {
    V call() throws Exception;
}

Exception Handling Context

Checked Exceptions: Exceptions checked at compile time (e.g., IOException, SQLException, InterruptedException). These must be declared in method signatures (throws) or handled inside try-catch blocks.
Unchecked Exceptions: Runtime exceptions derived from RuntimeException (e.g., NullPointerException, ArithmeticException). They do not require explicit declaration.

JAVA

import java.util.concurrent.*;

class ComputeTask implements Callable<Integer> {
    private final int input;
    public ComputeTask(int input) { this.input = input; }

    @Override
    public Integer call() throws Exception {
        if (input < 0) {
            throw new IllegalArgumentException("Input must be positive");
        }
        Thread.sleep(1000); // Simulating computation (Checked Exception thrown cleanly)
        return input * 42;
    }
}

public class CallableExample {
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        ExecutorService executor = Executors.newSingleThreadExecutor();
        Future<Integer> future = executor.submit(new ComputeTask(10));

        System.out.println("Main thread performing non-blocking work...");
        
        // Blocking call to extract the result from Future placeholder
        Integer result = future.get(); 
        System.out.println("Computed Result: " + result);
        
        executor.shutdown();
    }
}

Comparative Synthesis

Contract	Method Signature	Return Type	Checked Exceptions	Primary Execution Mechanism
`Thread`	`public void run()`	`void`	No	Subclassing `Thread` & calling `.start()`.
`Runnable`	`public void run()`	`void`	No	Passed to `Thread` or `ExecutorService.execute()`.
`Callable<V>`	`public V call() throws Exception`	Generic `V`	Yes	Submitted to `ExecutorService.submit()`.

3. Thread Life Cycle & State Transitions

A thread transitions through distinct execution states governed by the JVM and the underlying Operating System Scheduler.

Structure & Concept Flow

+-----------------------------------+

| |

v |

[NEW] ----> [RUNNABLE] <=================> [RUNNING] |

(start) (Scheduled) (Yield/Preempt) (Executions) |

^ | |

| v |

+------- [BLOCKED] <------------+ |

| (Waiting for Lock) |

| |

+--- [WAITING / TIMED_WAITING] -----+

(wait / sleep / join / park)

[TERMINATED]

Detailed State Breakdown

NEW: Instantiated via new Thread(), but start() has not yet been invoked. No underlying OS thread resources are allocated.
RUNNABLE: start() has been called. The thread is ready to run and resides in the runnable queue, waiting for CPU time slicing from the OS scheduler.
RUNNING: The thread is actively executing instructions on a CPU core.
BLOCKED: The thread is paused, waiting to acquire a monitor lock (e.g., entering a synchronized block held by another thread).
WAITING: The thread is waiting indefinitely for another thread to perform a specific action (e.g., via Object.wait(), Thread.join(), or LockSupport.park()).
TIMED_WAITING: The thread is paused for a specified duration (e.g., Thread.sleep(ms), Object.wait(timeout), Thread.join(timeout)).
TERMINATED: Execution has finished completely or aborted due to an unhandled exception.

Deep Dive: `Thread.sleep()` vs. `Object.wait()`

Real-Life Analogy: Hotel Room & Key

Thread.sleep(): You enter a locked hotel room, holding the room key (Lock). You lie down and sleep for 2 hours. While you sleep, you keep the key in your pocket. Nobody else can enter or use the hotel room during those 2 hours.
Object.wait(): You enter a locked hotel room with a key, looking for your missing briefcase. It isn't there. You step outside, leave the key on the reception desk (Release Lock), and take a seat in the waiting area (WAITING State). Other guests can now pick up the key and use the room. When the room service worker delivers your briefcase, they notify you (notify()), allowing you to retrieve the key from the desk and re-enter the room.

Structure & Concept Flow

Thread.sleep(duration):

Current Thread ---> Holds Lock ---> Enters TIMED_WAITING ---> Retains Lock Whole Time ---> Wakes Up

Object.wait():

Current Thread ---> Holds Lock ---> Releases Lock ---> Enters WAITING ---> Awaits notify() ---> Re-acquires Lock

Dimension	`Thread.sleep()`	`Object.wait()`
Origin Class	`java.lang.Thread` (Static Method).	`java.lang.Object` (Instance Method).
Lock Ownership	Retains all acquired monitor locks while sleeping.	Releases the monitor lock on the object it was invoked on.
Context Requirement	Can be invoked anywhere in standard code.	Must be invoked inside a `synchronized` block/method.
Awakening Trigger	Automatically wakes up when the duration elapses or upon interrupt.	Requires another thread to invoke `notify()` or `notifyAll()` on the same object.

4. Thread Communication: Condition Queues (`wait()`, `notify()`, `notifyAll()`)

Threads operating on shared memory coordinate state changes using Condition Queues attached to monitor objects.

Inter-Thread Signaling Mechanics

wait(): Causes the current thread to release its monitor lock and wait until another thread invokes notify() or notifyAll() on the same object monitor.
notify(): Wakes up a single thread arbitrarily chosen from the set of threads waiting on the object's monitor.
notifyAll(): Wakes up all threads waiting on the object's monitor. All awakened threads then compete to re-acquire the lock before continuing execution.

Real-Life Analogy: Restaurant Chef & Waiter

A Waiter Thread arrives at the pickup counter. If no cooked dish is available on the counter, the waiter cannot serve customers and enters a waiting state (wait()), relinquishing control of the counter. When a Chef Thread finishes cooking a meal, the chef places the food on the counter and rings the order bell (notify()). The bell signals the waiting waiter thread that food is ready, prompting the waiter to pick up the dish and deliver it.

Structure & Concept Flow

[Waiter Thread] [Chef Thread]

| |

Acquires Counter Lock Acquires Counter Lock

| |

Check: Food Available? (No) |

| |

Calls wait() |

(Releases Lock & Sleeps) |

| Prepares Food

| |

| Places Food on Counter

| |

| Calls notify()

| (Signals Waiting Threads)

| |

| Releases Counter Lock

| |

Awakened by notify() <--------------------------+

Re-acquires Lock

Picks up Food & Releases Lock

Complete Code Pattern: Classic Producer-Consumer Buffer

JAVA

import java.util.LinkedList;
import java.util.Queue;

public class BoundedBuffer {
    private final Queue<Integer> buffer = new LinkedList<>();
    private final int capacity;

    public BoundedBuffer(int capacity) {
        this.capacity = capacity;
    }

    public synchronized void produce(int item) throws InterruptedException {
        // ALWAYS check wait conditions inside a WHILE loop to guard against spurious wakeups
        while (buffer.size() == capacity) {
            System.out.println("Buffer FULL. Producer thread waiting...");
            wait(); // Releases lock and enters WAITING state
        }
        buffer.add(item);
        System.out.println("Produced: " + item);
        notifyAll(); // Wakes up consumer threads waiting on buffer space
    }

    public synchronized int consume() throws InterruptedException {
        while (buffer.isEmpty()) {
            System.out.println("Buffer EMPTY. Consumer thread waiting...");
            wait(); // Releases lock and enters WAITING state
        }
        int item = buffer.remove();
        System.out.println("Consumed: " + item);
        notifyAll(); // Wakes up producer threads waiting on empty slots
        return item;
    }
}

Crucial Rule: Always test the wait() condition inside a while loop, never an if statement. This guards against spurious wakeups, where a thread wakes up from a waiting state without receiving an explicit notification.

5. Thread Pools & The Executors Framework

Creating raw OS threads (new Thread()) for every incoming task introduces serious architectural drawbacks:

Creation/Teardown Costs: Allocating stack memory ( $512\text{ KB} - 1\text{ MB}$ per thread) and making system calls for thread creation is computationally expensive.
Resource Exhaustion: Creating thousands of raw threads can consume all available system RAM, triggering java.lang.OutOfMemoryError: unable to create new native thread.
Excessive Context Switching: When active threads significantly outnumber physical CPU cores, the OS spends more CPU cycles switching context between threads than executing application code.

The `ThreadPoolExecutor` Architecture

A thread pool addresses these issues by decoupling task submission from execution, reusing a bounded set of pre-allocated worker threads.

Structure & Concept Flow

Submitted Task

[Core Pool Available?] ----YES----> [Spawn Core Thread & Run Task]

[Work Queue Full?] ---------NO-----> [Enqueue Task in Blocking Queue]

NO (Queue is Full)

[Max Pool Reached?] --------NO-----> [Spawn Non-Core Worker Thread]

YES

[Trigger Rejection Handler Policy]

Core Components of `ThreadPoolExecutor`

JAVA

public ThreadPoolExecutor(
    int corePoolSize,                  // Minimum active threads retained in pool
    int maximumPoolSize,               // Upper bound on threads when queue overflows
    long keepAliveTime,                // Idle duration before non-core threads terminate
    TimeUnit unit,                     // Time unit for keepAliveTime
    BlockingQueue<Runnable> workQueue, // Buffer for pending tasks
    ThreadFactory threadFactory,       // Custom factory for naming/configuring threads
    RejectedExecutionHandler handler   // Strategy when queue & threads are saturated
);

Common Rejection Policies

AbortPolicy (Default): Throws RejectedExecutionException.
CallerRunsPolicy: Executes the rejected task synchronously on the thread that submitted it (providing natural backpressure).
DiscardPolicy: Silently drops the rejected task without throwing an exception.
DiscardOldestPolicy: Drops the oldest unhandled task at the head of the queue, then retries submission.

Built-In Executor Factory Strategies

JAVA

// 1. Fixed Thread Pool: Fixed number of reusable worker threads backed by an Unbounded Queue
ExecutorService fixedPool = Executors.newFixedThreadPool(4);

// 2. Cached Thread Pool: Dynamically spawns new threads as needed; reclaims idle threads after 60s
ExecutorService cachedPool = Executors.newCachedThreadPool();

// 3. Single Thread Executor: Exactly 1 worker thread processing tasks sequentially
ExecutorService singleThreador = Executors.newSingleThreadExecutor();

// 4. Scheduled Thread Pool: Supports delayed execution and periodic background job runs
ScheduledExecutorService scheduledPool = Executors.newScheduledThreadPool(2);

Executor Type	Core / Max Threads	Queue Type	Primary System Use Case
`FixedThreadPool`	$N / N$	`LinkedBlockingQueue` (Unbounded)	Predictable, CPU-bound workloads with bounded concurrency needs.
`CachedThreadPool`	$0 / \text{Integer.MAX\_VALUE}$	`SynchronousQueue` (Direct Handoff)	Burst-heavy, short-lived asynchronous IO tasks.
`ScheduledThreadPool`	$N / \text{Integer.MAX\_VALUE}$	`DelayedWorkQueue`	Cron jobs, background cleanup, periodic metric reporting.

Thread Pool Lifecycle Management

Task Submission Mechanisms

execute(Runnable): Submits a task for fire-and-forget execution. Returns void. Any unhandled runtime exception abruptly terminates the executing worker thread.
submit(Callable/Runnable): Submits a value-returning task and returns a Future<T> tracking execution. Any task exception is captured and re-thrown wrapped inside ExecutionException when Future.get() is invoked.

Shutdown Mechanisms

shutdown(): Initiates a graceful shutdown. Rejects new task submissions, but allows previously submitted tasks in the work queue to finish executing.
shutdownNow(): Attempts an immediate, forceful shutdown. Sends Thread.interrupt() signals to running worker threads, drains the pending queue, and returns a list of unexecuted Runnable tasks (List<Runnable>).

JAVA

public void gracefulShutdown(ExecutorService executor) {
    executor.shutdown(); // Stop accepting new tasks
    try {
        if (!executor.awaitTermination(60, TimeUnit.SECONDS)) {
            executor.shutdownNow(); // Cancel currently executing tasks
            if (!executor.awaitTermination(60, TimeUnit.SECONDS)) {
                System.err.println("Thread pool did not terminate!");
            }
        }
    } catch (InterruptedException ie) {
        executor.shutdownNow();
        Thread.currentThread().interrupt();
    }
}

6. Synchronization Primitives: `synchronized`, `volatile`, and Atomic Variables

In multithreaded systems, unsafe operations on shared data cause Data Race Conditions and Memory Visibility Issues.

Structure & Concept Flow

[Thread A Memory Cache] [Thread B Memory Cache]

Count = 1 (Local) Count = 0 (Local)

| |

v v

[RAM / Main Memory: Shared Variable Count = 0 (Stale Data Issue)]

1. The `synchronized` Keyword

synchronized guarantees both Mutual Exclusion (only one thread executes the block at a time) and Visibility (flushes local CPU cache updates to main RAM upon releasing the monitor lock).

A. Synchronized Method (Locks on Object Instance `this` or `Class` object)

JAVA

public class Counter {
    private int count = 0;

    // Locks execution on the 'this' instance
    public synchronized void increment() {
        count++;
    }

    // Locks execution on the static Counter.class object
    public static synchronized void globalReset() {
        // Class-level thread safety
    }
}

B. Synchronized Block (Fine-Grained Locking)

Synchronizing entire methods reduces concurrency. Prefer synchronizing only the critical section using a dedicated monitor object lock:

JAVA

public class GranularCounter {
    private int count = 0;
    private final Object lock = new Object(); // Explicit internal monitor lock

    public void increment() {
        // Non-critical operations execute concurrently without blocking
        doNonCriticalWork();

        synchronized (lock) { // Critical section bounded strictly
            count++;
        }
    }
}

2. The `volatile` Keyword

The volatile modifier ensures Memory Visibility without enforcing mutual exclusion or locking.

JAVA

public class WorkerFlag implements Runnable {
    // Forces threads to read/write directly to Main RAM instead of CPU local cache
    private volatile boolean running = true;

    public void stopWorker() {
        this.running = false; // Writes immediately flush to Main RAM
    }

    @Override
    public void run() {
        while (running) { // Always reads fresh status from Main RAM
            // Execute task loop
        }
        System.out.println("Worker stopped cleanly.");
    }
}

Key Rule: volatile guarantees visibility, but it does not guarantee atomicity. Operations like count++ are read-modify-write sequences consisting of three separate instructions. Marking int count as volatile will not prevent race conditions during concurrent increments.

3. Lock-Free Atomic Variables (Compare-And-Swap / CAS)

To perform atomic updates on shared counters or flags without lock contention overhead, Java provides atomic wrapper classes (AtomicInteger, AtomicLong, AtomicReference). These rely on CPU hardware primitives like Compare-And-Swap (CAS) instructions.

Structure & Concept Flow

CAS Execution Flow (AtomicInteger):

Current Read Value = 5

Target Update Value = 6

Execute Hardware Instruction CAS(Expected: 5, New: 6)

+-- Matches Memory Value (5)? --> Write 6 -> Return Success

+-- Modified by Thread B (Now 7)? -> Fail CAS -> Loop & Retry

JAVA

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicCounter {
    private final AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        // Lock-free atomic increment backed by hardware CAS loops
        count.incrementAndGet(); 
    }

    public int getValue() {
        return count.get();
    }
}

Synchronization Strategy Comparison

Strategy	Mutual Exclusion	Memory Visibility	Lock-Free	Concurrency Performance
`synchronized`	Yes	Yes	No	Low to Medium under high contention.
`volatile`	No	Yes	Yes	Extremely High (Read heavy/Single Writer).
`AtomicInteger` (CAS)	Yes (for single variable)	Yes	Yes	High (Optimistic retry under low/medium contention).

7. Advanced Explicit Locks: `ReentrantLock` & `ReadWriteLock`

While intrinsic synchronized blocks are simple, explicit locks from the java.util.concurrent.locks package offer finer control:

Ability to attempt non-blocking lock acquisition (tryLock()).
Timed lock attempts (tryLock(timeout, unit)).
Interruptible lock acquisition (lockInterruptibly()).
Support for Fair vs. Non-Fair lock ordering.

1. `ReentrantLock`

A thread holding a ReentrantLock can acquire the same lock multiple times without self-deadlocking. Unlocking must match locking counts explicitly.

JAVA

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class ExplicitLockCounter {
    private int count = 0;
    // Pass true for Fair Scheduling (FIFO), false for default Non-Fair (Higher Performance)
    private final Lock lock = new ReentrantLock(true); 

    public void increment() {
        lock.lock(); // Explicit Lock Acquisition
        try {
            count++; // Critical Section
        } finally {
            // ALWAYS unlock inside a finally block to prevent permanent deadlocks on exception
            lock.unlock(); 
        }
    }

    public boolean tryIncrement() {
        if (lock.tryLock()) { // Non-blocking attempt
            try {
                count++;
                return true;
            } finally {
                lock.unlock();
            }
        }
        return false; // Lock was held by another thread; return immediately without waiting
    }
}

2. `ReentrantReadWriteLock`

Most applications perform far more reads than writes. Standard mutual exclusion locks force reader threads to execute sequentially, which hampers read-heavy workloads. A ReadWriteLock allows multiple threads to read concurrently, while restricting writers to exclusive access.

Structure & Concept Flow

Concurrent Read-Write Lock Rules:

Multiple Readers <---> Allowed Concurrent Access

Reader + Writer <---> Mutually Exclusive (Writer blocks Readers)

Writer + Writer <---> Mutually Exclusive (Writer blocks Writers)

JAVA

import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class ReadWriteCache {
    private String data = "Initial State";
    private final ReadWriteLock rwLock = new ReentrantReadWriteLock();

    public String readData() {
        rwLock.readLock().lock(); // Multiple threads can acquire the readLock simultaneously
        try {
            return data;
        } finally {
            rwLock.readLock().unlock();
        }
    }

    public void writeData(String newData) {
        rwLock.writeLock().lock(); // Requires exclusive access; blocks all readers & writers
        try {
            this.data = newData;
        } finally {
            rwLock.writeLock().unlock();
        }
    }
}

8. Resource Control via Semaphores & Custom Barriers

1. `Semaphore`

A Semaphore manages a fixed set of virtual permits. Threads call acquire() to claim a permit and release() to return it. If no permits are available, acquire() blocks until one is returned.

Real-Life Analogy: Concert Tickets

Imagine a concert venue with a strict maximum capacity of 3 guest tickets (Permits). Eight fans (Threads) are standing in line. The first 3 fans receive tickets (acquire()) and enter the venue. The remaining 5 fans must wait outside. As soon as one fan leaves the venue and returns their ticket (release()), the ticket is immediately granted to the next fan waiting in line.

Structure & Concept Flow

Permit Pool: [P1] [P2] [P3] (3 Total Permits)

Threads T1-T8 Request Entry:

T1 acquires P1 ---> Granted

T2 acquires P2 ---> Granted

T3 acquires P3 ---> Granted

T4 acquires ---> No permits available! T4 BLOCKS

...

T1 finishes & releases P1 ---> T4 unblocks and acquires P1

JAVA

import java.util.concurrent.Semaphore;

public class LimitedResourcePool {
    // Allow a maximum of 3 concurrent worker threads inside the critical section
    private final Semaphore semaphore = new Semaphore(3);

    public void accessResource() {
        try {
            semaphore.acquire(); // Decrements permit count; blocks if count == 0
            System.out.println(Thread.currentThread().getName() + " acquired access.");
            Thread.sleep(1000); // Accessing throttled physical resource (e.g., Database Connection)
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            System.out.println(Thread.currentThread().getName() + " releasing access.");
            semaphore.release(); // Increments permit count; unblocks a waiting thread
        }
    }
}

2. Advanced Pattern: Custom Thread Barrier via Semaphores

A Barrier forces a set of parallel threads to wait for each other at a designated point before any are allowed to proceed.

Real-Life Analogy: The Hero Philosopher at the Barrier

Imagine five threads executing a multi-stage process. None of the threads are allowed to begin Phase 2 until all 5 threads complete Phase 1. The first 4 threads finish Phase 1 and wait at the barrier (acquire()). The 5th thread (the "hero" thread) completes Phase 1, notices it is the final thread required to cross the barrier, and calls release(4) to release permits for the other 4 waiting threads.

JAVA

import java.util.concurrent.Semaphore;

public class CustomThreadBarrier {
    private final int totalThreads;
    private int count;
    private final Semaphore mutex = new Semaphore(1);     // Guards state updates
    private final Semaphore barrier = new Semaphore(0);   // Blocks arrival threads

    public CustomThreadBarrier(int totalThreads) {
        this.totalThreads = totalThreads;
        this.count = totalThreads;
    }

    public void await() throws InterruptedException {
        mutex.acquire();
        count--;
        if (count == 0) { // The final "Hero" thread has arrived
            mutex.release();
            barrier.release(totalThreads - 1); // Unblocks all other waiting threads
            count = totalThreads; // Reset barrier state for reuse
        } else {
            mutex.release();
            barrier.acquire(); // Block until the final thread triggers release
        }
    }
}

9. Java Concurrent Collections

Using standard collections wrapped in Collections.synchronizedMap() or Collections.synchronizedList() creates performance bottlenecks because it locks the entire container on every operation. The java.util.concurrent package provides optimized, highly concurrent alternatives.

Key Concurrent Collections Overview

Structure & Concept Flow

Concurrent Collections Engine:

+-- ConcurrentHashMap (Segmented/Bucket Locking + CAS Reads)

+-- CopyOnWriteArrayList (Immutable Copy-on-Write for Reads)

+-- ConcurrentLinkedQueue (Lock-free CAS Node Linking)

+-- ArrayBlockingQueue / LinkedBlockingQueue (Lock-bounded Buffers)

1. `ConcurrentHashMap`

Internal Architecture: Replaces coarse table-level locking with fine-grained bucket-level locking (synchronized on individual bucket head nodes) alongside CAS instructions for node insertion.
Non-Blocking Reads: Read operations (get()) do not acquire locks, allowing high throughput for concurrent reads.
No ConcurrentModificationException: Iterators operate on state safely without throwing modification errors if updates occur mid-traversal.

2. `CopyOnWriteArrayList`

Internal Architecture: Every write operation (add(), set(), remove()) creates a new underlying copy of the array. Reads operate on the existing array without acquiring locks.
Use Case: Excellent for read-heavy, write-rare workloads (e.g., event listener lists, routing tables). Extremely expensive for write-heavy applications due to frequent array allocation overhead.

3. `ConcurrentLinkedQueue`

Internal Architecture: An unbounded, lock-free $O(1)$ queue backed by linked nodes. Uses hardware CAS instructions to adjust head and tail node pointers safely without locks.

4. `BlockingQueue` Implementations

ArrayBlockingQueue: Bounded, array-backed FIFO queue using explicit locks for thread coordination.
LinkedBlockingQueue: Optionally bounded, node-backed queue using separate locks for head insertions and tail removals, enabling concurrent pushes and pulls.

10. Asynchronous Programming: `Future` and `CompletableFuture`

Limitations of `Future<T>`

While Future<T> holds the result of an asynchronous computation, working with it has significant drawbacks:

get() is a blocking call that halts the main thread until computation finishes.
Tasks cannot be chained together (e.g., Run Task A, then pass its output to Task B).
Multiple futures cannot be combined without blocking.
No built-in asynchronous exception recovery mechanisms.

`CompletableFuture<T>` Execution Engine

CompletableFuture solves these limitations by supporting asynchronous callbacks, composition, and non-blocking chaining pipelines.

JAVA

import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;

public class AsyncPipeline {
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        // 1. Asynchronously fetch user data
        CompletableFuture<String> pipeline = CompletableFuture.supplyAsync(() -> {
            simulateWork(500);
            return "User:Alice";
        })
        // 2. Transform result asynchronously (Composition / Chaining)
        .thenApply(userData -> {
            return userData + " | Role:Admin";
        })
        // 3. Combine with another independent async future
        .thenCombine(CompletableFuture.supplyAsync(() -> "Status:Active"), (userRole, status) -> {
            return userRole + " | " + status;
        })
        // 4. Declarative exception handling fallback
        .exceptionally(throwable -> "Fallback Data: Default User");

        // Main thread continues executing without blocking during the pipeline steps
        System.out.println("Pipeline executing asynchronously...");
        
        // Extract ultimate combined value (join() throws Unchecked Exception)
        System.out.println("Final System Output: " + pipeline.join());
    }

    private static void simulateWork(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}

11. Practical LLD & Concurrency Interview Problems

Problem 1: Print Zero Even Odd

Task: Coordinate three threads (Thread A prints 0, Thread B prints even numbers, Thread C prints odd numbers) to generate the sequence 0102030405...N.

Structural Execution Flow

Structure & Concept Flow

[Zero Thread] --- (Prints 0) ---> [Is Next Number Odd or Even?]

| |

(Odd) (Even)

v v

[Odd Thread] [Even Thread]

(Prints 1) (Prints 2)

| |

+------+-------+

[Signals Zero Thread]

JAVA

import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;

class ZeroEvenOdd {
    private final int n;
    private final Semaphore zeroSem = new Semaphore(1); // Starts active
    private final Semaphore evenSem = new Semaphore(0);
    private final Semaphore oddSem = new Semaphore(0);

    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            zeroSem.acquire();
            printNumber.accept(0);
            if (i % 2 != 0) {
                oddSem.release();  // Hand off execution to Odd Thread
            } else {
                evenSem.release(); // Hand off execution to Even Thread
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            evenSem.acquire();
            printNumber.accept(i);
            zeroSem.release(); // Hand off execution back to Zero Thread
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            oddSem.acquire();
            printNumber.accept(i);
            zeroSem.release(); // Hand off execution back to Zero Thread
        }
    }
}

Problem 2: Multithreaded FizzBuzz

Task: Four threads coordinate output up to $N$ .

Thread A calls fizz() if $i \pmod 3 == 0$ and $i \pmod 5 \neq 0$ .
Thread B calls buzz() if $i \pmod 5 == 0$ and $i \pmod 3 \neq 0$ .
Thread C calls fizzbuzz() if $i \pmod{15} == 0$ .
Thread D calls number() if $i$ is not divisible by 3 or 5.

JAVA

import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;

class FizzBuzz {
    private final int n;
    private final Semaphore fizzSem = new Semaphore(0);
    private final Semaphore buzzSem = new Semaphore(0);
    private final Semaphore fizzBuzzSem = new Semaphore(0);
    private final Semaphore numSem = new Semaphore(1); // Drives evaluation pipeline

    public FizzBuzz(int n) {
        this.n = n;
    }

    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 != 0) {
                fizzSem.acquire();
                printFizz.run();
                numSem.release();
            }
        }
    }

    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            if (i % 5 == 0 && i % 3 != 0) {
                buzzSem.acquire();
                printBuzz.run();
                numSem.release();
            }
        }
    }

    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                fizzBuzzSem.acquire();
                printFizzBuzz.run();
                numSem.release();
            }
        }
    }

    public void number(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            numSem.acquire();
            if (i % 15 == 0) {
                fizzBuzzSem.release();
            } else if (i % 3 == 0) {
                fizzSem.release();
            } else if (i % 5 == 0) {
                buzzSem.release();
            } else {
                printNumber.accept(i);
                numSem.release();
            }
        }
    }
}

Problem 3: Design a Bounded Blocking Queue

Task: Implement a thread-safe Bounded Blocking Queue without using built-in Java concurrent queue classes.

JAVA

import java.util.concurrent.Semaphore;
import java.util.concurrent.ConcurrentLinkedDeque;

class BoundedBlockingQueue {
    private final ConcurrentLinkedDeque<Integer> queue = new ConcurrentLinkedDeque<>();
    private final Semaphore emptySlots; // Tracks available capacity for enqueuing
    private final Semaphore fullSlots;  // Tracks available elements for dequeuing

    public BoundedBlockingQueue(int capacity) {
        this.emptySlots = new Semaphore(capacity);
        this.fullSlots = new Semaphore(0);
    }

    public void enqueue(int element) throws InterruptedException {
        emptySlots.acquire(); // Block if queue capacity is fully exhausted
        queue.addLast(element);
        fullSlots.release();  // Signal consumer threads that an item is available
    }

    public int dequeue() throws InterruptedException {
        fullSlots.acquire();  // Block if no items are currently available
        int val = queue.removeFirst();
        emptySlots.release(); // Signal producer threads that capacity is free
        return val;
    }

    public int size() {
        return queue.size();
    }
}

Problem 4: The Dining Philosophers Problem

Task: Five philosophers sit at a round table with 5 single forks. A philosopher needs both adjacent forks to eat. Prevent circular-dependency deadlocks.

Deadlock Prevention Strategy

A circular deadlock happens if all 5 philosophers pick up their left fork simultaneously. To break this dependency:

Limit access to the table to at most $N-1$ (4) philosophers using a counting Semaphore.
Wrap individual fork accesses inside explicit locks (ReentrantLock).

Structure & Concept Flow

Table Capacity Control (Semaphore = 4 Permits)

+--> Philosopher 0 acquires Permit & Fork Locks (Eats safely)

+--> Philosopher 1 acquires Permit & Fork Locks (Eats safely)

+--> Philosopher 2 acquires Permit & Fork Locks (Eats safely)

+--> Philosopher 3 acquires Permit & Fork Locks (Eats safely)

+--> Philosopher 4 BLOCKED at Table Control (Deadlock Mathematically Impossible)

JAVA

import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {
    // Restrict the table to at most N-1 (4) philosophers simultaneously
    private final Semaphore maxDiners = new Semaphore(4);
    private final ReentrantLock[] forks = new ReentrantLock[5];

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new ReentrantLock();
        }
    }

    public void wantsToEat(int philosopher,
                            Runnable pickLeftFork,
                            Runnable pickRightFork,
                            Runnable eat,
                            Runnable putLeftFork,
                            Runnable putRightFork) throws InterruptedException {

        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;

        maxDiners.acquire(); // Limits table access to 4 diners to break circular wait
        
        forks[leftFork].lock();
        forks[rightFork].lock();

        try {
            pickLeftFork.run();
            pickRightFork.run();
            eat.run();
            putLeftFork.run();
            putRightFork.run();
        } finally {
            forks[rightFork].unlock();
            forks[leftFork].unlock();
            maxDiners.release(); // Allow waiting philosophers to enter table
        }
    }
}

Problem 5: Industrial Multithreaded Web Crawler

Task: Given a startUrl and an HtmlParser interface, crawl pages concurrently across multiple worker threads. Only explore links sharing the exact same Hostname as startUrl. Ensure no URL is crawled twice, and shut down gracefully when crawling completes.

JAVA

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

// Provided System Parser Contract Interface
interface HtmlParser {
    List<String> getUrls(String url);
}

public class MultithreadedWebCrawler {
    private final ConcurrentHashMap<String, Boolean> visited = new ConcurrentHashMap<>();
    private final ExecutorService executor = Executors.newFixedThreadPool(8);
    private final AtomicInteger activeTasks = new AtomicInteger(0);

    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        String targetHostName = extractHostName(startUrl);
        
        visited.put(startUrl, true);
        activeTasks.incrementAndGet();
        
        // Dispatch the initial crawling job
        executor.execute(new CrawlTask(startUrl, targetHostName, htmlParser));

        // Await completion: Block main thread while async tasks remain active
        while (activeTasks.get() > 0) {
            try {
                Thread.sleep(20); // Poll active task counts safely
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                break;
            }
        }

        executor.shutdown();
        return new ArrayList<>(visited.keySet());
    }

    private class CrawlTask implements Runnable {
        private final String currentUrl;
        private final String hostName;
        private final HtmlParser parser;

        public CrawlTask(String currentUrl, String hostName, HtmlParser parser) {
            this.currentUrl = currentUrl;
            this.hostName = hostName;
            this.parser = parser;
        }

        @Override
        public void run() {
            try {
                // Blocking network call executing inside worker thread pool
                List<String> extractedUrls = parser.getUrls(currentUrl);

                for (String url : extractedUrls) {
                    if (extractHostName(url).equals(hostName)) {
                        // Atomic CAS-backed check-and-insert using ConcurrentHashMap
                        if (visited.putIfAbsent(url, true) == null) {
                            activeTasks.incrementAndGet();
                            executor.execute(new CrawlTask(url, hostName, parser));
                        }
                    }
                }
            } finally {
                // Decrement active task counter upon completion
                activeTasks.decrementAndGet();
            }
        }
    }

    private String extractHostName(String url) {
        int idx = url.indexOf('/', 7); // Skip 'http://' or 'https://'
        return idx == -1 ? url : url.substring(0, idx);
    }
}

12. Summary and Key Takeaways

Processes vs. Threads: Processes own isolated memory spaces and rely on heavy IPC mechanisms. Threads reside within a single process, sharing the heap for fast communication, but requiring strict synchronization to prevent memory corruption.
Task Contracts: Use Runnable for simple void tasks. Prefer Callable<V> when tasks need to return values or throw checked exceptions. Handle results safely using Future<T> or CompletableFuture<T>.
State Management: Threads transition through NEW, RUNNABLE, RUNNING, BLOCKED, WAITING, TIMED_WAITING, and TERMINATED. Always invoke Object.wait() inside a while loop to guard against spurious wakeups.
Thread.sleep() vs. Object.wait(): sleep() pauses execution while maintaining all acquired locks. wait() surrenders its object monitor lock, allowing other waiting threads to access the critical section.
Resource Optimization with Thread Pools: Never manage raw OS threads directly in production code. Use ThreadPoolExecutor to bound context switching, manage work queues, and define explicit rejection strategies.
Memory Visibility & Atomicity: The volatile keyword guarantees memory visibility across CPU caches, but does not guarantee atomicity. For lock-free atomic updates on individual variables, use hardware CAS-backed atomic wrappers like AtomicInteger.
Fine-Grained Explicit Locking: Prefer ReentrantLock over coarse synchronized methods when you need features like tryLock() timeouts or fair scheduling. Use ReentrantReadWriteLock to increase throughput for read-heavy workloads.
Resource Throttling: Use Semaphore to limit concurrent access to a bounded pool of shared resources (e.g., database connections, rate limiters, or external API callers).
Asynchronous Orchestration: Use CompletableFuture for non-blocking task chaining, combining asynchronous pipelines, and declaring clean fallback exception handlers.

🧵 Concurrency & Multithreading COMPLETE Crash Course | All you need to know for any LLD Rounds ‼️

Concurrency & Multithreading: Complete Low-Level Design (LLD) & Systems Engineering Manual

1. Fundamentals of Concurrency: Processes vs. Threads

Core Mental Model & Conceptual Premise

Real-Life Analogy: Baking Cookies

Architectural Execution Hierarchy

Process vs. Thread Comparison

2. Thread Creation Models: Thread, Runnable, and Callable

1. Extending the Thread Class (Naive Approach)

2. Implementing the Runnable Interface (Idiomatic Approach)

3. The Callable<V> Interface & Future<V>

Exception Handling Context

Comparative Synthesis

3. Thread Life Cycle & State Transitions

Detailed State Breakdown

Deep Dive: Thread.sleep() vs. Object.wait()

Real-Life Analogy: Hotel Room & Key

4. Thread Communication: Condition Queues (wait(), notify(), notifyAll())

Inter-Thread Signaling Mechanics

Real-Life Analogy: Restaurant Chef & Waiter

Complete Code Pattern: Classic Producer-Consumer Buffer

5. Thread Pools & The Executors Framework

The ThreadPoolExecutor Architecture

Core Components of ThreadPoolExecutor

Common Rejection Policies

Built-In Executor Factory Strategies

Thread Pool Lifecycle Management

Task Submission Mechanisms

Shutdown Mechanisms

6. Synchronization Primitives: synchronized, volatile, and Atomic Variables

1. The synchronized Keyword

A. Synchronized Method (Locks on Object Instance this or Class object)

B. Synchronized Block (Fine-Grained Locking)

2. The volatile Keyword

3. Lock-Free Atomic Variables (Compare-And-Swap / CAS)

Synchronization Strategy Comparison

7. Advanced Explicit Locks: ReentrantLock & ReadWriteLock

1. ReentrantLock

2. ReentrantReadWriteLock

8. Resource Control via Semaphores & Custom Barriers

1. Semaphore

Real-Life Analogy: Concert Tickets

2. Advanced Pattern: Custom Thread Barrier via Semaphores

Real-Life Analogy: The Hero Philosopher at the Barrier

9. Java Concurrent Collections

Key Concurrent Collections Overview

1. ConcurrentHashMap

2. CopyOnWriteArrayList

3. ConcurrentLinkedQueue

4. BlockingQueue Implementations

10. Asynchronous Programming: Future and CompletableFuture

Limitations of Future<T>

CompletableFuture<T> Execution Engine

11. Practical LLD & Concurrency Interview Problems

Problem 1: Print Zero Even Odd

Structural Execution Flow

Problem 2: Multithreaded FizzBuzz

Problem 3: Design a Bounded Blocking Queue

Problem 4: The Dining Philosophers Problem

Deadlock Prevention Strategy

Problem 5: Industrial Multithreaded Web Crawler

12. Summary and Key Takeaways

2. Thread Creation Models: `Thread`, `Runnable`, and `Callable`

1. Extending the `Thread` Class (Naive Approach)

2. Implementing the `Runnable` Interface (Idiomatic Approach)

3. The `Callable<V>` Interface & `Future<V>`

Deep Dive: `Thread.sleep()` vs. `Object.wait()`

4. Thread Communication: Condition Queues (`wait()`, `notify()`, `notifyAll()`)

The `ThreadPoolExecutor` Architecture

Core Components of `ThreadPoolExecutor`

6. Synchronization Primitives: `synchronized`, `volatile`, and Atomic Variables

1. The `synchronized` Keyword

A. Synchronized Method (Locks on Object Instance `this` or `Class` object)

2. The `volatile` Keyword

7. Advanced Explicit Locks: `ReentrantLock` & `ReadWriteLock`

1. `ReentrantLock`

2. `ReentrantReadWriteLock`

1. `Semaphore`

1. `ConcurrentHashMap`

2. `CopyOnWriteArrayList`

3. `ConcurrentLinkedQueue`

4. `BlockingQueue` Implementations

10. Asynchronous Programming: `Future` and `CompletableFuture`

Limitations of `Future<T>`

`CompletableFuture<T>` Execution Engine