Process Synchronization Semaphore, Mutex, Monitor: Tutorial, Examples, FAQs & Interview Tips

Race Condition and Critical Section

A race condition occurs when multiple processes access and manipulate shared data concurrently, and the outcome depends on the order of execution. This leads to inconsistent results.

Example: Two processes both read a counter (value=5), both increment it, and both write back. Result: 6 instead of 7.

The critical section is the part of code where shared resources are accessed. The critical section problem requires a solution that satisfies:

Mutual Exclusion: Only one process can be in its critical section at a time
Progress: If no process is in its critical section, a process that wants to enter must be allowed to do so
Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections before a waiting process is allowed in

Peterson's Solution

A software-based solution for two processes. Uses two shared variables: flag[2] (indicates intent to enter) and turn (whose turn it is).

Satisfies all three requirements for two processes
Not practical for modern hardware (memory reordering issues)
Important for understanding the concept

Semaphores

A semaphore is an integer variable accessed only through two atomic operations: wait() (P) and signal() (V).

Binary Semaphore (Mutex): Value is 0 or 1. Used for mutual exclusion. Equivalent to a mutex lock.

Counting Semaphore: Value can be any non-negative integer. Used to control access to a resource with multiple instances.

wait(S): Decrement S. If S < 0, block the process.
signal(S): Increment S. If S

Mutex

A mutex (mutual exclusion lock) is a binary semaphore used to protect critical sections. A process must acquire the mutex before entering the critical section and release it when done.

acquire(): Lock the mutex (blocks if already locked)
release(): Unlock the mutex
Only the process that acquired the mutex can release it (ownership)

Monitors

A monitor is a high-level synchronization construct that encapsulates shared data and the procedures that operate on it. Only one process can be active inside a monitor at a time.

Provides mutual exclusion automatically
Uses condition variables for signaling: wait() and signal()
Easier to use correctly than semaphores
Used in Java (synchronized keyword), Python (threading.Condition)

Classic Synchronization Problems

Producer-Consumer (Bounded Buffer): Producer adds items to a buffer; Consumer removes items. Problem: Producer must wait if buffer is full; Consumer must wait if buffer is empty. Solution: Use semaphores (empty, full, mutex).

Readers-Writers: Multiple readers can read simultaneously; writers need exclusive access. Problem: Readers may starve writers or vice versa. Solution: Use semaphores with priority rules.

Dining Philosophers: Five philosophers sit at a table with five forks. Each needs two forks to eat. Problem: All pick up left fork simultaneously -> deadlock. Solutions: Allow only 4 philosophers at a time, use asymmetric solution (odd picks left first, even picks right first), use a monitor.

Hardware Solutions

TestAndSet: Atomic instruction that reads a variable and sets it to true in one uninterruptible operation. Used to implement mutex locks.
Compare-And-Swap (CAS): Atomic instruction that compares a memory location with an expected value and, if equal, replaces it with a new value. Foundation of lock-free data structures.
Disabling Interrupts: Disable interrupts before entering critical section, re-enable after. Simple but dangerous (can't be used in user mode, doesn't work on multiprocessors).

Previous Next