Threading homework — The dining philosophers

In a recent post, The ABCs

of Synchronization for Intermediate Users, I mentioned a homework assignment that

went with the article. As Tomáš later told me, the dining philosophers problem

is a textbook exercise.

The assignment (original English)

Five philosophers sit around a circular table. Each philosopher alternates between

thinking and eating rice. In front of each philosopher is a bowl of rice that is

constantly replenished by a dedicated waiter. Exactly five chopsticks are on the table,

with one chopstick between each adjacent pair of philosophers. Each philosopher must pick

up both chopsticks adjacent to his/her plate simultaneously before that philosopher can

eat.

Create a Java application that simulates this behavior. Avoid deadlock and the problem of

indefinite postponement, where one of more philosophers soon starve because philosophers

adjacent to the starving philosophers are always eating. Make sure that mutual exclusion

is enforced, so that two adjacent philosophers do not use the same chopstick at the same

time.

Approach

I’ll admit the problem caught my interest, and I didn’t want to leave it alone

until I’d programmed a solution. My approach

uses a pool of chopsticks.

When a philosopher wants to eat, they “ask” the table for chopsticks, and the table delegates the request to the pool. If no chopsticks are available, the thread (the philosopher) stops and joins a queue. When a philosopher returns the chopsticks, the waiting threads wake up. If a thread is at the front of the queue and its chopsticks are free, it gets them back. The program prints each step to the console.