Semaphore vs Mutex - When to Use Which

▶

Steps

setup

Initialize Mutex and Semaphore

The Mutex and Semaphore objects are created. Mutex starts unlocked with no owner. Semaphore is initialized with a count of 3, allowing up to 3 concurrent accesses.

💡 Initialization sets the starting state for synchronization primitives before any process uses them.

Line:

mutex = Mutex()
semaphore = Semaphore(3)

💡 Mutex ownership is empty and Semaphore count is at maximum capacity initially.

acquire

Process 1 acquires Mutex lock

Process 1 calls mutex.acquire(), which locks the mutex and sets Process 1 as the owner.

💡 Acquiring the mutex means exclusive access to the critical section is granted to Process 1.

Line:

mutex.acquire()

💡 Mutex ownership changes from None to Process 1, preventing others from entering the critical section.

critical_section

Process 1 enters critical section protected by Mutex

Process 1 is inside the critical section after acquiring the mutex lock. No other process can enter this section until the mutex is released.

💡 This step shows the exclusive access granted by the mutex lock.

Line:

# critical section

💡 Mutex ensures mutual exclusion by allowing only the owner process to proceed.

release

Process 1 releases Mutex lock

Process 1 calls mutex.release(), which clears ownership and unlocks the mutex, allowing others to acquire it.

💡 Releasing the mutex is necessary to avoid deadlock and allow other processes to enter the critical section.

Line:

mutex.release()

💡 Mutex ownership is reset to None, and the lock is available again.

acquire

Process 2 attempts to acquire Semaphore

Process 2 calls semaphore.wait(), which decrements the semaphore count from 3 to 2, allowing Process 2 to enter the critical section.

💡 Semaphore count controls how many processes can concurrently access the resource.

Line:

semaphore.wait()

💡 Semaphore count decreases, showing one less available slot for concurrent access.

critical_section

Process 2 enters critical section protected by Semaphore

Process 2 is inside the critical section after successfully decrementing the semaphore count. Up to 2 more processes can enter concurrently.

💡 Semaphore allows multiple processes to enter critical section up to its count limit.

Line:

# critical section

💡 Semaphore count enforces a limit on concurrent access rather than exclusive ownership.

release

Process 2 signals Semaphore to release slot

Process 2 calls semaphore.signal(), which increments the semaphore count from 2 back to 3, freeing a slot for other processes.

💡 Signaling the semaphore releases one concurrent access slot.

Line:

semaphore.signal()

💡 Semaphore count increases, indicating more available concurrent access.

acquire

Process 1 attempts to acquire Mutex again

Process 1 calls mutex.acquire() again. Since the mutex is unlocked, Process 1 acquires it and becomes the owner.

💡 Mutex acquisition blocks if locked, but here it succeeds immediately.

Line:

mutex.acquire()

💡 Mutex ownership transfers to Process 1 again, enforcing exclusive access.

release

Process 1 releases Mutex after second critical section

Process 1 calls mutex.release(), unlocking the mutex and clearing ownership.

💡 Releasing the mutex allows other processes to acquire it later.

Line:

mutex.release()

💡 Mutex ownership is cleared, making the lock available again.

final

Final state: Mutex unlocked, Semaphore count full

Both synchronization primitives are free: Mutex is unlocked with no owner, and Semaphore count is back to 3. Processes have completed their critical sections.

💡 The final state confirms that locks are properly released, preventing deadlocks.

Line:

# end of usage example

💡 Proper acquire and release cycles ensure safe synchronization.

import threading

class Mutex:
    def __init__(self):
        self.lock = threading.Lock()  # STEP 1
        self.owner = None

    def acquire(self):
        self.lock.acquire()  # STEP 2,8
        self.owner = threading.get_ident()

    def release(self):
        if self.owner != threading.get_ident():
            raise RuntimeError('Mutex released by non-owner')
        self.owner = None
        self.lock.release()  # STEP 4,9

class Semaphore:
    def __init__(self, count):
        self.sem = threading.Semaphore(count)  # STEP 1

    def wait(self):
        self.sem.acquire()  # STEP 5

    def signal(self):
        self.sem.release()  # STEP 7

# Usage example
mutex = Mutex()  # STEP 1
semaphore = Semaphore(3)  # STEP 1

# Mutex usage
mutex.acquire()  # STEP 2
# critical section  # STEP 3
mutex.release()  # STEP 4

# Semaphore usage
semaphore.wait()  # STEP 5
# critical section  # STEP 6
semaphore.signal()  # STEP 7

# Mutex usage again
mutex.acquire()  # STEP 8
# critical section
mutex.release()  # STEP 9

📊

Semaphore vs Mutex - When to Use Which - Watch the Algorithm Execute, Step by Step

Watching each step of lock acquisition and release helps you understand the fundamental difference between Mutex (exclusive ownership) and Semaphore (counted access).

1

ready

2

ready

Ready Queue

12

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:1 - Process 1 starts executing mutex.acquire()

1

running

2

ready

Ready Queue

2

Waiting Queue

empty

🖥CPU1t=1

Transition running → running pid:1 - Process 1 executes critical section under mutex lock

1

running

2

ready

Ready Queue

2

Waiting Queue

empty

🖥CPU1t=2

Transition running → ready pid:1 - Process 1 executes mutex.release()

1

ready

2

ready

Ready Queue

12

Waiting Queue

empty

🖥CPUidlet=3

1

Transition ready → running pid:2 - Process 2 starts executing semaphore.wait()

1

ready

2

running

Ready Queue

1

Waiting Queue

empty

🖥CPU2t=4

1

Transition running → running pid:2 - Process 2 executes critical section under semaphore control

1

ready

2

running

Ready Queue

1

Waiting Queue

empty

🖥CPU2t=5

1

Transition running → ready pid:2 - Process 2 executes semaphore.signal()

1

ready

2

ready

Ready Queue

12

Waiting Queue

empty

🖥CPUidlet=6

1

2

Transition ready → running pid:1 - Process 1 starts executing mutex.acquire() again

1

running

2

ready

Ready Queue

2

Waiting Queue

empty

🖥CPU1t=7

1

2

Transition running → ready pid:1 - Process 1 executes mutex.release() again

1

ready

2

ready

Ready Queue

12

Waiting Queue

empty

🖥CPUidlet=8

1

2

1

1

terminated

burst: 0

2

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=9

1

2

1

Key Takeaways

✓ Mutex enforces exclusive ownership, allowing only one process to enter the critical section at a time.

This exclusivity is hard to grasp from code alone but becomes clear when you see ownership change and lock state visually.

✓ Semaphore controls concurrent access by maintaining a count, allowing multiple processes up to the count limit to enter simultaneously.

Visualizing the semaphore count decrement and increment clarifies how concurrency limits are enforced.

✓ Proper acquire and release cycles are essential to avoid deadlocks and ensure synchronization primitives are available for other processes.

Seeing the full lifecycle of locking and unlocking helps understand the importance of releasing locks.

Practice

1. In which of the following scenarios is the concept of 'Hold and Wait' most likely to cause a deadlock?

easy

A. A process can forcibly preempt resources from other processes.

B. A process requests all required resources at once before execution begins.

C. A process releases all resources before requesting new ones.

D. A process holds one resource and waits to acquire another resource already held by another process.

Solution

1. Step 1: Understand 'Hold and Wait'

   This condition requires a process to hold at least one resource while waiting to acquire additional resources. A process holds one resource and waits to acquire another resource already held by another process directly describes this scenario.

2. Step 2: Analyze other options

   A process requests all required resources at once before execution begins avoids hold and wait by requesting all resources upfront. A process releases all resources before requesting new ones releases resources before requesting new ones, preventing hold and wait. A process can forcibly preempt resources from other processes describes preemption, which is a different condition.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only a process holding one resource and waiting to acquire another resource already held by another process matches the hold and wait condition necessary for deadlock.

Hint: Hold and Wait means holding some resources while waiting for others [OK]

Common Mistakes:

• Confusing hold and wait with requesting all resources at once
• Thinking preemption is part of hold and wait

2. In a Unix-like file system, which component is primarily responsible for mapping a file name to its data blocks on disk?

easy

A. The inode, which stores metadata and pointers to data blocks

B. The data block itself, which contains the file's content and its name

C. The superblock, which manages overall file system metadata

D. The directory entry, which contains the file name and a pointer to the inode

Solution

1. Step 1: Understand the role of directory entries in file name resolution

   Directory entries map file names to inode numbers, acting as the bridge between human-readable names and inode metadata.

2. Step 2: Clarify inode responsibilities

   Inodes store metadata and pointers to data blocks but do not contain file names.

3. Step 3: Differentiate superblock and data blocks

   The superblock manages file system-wide metadata, not individual file mappings; data blocks store file content, not names.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Directory entries handle name-to-inode mapping [OK]

Hint: Directory entries map names -> inodes; inodes map data blocks

Common Mistakes:

• Confusing inode as containing file names
• Assuming data blocks store file names
• Believing superblock handles file name mappings

3. Which of the following statements about deadlock prevention in the Dining Philosophers problem is INCORRECT?

medium

A. Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation

B. Allowing a philosopher to pick up both forks only if both are available prevents deadlock

C. Imposing a strict ordering on resource acquisition always prevents deadlock

D. Breaking one of the four Coffman conditions is sufficient to prevent deadlock

Solution

1. Step 1: Analyze each statement

   Imposing a strict ordering on resource acquisition always prevents deadlock is correct: ordering resources prevents circular wait; Allowing a philosopher to pick up both forks only if both are available prevents deadlock is correct: atomic acquisition avoids partial hold; Breaking one of the four Coffman conditions is sufficient to prevent deadlock is correct: breaking any Coffman condition prevents deadlock.

2. Step 2: Evaluate Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation

   Asymmetric fork picking prevents deadlock but does not guarantee no starvation, as some philosophers may be repeatedly delayed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation incorrectly claims starvation is guaranteed prevented.

Hint: Deadlock prevention ≠ starvation prevention [OK]

Common Mistakes:

• Assuming deadlock prevention implies starvation freedom
• Believing asymmetric picking solves all synchronization issues
• Confusing Coffman conditions with starvation conditions

4. Why might using multiple threads within a single process not always improve performance compared to multiple processes?

medium

A. Because thread context switching is slower than process context switching

B. Because threads have higher memory overhead than processes

C. Because threads share the same memory space, leading to potential synchronization bottlenecks

D. Because threads cannot run on multiple CPU cores simultaneously

Solution

1. Step 1: Analyze memory overhead

   Threads share memory, so they have lower memory overhead than processes, making Because threads have higher memory overhead than processes incorrect.

2. Step 2: Consider synchronization issues

   Shared memory requires synchronization mechanisms (locks, mutexes), which can cause contention and reduce performance.

3. Step 3: Evaluate context switching speed

   Thread context switching is generally faster than process switching, so Because thread context switching is slower than process context switching is false.

4. Step 4: Understand CPU core utilization

   Threads can run on multiple cores simultaneously, so Because threads cannot run on multiple CPU cores simultaneously is false.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Synchronization overhead can limit thread performance gains [OK]

Hint: Threads share memory but need locks; locks can slow things down [OK]

Common Mistakes:

• Assuming threads always outperform processes
• Confusing context switch overhead between threads and processes
• Believing threads cannot utilize multiple cores

5. What is a key limitation of the working set model in preventing thrashing that candidates often overlook?

medium

A. It requires tracking all page references, which can be expensive and complex

B. It guarantees zero page faults once the working set is allocated

C. It works best when all processes have identical working set sizes

D. It eliminates the need for load control mechanisms

Solution

1. Step 1: Understand working set model overhead

   The model requires monitoring page references over time windows, which can be costly.

2. Step 2: Analyze options

   A is correct because tracking page references precisely is resource-intensive.
   B is incorrect because even with working set allocation, some page faults can occur.
   C is incorrect because working set sizes vary widely among processes.
   D is incorrect because load control is still needed when total working sets exceed memory.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Working set tracking overhead is a practical limitation often underestimated.

Hint: Working set tracking = overhead cost

Common Mistakes:

• Assuming working set eliminates all page faults
• Believing all processes have similar working sets
• Ignoring the need for load control