The Dining Philosophers Problem in concurrent programming

Posed and solved by Edsger Dijkstra in 1965, the Dining Philosophers Problem is a classic problem in Concurrent Programming and is often used to illustrate synchronization issues and techniques for resolving them.

Five silent philosophers are sitting around a circular table. They never talk to each other, spending their time thinking. In the middle of the table is a bowl of rice. Between each pair of adjacent philosophers, there is a chopstick and they have agreed that each will only use the chopstick to his immediate right and left when eating from the bowl of rice. So unfortunately, as philosophy is not as well paid as computing, the philosophers can only afford five chopsticks laid out on the table such that the first philosopher’s right chopstick is the left chopstick of the second philosopher, whose right chopstick is the left chopstick of the third philosopher and so forth.

In order to eat, a philosopher has to have a pair of chopsticks so when he becomes hungry, he attempts to pick up to two chopsticks closest to him. Each philosopher can only pick up one chopstick at a time. If one of the chopsticks is already being used, the philosopher must wait for it to become available. When he has both chopsticks, he eats, without putting down them. Eating is not limited by the amount of rice left, so an infinite food supply is assumed. When he is done eating, he puts both chopsticks down and resumes thinking about the nature of the universe and circle repeats itself.

The problem is how to design a discipline of behaviour that will allow the five philosophers to share the five chopsticks and eat without letting any philosopher starve from prolonged lack of access to chopsticks, so that the philosophers can forever continue to alternate between eating and thinking.

A Java implementation of the problem for five diners (each represented by a thread) will follow in subsequent posts.