← 🔒 Synchronization & Concurrency
Subtopic 4 of 5

3.4Classic problems

The idea

The classic problems are templates: bounded buffer (producer-consumer), readers-writers and dining philosophers. Most exam questions give you one with a bug.

Think of it like this: A pizza counter: cooks put pizzas on a shelf with n spots, waiters take them. Cooks wait when it is full, waiters when it is empty, and only one person touches the shelf at a time.

Why it exists

They contain every typical mistake: forgetting a lock, taking locks in the wrong order, starving a class of users.

How it works

  1. Bounded buffer: empty = n, full = 0, mutex = 1.
  2. Producer: P(empty), P(mutex), put, V(mutex), V(full). Consumer: P(full), P(mutex), take, V(mutex), V(empty).
  3. The two "counting" semaphores come before the mutex; otherwise a sleeping producer can hold the mutex.
  4. Philosophers: break the circular wait (n − 1 seats, ordered forks, or pick up both together).

Worked example: The producer does P(mutex) then P(empty), and the buffer is full

The producer holds mutex and sleeps waiting for empty. The consumer needs mutex to free a slot, so it blocks too: deadlock.

Now play with it

  • →Load the producer-consumer scenario and run the consumer first: it blocks on full.
  • →Think about which swap of two lines would make this deadlock.
Prod
P(empty)
P(mutex)
in
out
V(mutex)
V(full)
Cons
P(full) (blocked)
P(mutex)
in
out
V(mutex)
V(empty)
semaphore empty1
semaphore full0
semaphore mutex1
Threads in critical section0
Statusrunning
No steps yet.

empty counts free slots, full counts items. The consumer cannot run until the producer has signalled full. P(s) waits until s > 0 then decrements; V(s) increments.

ProblemSemaphoresCommon mistake
Producer-consumer (buffer n)empty = n, full = 0, mutex = 1P(mutex) before P(empty): the producer sleeps holding the mutex and the consumer can never enter
Readers-writersmutex (protects readcount), wrt = 1reader-preference can starve writers
Dining philosophersone semaphore per forkeveryone takes the left fork: circular wait

Philosophers fix: at most n − 1 seated, pick up both forks together, or one philosopher picks up in the opposite order.

Check yourself

In the bounded-buffer solution the semaphore "full" is initially

Remember: empty = n, full = 0, mutex = 1; counting semaphores first, mutex innermost. Philosophers: break circular wait.
Exam notes (the dense version)

Producer-consumer (bounded buffer of n): semaphores empty = n, full = 0, mutex = 1; the producer does P(empty), P(mutex), add, V(mutex), V(full). Taking mutex before empty can deadlock. Readers-writers: many readers or one writer; the first reader locks writers out and the last one lets them back in; reader-preference can starve writers. Dining philosophers: if every philosopher grabs the left fork first, all can hold one fork and deadlock; fixes: allow at most n − 1 at the table, pick up both forks atomically, or make one philosopher left-handed (resource ordering).

Previous year questions: Synchronization & Concurrency (10)

PYQs are grouped by topic, so this is the full set for Synchronization & Concurrency; try the ones that match this subtopic. Open all 10 on the topic page.