Dining Philosophers Example

Using Semaphores: SpEx-JML , All sources

This is an example of a classic dining philosophers problem: n philosophers sit at a round table with n forks interleaved between them. Each philosopher thinks for a while, gets hungry, tries to eat, then thinks again, and so on. A philosopher needs both forks to eat: the right one and the left one. Only one philosopher at a time can use a fork. Proper synchronization is used to coordinate the use of forks so that all pholosophers can eat, without deadlocks or starvation.

This particular dining philosophers example is taken from Stephen Hartley book "Concurrent Programming".

Philosopher.java implements a philosopher that eats (takes forks) and thinks (puts forks) in a cycle. DiningServer.java implements a monitor that controls synchronization: when a philosopher becomes hungry, it requests forks from the dining server, that checks availability of forks. Each fork is represented by a binary semaphore (implemented by BinarySemaphore.java). The hungry philosopher tries to pick up its left fork first, and if it's taken, the philosopher is blocked. After obtaining the left fork, the philosopher tries to pick up the right fork. If not available, the philosopher blocks, retaining the left fork. Without the room counting semaphore (implemented by CountingSemaphore.java) this version of dinig philosophers deadlocks if all philosophers pick up their left fork. The room semaphore controls the number of philosophers allowed into the room to eat. To avoid a deadlock, at most all but one philosophers are allowed to attempt eating.

The version of DinigServer.java has been slightly modified, to allow all philosophers in a room to eat. We changed initialization of room from

room = new CountingSemaphore(numPhils-1);

to

room = new CountingSemaphore(numPhils);

This was done to produce a deadlock in the system. You can easily correct it back to produce a deadlock-free version of the DiningSever.