HW-09-Advanced-Multithreading/Answers.md

Question 1 — What are Atomic Variables?

Atomic variables are special variables that support indivisible (atomic) read-modify-write operations. "Atomic" means the operation completes as a single, uninterruptible unit — no thread can observe the variable in a partially-updated intermediate state.

Difference from Ordinary Variables

With a regular int, an operation like counter++ is actually three steps:

1. Read the current value
2. Increment it
3. Write it back

Between any two of those steps, another thread can jump in and read or write the same variable — causing a race condition and a lost update.

With an AtomicInteger, the entire increment is a single hardware-level operation (typically a CPU CAS — Compare-And-Swap instruction), making it thread-safe without needing a synchronized block or a lock.

---

Question 2 — Four Classes from java.util.concurrent.atomic

Class	What it wraps
AtomicInteger	int
AtomicLong	long
AtomicBoolean	boolean
AtomicReference<V>	Any object reference

Typical Use Case — AtomicLong as a Transaction ID Generator

In a banking system, every new transaction needs a unique, incrementing ID, and multiple threads generate transactions concurrently.

AtomicLong transactionId = new AtomicLong(0);

// Each thread calls:
long myId = transactionId.getAndIncrement();

getAndIncrement() atomically returns the current value and increments it. No two threads ever receive the same ID, and no synchronized block is needed.

---

Question 3 — Locks vs. Atomic Variables

	Atomic Variables	Locks
Mechanism	Hardware CAS (non-blocking)	OS-level mutex (blocking)
Overhead	Very low	Higher (thread suspension/waking)
Scope	Single variable	Arbitrary code region
Composability	Hard to compose multiple atomics safely	Easy — lock covers multiple statements
Blocking	Never blocks (spin/retry on failure)	Blocks waiting threads

Use Atomic Variables when:

• You need to update a single variable (a counter, a flag, a reference).
• Contention is low to moderate — CAS retries are cheap.
• You want non-blocking, lock-free progress guarantees.

Use a Lock when:

• You need to atomically update multiple variables together (e.g., deducting from one account and adding to another — exactly the transfer() case in this assignment).
• The critical section involves complex logic spanning multiple steps.
• You need Condition variables for conditional waiting (e.g., wait-for-sufficient-funds).
• You need fairness guarantees (ReentrantLock supports fair ordering; CAS-based atomics do not).

---

Bonus Task — Race Condition Demonstration

import java.util.concurrent.atomic.AtomicInteger;

public class RaceConditionDemo {
    static int normalCounter = 0;
    static AtomicInteger atomicCounter = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        int numThreads = 100;
        int increments = 1000;
        Thread[] threads = new Thread[numThreads];

        for (int i = 0; i < numThreads; i++) {
            threads[i] = new Thread(() -> {
                for (int j = 0; j < increments; j++) {
                    normalCounter++;                 // NOT thread-safe: read-modify-write race
                    atomicCounter.incrementAndGet(); // Thread-safe: single atomic CAS
                }
            });
            threads[i].start();
        }

        for (Thread t : threads) t.join(); // Wait for all threads to finish

        System.out.println("Expected:       " + (numThreads * increments)); // 100,000
        System.out.println("Normal counter: " + normalCounter);             // likely < 100,000
        System.out.println("Atomic counter: " + atomicCounter.get());       // always 100,000
    }
}

Sample Output

Expected:       100000
Normal counter: 94371     ← lost updates due to race condition
Atomic counter: 100000    ← always correct

The normal counter prints a value less than 100,000 because concurrent threads overwrite each other's increments. The AtomicInteger always produces the correct result because incrementAndGet() is a single indivisible CPU-level operation.

---

Question 4 — Correct but Slow Under High Contention

A program can be completely correct (no race conditions, no lost updates) yet still scale poorly. Three concurrency-related factors that limit scalability even when correctness is guaranteed:

1. Lock Contention

If many threads compete for the same lock, only one proceeds at a time while the rest are blocked and descheduled by the OS. The more threads you add, the longer the queue in front of that lock. Throughput plateaus or even degrades. A single synchronized method on a shared object becomes a serialization bottleneck — the program effectively runs single-threaded through that section regardless of how many cores are available.

2. Amdahl's Law / Sequential Sections

Even a small fraction of code that must run serially severely caps maximum speedup. If 10% of your code is sequential (e.g., a global lock, a single-threaded flush, or a synchronized queue), you can never exceed 10× speedup no matter how many CPU cores you add. The formula is:

Max Speedup = 1 / (sequential_fraction + parallel_fraction / N)

So even 5% sequential code limits you to 20× speedup with infinite threads.

3. False Sharing

Modern CPUs cache memory in cache lines (typically 64 bytes). If two threads write to different variables that happen to reside in the same cache line, the CPU coherence protocol forces those cache lines to be invalidated and transferred between cores on every write — even though the threads are touching logically independent data. This causes massive invisible overhead that manifests as contention without any lock being held.

4. Lock Granularity (bonus factor)

Using one coarse-grained lock (e.g., one lock for the entire bank) serializes all operations. Fine-grained locking (one lock per account) allows truly concurrent independent operations — but requires more careful design to avoid deadlocks. Poor granularity choices can make a correct solution perform no better than a single-threaded one.

---

Question 5 — Why More Threads ≠ More Performance

Adding more threads beyond a certain point hurts rather than helps. The key reasons:

Context Switching

Every time the OS switches the CPU from one thread to another, it must save and restore the entire CPU state (registers, program counter, stack pointer, cache state). With many threads, this overhead grows significantly. If you have more threads than CPU cores, threads spend more time being swapped in and out than doing actual work — a phenomenon called thrashing.

Contention

When multiple threads compete for the same lock or resource, most sit blocked doing nothing productive. Adding more threads just lengthens the queue — it doesn't increase throughput. At high thread counts, the time threads spend waiting can dwarf the time spent working.

Cache Coherence

Modern CPUs maintain per-core caches. When multiple threads on different cores read and write the same memory, the hardware must keep all caches consistent (via protocols like MESI). Each write to a shared variable forces other cores to invalidate their cached copy and fetch the new value from main memory or a neighboring core's cache. This traffic grows with thread count and becomes a bottleneck independent of any locking.

Synchronization Overhead

Every synchronized block, lock.lock() call, or atomic CAS has its own cost — even when there's no contention. With many threads all paying this overhead per operation, the accumulated cost adds up. Operations like volatile writes force memory fences that prevent compiler and CPU reordering, adding latency to every access.

The Combined Effect

Performance follows a curve, not a line:

• Improves as you add threads up to roughly the number of CPU cores (or slightly above for I/O-bound work)
• Then levels off
• Eventually decreases as overhead and contention dominate

This is why thread pool sizing is a tuning exercise, not "more is always better."

---

Question 6 — Why Deadlocks Hide Until Production

Why They Don't Appear During Testing

Deadlocks require a very specific interleaving of threads — for example:

1. Thread 1 acquires lock A
2. Thread 2 acquires lock B
3. Thread 1 tries to acquire lock B → blocks
4. Thread 2 tries to acquire lock A → blocks
5. Both wait forever → deadlock

The OS thread scheduler determines these orderings non-deterministically based on CPU load, OS timeslicing, hardware interrupts, JIT compilation state, and dozens of other factors.

In a typical test environment:

• Fewer threads are running
• The machine is lightly loaded
• Tests complete quickly, reducing the window of opportunity
• The JVM may use different thread scheduling from production hardware

The exact scheduling window that causes deadlock may statistically occur once every millions of operations — trivially missed in a short test run, but inevitable under sustained production load with hundreds of concurrent threads running for hours.

Two Strategies to Expose Deadlocks During Testing

Strategy 1 — Stress Testing with Injected Delays

Deliberately insert Thread.sleep() or Thread.yield() calls inside critical sections, particularly between the first and second lock acquisitions:

void transfer(BankAccount target, long amount) {
    lock.lock();
    try {
        Thread.sleep(1); // <-- inject here during testing to widen the race window
        target.lock.lock();
        try {
            // ... transfer logic
        } finally {
            target.lock.unlock();
        }
    } finally {
        lock.unlock();
    }
}

This artificially widens the window where a context switch can occur, making the "right" (wrong) interleaving far more likely. Tools like jcstress (the Java Concurrency Stress test harness) are designed specifically for this — they systematically vary thread scheduling to expose rare race conditions and deadlocks.

Strategy 2 — High-Concurrency Watchdog Tests

Write a test that launches many threads performing cross-transfers simultaneously (A→B, B→A, A→C, C→A, etc.) under high concurrency and runs them for an extended period. Include a watchdog thread that detects if any thread is stuck for longer than a timeout threshold:

@Test(timeout = 10000)
void testNoDeadlockUnderStress() throws InterruptedException {
    ExecutorService executor = Executors.newFixedThreadPool(50);
    List<Future<?>> futures = new ArrayList<>();

    for (int i = 0; i < 10000; i++) {
        BankAccount from = accounts.get(random.nextInt(accounts.size()));
        BankAccount to   = accounts.get(random.nextInt(accounts.size()));
        futures.add(executor.submit(() -> from.transfer(to, 10)));
    }

    // If deadlock occurs, test times out and fails
    for (Future<?> f : futures) f.get(5, TimeUnit.SECONDS);
    executor.shutdown();
}

If a deadlock exists, the test will time out and fail deterministically — turning a production mystery into a reproducible test failure.