Process Synchronization – IX – Dining Philosophers Problem

In the previous post, we discussed the Reader-Writers Problem, which is one of the classical problems of synchronization. 

In this post, we shall discuss the Dining Philosophers problem (first proposed by EW Dijkstra), which is a simple representation of a large class of concurrency-control problems. In these types of problems, the primary task is to allocate several resources among several processes in a deadlock-free and starvation-free manner.

PROBLEM STATEMENT

The problem can be summarized in the following steps:

  • Consider five philosophers who spend their lives thinking and eating.
Dining Philosophers Problem - 5 philosophers sitting around a round table with 5 chopsticks
Dining Philosophers Problem – 5 philosophers sitting around a round table with 5 chopsticks

  • The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher.
  • In the centre of the table is a bowl of rice, and the table is laid with five single chopsticks.
  • When a philosopher thinks, (s)he does not interact with her colleagues.
  • From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to him/her (the chopsticks that are between her and her left and right neighbours).
  • A philosopher may pick up only one chopstick at a time. Obviously, she cannot pick up a chopstick that is already in the hand of a neighbour. (No Race Condition)
  • When a hungry philosopher has both her chopsticks at the same time, she eats without releasing the chopsticks.
  • When (s)he is finished eating, she puts down both chopsticks and starts thinking again.

Thus each philosopher alternates between eating and thinking. The problem is to design a solution (a concurrent algorithm), such that no philosopher will starve, i.e. each philosopher can continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.

SOLUTION

The basic idea behind the Dining Philosophers Problem is to ensure that:

  • Resource Starvation doesn’t occur.
    • Note that Resource starvation can also occur independently of a deadlock if a particular philosopher is unable to acquire both forks because of a timing problem.
  • Mutual Exclusion occurs.
    • This is inbuilt in the statement of the problem.
    • Failures of philosophers → analogous to the difficulties arising in real computer programming when multiple programs need exclusive access to shared resources.

Code Discussion

  • All the chopsticks are represented with an array of semaphores all initialized to 1.
  • Whenever a philosopher wants to eat, he/she acquires first the chopstick to the left of it, and then the chopstick to the right of it.
  • It eats for a while, then releases the chopsticks and thinks.

Though this solution guarantees that no two neighbouring philosophers will be eating simultaneously, still it is not an accepted solution because a deadlock can still occur.

  • Suppose that all five philosophers become hungry at the same time and each grabs her left chopstick. All the elements of chopstick will now be equal to 0. When each philosopher tries to grab his/her right chopstick, (s)he will be delayed forever.

SOLVING THE DEADLOCK PROBLEM

We can use several remedies to solve the deadlock problem.

  • Allow at most four philosophers to be sitting simultaneously at the table.
    • This means that for N chopsticks, only N-1 philosophers allowed to compete for them.
    • This ensures that at least one of them will succeed to acquire both the chopsticks, however rigid the protocol be.
  • Allow a philosopher to pick up his/her chopsticks only if both chopsticks are available (to do this, (s)he must pick them up in a critical section).
  • Use an asymmetric solution—that is, an odd-numbered philosopher picks up first his/her left chopstick and then her right chopstick, whereas an even numbered philosopher picks up her right chopstick and then her left chopstick.

A deadlock-free solution does not necessarily eliminate the possibility of starvation.

An acceptable solution to the dining philosophers problem is the one that guards not only against deadlock, but also against the possibility that one of the philosophers might starve to death.
In the next post, we will discuss Process Scheduling. Until then, keep reading and sharing!! 🙂
Sources: 1, 2