Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 66 ยท Synchronization

Dining Philosophers and the Sleeping Barber

Solve two classic synchronization puzzles with semaphores. Compare deadlock-prone and deadlock-free philosophers and simulate a barber shop with limited chairs.

Computer scientists keep a small set of puzzles to test synchronization ideas. Two of them are famous because each captures a different real danger. The dining philosophers show how sharing several resources can deadlock. The sleeping barber shows how to coordinate a server with a limited waiting room, which is how a web server's request queue behaves.

The dining philosophers

Five philosophers sit at a round table. A bowl of food is in the middle and there is one chopstick between each pair of neighbours (five in total). A philosopher alternates between thinking and eating. To eat, she needs both the chopstick on her left and the one on her right. When she finishes, she puts both back.

flowchart TB
    P0(("P0")) --- C0["chopstick 0"] --- P1(("P1")) --- C1["chopstick 1"] --- P2(("P2")) --- C2["chopstick 2"] --- P3(("P3")) --- C3["chopstick 3"] --- P4(("P4")) --- C4["chopstick 4"] --- P0

Philosopher i uses chopsticks i (left) and (i + 1) mod 5 (right).

The obvious solution uses one semaphore per chopstick (all starting at 1):

TEXT
philosopher i:
    wait(chopstick[i])               # pick up left
    wait(chopstick[(i + 1) % 5])     # pick up right
    eat
    signal(chopstick[i]); signal(chopstick[(i + 1) % 5])

Mutual exclusion on each chopstick is guaranteed. But if all five pick up their left chopstick at the same moment, each now waits forever for a right one held by a neighbour: a deadlock (a circular wait). A simulation can count how often that happens and test three repairs:

  • Resource ordering: always take the lower-numbered chopstick first. The last philosopher takes chopstick 0 before 4, which breaks the circle.
  • Limit the table: a semaphore room = 4 allows at most four philosophers to try at once, so at least one can always get two chopsticks.
  • Both or none: pick up chopsticks only if both are free (needs a lock around the check).
Python Three seatings, one deadlock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive strategy deadlocks in a large share of the runs; the other two never do. Starvation is a separate matter: ordering and the room rule prevent deadlock, but a very unlucky philosopher could still be passed over repeatedly. A fair queue on each chopstick fixes that. A monitor-based solution is shown in the monitors lesson.

The philosophers are a model of processes needing several resources at once, for example a thread that needs a database row lock and a file lock. The same cures apply: impose a global lock order, or limit how many contenders enter.

The sleeping barber

A barber shop has one barber, one barber chair, and a waiting room with a fixed number of chairs (say 3).

  • If there are no customers, the barber sleeps in his chair.
  • A customer who arrives wakes the barber if he is asleep.
  • If the barber is busy and a waiting chair is free, the customer sits and waits.
  • If all chairs are taken, the customer leaves without a haircut.

The risks are the usual ones: the barber sleeping while a customer waits (a missed wake-up), two customers taking the same chair, or counting waiting customers wrongly.

Three semaphores solve it. customers counts waiting customers (and wakes the barber), barber signals that the barber is ready, and mutex protects the counter waiting.

TEXT
barber:                         customer:
    loop:                           wait(mutex)
        wait(customers)  # sleep    if waiting < CHAIRS:
        wait(mutex)                     waiting += 1
        waiting -= 1                    signal(customers)  # wake barber
        signal(barber)                  signal(mutex)
        signal(mutex)                   wait(barber)       # my turn
        cut hair                        get haircut
                                    else:
                                        signal(mutex); leave
Python A barber shop with three chairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Served plus left customers always add up to ten, the waiting room never holds more than three, and at the end only the barber is blocked, asleep, waiting for new work. This bounded waiting room is the pattern behind a listen backlog on a network socket, a thread pool's task queue, or a print spooler: when the queue is full, new requests are rejected instead of letting the system be overwhelmed.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can the naive dining-philosophers solution deadlock?

    If all five take their left chopstick first, every one waits for a neighbour's chopstick: a circular wait.
  2. 2. How does a semaphore room = 4 prevent the deadlock?

    With only four contenders for five chopsticks, a circular wait of all of them cannot form.
  3. 3. In the sleeping barber problem, what does a customer do when all chairs are taken?

    The waiting room is bounded. A customer who finds it full leaves, which models rejecting requests when a queue is full.
  4. 4. Which semaphore in the barber solution counts the waiting customers and wakes the barber?

    Each arriving customer signals customers; the barber waits on it, so he sleeps when the count is zero.

Summary

  • Dining philosophers model several processes each needing two or more shared resources; the naive solution deadlocks.
  • Fix it by ordering resources globally, by limiting how many contenders enter, or by taking both resources atomically.
  • The sleeping barber coordinates one server with a bounded waiting room using customers, barber and mutex.
  • Rejecting work when a queue is full is a deliberate design choice, not a bug.

Next: Monitors and Condition Variables