When multiple threads or processes access shared data concurrently, the result can depend on timing — this is a race condition. Synchronization is the art of coordinating access to shared resources so that the outcome is deterministic.
The Critical Section Problem
A critical section is a piece of code that accesses shared resources (variables, files, data structures). The problem: ensure that when one thread is in its critical section, no other thread is in its critical section for the same resource.
Three Requirements
| Requirement | Meaning |
|---|---|
| Mutual exclusion | Only one process can be in its critical section at a time |
| Progress | If no process is in the critical section, a waiting process should be able to enter without indefinite delay |
| Bounded waiting | A process shouldn’t wait forever — there’s a limit on how many times others can enter ahead of it |
Synchronization Primitives
Mutex (Mutual Exclusion Lock)
- Ownership-based: only the thread that locked it can unlock it
- Binary state: locked or unlocked
- The thread sleeps while waiting (no busy-waiting)
Semaphore
An integer with two atomic operations: wait() (P, decrement) and signal() (V, increment).
| Type | Range | Use case |
|---|---|---|
| Binary | 0 or 1 | Signaling between threads |
| Counting | 0 to N | Managing a pool of resources |
Key Difference: Mutex vs Binary Semaphore
| Mutex | Binary Semaphore | |
|---|---|---|
| Ownership | Yes — only owner unlocks | No — any thread can signal |
| Purpose | Mutual exclusion | Signaling |
| Recursive | Usually supported | Not supported |
The Race Condition
// Two threads execute concurrently:
counter++; // read, increment, write — NOT atomic
// Thread A reads 5, Thread B reads 5
// Both write 6 — should be 7Q: What is a race condition?
A: When the outcome of concurrent execution depends on the timing or interleaving of threads. Example: two threads incrementing a shared counter → both read the same value, both write the same result → one increment is lost.
Q: What are the three requirements for a critical section solution?
A: Mutual exclusion (no two in critical section simultaneously), progress (someone who wants to enter eventually can), bounded waiting (no process waits forever). All three must hold for a correct solution.
Q: What’s the difference between mutex and semaphore?
A: Mutex has ownership — same thread must lock and unlock. Semaphore is signaling — any thread can wait or signal. Mutex is for mutual exclusion; semaphore can be used for both mutual exclusion and coordination.
Q: What is a monitor?
A: A high-level synchronization construct (Java synchronized) that encapsulates shared data with procedures. Only one thread can be active in the monitor at a time — automatic mutual exclusion. Monitors use condition variables for signaling.
Premium Content
Unlock Concurrency & Synchronization and all premium lessons with a subscription.
From ₹199.99/year — See plans