Dining Philosophers problem

The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things – eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of rice in the center. A single chopstick is placed in between each philosopher, and as such, each philosopher has one chopstick to his or her left and one chopstick to his or her right. It is assumed that a philosopher must eat with two chopsticks. The philosopher can only use a chopstick on his or her immediate left or right.
Illustration of the dining philosophers problem
Illustration of the dining philosophers problem

The philosophers never speak to each other, which creates a dangerous possibility of deadlock when every philosopher holds a left chopstick and waits perpetually for a right chopstick (or vice versa).

Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a ‘cycle of unwarranted requests’. In this case philosopher P1 waits for the chopstick grabbed by philosopher P2 who is waiting for the chopstick of philosopher P3 and so forth, making a circular chain.

Starvation (and the pun was intended in the original problem description) might also occur independently of deadlock if a philosopher is unable to acquire both chopsticks due to a timing issue. For example there might be a rule that the philosophers put down a chopstick after waiting five minutes for the other chopstick to become available and wait a further five minutes before making their next attempt. This scheme eliminates the possibility of deadlock (the system can always advance to a different state) but still suffers from the problem of livelock. If all five philosophers appear in the dining room at exactly the same time and each picks up their left chopstick at the same time the philosophers will wait five minutes until they all put their chopsticks down and then wait a further five minutes before they all pick them up again.

The lack of available chopsticks is an analogy to the locking of shared resources in real computer programming, a situation known as concurrency. Locking a resource is a common technique to ensure the resource is accessed by only one program or chunk of code at a time. When the resource a program is interested in is already locked by another one, the program waits until it is unlocked. When several programs are involved in locking resources, deadlock might happen, depending on the circumstances. For example, one program needs two files to process. When two such programs lock one file each, both programs wait for the other one to unlock the other file, which will never happen.

In general the dining philosophers problem is a generic and abstract problem set used for explaining varied set of problems which hold mutual exclusion as its core idea. For example, as in the above case deadlock/livelock is well explained with this problem set.