Concurrency Hazards
Introduction: Concurrency Hazards
Section titled “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
Section titled “Visual: Common Hazards”Deadlocks
Section titled “Deadlocks”A deadlock occurs when two or more threads are blocked forever, waiting for each other.
Coffman Conditions (All Must Be Present)
Section titled “Coffman Conditions (All Must Be Present)”- Mutual Exclusion: Resources cannot be shared
- Hold and Wait: Threads hold resources while waiting for others
- No Preemption: Resources cannot be forcibly taken
- Circular Wait: Circular chain of waiting threads
Visual: Deadlock Scenario
Section titled “Visual: Deadlock Scenario”Example: Deadlock Code
Section titled “Example: Deadlock Code”1public class DeadlockExample {2 private static final Object lock1 = new Object();3 private static final Object lock2 = new Object();4
5 public static void main(String[] args) {6 Thread thread1 = new Thread(() -> {7 synchronized (lock1) {8 System.out.println("Thread 1: Holding lock1");9 try {10 Thread.sleep(100);11 } catch (InterruptedException e) {12 Thread.currentThread().interrupt();13 }14 synchronized (lock2) { // Waiting for lock215 System.out.println("Thread 1: Holding lock1 and lock2");16 }17 }18 });19
20 Thread thread2 = new Thread(() -> {21 synchronized (lock2) { // Different order!22 System.out.println("Thread 2: Holding lock2");23 try {24 Thread.sleep(100);25 } catch (InterruptedException e) {26 Thread.currentThread().interrupt();27 }28 synchronized (lock1) { // Waiting for lock129 System.out.println("Thread 2: Holding lock1 and lock2");30 }31 }32 });33
34 thread1.start();35 thread2.start();36 // Both threads will deadlock!37 }38}1import threading2import time3
4lock1 = threading.Lock()5lock2 = threading.Lock()6
7def thread1():8 with lock1:9 print("Thread 1: Holding lock1")10 time.sleep(0.1)11 with lock2: # Waiting for lock212 print("Thread 1: Holding lock1 and lock2")13
14def thread2():15 with lock2: # Different order!16 print("Thread 2: Holding lock2")17 time.sleep(0.1)18 with lock1: # Waiting for lock119 print("Thread 2: Holding lock1 and lock2")20
21threading.Thread(target=thread1).start()22threading.Thread(target=thread2).start()23# Both threads will deadlock!Prevention: Lock Ordering
Section titled “Prevention: Lock Ordering”Solution: Always acquire locks in the same order everywhere!
1public class DeadlockPrevention {2 private static final Object lock1 = new Object();3 private static final Object lock2 = new Object();4
5 // Helper method to ensure consistent ordering6 private static void acquireLocks(Object first, Object second) {7 Object lockA = first.hashCode() < second.hashCode() ? first : second;8 Object lockB = first.hashCode() < second.hashCode() ? second : first;9
10 synchronized (lockA) {11 synchronized (lockB) {12 // Critical section13 }14 }15 }16
17 public static void method1() {18 acquireLocks(lock1, lock2); // Always same order!19 }20
21 public static void method2() {22 acquireLocks(lock2, lock1); // Same order enforced!23 }24}1import threading2
3lock1 = threading.Lock()4lock2 = threading.Lock()5
6def acquire_locks(first, second):7 """Ensure consistent lock ordering"""8 locks = sorted([first, second], key=id) # Order by object ID9 with locks[0]:10 with locks[1]:11 # Critical section12 pass13
14def method1():15 acquire_locks(lock1, lock2) # Always same order!16
17def method2():18 acquire_locks(lock2, lock1) # Same order enforced!Prevention: Timeout-Based Locking
Section titled “Prevention: Timeout-Based Locking”1import java.util.concurrent.locks.ReentrantLock;2import java.util.concurrent.TimeUnit;3
4public class TimeoutLocking {5 private static ReentrantLock lock1 = new ReentrantLock();6 private static ReentrantLock lock2 = new ReentrantLock();7
8 public static boolean tryAcquireLocks() {9 boolean acquired1 = false;10 boolean acquired2 = false;11
12 try {13 acquired1 = lock1.tryLock(100, TimeUnit.MILLISECONDS);14 if (!acquired1) return false;15
16 acquired2 = lock2.tryLock(100, TimeUnit.MILLISECONDS);17 if (!acquired2) {18 lock1.unlock(); // Release first lock19 return false;20 }21
22 // Both locks acquired23 return true;24 } catch (InterruptedException e) {25 if (acquired1) lock1.unlock();26 if (acquired2) lock2.unlock();27 Thread.currentThread().interrupt();28 return false;29 }30 }31}Livelock
Section titled “Livelock”Livelock occurs when threads are actively working but making no progress due to repeated state changes.
Visual: Livelock
Section titled “Visual: Livelock”Example: Livelock (Polite Algorithm)
Section titled “Example: Livelock (Polite Algorithm)”1public class LivelockExample {2 static class Person {3 boolean isMoving = false;4 String name;5
6 Person(String name) {7 this.name = name;8 }9
10 synchronized void moveAside(Person other) {11 while (other.isMoving) {12 System.out.println(name + ": Waiting for " + other.name);13 try {14 Thread.sleep(100);15 } catch (InterruptedException e) {16 Thread.currentThread().interrupt();17 }18 }19 isMoving = true;20 System.out.println(name + ": Moving aside");21 isMoving = false;22 }23 }24
25 public static void main(String[] args) {26 Person alice = new Person("Alice");27 Person bob = new Person("Bob");28
29 new Thread(() -> {30 while (true) {31 alice.moveAside(bob); // Alice moves for Bob32 }33 }).start();34
35 new Thread(() -> {36 while (true) {37 bob.moveAside(alice); // Bob moves for Alice38 }39 }).start();40
41 // Both threads keep moving but never progress!42 }43}Solution: Randomization
Section titled “Solution: Randomization”1import java.util.Random;2
3public class LivelockSolution {4 private static Random random = new Random();5
6 synchronized void moveAside(Person other) {7 // Add randomization to break livelock8 if (random.nextBoolean()) {9 try {10 Thread.sleep(random.nextInt(100)); // Random delay11 } catch (InterruptedException e) {12 Thread.currentThread().interrupt();13 }14 }15 // Proceed with movement16 }17}Starvation
Section titled “Starvation”Starvation occurs when a thread is unable to gain regular access to shared resources.
Visual: Starvation
Section titled “Visual: Starvation”Prevention: Fair Locks
Section titled “Prevention: Fair Locks”1import java.util.concurrent.locks.ReentrantLock;2
3public class FairLockExample {4 // Fair lock ensures FIFO ordering5 private static ReentrantLock fairLock = new ReentrantLock(true);6
7 public static void accessResource() {8 fairLock.lock();9 try {10 // Critical section11 } finally {12 fairLock.unlock();13 }14 }15}False Sharing
Section titled “False Sharing”False sharing occurs when multiple threads modify different variables on the same CPU cache line.
Visual: False Sharing
Section titled “Visual: False Sharing”Example: False Sharing and Solution
Section titled “Example: False Sharing and Solution”1// ❌ False sharing2class Counter {3 volatile long count1; // Same cache line4 volatile long count2; // Same cache line5}6
7// ✅ Solution: Padding8class PaddedCounter {9 volatile long count1;10 long p1, p2, p3, p4, p5, p6, p7; // Padding (56 bytes)11 volatile long count2;12 long p8, p9, p10, p11, p12, p13, p14; // More padding13}14
15// Or use @Contended (Java 8+)16class ContendedCounter {17 @sun.misc.Contended18 volatile long count1;19
20 @sun.misc.Contended21 volatile long count2;22}Interview Questions
Section titled “Interview Questions”Q1: “What are the four conditions for deadlock?”
Section titled “Q1: “What are the four conditions for deadlock?””Answer: Coffman conditions (all must be present):
- Mutual Exclusion: Resources cannot be shared
- Hold and Wait: Threads hold resources while waiting
- No Preemption: Resources cannot be forcibly taken
- Circular Wait: Circular chain of waiting threads
Q2: “How would you prevent deadlocks?”
Section titled “Q2: “How would you prevent deadlocks?””Answer:
- Lock ordering: Always acquire locks in consistent order
- Timeout-based locking: Use
tryLock()with timeout - Avoid nested locks: Minimize lock nesting
- Lock-free alternatives: Use atomic operations when possible
Q3: “What’s the difference between deadlock and livelock?”
Section titled “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?”
Section titled “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
@Contendedannotation, align data structures
Key Takeaways
Section titled “Key Takeaways”Summary
Section titled “Summary”Mastering concurrency hazards is essential for building robust concurrent systems. Always:
- Design carefully to prevent hazards
- Use proper synchronization primitives
- Test thoroughly under concurrent conditions
- 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! 🚀