Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
Chapter 7: Synchronization Examples
Classical Problems of Process Synchronization
Bounded-Buffer • Readers-Writers • Dining Philosophers • Monitor Solution
Overview — The 3 Classical Problems
# Problem Core Challenge
1 Bounded-Buffer Producer puts items into a shared buffer; Consumer takes them out.
How to avoid overflow and underflow?
2 Readers-Writers Multiple readers can read simultaneously, but a writer needs exclusive
access. How to avoid conflicts?
3 Dining Philosophers 5 philosophers share 5 chopsticks. How to eat without deadlock or
starvation?
📌 These 3 problems are the STANDARD BENCHMARKS used to test any new synchronization
mechanism. If your solution solves all 3 correctly, it is considered solid.
1. Bounded-Buffer Problem
A shared buffer of N slots. Producer adds items one at a time. Consumer removes items one
at a time. Challenge: Producer must NOT add when full. Consumer must NOT remove when
empty. Both must NOT access buffer simultaneously.
Real-World Analogy
• Producer = Chef making food, placing plates on a counter (buffer)
• Consumer = Waiter picking plates from the counter to serve
• Buffer = The counter — limited space (N plates max)
• Problems without sync: Chef adds when counter is full → plate falls off (overflow). Waiter picks when
counter is empty → nothing to serve (underflow). Both grab same plate → wrong data.
Three Semaphore Variables
mutex init = 1 Binary semaphore — ensures only ONE process (producer
OR consumer) accesses buffer at a time. Prevents
simultaneous modification.
full init = 0 Counts FULL slots. Starts at 0 (buffer empty). Consumer
waits if full==0 (nothing to consume).
empty init = N Counts EMPTY slots. Starts at N (all slots free). Producer
waits if empty==0 (buffer full).
Page 1
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
How Semaphores Interact — Quick Logic
Situation Producer does Consumer does
Buffer FULL (empty=0) wait(empty) → BLOCKS until space signal(empty) → unblocks producer
Buffer EMPTY (full=0) signal(full) → unblocks consumer wait(full) → BLOCKS until item ready
Both want buffer wait(mutex) → only one gets in wait(mutex) → other waits
Producer Process — Code & Explanation
Code What it does & why
while (true) { wait(empty) → Decrease empty count. If empty=0
// produce item (buffer full), BLOCK here until consumer frees space.
wait(empty);
wait(mutex);
wait(mutex) → Lock the buffer for exclusive access. No
// add to buffer
consumer can interfere now.
signal(mutex);
signal(full);
} signal(mutex) → Unlock the buffer. Consumer may now
access.
signal(full) → Increase full count. Tells consumer: one
more item is ready!
Consumer Process — Code & Explanation
Code What it does & why
while (true) { wait(full) → Decrease full count. If full=0 (buffer empty),
wait(full); BLOCK here until producer adds item.
wait(mutex);
// remove from buffer
wait(mutex) → Lock the buffer for exclusive access. No
signal(mutex);
producer can interfere now.
signal(empty);
// consume item
} signal(mutex) → Unlock the buffer. Producer may now
access.
signal(empty) → Increase empty count. Tells producer:
one slot is now free!
Critical Order Rule — Why wait(empty) BEFORE wait(mutex)?
⚠️ WRONG order: wait(mutex) then wait(empty). This causes DEADLOCK! Producer holds mutex,
waits for empty. Consumer needs mutex to signal empty. Neither can proceed!
✅ CORRECT order: wait(empty/full) FIRST, then wait(mutex). Resource semaphore always
BEFORE the mutex. This avoids deadlock.
Step-by-Step Trace Example (N=3 buffer)
Step Action empty full mutex
Init Semaphores initialized 3 0 1
Page 2
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
1 Producer: wait(empty)→2, 2 1 1
wait(mutex)→0, ADD item,
signal(mutex)→1, signal(full)→1
2 Producer: adds 2nd item 1 2 1
3 Producer: adds 3rd item 0 3 1
4 Producer: wait(empty)→−1 → 0 3 1
BLOCKED (buffer full)
5 Consumer: wait(full)→2, 1 2 1
wait(mutex)→0, REMOVE item,
signal(mutex)→1, signal(empty)→1
6 Producer UNBLOCKS (empty=1 now) 0 3 1
2. Readers-Writers Problem
A shared data set (e.g., a database) is accessed by two types of processes: Readers (only
read — no modification) and Writers (can read and write — modify data). Multiple readers can
read simultaneously, but a writer needs EXCLUSIVE access — no readers or other writers
allowed.
Real-World Analogy
• Shared database = Library book with annotations
• Readers = Students reading the book (many can read at once — no conflict)
• Writer = Editor revising the book (needs the book ALONE — nobody reads while editing)
Rules
Scenario Allowed? Why
Reader + Reader (simultaneous) ✅ YES Reading doesn't change data —
no conflict
Writer alone ✅ YES Exclusive access — no conflict
Writer + Reader (simultaneous) ❌ NO Writer modifies data — reader
gets corrupt data
Writer + Writer (simultaneous) ❌ NO Both modify — result is
unpredictable
Four Shared Variables
rw_mutex init = 1 Controls exclusive access for WRITERS. Writer grabs it
before writing; readers grab it only when first reader enters.
mutex init = 1 Protects read_count variable itself (binary semaphore).
Ensures read_count is updated atomically.
Page 3
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
read_count init = 0 (integer) Tracks how many readers are CURRENTLY reading. NOT a
semaphore — it is a plain integer counter.
Writer Process — Code & Explanation
Code What it does
while (true) { wait(rw_mutex) → Grab exclusive lock. BLOCKS if any
wait(rw_mutex); reader OR writer currently active. Entire data set is locked
// WRITE here for this writer alone.
signal(rw_mutex);
}
signal(rw_mutex) → Release lock. Now readers or next
writer can proceed.
Reader Process — Code & Explanation (Key Logic)
Code What it does
while (true) { ENTRY SECTION:
// --- ENTRY --- wait(mutex) → Lock to safely update read_count
wait(mutex); read_count++ → One more reader entered
read_count++; if read_count==1 → I am the FIRST reader → block any
if (read_count == 1) writer by grabbing rw_mutex
wait(rw_mutex); signal(mutex) → Unlock read_count so others can update
signal(mutex); it
// READ here
// --- EXIT ---
EXIT SECTION:
wait(mutex);
wait(mutex) → Lock to safely update read_count
read_count--;
read_count-- → One fewer reader
if (read_count == 0)
if read_count==0 → I am the LAST reader → release
signal(rw_mutex);
rw_mutex so writers can proceed
signal(mutex);
signal(mutex) → Unlock read_count
}
The Key Insight — First and Last Reader
FIRST Reader (read_count becomes 1) LAST Reader (read_count becomes 0)
Calls wait(rw_mutex) to BLOCK any writer Calls signal(rw_mutex) to ALLOW writers
Locks out writers for ALL subsequent readers Unlocks for writers when ALL readers are done
Other readers: NO need to call wait(rw_mutex) Other readers: just decrement read_count & exit
Two Variations — First & Second Reader-Writer Problem
Variation Rule Problem
1st Reader-Writer Readers have priority. Writer waits until Writer may STARVE — new readers
ALL readers done. New readers can keep arriving, writer never gets in.
join even if writer waiting.
2nd Reader-Writer Writer has priority. Once writer ready, Readers may STARVE — writers keep
no NEW readers allowed. Existing arriving, readers never get in.
readers finish, writer enters.
💡 Many modern operating systems solve this with Reader-Writer LOCKS — a built-in kernel primitive
that handles both variations cleanly.
Page 4
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
3. Dining Philosophers Problem
5 philosophers sit at a round table with a bowl of rice. Each philosopher alternates between
THINKING and EATING. To eat, she needs BOTH chopsticks (left + right). Only 5 chopsticks
exist — one between each pair. Challenge: Let everyone eat without deadlock or starvation.
The Setup
Item Description
5 Philosophers P0, P1, P2, P3, P4 — sitting in a circle
5 Chopsticks chopstick[0], [1], [2], [3], [4] — one between each pair
Pi's chopsticks Left = chopstick[i], Right = chopstick[(i+1)%5]
To eat Pi must hold BOTH chopstick[i] AND chopstick[(i+1)%5]
Semaphore chopstick[5], each initialized to 1 (free)
Chopstick Table — Who Shares What
Philosopher Left Chopstick Right Chopstick Formula
P0 chopstick[0] chopstick[1] i=0, (0+1)%5=1
P1 chopstick[1] chopstick[2] i=1, (1+1)%5=2
P2 chopstick[2] chopstick[3] i=2, (2+1)%5=3
P3 chopstick[3] chopstick[4] i=3, (3+1)%5=4
P4 chopstick[4] chopstick[0] i=4, (4+1)%5=0 ← wraps!
Naive Semaphore Solution — The Code
// Philosopher i
while (true) {
wait(chopstick[i]); // pick up LEFT chopstick
wait(chopstick[(i+1) % 5]); // pick up RIGHT chopstick
/* EAT */
signal(chopstick[i]); // put down LEFT chopstick
signal(chopstick[(i+1) % 5]); // put down RIGHT chopstick
/* THINK */
}
The Deadlock Problem with Naive Solution
💀 DEADLOCK SCENARIO: All 5 philosophers pick up their LEFT chopstick simultaneously. Now
each has 1 chopstick and waits for the RIGHT one (held by their neighbor). Nobody can eat. Nobody
releases. DEADLOCK!
Philosopher Holds Waiting For
P0 chopstick[0] chopstick[1] (held by P1)
Page 5
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
P1 chopstick[1] chopstick[2] (held by P2)
P2 chopstick[2] chopstick[3] (held by P3)
P3 chopstick[3] chopstick[4] (held by P4)
P4 chopstick[4] chopstick[0] (held by P0)
🔄 This is CIRCULAR WAIT — one of the 4 necessary conditions for deadlock.
P0→P1→P2→P3→P4→P0: a complete circle!
3 Deadlock Remedies for the Naive Solution
1 Limit to 4 philosophers
Only 4 out of 5 can sit at the table at the same time. This guarantees at least one philosopher can
always eat (5 chopsticks, max 4 holding left → at least one pair is free).
2 Pick up BOTH or NONE (atomic pickup)
A philosopher can only pick up chopsticks if BOTH are available simultaneously — inside a critical
section. No partial pickup allowed. Eliminates Hold and Wait condition.
3 Asymmetric solution (odd/even rule)
ODD-numbered philosophers (P1, P3): pick up LEFT then RIGHT. EVEN-numbered philosophers
(P0, P2, P4): pick up RIGHT then LEFT. Breaks the circular wait pattern.
4. Monitor Solution to Dining Philosophers
The Monitor solution is the most elegant fix. It uses 3 states per philosopher
(THINKING/HUNGRY/EATING) and condition variables. No deadlock. But starvation is still
possible.
Three States — What Each Means
State Meaning Chopstick Status
💭 THINKING Not hungry — not interested in Not needed
eating
😋 HUNGRY Wants to eat — trying to get Requested but not yet obtained
chopsticks
🍜 EATING Both chopsticks obtained — Both held
currently eating
Monitor Data Structures
• state[5]: Array of 5 states — one per philosopher. Initialized to THINKING.
• self[5]: Array of 5 condition variables — one per philosopher. Used to SLEEP/WAKE a specific philosopher.
• Why separate condition vars? Each philosopher waits on her OWN condition. Only SHE is woken when
HER chopsticks become free — not everyone.
Page 6
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
Full Monitor Code
monitor DiningPhilosophers {
enum {THINKING, HUNGRY, EATING} state[5];
condition self[5];
// Philosopher i wants to eat
void pickup(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait(); // sleep if can't eat
}
// Philosopher i finished eating
void putdown(int i) {
state[i] = THINKING;
test((i + 4) % 5); // check LEFT neighbor
test((i + 1) % 5); // check RIGHT neighbor
}
// Can philosopher i eat? Check neighbors
void test(int i) {
if (state[(i+4)%5] != EATING // left not eating
&& state[i] == HUNGRY // i actually wants to eat
&& state[(i+1)%5] != EATING) { // right not eating
state[i] = EATING;
self[i].signal(); // wake i up
}
}
initialization_code() {
for (int i=0; i<5; i++) state[i] = THINKING;
}
}
pickup() — Step-by-Step
1 state[i] = HUNGRY
Philosopher announces: 'I want to eat'
2 test(i)
Check: are BOTH neighbors not eating right now? If yes → state[i]=EATING, self[i].signal(). If no →
nothing changes.
3 if (state[i] != EATING) self[i].wait()
test() didn't set state to EATING → at least one neighbor is eating → SLEEP on own condition
variable. Will wake when neighbor calls putdown().
test() — The Core Logic — 3 Conditions ALL must be TRUE
# Condition Why it's needed
① state[(i+4)%5] != EATING LEFT neighbor must NOT be eating → left chopstick is
FREE. (i+4)%5 wraps around the circular table.
② state[i] == HUNGRY Philosopher i actually wants to eat. Don't signal a THINKING
philosopher — waste of signal.
Page 7
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
③ state[(i+1)%5] != EATING RIGHT neighbor must NOT be eating → right chopstick is
FREE. (i+1)%5 wraps around.
ALL state[i]=EATING, self[i].signal() Both chopsticks free + philosopher hungry → let her eat!
TR Signal wakes her if she was sleeping.
UE
Why (i+4)%5 for Left Neighbor?
Philosopher i Left neighbor (i+4)%5 Verification
P0 P4 (0+4)%5 = 4 ✓ chopstick[4] is P4's right
P1 P0 (1+4)%5 = 0 ✓ chopstick[0] is P0's left
P4 P3 (4+4)%5 = 3 ✓ chopstick[3] is P3's left
💡 (i+4)%5 is the same as (i−1+5)%5 — the LEFT neighbor on a circular table of 5. This avoids
negative indices.
putdown() — Step-by-Step
1 state[i] = THINKING
Philosopher announces she is done eating and now just thinking
2 test((i+4)%5) — check LEFT neighbor
Now that I put down my chopstick, maybe my LEFT neighbor who was HUNGRY can now eat! test()
will check and signal her if so.
3 test((i+1)%5) — check RIGHT neighbor
Same for RIGHT neighbor. My right chopstick is now free — maybe she can eat now!
Complete Timeline — Philosopher 0 (HUNGRY, P4 eating)
Who Acts What Happens
P0: pickup(0) state[0]=HUNGRY. test(0): P4 is EATING → condition ① fails → state[0] stays
HUNGRY. self[0].wait() → P0 SLEEPS 😴
P4: putdown(4) state[4]=THINKING. test(3) → checks P3. test(0) → checks P0!
test(0) called Check: state[4]!=EATING ✓ (just became THINKING) AND state[0]==HUNGRY
✓ AND state[1]!=EATING ✓
All 3 TRUE state[0]=EATING. self[0].signal() → P0 WAKES UP! 🎉
P0 resumes pickup(0) returns. P0 now eating with both chopsticks.
P0: putdown(0) P0 finishes. state[0]=THINKING. Tests P4 and P1 — wakes any HUNGRY
neighbor.
Monitor Solution — Properties
Property Verdict
Deadlock Free? ✅ YES — no circular wait possible. Philosopher only eats when
Page 8
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
BOTH neighbors are not eating.
Starvation Free? ⚠️NO — a philosopher could be repeatedly skipped if both
neighbors keep eating in turns.
Mutual Exclusion? ✅ YES — monitor ensures only one procedure executes at a
time.
How to use? [Link](i); EAT;
[Link](i);
5. Side-by-Side Problem Comparison
Feature Bounded-Buffer Readers-Writers Dining Philosophers
Processes Producer, Consumer Readers, Writers 5 Philosophers
Shared resource Circular buffer (N slots) Data set (database) 5 chopsticks (circular)
Key semaphores mutex, full, empty rw_mutex, mutex chopstick[5] or monitor
Main challenge Overflow / Underflow Concurrent read vs Deadlock & starvation
exclusive write
Deadlock risk? Yes (wrong order) Yes (if writer starves) Yes (circular chopstick
grab)
Starvation risk? No (if fair semaphore) Yes (1st or 2nd problem) Yes (monitor solution)
Best solution 3 semaphores Reader-Writer locks Monitor with 3 states
(kernel)
6. Quick Revision Cheat Sheet
Term / Concept In One Line
Bounded-Buffer Problem Producer adds, Consumer removes from shared N-slot buffer. Prevent
overflow, underflow, simultaneous access.
mutex (B-B) Binary semaphore init=1. Ensures only ONE of producer/consumer in
buffer at a time.
full (B-B) Counting semaphore init=0. Consumer waits here when buffer empty.
Producer increments after adding.
empty (B-B) Counting semaphore init=N. Producer waits here when buffer full.
Consumer increments after removing.
Order rule Always wait(resource semaphore) BEFORE wait(mutex). Opposite order
→ deadlock!
Readers-Writers Problem Multiple readers at once is OK. Writer needs exclusive access — no
readers or other writers.
rw_mutex (R-W) Semaphore init=1. Writer grabs it alone. 1st reader grabs it (blocks
writers). Last reader releases it.
mutex (R-W) Semaphore init=1. Only protects read_count update — nothing else.
read_count (R-W) Integer init=0. Counts current readers. NOT a semaphore.
First Reader-Writer Readers have priority → writers may starve.
Page 9
Chapter 7: Synchronization Examples | Classical Problems of Process Synchronization | FAST-NUCES
Second Reader-Writer Writers have priority → readers may starve.
Reader-Writer Lock Kernel primitive solving both variations cleanly.
Dining Philosophers 5 philosophers, 5 chopsticks. Each needs 2 to eat. Avoid deadlock +
starvation.
Naive deadlock All grab left chopstick → circular wait → deadlock!
Remedy 1 Max 4 philosophers sitting at once → at least 1 pair of chopsticks always
free.
Remedy 2 Atomic pickup: grab BOTH or NONE → eliminates Hold and Wait
condition.
Remedy 3 Asymmetric: odd philosophers left-then-right, even right-then-left →
breaks circular wait.
THINKING state Philosopher not hungry — chopsticks not needed.
HUNGRY state Philosopher wants to eat — waiting for both chopsticks.
EATING state Philosopher has both chopsticks — currently eating.
pickup(i) Sets HUNGRY, calls test(i). If can't eat → self[i].wait() (sleep).
test(i) Checks: left NOT eating AND i is HUNGRY AND right NOT eating → set
EATING, signal self[i].
putdown(i) Sets THINKING, calls test(left neighbor) and test(right neighbor) to wake
hungry neighbors.
self[i].wait() Philosopher i sleeps on her OWN condition variable.
self[i].signal() Wakes philosopher i specifically (not all waiting philosophers).
(i+4)%5 Index of LEFT neighbor on circular table of 5. Same as (i-1+5)%5.
(i+1)%5 Index of RIGHT neighbor on circular table of 5. Wraps: (4+1)%5=0.
Monitor: deadlock? No deadlock — test() only allows eating when BOTH neighbors are NOT
eating.
Monitor: starvation? Still possible — a philosopher may be repeatedly skipped by neighbors.
Good Luck, Mahad! — Chapter 7: Synchronization Examples ✓
Bounded-Buffer → Readers-Writers → Dining Philosophers → Monitor Solution
Page 10