Concurrency Hazards

Introduction: Concurrency Hazards

Concurrent programming introduces several hazards that can cause systems to fail, perform poorly, or behave unpredictably. Understanding and preventing these hazards is crucial.

Visual: Common Hazards

---

Deadlocks

A deadlock occurs when two or more threads are blocked forever, waiting for each other.

Coffman Conditions (All Must Be Present)

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

Visual: Deadlock Scenario

Example: Deadlock Code

Java

DeadlockExample.java

public class DeadlockExample {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread 1: Holding lock1");
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                synchronized (lock2) {  // Waiting for lock2
                    System.out.println("Thread 1: Holding lock1 and lock2");
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {  // Different order!
                System.out.println("Thread 2: Holding lock2");
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                synchronized (lock1) {  // Waiting for lock1
                    System.out.println("Thread 2: Holding lock1 and lock2");
                }
            }
        });

        thread1.start();
        thread2.start();
        // Both threads will deadlock!
    }
}

Python

deadlock_example.py

import threading
import time

lock1 = threading.Lock()
lock2 = threading.Lock()

def thread1():
    with lock1:
        print("Thread 1: Holding lock1")
        time.sleep(0.1)
        with lock2:  # Waiting for lock2
            print("Thread 1: Holding lock1 and lock2")

def thread2():
    with lock2:  # Different order!
        print("Thread 2: Holding lock2")
        time.sleep(0.1)
        with lock1:  # Waiting for lock1
            print("Thread 2: Holding lock1 and lock2")

threading.Thread(target=thread1).start()
threading.Thread(target=thread2).start()
# Both threads will deadlock!

Prevention: Lock Ordering

Solution: Always acquire locks in the same order everywhere!

Java

DeadlockPrevention.java

public class DeadlockPrevention {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    // Helper method to ensure consistent ordering
    private static void acquireLocks(Object first, Object second) {
        Object lockA = first.hashCode() < second.hashCode() ? first : second;
        Object lockB = first.hashCode() < second.hashCode() ? second : first;

        synchronized (lockA) {
            synchronized (lockB) {
                // Critical section
            }
        }
    }

    public static void method1() {
        acquireLocks(lock1, lock2);  // Always same order!
    }

    public static void method2() {
        acquireLocks(lock2, lock1);  // Same order enforced!
    }
}

Python

deadlock_prevention.py

import threading

lock1 = threading.Lock()
lock2 = threading.Lock()

def acquire_locks(first, second):
    """Ensure consistent lock ordering"""
    locks = sorted([first, second], key=id)  # Order by object ID
    with locks[0]:
        with locks[1]:
            # Critical section
            pass

def method1():
    acquire_locks(lock1, lock2)  # Always same order!

def method2():
    acquire_locks(lock2, lock1)  # Same order enforced!

Prevention: Timeout-Based Locking

Java

TimeoutLocking.java

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

public class TimeoutLocking {
    private static ReentrantLock lock1 = new ReentrantLock();
    private static ReentrantLock lock2 = new ReentrantLock();

    public static boolean tryAcquireLocks() {
        boolean acquired1 = false;
        boolean acquired2 = false;

        try {
            acquired1 = lock1.tryLock(100, TimeUnit.MILLISECONDS);
            if (!acquired1) return false;

            acquired2 = lock2.tryLock(100, TimeUnit.MILLISECONDS);
            if (!acquired2) {
                lock1.unlock();  // Release first lock
                return false;
            }

            // Both locks acquired
            return true;
        } catch (InterruptedException e) {
            if (acquired1) lock1.unlock();
            if (acquired2) lock2.unlock();
            Thread.currentThread().interrupt();
            return false;
        }
    }
}

---

Livelock

Livelock occurs when threads are actively working but making no progress due to repeated state changes.

Visual: Livelock

Example: Livelock (Polite Algorithm)

Java

LivelockExample.java

public class LivelockExample {
    static class Person {
        boolean isMoving = false;
        String name;

        Person(String name) {
            this.name = name;
        }

        synchronized void moveAside(Person other) {
            while (other.isMoving) {
                System.out.println(name + ": Waiting for " + other.name);
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
            isMoving = true;
            System.out.println(name + ": Moving aside");
            isMoving = false;
        }
    }

    public static void main(String[] args) {
        Person alice = new Person("Alice");
        Person bob = new Person("Bob");

        new Thread(() -> {
            while (true) {
                alice.moveAside(bob);  // Alice moves for Bob
            }
        }).start();

        new Thread(() -> {
            while (true) {
                bob.moveAside(alice);  // Bob moves for Alice
            }
        }).start();

        // Both threads keep moving but never progress!
    }
}

Solution: Randomization

Java

LivelockSolution.java

import java.util.Random;

public class LivelockSolution {
    private static Random random = new Random();

    synchronized void moveAside(Person other) {
        // Add randomization to break livelock
        if (random.nextBoolean()) {
            try {
                Thread.sleep(random.nextInt(100));  // Random delay
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        // Proceed with movement
    }
}

---

Starvation

Starvation occurs when a thread is unable to gain regular access to shared resources.

Visual: Starvation

Prevention: Fair Locks

Java

FairLockExample.java

import java.util.concurrent.locks.ReentrantLock;

public class FairLockExample {
    // Fair lock ensures FIFO ordering
    private static ReentrantLock fairLock = new ReentrantLock(true);

    public static void accessResource() {
        fairLock.lock();
        try {
            // Critical section
        } finally {
            fairLock.unlock();
        }
    }
}

---

False Sharing

False sharing occurs when multiple threads modify different variables on the same CPU cache line.

Visual: False Sharing

Example: False Sharing and Solution

Java

FalseSharing.java

// ❌ False sharing
class Counter {
    volatile long count1;  // Same cache line
    volatile long count2;  // Same cache line
}

// ✅ Solution: Padding
class PaddedCounter {
    volatile long count1;
    long p1, p2, p3, p4, p5, p6, p7;  // Padding (56 bytes)
    volatile long count2;
    long p8, p9, p10, p11, p12, p13, p14;  // More padding
}

// Or use @Contended (Java 8+)
class ContendedCounter {
    @sun.misc.Contended
    volatile long count1;

    @sun.misc.Contended
    volatile long count2;
}

---

Interview Questions

Q1: “What are the four conditions for deadlock?”

Answer: Coffman conditions (all must be present):

1. Mutual Exclusion: Resources cannot be shared
2. Hold and Wait: Threads hold resources while waiting
3. No Preemption: Resources cannot be forcibly taken
4. Circular Wait: Circular chain of waiting threads

Q2: “How would you prevent deadlocks?”

Answer:

1. Lock ordering: Always acquire locks in consistent order
2. Timeout-based locking: Use tryLock() with timeout
3. Avoid nested locks: Minimize lock nesting
4. Lock-free alternatives: Use atomic operations when possible

Q3: “What’s the difference between deadlock and livelock?”

Answer:

• Deadlock: Threads are blocked waiting (frozen)
• Livelock: Threads are active but making no progress (busy but stuck)
• Both: Prevent progress, but livelock uses CPU resources

Q4: “What is false sharing and how do you prevent it?”

Answer:

• False sharing: Multiple threads modify different variables on same cache line
• Impact: Unnecessary cache invalidation, performance degradation
• Prevention: Add padding, use @Contended annotation, align data structures

---

Key Takeaways

Remember

• Deadlock: 4 Coffman conditions, prevent with lock ordering
• Livelock: Active but no progress, prevent with randomization
• Starvation: Thread never gets resources, prevent with fair locks
• False Sharing: Cache line conflicts, prevent with padding
• Detection: Thread dumps, monitoring tools, deadlock detection algorithms
• Prevention: Better than detection—design carefully!

---

Summary

Mastering concurrency hazards is essential for building robust concurrent systems. Always:

1. Design carefully to prevent hazards
2. Use proper synchronization primitives
3. Test thoroughly under concurrent conditions
4. Monitor for hazards in production

Congratulations on completing the Advanced Concurrency module! 🎉

You’ve learned:

• Threads vs Processes
• Synchronization Primitives
• Producer-Consumer Pattern
• Thread Pools & Executors
• Concurrent Collections
• Asynchronous Patterns
• Lock-Free Programming
• Concurrency Hazards

You’re now well-prepared for LLD interviews involving concurrency! 🚀