{"title":"Mutex and Semaphores","description":null,"content":"# Mutex and Semaphores\n\nA bathroom with a single lock. A parking lot with 50 spaces. A restaurant with 10 tables.\n\nThese real-world scenarios map directly to two fundamental synchronization primitives: **mutex** and **semaphore**.\n\nA mutex is like the bathroom lock. Only one person can use it at a time. A semaphore is like the parking lot. Multiple cars can enter, but only up to the capacity.\n\nIn this article, we'll explore:\n\n- What is a Mutex and how it works\n- What is a Semaphore and its types\n- Key differences between them\n- When to use each\n- Implementation patterns and pitfalls\n\n---\n\nIf you're enjoying this newsletter and want to get even more value, consider becoming a **[paid subscriber](https://blog.algomaster.io/subscribe)**.\n\nAs a paid subscriber, you'll unlock all **premium articles** and gain full access to all **[premium courses](https://algomaster.io/newsletter/paid/resources)** on **[algomaster.io](https://algomaster.io)**.\n\n[Unlock Full Access](undefined)\n\n---\n\n## 1. What is a Mutex?\n\nA **Mutex** (Mutual Exclusion) is a synchronization primitive that allows only one thread to access a resource at a time.\n\nThink of it as a key to a room. Only the thread holding the key can enter. Other threads must wait until the key is returned.\n\n\n```mermaid\nflowchart LR\n subgraph Mutex[\"Mutex (Lock)\"]\n Key[\"🔑 Key\"]\n end\n\n T1[\"Thread 1
(has key)\"]\n T2[\"Thread 2
(waiting)\"]\n T3[\"Thread 3
(waiting)\"]\n Resource[\"Protected
Resource\"]\n\n T1 -->|\"holds\"| Key\n Key -->|\"grants access\"| Resource\n T2 -.->|\"waiting for\"| Key\n T3 -.->|\"waiting for\"| Key\n\n style Mutex fill:#ffa94d,stroke:#000,color:#000\n style Key fill:#69db7c,stroke:#000,color:#000\n style T1 fill:#00ceff,stroke:#000,color:#000\n style T2 fill:#9775fa,stroke:#000,color:#000\n style T3 fill:#9775fa,stroke:#000,color:#000\n style Resource fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### Key Properties of Mutex\n\n1. **Mutual Exclusion**: Only one thread can hold the mutex at a time\n2. **Ownership**: The thread that locks must be the one to unlock\n3. **Blocking**: Threads waiting for the mutex are blocked (sleeping)\n\n### Basic Mutex Operations\n\n\n```java\nimport java.util.concurrent.locks.Lock;\nimport java.util.concurrent.locks.ReentrantLock;\n\npublic class Counter {\n private int count = 0;\n private final Lock mutex = new ReentrantLock();\n\n public void increment() {\n mutex.lock(); // Acquire the mutex\n try {\n count++; // Critical section\n } finally {\n mutex.unlock(); // Release the mutex\n }\n }\n}\n```\n\n\nThe flow of mutex acquisition:\n\n\n```mermaid\nsequenceDiagram\n participant T1 as Thread 1\n participant M as Mutex\n participant T2 as Thread 2\n\n T1->>M: lock()\n M-->>T1: Acquired\n\n T2->>M: lock()\n Note over T2: Blocked (waiting)\n\n T1->>T1: Execute critical section\n\n T1->>M: unlock()\n M-->>T2: Acquired\n\n T2->>T2: Execute critical section\n T2->>M: unlock()\n```\n\n\n---\n\n## 2. What is a Semaphore?\n\nA **Semaphore** is a synchronization primitive that controls access to a resource by maintaining a count of available permits.\n\nThink of it as a parking lot attendant. The lot has N spaces. Each car that enters takes a permit (decrementing the count). When a car leaves, it returns a permit (incrementing the count). When count reaches zero, new cars must wait.\n\n\n```mermaid\nflowchart TB\n subgraph Semaphore[\"Semaphore (permits = 3)\"]\n P1[\"Permit 1\"]\n P2[\"Permit 2\"]\n P3[\"Permit 3\"]\n end\n\n T1[\"Thread 1\"] -->|\"acquired\"| P1\n T2[\"Thread 2\"] -->|\"acquired\"| P2\n T3[\"Thread 3\"] -->|\"acquired\"| P3\n\n T4[\"Thread 4
(waiting)\"]\n T5[\"Thread 5
(waiting)\"]\n\n T4 -.->|\"no permits\"| Semaphore\n T5 -.->|\"no permits\"| Semaphore\n\n style Semaphore fill:#69db7c,stroke:#000,color:#000\n style P1 fill:#00ceff,stroke:#000,color:#000\n style P2 fill:#00ceff,stroke:#000,color:#000\n style P3 fill:#00ceff,stroke:#000,color:#000\n style T1 fill:#ffa94d,stroke:#000,color:#000\n style T2 fill:#ffa94d,stroke:#000,color:#000\n style T3 fill:#ffa94d,stroke:#000,color:#000\n style T4 fill:#9775fa,stroke:#000,color:#000\n style T5 fill:#9775fa,stroke:#000,color:#000\n```\n\n\n### Semaphore Operations\n\nA semaphore has two fundamental operations:\n\n\n| ##### Operation | ##### Also Called | ##### Description |\n| --- | --- | --- |\n| **acquire()** | wait(), P(), down() | Decrement count. Block if count is 0 |\n| **release()** | signal(), V(), up() | Increment count. Wake up waiting thread |\n\n\n\n```java\nimport java.util.concurrent.Semaphore;\n\npublic class ConnectionPool {\n private final Semaphore semaphore;\n\n public ConnectionPool(int maxConnections) {\n this.semaphore = new Semaphore(maxConnections);\n }\n\n public Connection getConnection() throws InterruptedException {\n semaphore.acquire(); // Wait for available permit\n return createConnection();\n }\n\n public void releaseConnection(Connection conn) {\n closeConnection(conn);\n semaphore.release(); // Return permit\n }\n}\n```\n\n\n---\n\n## 3. Types of Semaphores\n\n### 3.1 Binary Semaphore\n\nA semaphore with only two states: 0 or 1. It behaves similarly to a mutex.\n\n\n```mermaid\nstateDiagram-v2\n [*] --> Available: Initial state (1)\n Available --> Unavailable: acquire()\n Unavailable --> Available: release()\n\n note right of Available\n Permit count = 1\n Threads can acquire\n end note\n\n note right of Unavailable\n Permit count = 0\n Threads must wait\n end note\n```\n\n\n\n```java\n// Binary semaphore (permits = 1)\nSemaphore binarySemaphore = new Semaphore(1);\n\n// Thread 1\nbinarySemaphore.acquire(); // Permit: 1 -> 0\n// Critical section\nbinarySemaphore.release(); // Permit: 0 -> 1\n\n// Thread 2 (if called while Thread 1 holds it)\nbinarySemaphore.acquire(); // Blocks until permit available\n```\n\n\n### 3.2 Counting Semaphore\n\nA semaphore that allows multiple threads to access a resource, up to a specified limit.\n\n\n```mermaid\nflowchart LR\n subgraph CountingSemaphore[\"Counting Semaphore\"]\n Count[\"Count: N\"]\n end\n\n Acquire[\"acquire()\"]\n Release[\"release()\"]\n\n Acquire -->|\"count--\"| Count\n Release -->|\"count++\"| Count\n\n Note1[\"If count > 0: proceed
If count = 0: block\"]\n\n style CountingSemaphore fill:#69db7c,stroke:#000,color:#000\n style Count fill:#00ceff,stroke:#000,color:#000\n style Acquire fill:#ffa94d,stroke:#000,color:#000\n style Release fill:#9775fa,stroke:#000,color:#000\n```\n\n\nExample: Limiting concurrent database connections\n\n\n```java\npublic class DatabasePool {\n private static final int MAX_CONNECTIONS = 10;\n private final Semaphore semaphore = new Semaphore(MAX_CONNECTIONS);\n private final Queue pool = new ConcurrentLinkedQueue<>();\n\n public Connection acquire() throws InterruptedException {\n semaphore.acquire(); // Block if 10 connections already in use\n return pool.poll();\n }\n\n public void release(Connection conn) {\n pool.offer(conn);\n semaphore.release(); // Allow another thread to acquire\n }\n}\n```\n\n\n---\n\n## 4. Mutex vs Semaphore\n\nWhile binary semaphores and mutexes seem similar, they have important differences:\n\n\n```mermaid\nflowchart TB\n subgraph Mutex[\"Mutex\"]\n M1[\"Ownership: Yes\"]\n M2[\"Count: 0 or 1\"]\n M3[\"Unlock: Only owner\"]\n M4[\"Purpose: Mutual exclusion\"]\n end\n\n subgraph Semaphore[\"Semaphore\"]\n S1[\"Ownership: No\"]\n S2[\"Count: 0 to N\"]\n S3[\"Release: Any thread\"]\n S4[\"Purpose: Resource limiting / Signaling\"]\n end\n\n style Mutex fill:#00ceff,stroke:#000,color:#000\n style Semaphore fill:#ffa94d,stroke:#000,color:#000\n style M1 fill:#38d9a9,stroke:#000,color:#000\n style M2 fill:#38d9a9,stroke:#000,color:#000\n style M3 fill:#38d9a9,stroke:#000,color:#000\n style M4 fill:#38d9a9,stroke:#000,color:#000\n style S1 fill:#38d9a9,stroke:#000,color:#000\n style S2 fill:#38d9a9,stroke:#000,color:#000\n style S3 fill:#38d9a9,stroke:#000,color:#000\n style S4 fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### Comparison Table\n\n\n| ##### Aspect | ##### Mutex | ##### Semaphore |\n| --- | --- | --- |\n| **Ownership** | Yes, only owner can unlock | No ownership concept |\n| **Count** | Binary (0 or 1) | Can be any non-negative integer |\n| **Who can release** | Only the acquiring thread | Any thread |\n| **Purpose** | Protect critical sections | Limit concurrent access, signaling |\n| **Use case** | Exclusive resource access | Connection pools, rate limiting |\n| **Recursive** | Often supported | Not applicable |\n\n\n### The Ownership Difference\n\nThis is the most important distinction:\n\n\n```java\n// Mutex - Only owner can unlock\nLock mutex = new ReentrantLock();\n\n// Thread 1\nmutex.lock();\n// Only Thread 1 can call mutex.unlock()\n\n// Semaphore - Any thread can release\nSemaphore sem = new Semaphore(1);\n\n// Thread 1\nsem.acquire();\n\n// Thread 2 can call release (useful for signaling)\nsem.release(); // Valid! No ownership requirement\n```\n\n\nThis makes semaphores useful for **signaling** between threads, while mutexes are strictly for **mutual exclusion**.\n\n---\n\n## 5. Semaphore for Signaling\n\nBecause semaphores have no ownership, they can coordinate between different threads. One thread signals an event, another waits for it.\n\n### Example: Producer-Consumer Signaling\n\n\n```java\npublic class ProducerConsumer {\n private final Semaphore itemsAvailable = new Semaphore(0); // Start empty\n private final Semaphore spacesAvailable = new Semaphore(10); // Buffer size\n private final Queue buffer = new ConcurrentLinkedQueue<>();\n\n public void produce(Item item) throws InterruptedException {\n spacesAvailable.acquire(); // Wait for space\n buffer.offer(item);\n itemsAvailable.release(); // Signal item available\n }\n\n public Item consume() throws InterruptedException {\n itemsAvailable.acquire(); // Wait for item\n Item item = buffer.poll();\n spacesAvailable.release(); // Signal space available\n return item;\n }\n}\n```\n\n\n\n```mermaid\nsequenceDiagram\n participant P as Producer\n participant Space as spacesAvailable (10)\n participant Items as itemsAvailable (0)\n participant C as Consumer\n\n Note over Space: permits = 10\n Note over Items: permits = 0\n\n P->>Space: acquire() [10->9]\n P->>P: Add item to buffer\n P->>Items: release() [0->1]\n\n C->>Items: acquire() [1->0]\n C->>C: Take item from buffer\n C->>Space: release() [9->10]\n\n Note over C: Consumer was waiting
until producer signaled\n```\n\n\n---\n\n## 6. Common Use Cases\n\n### 6.1 Mutex: Protecting Shared State\n\n\n```java\npublic class BankAccount {\n private double balance;\n private final Lock mutex = new ReentrantLock();\n\n public void transfer(BankAccount to, double amount) {\n mutex.lock();\n try {\n if (balance >= amount) {\n balance -= amount;\n to.deposit(amount);\n }\n } finally {\n mutex.unlock();\n }\n }\n}\n```\n\n\n### 6.2 Semaphore: Connection Pool\n\n\n```java\npublic class ConnectionPool {\n private final Semaphore semaphore;\n private final BlockingQueue connections;\n\n public ConnectionPool(int size) {\n this.semaphore = new Semaphore(size);\n this.connections = new ArrayBlockingQueue<>(size);\n for (int i = 0; i < size; i++) {\n connections.add(createConnection());\n }\n }\n\n public Connection borrow() throws InterruptedException {\n semaphore.acquire();\n return connections.take();\n }\n\n public void returnConnection(Connection conn) {\n connections.offer(conn);\n semaphore.release();\n }\n}\n```\n\n\n### 6.3 Semaphore: Rate Limiting\n\n\n```java\npublic class RateLimiter {\n private final Semaphore semaphore;\n\n public RateLimiter(int maxRequestsPerSecond) {\n this.semaphore = new Semaphore(maxRequestsPerSecond);\n\n // Replenish permits every second\n ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);\n scheduler.scheduleAtFixedRate(() -> {\n int permitsToAdd = maxRequestsPerSecond - semaphore.availablePermits();\n semaphore.release(permitsToAdd);\n }, 1, 1, TimeUnit.SECONDS);\n }\n\n public boolean tryAcquire() {\n return semaphore.tryAcquire();\n }\n}\n```\n\n\n### 6.4 Semaphore: Bounded Resource Access\n\n\n```java\npublic class PrinterPool {\n private final Semaphore semaphore = new Semaphore(3); // 3 printers\n\n public void print(Document doc) throws InterruptedException {\n semaphore.acquire();\n try {\n // Use one of the 3 printers\n Printer printer = getAvailablePrinter();\n printer.print(doc);\n } finally {\n semaphore.release();\n }\n }\n}\n```\n\n\n---\n\n## 7. Fairness\n\nBoth mutex and semaphore can be configured for **fairness**, meaning threads acquire them in the order they requested.\n\n\n```mermaid\nflowchart TB\n subgraph Unfair[\"Non-Fair (Default)\"]\n U1[\"Thread arrives\"]\n U2[\"Check if available\"]\n U3[\"Acquire immediately
(may skip queue)\"]\n end\n\n subgraph Fair[\"Fair\"]\n F1[\"Thread arrives\"]\n F2[\"Join queue\"]\n F3[\"Wait for turn\"]\n F4[\"Acquire when
first in queue\"]\n end\n\n style Unfair fill:#ffa94d,stroke:#000,color:#000\n style Fair fill:#69db7c,stroke:#000,color:#000\n```\n\n\n\n```java\n// Non-fair (default) - better throughput\nLock mutex = new ReentrantLock();\nSemaphore sem = new Semaphore(5);\n\n// Fair - threads served in order (FIFO)\nLock fairMutex = new ReentrantLock(true);\nSemaphore fairSem = new Semaphore(5, true);\n```\n\n\n\n| ##### Mode | ##### Pros | ##### Cons |\n| --- | --- | --- |\n| Non-fair | Higher throughput | Possible starvation |\n| Fair | No starvation, predictable | Lower throughput |\n\n\n---\n\n## 8. Advanced: Reentrant Mutex\n\nA **reentrant** (or recursive) mutex allows the same thread to acquire it multiple times without deadlocking.\n\n\n```java\nLock mutex = new ReentrantLock();\n\npublic void outer() {\n mutex.lock();\n try {\n // Do something\n inner(); // Calls lock again\n } finally {\n mutex.unlock();\n }\n}\n\npublic void inner() {\n mutex.lock(); // Same thread, already holds lock - OK!\n try {\n // Do something\n } finally {\n mutex.unlock();\n }\n}\n```\n\n\nThe mutex tracks how many times it was locked by the owning thread. It only truly releases when the lock count reaches zero.\n\n\n```mermaid\nflowchart TB\n subgraph ReentrantLock[\"Reentrant Lock State\"]\n Owner[\"Owner: Thread-1\"]\n Count[\"Hold Count: 2\"]\n end\n\n Lock1[\"First lock()\"]\n Lock2[\"Second lock()\"]\n Unlock1[\"First unlock()\"]\n Unlock2[\"Second unlock()\"]\n\n Lock1 -->|\"count: 0->1\"| ReentrantLock\n Lock2 -->|\"count: 1->2\"| ReentrantLock\n Unlock1 -->|\"count: 2->1\"| ReentrantLock\n Unlock2 -->|\"count: 1->0
Actually released\"| Free[\"Available\"]\n\n style ReentrantLock fill:#00ceff,stroke:#000,color:#000\n style Free fill:#69db7c,stroke:#000,color:#000\n```\n\n\nSemaphores are **not** reentrant. Each acquire decrements the count regardless of which thread called it.\n\n---\n\n## 9. Common Pitfalls\n\n### Pitfall 1: Forgetting to Release\n\n\n```java\n// Bad: Leak if exception occurs\nsemaphore.acquire();\ndoWork(); // If this throws, permit is never released\nsemaphore.release();\n\n// Good: Use try-finally\nsemaphore.acquire();\ntry {\n doWork();\n} finally {\n semaphore.release();\n}\n```\n\n\n### Pitfall 2: Releasing Without Acquiring\n\n\n```java\nSemaphore sem = new Semaphore(3);\n\n// Bad: Releases without acquiring\nsem.release(); // Now permits = 4, exceeds intended limit!\n\n// Semaphores don't track who acquired - they just count\n```\n\n\n### Pitfall 3: Using Semaphore When Mutex is Needed\n\n\n```java\n// Bad: Using semaphore for mutual exclusion\nSemaphore sem = new Semaphore(1);\n\n// Thread 1 acquires\nsem.acquire();\n// Critical section\n\n// Thread 2 accidentally releases (bug!)\nsem.release();\n\n// Thread 3 can now enter critical section\n// Two threads in critical section - race condition!\n\n// Good: Use mutex for mutual exclusion\nLock mutex = new ReentrantLock();\n// Only the owner can unlock\n```\n\n\n### Pitfall 4: Deadlock with Multiple Resources\n\n\n```java\n// Thread 1 // Thread 2\nsemaphoreA.acquire(); semaphoreB.acquire();\nsemaphoreB.acquire(); // Block semaphoreA.acquire(); // Block\n// Deadlock!\n\n// Solution: Always acquire in same order\n```\n\n\n### Pitfall 5: Wrong Initial Count\n\n\n```java\n// Mistake: Starting with 0 when you mean \"unlocked\"\nSemaphore sem = new Semaphore(0); // All threads will block!\n\n// Correct for mutual exclusion\nSemaphore sem = new Semaphore(1); // One thread can proceed\n\n// Correct for signaling (start blocked, wait for signal)\nSemaphore signal = new Semaphore(0); // Intentionally 0\n```\n\n\n---\n\n## 10. Choosing Between Mutex and Semaphore\n\n\n```mermaid\nflowchart TD\n Start[\"Need synchronization?\"]\n Q1[\"Protecting shared
state from concurrent
modification?\"]\n Q2[\"Limiting concurrent
access to N resources?\"]\n Q3[\"Signaling between
threads?\"]\n\n Mutex[\"Use Mutex\"]\n CountSem[\"Use Counting
Semaphore (N)\"]\n BinSem[\"Use Binary
Semaphore (1)\"]\n\n Start --> Q1\n Q1 -->|\"Yes\"| Mutex\n Q1 -->|\"No\"| Q2\n Q2 -->|\"Yes\"| CountSem\n Q2 -->|\"No\"| Q3\n Q3 -->|\"Yes\"| BinSem\n\n style Start fill:#00ceff,stroke:#000,color:#000\n style Q1 fill:#ffa94d,stroke:#000,color:#000\n style Q2 fill:#ffa94d,stroke:#000,color:#000\n style Q3 fill:#ffa94d,stroke:#000,color:#000\n style Mutex fill:#69db7c,stroke:#000,color:#000\n style CountSem fill:#69db7c,stroke:#000,color:#000\n style BinSem fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Quick Reference\n\n\n| ##### Scenario | ##### Use |\n| --- | --- |\n| Protect shared variable | Mutex |\n| Only one thread in critical section | Mutex |\n| Limit database connections to 10 | Semaphore(10) |\n| Thread A signals Thread B | Semaphore(0) + release/acquire |\n| Rate limit to N requests/second | Semaphore(N) |\n| Object pool with fixed size | Semaphore(poolSize) |\n\n\n---\n\n## 11. Summary\n\n**Mutex** and **Semaphore** are fundamental synchronization primitives:\n\n\n```mermaid\nflowchart LR\n subgraph Mutex[\"Mutex\"]\n M1[\"Binary: 0 or 1\"]\n M2[\"Ownership\"]\n M3[\"Mutual exclusion\"]\n end\n\n subgraph Semaphore[\"Semaphore\"]\n S1[\"Counting: 0 to N\"]\n S2[\"No ownership\"]\n S3[\"Resource limiting
+ Signaling\"]\n end\n\n style Mutex fill:#00ceff,stroke:#000,color:#000\n style Semaphore fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n**Key Differences:**\n\n\n| ##### Mutex | ##### Semaphore |\n| --- | --- |\n| Only owner unlocks | Any thread can release |\n| Binary (locked/unlocked) | Counting (0 to N permits) |\n| For critical sections | For limiting access / signaling |\n| Supports reentrancy | Not reentrant |\n\n\n**When to Use:**\n\n- **Mutex**: Protecting shared state, ensuring only one thread executes critical code\n- **Counting Semaphore**: Limiting concurrent access (pools, rate limiting)\n- **Binary Semaphore**: Signaling between threads\n\n**Best Practices:**\n\n1. Use mutex for mutual exclusion (not binary semaphore)\n2. Always release in a finally block\n3. Be careful not to release without acquiring\n4. Consider fairness for preventing starvation\n5. Acquire multiple semaphores in consistent order to avoid deadlock\n\n---\n\nThank you for reading!\n\nIf you found it valuable, hit a like and consider subscribing for more such content every week.\n\nIf you have any questions or suggestions, leave a comment.\n\nThis post is public so feel free to share it.\n\n[Share](undefined)\n\n---\n\n**P.S.** If you're enjoying this newsletter and want to get even more value, consider becoming a **[paid subscriber](https://blog.algomaster.io/subscribe)**.\n\nAs a paid subscriber, you'll unlock all **premium articles** and gain full access to all **[premium courses](https://algomaster.io/newsletter/paid/resources)** on **[algomaster.io](https://algomaster.io)**.\n\n[Unlock Full Access](undefined)\n\n**There are [group discounts](https://blog.algomaster.io/subscribe?group=true), [gift options](https://blog.algomaster.io/subscribe?gift=true), and [referral bonuses](https://blog.algomaster.io/leaderboard) available.**\n\n---\n\nCheckout my **[Youtube channel](https://www.youtube.com/@ashishps_1/videos)** for more in-depth content.\n\nFollow me on **[LinkedIn](https://www.linkedin.com/in/ashishps1/)** and **[X](https://twitter.com/ashishps_1)** to stay updated.\n\nCheckout my **[GitHub repositories](https://github.com/ashishps1)** for free interview preparation resources.\n\nI hope you have a lovely day!\n\nSee you soon, Ashish\n\n---\n\n## References\n\n- [Java Concurrency in Practice (Brian Goetz)](undefined) - Chapter 5: Building Blocks\n- [The Little Book of Semaphores (Allen Downey)](undefined) - Free, comprehensive guide\n- [Operating System Concepts (Silberschatz)](undefined) - Chapter 6: Synchronization Tools\n- [Java Semaphore Documentation](undefined)\n\n---\n\n## Images Needed\n\n[IMAGE 1: Mutex Concept] \n\n[IMAGE 2: Semaphore Concept] \n\n[IMAGE 3: Binary vs Counting Semaphore] \n\n[IMAGE 4: Mutex vs Semaphore Comparison] \n\n[IMAGE 5: Producer-Consumer with Semaphores] \n\n[IMAGE 6: Decision Flowchart] ","pageType":"lld-interviews"}

Mutex and Semaphores

Ashish Pratap Singh

Get Premium