The Dining Philosophers Problem

sponsored links

There is always a cold war  between scientists and philosophers. The scientists don't agree what philosophers say and the philosophers don't even bother to understand the words what the scientist is trying to explain. They always have been pulling the leg of each others when ever they get chance. That's the reason why the computer scientists (originally formulated in 1956 by Edsger Dijkstra) named this problem after the philosophers. In this problem there are five philosophers who spend their entire lives thinking and eating. The philosophers share a common circular table surroinded by five chairs, each belonging to one philosopher. In the center of the table there is a bowl of rice, and the table is laid with five single chopsticks. When a philosopher thinks, he does not interact with his colleagues. From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to him (the chopsticks that are between him and his left and reight neighbours). A philosopher may pick up only one chopstick at a time. Obviously, he cannot pick up a chopstick that is already in the hand of his neighbour. When a hungry philosopher has both her chopsticks at the same time, he eats without releasing his chopsticks. When he finished eating, he puts down both of his chopsticks and starts thinking again.

The dining philosophers problem is considered as a classic synchronization problem, neither because of its practical importance, nor because the scientists dislike philosophers (as mentioned above), but because it is an example for a large class of concurrency control problems. It is a simple representation of the need to allocate several resources among several processes in deadlock and starvation free manner.

In short, we can state the "Dining philosopher's problem: as follows :

Devise an algorithm that will allow the philosophers to eat. The algorithm must satisfy mutual exclusion (no two philosophers can use the same form at the same time) while avoiding deadlock and starvation.

The following is a solution that uses semaphores. Each philosopher picks up first fork on the left and then the fort on the right. After the philosopher finishes eating, the two forks are replaced on the table. This solution, also, leads to deadlock. If all the philosophers are hungry at the same time they all sit down, they all pick up the form on their left, and they all reach out fork the other fork, which isn't there. In this undignified position, all philosophers starve.

To overcome the risk of deadlock, we could buy five additional forks or teach the philosophers to each the food with just one fork. As another approach, we could consider adding a footman who allows only four philosophers at a time into the dining room. With at most four seated philosophers at each one philosopher will have access to two forks. This solution is free of dead lock and starvation.

Read complete study material of IBPS IT Officers from here

Sai Spandana Kotturi

sponsored links