Complete Multithreading & Concurrency Guide

Complete Multithreading & Concurrency Guide.mdx

Complete Multithreading & Concurrency Guide

Table of Contents

1. Process vs Thread
2. Thread Lifecycle
3. Creating Threads
4. Synchronization Basics
5. Locks vs Synchronized
6. Deadlock
7. wait(), notify(), notifyAll()
8. volatile Keyword
9. Atomic Variables
10. Thread Pools & Executors
11. Producer-Consumer Problem
12. Mutex vs Semaphore
13. Monitor
14. Thread Safety Techniques
15. Concurrent Collections
16. Happens-Before Relationship
17. Common Interview Questions

---

Process vs Thread

Process

• Own memory space (separate heap, stack, code segment)
• Heavyweight - slow context switching (requires OS intervention)
• IPC required for communication (pipes, sockets, shared memory)
• Isolation - crash in one process doesn't affect others
• Resource intensive - more memory overhead

Thread

• Shares heap with other threads in the same process
• Own stack & program counter (registers)
• Lightweight - fast context switching
• Direct communication through shared memory
• Efficient - lower memory overhead

Interview Line: "Threads improve throughput by sharing memory within a process, but require synchronization mechanisms to avoid race conditions and ensure data consistency."

Use Cases:

• Processes: Isolation needed (browsers use separate processes per tab)
• Threads: Performance-critical, frequent communication (web servers handling requests)

---

Thread Lifecycle

States

NEW → RUNNABLE → RUNNING → BLOCKED/WAITING/TIMED_WAITING → TERMINATED

1. NEW - Thread created but not started
2. RUNNABLE - Ready to run, waiting for CPU
3. RUNNING - Currently executing
4. BLOCKED - Waiting for monitor lock
5. WAITING - Waiting indefinitely for another thread
6. TIMED_WAITING - Waiting for specified time
7. TERMINATED - Execution completed

Key Differences

Method	State	Releases Lock?
sleep()	TIMED_WAITING	❌ NO
wait()	WAITING	✅ YES
join()	WAITING	✅ YES
yield()	RUNNABLE	N/A

⚠️ Trap: sleep() does NOT release locks, wait() does!

---

Creating Threads

1. Extend Thread (Not Recommended)

class MyThread extends Thread {
    public void run() {
        System.out.println("Thread running");
    }
}
// Usage
new MyThread().start();

2. Implement Runnable ✅ Preferred

class MyTask implements Runnable {
    public void run() {
        System.out.println("Task running");
    }
}
// Usage
new Thread(new MyTask()).start();

3. Callable + Future

Callable<Integer> task = () -> {
    return 42;
};
ExecutorService executor = Executors.newSingleThreadExecutor();
Future<Integer> future = executor.submit(task);
Integer result = future.get(); // blocking

4. Executors (Real-World) ⭐

ExecutorService executor = Executors.newFixedThreadPool(10);
executor.submit(() -> {
    // task logic
});
executor.shutdown();

Why Runnable > Thread:

• Allows class to extend other classes
• Separation of task logic from execution
• Better OOP design
• Compatible with thread pools

---

Synchronization Basics

Why Needed?

1. Race Conditions - Multiple threads accessing shared data
2. Visibility Issues - Changes not visible across threads
3. Atomicity - Operations not atomic by default

synchronized Keyword

// Method level
public synchronized void increment() {
    count++;
}

// Block level
synchronized(lock) {
    // critical section
    count++;
}

What it does:

• Provides mutual exclusion (one thread at a time)
• Establishes happens-before relationship
• Ensures visibility of changes

⚠️ Traps:

• Don't synchronize on mutable objects (String, Integer)
• Avoid synchronizing on this in public APIs
• Excessive synchronization kills performance

---

Locks vs Synchronized

synchronized

• Implicit lock acquisition/release
• Automatic release on exception
• Simple to use
• Block-scoped only

ReentrantLock

ReentrantLock lock = new ReentrantLock();

lock.lock();
try {
    // critical section
} finally {
    lock.unlock(); // must be in finally
}

Advanced Features:

// Try-lock with timeout
if (lock.tryLock(1, TimeUnit.SECONDS)) {
    try {
        // critical section
    } finally {
        lock.unlock();
    }
}

// Fairness
ReentrantLock fairLock = new ReentrantLock(true);

// Check if held
lock.isHeldByCurrentThread();

// Interruptible
lock.lockInterruptibly();

Feature	synchronized	ReentrantLock
Try-lock	❌	✅
Timeout	❌	✅
Fairness	❌	✅
Interruptible	❌	✅
Complexity	Simple	More control

Interview Line: "ReentrantLock offers more flexibility than synchronized but requires explicit unlock management. Use synchronized for simple cases, ReentrantLock when you need try-lock, timeouts, or fairness."

---

Deadlock

Four Conditions (Coffman Conditions)

All must be present for deadlock:

1. Mutual Exclusion - Resources cannot be shared
2. Hold and Wait - Thread holds resources while waiting for others
3. No Preemption - Resources cannot be forcibly taken
4. Circular Wait - Circular chain of threads waiting for resources

Classic Example

// Thread 1
synchronized(lockA) {
    synchronized(lockB) {
        // work
    }
}

// Thread 2
synchronized(lockB) {
    synchronized(lockA) {
        // work - DEADLOCK!
    }
}

Prevention Strategies

1. Lock Ordering ✅

// Always acquire locks in same order
synchronized(lockA) {
    synchronized(lockB) {
        // safe
    }
}

2. Timeout with tryLock

if (lockA.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
        if (lockB.tryLock(100, TimeUnit.MILLISECONDS)) {
            try {
                // work
            } finally {
                lockB.unlock();
            }
        }
    } finally {
        lockA.unlock();
    }
}

3. Avoid Nested Locks

4. Use Deadlock Detection Tools

• JConsole, VisualVM
• Thread dumps

---

wait(), notify(), notifyAll()

Rules

• Must be called inside synchronized block
• Called on the monitor object
• wait() releases the lock
• notify() does NOT release lock immediately

Usage

synchronized(lock) {
    while (!condition) {
        lock.wait(); // releases lock, waits
    }
    // condition met, proceed
}

synchronized(lock) {
    condition = true;
    lock.notifyAll(); // wakes all waiting threads
}

Method	Releases Lock?	Wakes Threads	Use Case
wait()	✅ YES	N/A	Wait for condition
notify()	Eventually	One thread	Single waiter
notifyAll()	Eventually	All threads	Multiple waiters

⚠️ Traps:

• Always use while loop, not if (spurious wakeups)
• Prefer notifyAll() over notify() (safer)
• Must own the monitor (be in synchronized block)

---

volatile Keyword

What it Guarantees

✅ Visibility - Changes visible to all threads immediately
✅ Ordering - Prevents instruction reordering
❌ NOT Atomicity - count++ is still unsafe

Usage

private volatile boolean running = true;

// Thread 1
public void stop() {
    running = false; // visible immediately
}

// Thread 2
public void run() {
    while (running) {
        // work
    }
}

When to Use

• Flags and status variables
• Double-checked locking
• Single writer, multiple readers

When NOT to Use

volatile int count = 0;
count++; // NOT thread-safe! (read-modify-write)

Interview Line: "volatile ensures visibility across threads but doesn't provide atomicity. Use it for flags, use AtomicInteger for counters."

---

Atomic Variables

Common Classes

• AtomicInteger, AtomicLong, AtomicBoolean
• AtomicReference
• CAS-based (Compare-And-Swap) - lock-free

Usage

AtomicInteger count = new AtomicInteger(0);

count.incrementAndGet(); // atomic i++
count.getAndIncrement(); // atomic ++i
count.addAndGet(5);      // atomic += 5
count.compareAndSet(10, 20); // CAS

How CAS Works

// Pseudocode
boolean compareAndSet(int expected, int update) {
    if (value == expected) {
        value = update;
        return true;
    }
    return false;
}

⚠️ Trap: Atomic variables are thread-safe individually, but multiple atomic operations together are NOT atomic.

// NOT ATOMIC
if (count.get() == 0) {
    count.incrementAndGet(); // race condition here
}

---

Thread Pools & Executors

Why Thread Pools?

• Avoid thread creation overhead
• Control concurrency (limit threads)
• Prevent resource exhaustion
• Reuse threads

Types

1. FixedThreadPool

ExecutorService executor = Executors.newFixedThreadPool(10);
// Fixed number of threads, unbounded queue

2. CachedThreadPool

ExecutorService executor = Executors.newCachedThreadPool();
// Creates threads as needed, reuses idle threads

3. SingleThreadExecutor

ExecutorService executor = Executors.newSingleThreadExecutor();
// Single worker thread, sequential execution

4. ScheduledThreadPool

ScheduledExecutorService executor = Executors.newScheduledThreadPool(5);
executor.schedule(task, 10, TimeUnit.SECONDS);
executor.scheduleAtFixedRate(task, 0, 1, TimeUnit.SECONDS);

Best Practices

ExecutorService executor = Executors.newFixedThreadPool(10);
try {
    for (int i = 0; i < 100; i++) {
        executor.submit(() -> {
            // task
        });
    }
} finally {
    executor.shutdown();
    executor.awaitTermination(1, TimeUnit.MINUTES);
}

Interview Line: "Thread pools decouple task submission from execution strategy, providing better resource management and scalability."

Thread Pool Sizing

CPU-bound: threads = CPU cores + 1
I/O-bound: threads = CPU cores * (1 + wait/compute ratio)

---

Producer-Consumer Problem

Problem Statement

Producers create data, consumers process it. Need synchronization to prevent:

• Producers overwriting data
• Consumers processing same data twice
• Buffer overflow/underflow

Solution 1: wait/notify

class Buffer {
    private Queue<Integer> queue = new LinkedList<>();
    private int capacity;

    public synchronized void produce(int item) throws InterruptedException {
        while (queue.size() == capacity) {
            wait(); // buffer full
        }
        queue.add(item);
        notifyAll(); // wake consumers
    }

    public synchronized int consume() throws InterruptedException {
        while (queue.isEmpty()) {
            wait(); // buffer empty
        }
        int item = queue.remove();
        notifyAll(); // wake producers
        return item;
    }
}

Solution 2: BlockingQueue ✅ Preferred

BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);

// Producer
queue.put(item); // blocks if full

// Consumer
int item = queue.take(); // blocks if empty

BlockingQueue Implementations:

• ArrayBlockingQueue - bounded, array-based
• LinkedBlockingQueue - optionally bounded, linked-node
• PriorityBlockingQueue - unbounded, priority-ordered
• SynchronousQueue - no capacity, direct handoff

---

Mutex vs Semaphore

Mutex (Mutual Exclusion)

• Binary lock (locked/unlocked)
• Ownership - same thread must acquire and release
• Purpose: Protect critical section

ReentrantLock mutex = new ReentrantLock();
mutex.lock();
try {
    // critical section
} finally {
    mutex.unlock();
}

Semaphore

• Counter-based (n permits)
• No ownership - any thread can release
• Purpose: Control access to resource pool

Semaphore semaphore = new Semaphore(3); // 3 permits

semaphore.acquire(); // decrements counter
try {
    // access resource
} finally {
    semaphore.release(); // increments counter
}

Comparison

Feature	Mutex	Semaphore
Type	Binary (0/1)	Counter (0 to n)
Ownership	Required	Not required
Use Case	Critical section	Resource pool
Example	Lock	Connection pool

Binary Semaphore vs Mutex

While binary semaphore (count=1) seems similar to mutex:

• Mutex has ownership semantics
• Semaphore can be released by any thread
• Use mutex for critical sections, semaphore for signaling

Classic Use Case: Limiting Concurrent Access

// Allow max 5 concurrent database connections
Semaphore dbConnections = new Semaphore(5);

public void queryDatabase() throws InterruptedException {
    dbConnections.acquire();
    try {
        // execute query
    } finally {
        dbConnections.release();
    }
}

---

Monitor

What is a Monitor?

A high-level synchronization construct that combines:

• Mutex (mutual exclusion)
• Condition variables (wait/notify)
• Encapsulation of shared data

In Java

Every Java object is a monitor:

• synchronized provides mutex
• wait()/notify() provides condition variables

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

    // Monitor: encapsulates data + synchronization
    public synchronized void put(int item) throws InterruptedException {
        while (queue.size() == capacity) {
            wait(); // condition: not full
        }
        queue.add(item);
        notifyAll();
    }

    public synchronized int get() throws InterruptedException {
        while (queue.isEmpty()) {
            wait(); // condition: not empty
        }
        int item = queue.remove();
        notifyAll();
        return item;
    }
}

Monitor vs Mutex

• Mutex: Low-level lock
• Monitor: High-level construct (mutex + condition variables + data)

---

Thread Safety Techniques

1. Immutability ⭐ Best

public final class ImmutablePoint {
    private final int x;
    private final int y;
    
    public ImmutablePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
    // No setters, thread-safe by design
}

2. Synchronization

public synchronized void increment() {
    count++;
}

3. Thread Confinement

// Each thread has own instance
ThreadLocal<SimpleDateFormat> formatter = ThreadLocal.withInitial(
    () -> new SimpleDateFormat("yyyy-MM-dd")
);

4. Atomic Variables

AtomicInteger count = new AtomicInteger();

5. Concurrent Collections

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

6. Copy-on-Write

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

Best Practice: Prefer immutability > thread confinement > concurrent collections > synchronization

---

Concurrent Collections

ConcurrentHashMap

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

map.put("key", 1);
map.putIfAbsent("key", 2); // atomic
map.compute("key", (k, v) -> v == null ? 1 : v + 1); // atomic

How it works:

• Segmented locking (pre-Java 8)
• CAS + synchronized (Java 8+)
• Fine-grained locking for better concurrency

⚠️ Trap: Iterators are weakly consistent (may not reflect recent updates)

CopyOnWriteArrayList

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

When to use: Read-heavy, write-rare scenarios

• Writes: Create copy of array (expensive)
• Reads: Lock-free, very fast

BlockingQueue

BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(100);

queue.put(item);    // blocks if full
queue.take();       // blocks if empty
queue.offer(item);  // non-blocking, returns false if full
queue.poll();       // non-blocking, returns null if empty

Collections.synchronizedXxx

List<String> list = Collections.synchronizedList(new ArrayList<>());

// Still need external synchronization for compound operations
synchronized(list) {
    if (list.isEmpty()) {
        list.add("item");
    }
}

⚠️ Performance: Much slower than concurrent collections

---

Happens-Before Relationship

Definition

Action A happens-before action B means:

• Memory writes by A are visible to B
• A is ordered before B

Key Rules

1. Program Order: Within a thread, statement 1 happens-before statement 2
2. Monitor Lock: Unlock happens-before subsequent lock on same monitor
3. volatile: Write to volatile happens-before read of that volatile
4. Thread Start: thread.start() happens-before any action in that thread
5. Thread Join: Actions in thread happen-before thread.join() returns
6. Transitivity: If A → B and B → C, then A → C

Example: Why volatile Works

// Thread 1
x = 42;          // 1
volatile flag = true;  // 2

// Thread 2
if (flag) {      // 3
    int y = x;   // 4 - sees x = 42
}

Happens-before chain: 1 → 2 → 3 → 4

Why This Matters

Explains visibility bugs:

// Without volatile
boolean ready = false;
int value = 0;

// Thread 1
value = 42;
ready = true;  // may be reordered before value = 42

// Thread 2
if (ready) {
    System.out.println(value); // may print 0!
}

---

Common Interview Questions

1. sleep() vs wait()

Aspect	sleep()	wait()
Class	Thread	Object
Lock	Doesn't release	Releases lock
Wake	After time	notify()/notifyAll()
Use	Pause execution	Condition waiting

2. How does volatile work internally?

• Prevents CPU caching of variable
• Flush writes to main memory immediately
• Read from main memory (not cache)
• Memory barrier prevents reordering

3. How to make a class thread-safe?

1. Make it immutable
2. Use synchronized methods/blocks
3. Use concurrent collections
4. Use atomic variables
5. Use thread confinement (ThreadLocal)

4. Why notifyAll() over notify()?

• notify() wakes random thread (may wake wrong one)
• notifyAll() wakes all (they compete for lock)
• Safer: avoids missed signals

5. How does ConcurrentHashMap work?

Java 8+:

• CAS for most operations
• Synchronized for conflicts
• Tree bins for hash collisions (> 8 elements)
• No segment locking

6. Thread pool sizing?

• CPU-bound: cores + 1
• I/O-bound: cores × (1 + wait/compute)
• Mixed: Benchmark and tune

7. What is a race condition?

Multiple threads access shared data concurrently, and outcome depends on timing/interleaving of operations.

// Race condition
if (count == 0) {
    count++; // another thread may increment here
}

8. What is thread starvation?

Thread unable to gain regular access to shared resources (lower priority, unfair scheduling).

9. What is livelock?

Threads actively respond to each other but make no progress (both keep yielding to the other).

10. synchronized method vs block?

• Method: Locks entire object (this)
• Block: Can lock specific object, finer granularity

---

Quick One-Liners for Interviews

1. "Thread safety is about correctness, not performance"
2. "Concurrency bugs are non-deterministic and hard to reproduce"
3. "Synchronization is about memory visibility, not just mutual exclusion"
4. "Prefer immutability > thread confinement > synchronization"
5. "Always use thread pools in production, never create threads manually"
6. "Deadlock requires all four Coffman conditions simultaneously"
7. "volatile ensures visibility, AtomicInteger ensures atomicity"
8. "wait() must be in a while loop, not if, due to spurious wakeups"

---

When to Avoid Multithreading

• More threads than CPU cores without I/O
• Excessive locking (worse than single-threaded)
• Simple logic where overhead > benefit
• I/O-bound misuse (use async I/O instead)
• Debugging nightmare for marginal gains

---

Summary Cheat Sheet

Concept	Key Takeaway
Thread	Lightweight, shares memory
synchronized	Simple mutual exclusion
ReentrantLock	Advanced features (try-lock, fairness)
volatile	Visibility, not atomicity
Atomic	Lock-free atomicity
wait/notify	Inter-thread communication
Deadlock	Lock ordering prevents it
Thread Pool	Production-ready concurrency
Semaphore	Resource pool control
Monitor	Mutex + condition variables
Happens-Before	Memory visibility guarantee

---

This guide covers the essential multithreading concepts for interviews and real-world development. Practice implementing these patterns and understand the tradeoffs between different approaches.