Synchronization (Mutex, Semaphore)

Synchronization (Mutex, Semaphore)

Why This Matters

Think of synchronization like a bathroom with a lock. Only one person can use it at a time. When someone is inside, they lock the door (acquire the lock). When they're done, they unlock it (release the lock), and the next person can use it. Mutexes and semaphores do the same for code—they ensure only one thread (or a limited number) can access a shared resource at a time.

This matters because without synchronization, multiple threads can access shared data simultaneously, causing race conditions. One thread might read data while another is writing it, leading to inconsistent or corrupted data. Synchronization prevents this by coordinating access, but it also adds overhead and can cause contention.

In interviews, when someone asks "How would you design a concurrent system?", they're testing whether you understand synchronization. Do you know when to use mutexes vs semaphores? Do you understand deadlocks and contention? Most engineers don't. They use locks everywhere and wonder why the system is slow.

What Engineers Usually Get Wrong

Most engineers think "more locks = safer code." But locks have overhead—acquiring and releasing locks takes time, and if many threads are waiting for the same lock, they're blocked. This can hurt performance. Also, locks can cause deadlocks if acquired in the wrong order. The key is to use locks only when necessary, and to minimize the time locks are held.

Engineers also confuse mutexes and semaphores. A mutex allows only one thread to access a resource (like a bathroom with one stall). A semaphore allows multiple threads (like a parking lot with N spaces). Use mutexes for exclusive access, semaphores for limiting concurrent access.

How This Breaks Systems in the Real World

A service was using a mutex to protect a shared counter. Every thread that incremented the counter had to acquire the mutex. Under normal load, this worked. But during high traffic, many threads were waiting for the mutex. The mutex became a bottleneck. Performance degraded significantly. The fix? Use atomic operations or lock-free data structures for simple operations like counter increments. Only use mutexes when you need to protect complex operations.

Another story: A service was using locks but didn't have timeouts. When a thread holding a lock crashed or hung, other threads waited forever. The system became unresponsive. The fix? Always use timeouts when acquiring locks. If a lock can't be acquired within the timeout, fail fast and retry or return an error. This prevents indefinite waiting.

---

Why Synchronization?

Problem: Race conditions when multiple threads access shared data.

# Without synchronization
counter = 0

def increment():
    global counter
    counter += 1  # Not atomic!

# Thread 1 and Thread 2 both increment
# Expected: counter = 2
# Actual: counter = 1 (race condition!)

Solution: Use synchronization primitives to coordinate access.

---

Mutex (Mutual Exclusion)

Mutex ensures only one thread can access a resource at a time.

Characteristics:

• Binary: Locked (1) or unlocked (0)
• Ownership: Thread that locks must unlock
• Blocking: Threads wait if mutex is locked

Mutex Operations

Lock (Acquire):

Thread tries to lock mutex
  If unlocked: Lock and continue
  If locked: Block until unlocked

Unlock (Release):

Thread unlocks mutex
  Wake up waiting threads
  One thread acquires lock

Example

import threading

# Shared resource
counter = 0
mutex = threading.Lock()

def increment():
    global counter
    mutex.acquire()  # Lock
    try:
        counter += 1
    finally:
        mutex.release()  # Unlock

# Or use context manager
def increment_safe():
    global counter
    with mutex:  # Automatic lock/unlock
        counter += 1

# Multiple threads
threads = []
for i in range(10):
    t = threading.Thread(target=increment)
    threads.append(t)
    t.start()

for t in threads:
    t.join()

print(f"Counter: {counter}")  # Always 10

---

Semaphore

Semaphore allows multiple threads to access a resource (up to a limit).

Characteristics:

• Counting: Can allow N threads
• Non-negative: Count can be 0, 1, 2, ...
• Wait/Signal: Wait (decrement), Signal (increment)

Semaphore Operations

Wait (P, Down, Acquire):

If count > 0:
  Decrement count
  Continue
Else:
  Block until count > 0

Signal (V, Up, Release):

Increment count
Wake up one waiting thread

Types of Semaphores

1. Binary Semaphore (Mutex-like)

Count: 0 or 1
Similar to mutex

2. Counting Semaphore

Count: 0 to N
Allows N threads simultaneously

Example

import threading

# Semaphore allowing 3 threads
semaphore = threading.Semaphore(3)

def access_resource(thread_id):
    semaphore.acquire()  # Wait
    try:
        print(f"Thread {thread_id} accessing resource")
        time.sleep(1)  # Simulate work
    finally:
        semaphore.release()  # Signal

# 10 threads, but only 3 can access at once
threads = []
for i in range(10):
    t = threading.Thread(target=access_resource, args=(i,))
    threads.append(t)
    t.start()

---

Mutex vs Semaphore

Feature	Mutex	Semaphore
Type	Binary (0 or 1)	Counting (0 to N)
Ownership	Thread that locks must unlock	Any thread can signal
Use case	Mutual exclusion	Resource counting
Initial value	1 (unlocked)	N (number of resources)

Key difference:

• Mutex: Only one thread at a time
• Semaphore: N threads at a time

---

Examples

Producer-Consumer with Semaphore

import threading
import queue

buffer = queue.Queue(maxsize=10)
mutex = threading.Lock()
empty = threading.Semaphore(10)  # 10 empty slots
full = threading.Semaphore(0)    # 0 full slots

def producer():
    for i in range(100):
        item = f"item-{i}"
        
        empty.acquire()  # Wait for empty slot
        mutex.acquire()
        try:
            buffer.put(item)
            print(f"Produced: {item}")
        finally:
            mutex.release()
        full.release()  # Signal item added

def consumer():
    for i in range(100):
        full.acquire()  # Wait for item
        mutex.acquire()
        try:
            item = buffer.get()
            print(f"Consumed: {item}")
        finally:
            mutex.release()
        empty.release()  # Signal slot freed

Reader-Writer Problem

import threading

class ReaderWriter:
    def __init__(self):
        self.readers = 0
        self.mutex = threading.Lock()
        self.write_mutex = threading.Lock()  # For writers
    
    def reader_lock(self):
        self.mutex.acquire()
        self.readers += 1
        if self.readers == 1:
            self.write_mutex.acquire()  # First reader locks writers
        self.mutex.release()
    
    def reader_unlock(self):
        self.mutex.acquire()
        self.readers -= 1
        if self.readers == 0:
            self.write_mutex.release()  # Last reader unlocks writers
        self.mutex.release()
    
    def writer_lock(self):
        self.write_mutex.acquire()  # Exclusive lock
    
    def writer_unlock(self):
        self.write_mutex.release()

---

Common Pitfalls

• Deadlock: Holding multiple locks in wrong order. Fix: Always acquire locks in same order
• Forgetting to unlock: Mutex stays locked forever. Fix: Use try-finally, context managers
• Not using mutex: Race conditions. Fix: Protect all shared data access
• Too many locks: Performance degradation. Fix: Minimize critical sections, use lock-free data structures when possible
• Priority inversion: Low priority thread holds lock needed by high priority. Fix: Use priority inheritance

---

Interview Questions

Beginner

Q: What is a mutex and why is it needed?

A:

Mutex (Mutual Exclusion) ensures only one thread can access a resource at a time.

Why needed:

• Race conditions: Multiple threads accessing shared data simultaneously
• Data corruption: Concurrent writes can corrupt data
• Consistency: Ensure data remains consistent

Example:

# Without mutex (race condition)
counter = 0

def increment():
    global counter
    counter += 1  # Not atomic!
    # Thread 1: Read counter (0)
    # Thread 2: Read counter (0)
    # Thread 1: Write counter (1)
    # Thread 2: Write counter (1)
    # Result: counter = 1 (should be 2!)

# With mutex
mutex = threading.Lock()

def increment():
    global counter
    with mutex:
        counter += 1  # Atomic operation
    # Thread 1: Lock, increment, unlock
    # Thread 2: Wait, lock, increment, unlock
    # Result: counter = 2 (correct!)

Operations:

• Lock (acquire): Get exclusive access
• Unlock (release): Release access

---

Intermediate

Q: Explain the difference between mutex and semaphore. When would you use each?

A:

Mutex:

• Type: Binary (0 or 1)
• Ownership: Thread that locks must unlock
• Use case: Mutual exclusion (only one thread at a time)
• Example: Protecting shared variable

Semaphore:

• Type: Counting (0 to N)
• Ownership: Any thread can signal
• Use case: Resource counting (N threads at a time)
• Example: Limiting concurrent database connections

Key Difference:

Mutex: Only 1 thread can access
Semaphore: N threads can access

Example:

# Mutex: Only one thread at a time
mutex = threading.Lock()
with mutex:
    # Only one thread here
    shared_resource.modify()

# Semaphore: 3 threads at a time
semaphore = threading.Semaphore(3)
with semaphore:
    # Up to 3 threads here
    database_connection.use()

When to use:

• Mutex: Mutual exclusion (shared variable, critical section)
• Semaphore: Resource counting (connection pool, rate limiting)

---

Senior

Q: Design a synchronization system for a multi-threaded application that handles reader-writer scenarios, producer-consumer patterns, and prevents deadlocks. How do you optimize for performance?

A:

class SynchronizationSystem {
  private mutexes: Map<string, Mutex>;
  private semaphores: Map<string, Semaphore>;
  private deadlockDetector: DeadlockDetector;
  
  constructor() {
    this.mutexes = new Map();
    this.semaphores = new Map();
    this.deadlockDetector = new DeadlockDetector();
  }
  
  // 1. Reader-Writer Lock
  class ReaderWriterLock {
    private readers: number = 0;
    private readMutex: Mutex;
    private writeMutex: Mutex;
    
    async readerLock(): Promise<void> {
      await this.readMutex.lock();
      this.readers++;
      if (this.readers === 1) {
        await this.writeMutex.lock(); // First reader locks writers
      }
      this.readMutex.unlock();
    }
    
    async readerUnlock(): Promise<void> {
      await this.readMutex.lock();
      this.readers--;
      if (this.readers === 0) {
        this.writeMutex.unlock(); // Last reader unlocks writers
      }
      this.readMutex.unlock();
    }
    
    async writerLock(): Promise<void> {
      await this.writeMutex.lock(); // Exclusive lock
    }
    
    async writerUnlock(): Promise<void> {
      this.writeMutex.unlock();
    }
  }
  
  // 2. Producer-Consumer with Semaphores
  class ProducerConsumer {
    private buffer: Queue;
    private mutex: Mutex;
    private empty: Semaphore; // Empty slots
    private full: Semaphore;  // Full slots
    
    constructor(bufferSize: number) {
      this.buffer = new Queue(bufferSize);
      this.mutex = new Mutex();
      this.empty = new Semaphore(bufferSize);
      this.full = new Semaphore(0);
    }
    
    async produce(item: any): Promise<void> {
      await this.empty.wait(); // Wait for empty slot
      await this.mutex.lock();
      try {
        this.buffer.enqueue(item);
      } finally {
        this.mutex.unlock();
      }
      this.full.signal(); // Signal item added
    }
    
    async consume(): Promise<any> {
      await this.full.wait(); // Wait for item
      await this.mutex.lock();
      let item;
      try {
        item = this.buffer.dequeue();
      } finally {
        this.mutex.unlock();
      }
      this.empty.signal(); // Signal slot freed
      return item;
    }
  }
  
  // 3. Deadlock Prevention
  class DeadlockPrevention {
    private lockOrder: Map<string, number>;
    
    async acquireLocks(lockNames: string[]): Promise<void> {
      // Sort locks by order (prevent deadlock)
      const sorted = lockNames.sort((a, b) => 
        this.getLockOrder(a) - this.getLockOrder(b)
      );
      
      const acquired = [];
      try {
        for (const lockName of sorted) {
          await this.acquireLock(lockName);
          acquired.push(lockName);
        }
      } catch (error) {
        // Release acquired locks
        for (const lockName of acquired.reverse()) {
          await this.releaseLock(lockName);
        }
        throw error;
      }
    }
  }
  
  // 4. Lock-Free Data Structures
  class LockFreeQueue {
    // Use atomic operations instead of locks
    // Better performance for high contention
  }
  
  // 5. Performance Optimization
  optimizePerformance(): void {
    // Use lock-free data structures when possible
    // Minimize critical sections
    // Use read-write locks for read-heavy workloads
    // Use fine-grained locking (lock per data structure)
  }
}

Features:

1. Reader-writer locks: Multiple readers, exclusive writers
2. Producer-consumer: Semaphores for coordination
3. Deadlock prevention: Lock ordering, timeout
4. Lock-free structures: Atomic operations for performance
5. Optimization: Fine-grained locking, minimize critical sections

---

Failure Stories You'll Recognize

The Mutex Bottleneck: A service was using a mutex to protect a shared counter. Every thread that incremented the counter had to acquire the mutex. Under normal load, this worked. But during high traffic, many threads were waiting for the mutex. The mutex became a bottleneck. Performance degraded significantly. The fix? Use atomic operations or lock-free data structures for simple operations like counter increments. Only use mutexes when you need to protect complex operations.

The Hanging Locks: A service was using locks but didn't have timeouts. When a thread holding a lock crashed or hung, other threads waited forever. The system became unresponsive. The fix? Always use timeouts when acquiring locks. If a lock can't be acquired within the timeout, fail fast and retry or return an error. This prevents indefinite waiting.

The Deadlock: A service was using multiple locks. Threads acquired locks in different orders depending on the code path. Under normal load, this worked. But during high traffic, threads started deadlocking. The system became unresponsive. The fix? Always acquire locks in a consistent order (e.g., always lock by resource ID in ascending order). This prevents circular wait, which prevents deadlocks.

What Interviewers Are Really Testing

They want to hear you talk about synchronization as a necessary evil, not a solution. Junior engineers say "use locks to prevent race conditions." Senior engineers say "locks prevent race conditions but have overhead and can cause deadlocks. Use locks only when necessary. Minimize the time locks are held. Use atomic operations for simple operations. Always acquire locks in the same order to prevent deadlocks."

When they ask "How would you design a concurrent system?", they're testing:

• Do you understand when to use mutexes vs semaphores?

• Do you know how to prevent deadlocks?

• Can you minimize lock contention?

• Mutex: Binary lock for mutual exclusion (only one thread at a time)

• Semaphore: Counting lock for resource management (N threads at a time)

• Race conditions: Prevented by synchronization primitives

• Mutex operations: Lock (acquire), Unlock (release)

• Semaphore operations: Wait (decrement), Signal (increment)

• Use mutex for: Mutual exclusion, protecting shared variables

• Use semaphore for: Resource counting, producer-consumer, rate limiting

• Deadlock prevention: Always acquire locks in same order

• Best practices: Use try-finally, context managers, minimize critical sections

How InterviewCrafted Will Teach This

We'll teach this through production failures, not definitions. Instead of memorizing "mutex provides mutual exclusion," you'll learn through scenarios like "why did our system become slow when many threads were waiting for a lock?"

You'll see how synchronization affects performance, reliability, and system design. When an interviewer asks "how would you design a concurrent system?", you'll think about locks, contention, deadlocks, and optimization—not just "use mutexes."

• Process vs Thread - Understanding threads that need synchronization when sharing memory
• Deadlock Conditions and Prevention - How improper synchronization can lead to deadlocks and how to prevent them
• Context Switching - How synchronization affects context switching and thread scheduling
• Shared Memory vs Message Passing - Alternative to synchronization for inter-process communication
• Thread Models (1:1, N:1, M:N) - How different thread models affect synchronization needs