Synchronization (Mutex, Semaphore)

Synchronization primitives coordinate access to shared resources in multi-threaded programs, preventing race conditions and ensuring data consistency.

---

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

---

Key Takeaways

• 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