Classic problems: bounded buffer, readers–writers, dining philosophers

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. A semaphore for ordering starts at? from Lesson 3.2.1
2. Final value of a semaphore? from Lesson 3.2.1
3. In producer–consumer, when must the producer wait? from Lesson 1.2.2

1 · The Hook

Three stories appear again and again in GATE: a bakery shelf with limited space (bounded buffer), a notice board that many can read but only one can edit (readers–writers), and five philosophers with five chopsticks (dining philosophers). Each one shows a different danger, and the exam usually asks what goes wrong when one line is moved.

3 · Core Concept

Predict First — the answer

It takes the mutex, then sleeps on full while holding the mutex. The producer can never get the mutex to add an item: deadlock.

In plain words

Each classic problem is a pattern to copy. Bounded buffer: count the empty and full slots with two counting semaphores and guard the buffer with a mutex. Readers–writers: the first reader locks out writers and the last reader lets them back in. Dining philosophers: if everyone grabs the left chopstick first, everyone can end up stuck.

1. Bounded buffer (producer–consumer with N slots)

Semaphores: mutex = 1, empty = N (free slots), full = 0 (filled slots).

Producer:                    Consumer:
  wait(empty);                 wait(full);
  wait(mutex);                 wait(mutex);
  add item to buffer;          remove item from buffer;
  signal(mutex);               signal(mutex);
  signal(full);                signal(empty);

• Always do the counting wait first, then the mutex. Swapping the two waits in the consumer deadlocks on an empty buffer; swapping them in the producer deadlocks on a full buffer.
• Swapping the two signals is harmless.

2. Readers–writers (first version: readers have priority)

Many readers may read together; a writer needs the data alone. Semaphores: rw = 1 (writers' lock), mutex = 1 (protects read_count), and read_count = 0.

Writer:                      Reader:
  wait(rw);                    wait(mutex);
  write;                       read_count++;
  signal(rw);                  if (read_count == 1) wait(rw);   // first reader locks writers out
                               signal(mutex);
                               read;
                               wait(mutex);
                               read_count--;
                               if (read_count == 0) signal(rw); // last reader lets writers in
                               signal(mutex);

• Readers overlap; a writer is always alone.
• Writers can starve: while readers keep arriving, read_count never reaches 0. (A second version gives writers priority and can starve readers.)

3. Dining philosophers

Five philosophers sit at a round table with one chopstick between each pair (chopstick semaphores all 1). To eat, a philosopher needs both neighbouring chopsticks.

wait(chop[i]);  wait(chop[(i+1) % 5]);   // left, then right
eat;
signal(chop[(i+1) % 5]);  signal(chop[i]);

If all five pick up their left chopstick at once, each waits for ever for the right one: deadlock. Fixes:

• Allow at most 4 at the table at a time (a counting semaphore room = 4).
• Asymmetry: one philosopher (or every odd one) picks the right chopstick first.
• Pick up both chopsticks only when both are free (inside a critical section).

At most ⌊5/2⌋ = 2 philosophers can eat at the same time.

4 · Visual

Five philosophers, five chopsticks. Philosopher i needs c(i) on one side and c(i+1) on the other; if all take one side first, all wait.

5 · Worked Examples

Example 1 Easy

A bounded buffer has 8 slots. Initial values of empty, full and mutex?

Solution

empty = 8, full = 0, mutex = 1.

Example 2 Medium

In the readers–writers solution, why does only the first reader do wait(rw)?

Solution

Once one reader holds rw, writers are already locked out; later readers just add to read_count. The last reader releases rw.

Example 3 GATE

The producer is written as wait(mutex); wait(empty); add; signal(mutex); signal(full); (the consumer is correct). When can this deadlock?

Solution

When the buffer is full: the producer takes the mutex and sleeps on empty; the consumer can't get the mutex to remove an item.

6 · GATE Traps

• Order of waits matters (counting first, mutex second); order of signals does not.
• First readers–writers: readers can lock writers out for ever (writer starvation), not the other way round.
• Dining philosophers deadlock needs all philosophers to grab the same side first.
• "At most 4 at the table" works because then at least one philosopher can get both chopsticks.

7 · Memory Hook

"Count first, lock second. First reader locks, last reader unlocks. Break the circle of philosophers."

8 · Connect the Dots

Semaphores are powerful but easy to misuse: one swapped line causes deadlock. The next lesson introduces monitors, which let the compiler handle the locking, and collects a step-by-step method for GATE's "analyse this concurrent code" questions.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Bounded buffer

In the consumer, wait(full); wait(mutex); is changed to wait(mutex); wait(full);. What can happen?

1. (A) Two consumers remove the same item
2. (B) Nothing changes
3. (C) Deadlock when the buffer is full
4. (D) Deadlock when the buffer is empty

Q2 · NAT · 1 mark(s) — Initial values

A bounded buffer has 12 slots. Initial value of the semaphore empty?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Readers–writers

In the first (reader-priority) readers–writers solution, who can starve?

1. (A) Readers
2. (B) Writers
3. (C) Neither
4. (D) Both equally

Q4 · NAT · 1 mark(s) — Philosophers

Five dining philosophers: what is the maximum number that can eat at the same time?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Philosophers

Which changes prevent deadlock in the dining philosophers (each normally picks left, then right)?

1. (A) A philosopher picks up both chopsticks only when both are free
2. (B) Allow at most 4 philosophers at the table
3. (C) One philosopher picks right first, then left
4. (D) Every philosopher picks right first, then left

10 · Rule Card

• Bounded buffer: mutex = 1, empty = N, full = 0; counting wait before mutex wait; signals in any order.
• Readers–writers (reader priority): first reader waits on rw, last reader signals rw; writers may starve.
• Dining philosophers: all left-first → deadlock; fixes: ≤ 4 at table, asymmetry, both-at-once. Max ⌊n/2⌋ eat together.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

bounded-buffer problemempty/full/mutex semaphoresorder of waitsreaders–writers problemread_countwriter starvationdining philosophersdeadlock fixes for the philosophers