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!

Go

deadlock_example.go

package main

import "fmt"

func main() {
  ch1 := make(chan struct{})
  ch2 := make(chan struct{})

  // Goroutine 1: send on ch1, then wait on ch2
  go func() {
    fmt.Println("Goroutine 1: sending on ch1")
    ch1 <- struct{}{}           // blocks until goroutine 2 receives
    fmt.Println("Goroutine 1: waiting on ch2")
    <-ch2
  }()

  // Goroutine 2: send on ch2, then wait on ch1 — circular wait!
  go func() {
    fmt.Println("Goroutine 2: sending on ch2")
    ch2 <- struct{}{}           // blocks until goroutine 1 receives
    fmt.Println("Goroutine 2: waiting on ch1")
    <-ch1
  }()

  // Both goroutines will deadlock — Go runtime detects and panics
  select {}
}

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!

Go

deadlock_prevention.go

package main

import (
  "fmt"
  "sync"
)

var (
  mu1 sync.Mutex
  mu2 sync.Mutex
)

// acquireLocks always locks mu1 before mu2 — consistent ordering
func acquireLocks(first, second *sync.Mutex) {
  first.Lock()
  defer first.Unlock()
  second.Lock()
  defer second.Unlock()
  // critical section
}

func method1() {
  acquireLocks(&mu1, &mu2) // mu1 → mu2
}

func method2() {
  acquireLocks(&mu1, &mu2) // same order enforced!
}

func main() {
  var wg sync.WaitGroup
  wg.Add(2)
  go func() { defer wg.Done(); method1(); fmt.Println("method1 done") }()
  go func() { defer wg.Done(); method2(); fmt.Println("method2 done") }()
  wg.Wait()
}

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;
        }
    }
}

Go

timeout_locking.go

package main

import (
  "fmt"
  "sync"
  "time"
)

var (
  mu1 sync.Mutex
  mu2 sync.Mutex
)

func tryAcquireLocks(timeout time.Duration) bool {
  acquired1 := make(chan struct{}, 1)
  go func() {
    mu1.Lock()
    acquired1 <- struct{}{}
  }()

  select {
  case <-acquired1:
    // got mu1, now try mu2
  case <-time.After(timeout):
    return false // timed out waiting for mu1
  }

  acquired2 := make(chan struct{}, 1)
  go func() {
    mu2.Lock()
    acquired2 <- struct{}{}
  }()

  select {
  case <-acquired2:
    // got both locks — critical section here
    mu2.Unlock()
    mu1.Unlock()
    return true
  case <-time.After(timeout):
    mu1.Unlock() // release first lock before giving up
    return false
  }
}

func main() {
  ok := tryAcquireLocks(100 * time.Millisecond)
  fmt.Println("Locks acquired:", ok)
}

---

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!
    }
}

Go

livelock_example.go

package main

import (
  "fmt"
  "runtime"
  "sync/atomic"
)

var (
  aliceMoving int32
  bobMoving   int32
)

func moveAside(myFlag, otherFlag *int32, name, otherName string) {
  for atomic.LoadInt32(otherFlag) == 1 {
    fmt.Printf("%s: waiting for %s\n", name, otherName)
    runtime.Gosched() // yield CPU — but both keep yielding forever
  }
  atomic.StoreInt32(myFlag, 1)
  fmt.Printf("%s: moving aside\n", name)
  atomic.StoreInt32(myFlag, 0)
}

func main() {
  done := make(chan struct{})

  go func() {
    for {
      select {
      case <-done:
        return
      default:
        moveAside(&aliceMoving, &bobMoving, "Alice", "Bob")
      }
    }
  }()

  go func() {
    for {
      select {
      case <-done:
        return
      default:
        moveAside(&bobMoving, &aliceMoving, "Bob", "Alice")
      }
    }
  }()

  // Both goroutines keep moving but never make real progress!
  // (Press Ctrl+C to stop in a real run)
  select {}
}

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
    }
}

Go

livelock_solution.go

package main

import (
  "fmt"
  "math/rand"
  "runtime"
  "sync/atomic"
  "time"
)

var (
  aliceMoving int32
  bobMoving   int32
)

func moveAsideRandom(myFlag, otherFlag *int32, name, otherName string) {
  for atomic.LoadInt32(otherFlag) == 1 {
    // Add randomization to break livelock
    if rand.Intn(2) == 0 {
      delay := time.Duration(rand.Intn(100)) * time.Millisecond
      time.Sleep(delay) // random back-off
    } else {
      runtime.Gosched() // just yield
    }
    fmt.Printf("%s: backing off, waiting for %s\n", name, otherName)
  }
  atomic.StoreInt32(myFlag, 1)
  fmt.Printf("%s: moving aside\n", name)
  atomic.StoreInt32(myFlag, 0)
}

func main() {
  go moveAsideRandom(&aliceMoving, &bobMoving, "Alice", "Bob")
  go moveAsideRandom(&bobMoving, &aliceMoving, "Bob", "Alice")

  time.Sleep(500 * time.Millisecond)
  fmt.Println("Done — randomization broke the livelock")
}

---

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();
        }
    }
}

Go

fair_lock_example.go

package main

import (
  "fmt"
  "sync"
  "time"
)

// Go's sync.Mutex does NOT guarantee FIFO ordering — it is not a "fair" lock.
// For fairness, use a channel-based ticket queue.

type FairMutex struct {
  queue chan struct{}
}

func NewFairMutex() *FairMutex {
  // Buffered channel acts as a FIFO queue
  return &FairMutex{queue: make(chan struct{}, 1)}
}

func (m *FairMutex) Lock() {
  m.queue <- struct{}{} // enqueue — blocks if another goroutine holds it
}

func (m *FairMutex) Unlock() {
  <-m.queue // dequeue — next waiter unblocks in order
}

func accessResource(id int, mu *FairMutex, wg *sync.WaitGroup) {
  defer wg.Done()
  mu.Lock()
  defer mu.Unlock()
  fmt.Printf("Goroutine %d: in critical section\n", id)
  time.Sleep(10 * time.Millisecond)
}

func main() {
  mu := NewFairMutex()
  var wg sync.WaitGroup

  for i := 1; i <= 5; i++ {
    wg.Add(1)
    go accessResource(i, mu, &wg)
  }

  wg.Wait()
  fmt.Println("All goroutines completed — FIFO ordering ensured")
}

---

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;
}

Go

false_sharing.go

package main

import (
  "fmt"
  "sync"
  "sync/atomic"
)

// ❌ False sharing: count1 and count2 share the same 64-byte cache line
type Counter struct {
  count1 int64
  count2 int64
}

// ✅ Solution: pad each counter to its own cache line (64 bytes each)
type PaddedCounter struct {
  count1 int64
  _pad1  [56]byte // padding to fill 64-byte cache line
  count2 int64
  _pad2  [56]byte
}

func benchmarkFalseSharing() {
  c := &Counter{}
  var wg sync.WaitGroup

  wg.Add(2)
  go func() {
    defer wg.Done()
    for i := 0; i < 1_000_000; i++ {
      atomic.AddInt64(&c.count1, 1) // modifies same cache line as count2
    }
  }()
  go func() {
    defer wg.Done()
    for i := 0; i < 1_000_000; i++ {
      atomic.AddInt64(&c.count2, 1) // cache invalidation from goroutine 1
    }
  }()
  wg.Wait()
  fmt.Printf("count1=%d count2=%d\n", c.count1, c.count2)
}

func benchmarkPadded() {
  c := &PaddedCounter{}
  var wg sync.WaitGroup

  wg.Add(2)
  go func() {
    defer wg.Done()
    for i := 0; i < 1_000_000; i++ {
      atomic.AddInt64(&c.count1, 1) // own cache line — no false sharing
    }
  }()
  go func() {
    defer wg.Done()
    for i := 0; i < 1_000_000; i++ {
      atomic.AddInt64(&c.count2, 1)
    }
  }()
  wg.Wait()
  fmt.Printf("count1=%d count2=%d\n", c.count1, c.count2)
}

func main() {
  fmt.Print("False sharing: ")
  benchmarkFalseSharing()
  fmt.Print("Padded:        ")
  benchmarkPadded()
}

---

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! 🚀