Synchronization
When multiple threads or processes access shared resources concurrently, synchronization mechanisms ensure correct behavior. Without synchronization, race conditions lead to corrupted data, lost updates, and unpredictable behavior.
Why Synchronization Matters
// Classic race condition
int counter = 0;
// Thread 1 // Thread 2
counter++; counter++;
// Could be: load, load, inc, store, inc, store → counter = 1 (not 2!)
The counter++ operation is not atomic. It involves:
- Read counter from memory
- Increment in register
- Write back to memory
If two threads interleave these steps, the result is wrong.
The Critical Section Problem
A critical section is code that accesses shared resources and must not be executed by more than one thread at a time. The solution must satisfy:
- Mutual Exclusion: At most one thread in the critical section
- Progress: If no thread is in CS, a waiting thread must be allowed to enter
- Bounded Waiting: A thread must not wait forever (no starvation)
Chapter Contents
- Critical Section Problem — the fundamental problem
- Peterson’s Algorithm — software-only solution for 2 threads
- Mutexes — the simplest locking primitive
- Semaphores — counting synchronization
- Spinlocks — busy-wait locks for short critical sections
- Monitors — high-level synchronization construct
- Readers-Writers Problem — concurrent read access
- Dining Philosophers Problem — resource allocation
- Sleeping Barber Problem — signaling and counting
- Lock-Free Data Structures — synchronization without locks
- Compare-and-Swap (CAS) — atomic primitive
- Memory Barriers — ordering memory operations
- Deadlocks — when threads wait forever
Synchronization Mechanism Comparison
| Mechanism | Type | Use Case | Complexity |
|---|---|---|---|
| Mutex | Binary lock | Protect critical section | Low |
| Semaphore | Counting | Resource pool, signaling | Medium |
| Spinlock | Busy-wait lock | Short CS, no context switch | Low |
| Monitor | High-level | Object-oriented sync | Medium |
| Condition Variable | Signaling | Wait for condition | Medium |
| Read-Write Lock | Multiple readers | Read-heavy workloads | Medium |
| Barrier | Synchronization | Wait for all threads | Medium |
| Lock-free (CAS) | Non-blocking | High-performance | High |
Interview Quick Facts
- Mutex vs Semaphore: Mutex = mutual exclusion (binary, owner-based). Semaphore = signaling/counting (no owner concept).
- Spinlock vs Mutex: Spinlock busy-waits (no context switch, good for short CS). Mutex sleeps (context switch, good for long CS).
- Monitor = mutex + condition variables + encapsulated data
- Deadlock requires all 4 conditions: mutual exclusion, hold-and-wait, no preemption, circular wait
Diagram: Synchronization Hierarchy
graph TD
A[Shared Resource Access]
A --> B[Blocking]
A --> C[Non-Blocking]
B --> D[Mutex]
B --> E[Semaphore]
B --> F[Monitor]
B --> G[Read-Write Lock]
B --> H[Barrier]
C --> I[Lock-Free CAS]
C --> J[Wait-Free]
D --> K[Spinlock Variant]
E --> L[Counting Semaphore]
E --> M[Binary Semaphore]
Cross-References
- Deadlocks — what happens when synchronization goes wrong
- I/O — device synchronization
- Filesystems — concurrent file access
- Containers — namespace isolation