Notes › Operating Systems
Process Synchronization — Mutex and Semaphore
When processes or threads share data, the result can depend on the order they run in — a race condition. Synchronization makes sure shared data stays correct.
Race condition example
Two threads run count = count + 1 (read → add → write) at the same time, starting from 5:
T1 reads 5 T2 reads 5
T1 writes 6 T2 writes 6 → final 6, expected 7
The critical section problem
The critical section is the code that touches shared data. A correct solution must give:
- Mutual exclusion — at most one process in the critical section.
- Progress — if nobody is inside, a waiting process can enter without endless delay.
- Bounded waiting — a process can't be overtaken forever (no starvation).
entry section ← ask permission
critical section
exit section ← release
remainder section
Peterson's solution (2 processes, software only)
// shared: bool flag[2]; int turn;
flag[i] = true; // I want to enter
turn = j; // but you go first if you want
while (flag[j] && turn == j); // busy wait
/* critical section */
flag[i] = false;
Meets all three conditions — but modern CPUs reorder memory operations, so real systems use hardware instructions (test-and-set, compare-and-swap) instead.
Mutex (lock)
A binary lock with an owner: only the thread that locked it can unlock it.
pthread_mutex_lock(&m);
count++; // critical section
pthread_mutex_unlock(&m);
Semaphore
An integer S changed only by two atomic operations:
- wait / P / down:
S--; ifS < 0, block. - signal / V / up:
S++; if someone is waiting, wake one.
| Type | Initial value | Use |
|---|---|---|
| Binary semaphore | 1 | mutual exclusion (like a lock) |
| Counting semaphore | N | N identical resources (N printers, a pool of N connections) |
Mutex vs semaphore
| Mutex | Semaphore | |
|---|---|---|
| Value | locked / unlocked | integer |
| Ownership | yes — the locker unlocks | no — any thread can signal |
| Purpose | mutual exclusion | mutual exclusion and signalling / counting |
| Example | protect a shared counter | limit 3 threads to a resource; producer tells consumer "item ready" |
Classic problems
Producer–consumer (bounded buffer of size N)
semaphores: mutex = 1, empty = N, full = 0
producer: wait(empty); wait(mutex); add item; signal(mutex); signal(full);
consumer: wait(full); wait(mutex); take item; signal(mutex); signal(empty);
Doing wait(mutex) before wait(empty) can deadlock — order matters.
Readers–writers: many readers may read together, a writer needs exclusive access. A simple solution can starve writers.
Dining philosophers: 5 philosophers, 5 forks; each needs two forks. If all pick up the left fork first → deadlock. Fixes: one philosopher picks the right fork first, allow only 4 to sit, or pick both forks atomically.
Monitors and condition variables
A monitor (Java synchronized, C++ std::mutex + std::condition_variable) bundles the lock with the data; condition variables let a thread wait() until another signal()s that a condition changed.
Busy waiting vs blocking
- Spinlock: loops until the lock is free — wastes CPU, but good for very short waits on multi-core systems.
- Blocking: the thread sleeps and is woken up — better for longer waits.
Interview one-liners
- Race condition = result depends on timing of shared access.
- Three requirements: mutual exclusion, progress, bounded waiting.
- A mutex has an owner; a semaphore is a counter anyone can signal.
- Wrong order of
wait()calls can cause deadlock — see Deadlocks. - Related: Process vs Thread, Multithreading in Java.