Mutex & Semaphores

When multiple threads access shared mutable data, we must coordinate access. Two of the most important synchronization primitives provided by operating systems are Mutexes and Semaphores. Although they appear similar, they serve different synchronization purposes.

1. Learning Objectives

• Differentiate between a Mutex (Mutual Exclusion lock) and a Semaphore.
• Explain the concept of Lock Ownership and Reentrancy.
• Understand how Counting Semaphores manage limited resource pools.
• Implement thread throttling using Semaphores.
• Compare Binary Semaphores with Mutexes in terms of ownership and release mechanics.

2. Problem & Naive Solution

Imagine you are building a database connection pool. The database allows a maximum of 3 concurrent connections. If 10 application threads attempt to execute queries concurrently, we must throttle them, allowing only 3 threads to acquire connections while holding the rest in a wait queue.

The Naive Solution (Uncontrolled Connection Fetching)

A developer attempts to coordinate access by using a simple counter and locks:

3. Issues with the Naive Approach

• High Lock Contention: The getConnection() method is fully synchronized. Only one thread can check and acquire a connection at a time. This introduces a synchronization bottleneck even when connections are available.
• Complex Signaling Logic: Managing wait/notify lists manually increases the risk of thread starvation or notification loss (e.g., if you accidentally call notify() instead of notifyAll()).

4. Real-world Analogy

5. Theory: Mutex vs. Semaphore Primitives

Let's explore the core differences between Mutexes and Semaphores:

A. Lock Ownership Semantics

• Mutex: Features Ownership. Only the thread that locks the mutex can unlock it. If Thread A locks a mutex, Thread B cannot release it.
• Semaphore: Has no ownership. Any thread can increment the permit count by calling release(), even if it didn't call acquire(). This makes semaphores useful for producer-consumer signaling.

B. Reentrancy

• Mutex: Can be reentrant (recursive). If Thread A holds a reentrant mutex, it can acquire it again without deadlocking. It maintains a lock count and releases the lock once the outer block exits.
• Semaphore: Is not reentrant. If a thread attempts to acquire a permit from a semaphore twice when only one permit is available, it will block on its second request, causing a deadlock.

C. Counting Semaphore Permissibility

A Semaphore manages a counter variable. It exposes two atomic operations:

• acquire() / wait(): Decrements the permit count. If the count is $\le 0$, the thread blocks and joins the semaphore's wait queue.
• release() / signal(): Increments the permit count. If the count was $\le 0$, it wakes up a waiting thread from the queue.

6. Visual Diagram

This diagram shows how a counting semaphore manages a queue of threads competing for 3 permits.

7. Syntax Explanation

To manage permits and locks, languages provide standard library classes:

• Java: Provides java.util.concurrent.Semaphore for permit tracking and java.util.concurrent.locks.ReentrantLock for mutual exclusion.
• Python: Provides threading.Lock() (mutex) and threading.Semaphore(value=N) (counting semaphore).
• C++: Provides std::mutex for locks and std::counting_semaphore (since C++20) for permit tracking.

8. Step-by-Step Implementation

1. Initialize the Semaphore: Instantiate the semaphore with the maximum limit of concurrent permits.
2. Acquire Permits: Wrap the resource acquisition step in an .acquire() call. This blocks threads if the pool is full.
3. Execute Safe Work: Run the query or process the task.
4. Ensure Release: Wrap the .release() call inside a finally block to guarantee the permit is returned, even if an exception occurs.

9. Complete Code (Rate-Limited Connection Pool)

This program uses a semaphore to limit database access to 3 concurrent threads, demonstrating how additional threads wait in a queue.

10. Code Walkthrough

• Permit Throttling Mechanics: When the program starts, the first 3 threads (Worker-1, Worker-2, Worker-3) call semaphore.acquire(). They immediately decrement the permit count to 0 and proceed to run. The remaining threads (Worker-4, Worker-5, Worker-6) block on .acquire(), waiting in the FIFO queue.
• Finally Block Guard: Placing semaphore.release() in a finally block ensures that the permit is released back to the pool even if the query throws an exception, preventing thread starvation.

11. Complexity Analysis

• Time Complexity: acquire() and release() are $O(1)$ operations. They use atomic counter changes and OS-level wait queues.
• Space Complexity: $O(N)$ memory space to manage the wait queue of blocked threads.

12. Best Practices

• Always Release in a Finally Block: Release locks and permits inside a finally block to prevent resource leaks and thread hangs.
• Enforce Fairness When Needed: Set the fairness flag to true (e.g., new Semaphore(permits, true)) in applications where thread acquisition order must match request order, preventing thread starvation. Note that fairness can introduce additional context-switching overhead.

13. Common Mistakes

• Using Binary Semaphores as Mutexes: Assuming a Binary Semaphore is identical to a Mutex. Since semaphores lack ownership, any thread can call release() on a binary semaphore, potentially releasing a lock that is currently held by another thread.
• Permit Leaks: Forgetting to call release() when exiting a method. Over time, this leaks permits, eventually causing the application to hang when the permit count reaches 0.

14. Interview Discussion

15. Practice Exercises

• Easy: Write a program that implements a binary semaphore to protect a shared integer counter.
• Medium: Build a print spooler coordinator. Limit concurrent access to a printer pool (size = 2) using a Semaphore.
• Hard: Implement a custom reentrant lock using a binary semaphore and a thread ownership reference.

16. Challenge Problem

Design a Concurrent API Rate Limiter. The rate limiter must restrict requests for an API endpoint to a maximum of 100 calls per minute. When a client exceeds the limit, block their requests or return an HTTP 429 error. Use a counting semaphore to manage request permits, and use a background thread to reset the permits to 100 every 60 seconds.

17. Summary & Cheat Sheet

18. Quiz

19. Next Lesson Preview

In the next lesson, we will cover Condition Variables. We will study how to implement thread-safe signaling queues, resolve the classic Producer-Consumer problem, and prevent CPU busy-waiting using monitor wait sets!