Dining Philosophers Problem in Operating Systems | OS Tutorials

Dining Philosophers is a very famous problem in concurrency in operating systems, originally proposed by Tony Hoare based on an exam question set by Dijkstra. Four (or five) philosophers meet over a shared bowl of noodles. One chopstick is laid between each place (ie, 5 chopsticks), but two chopsticks are needed to eat the noodles.

Dining Philosophers Problem

A philosopher can only use the chopsticks immediately on his or her left and right. The chopsticks are picked up from the table for eating, then replaced when finished, so the next philosopher can use the same chopsticks. Figure 1 illustrates the concept of dinning philosopher problem.

Each philosopher alternately eats and thinks for random periods of time. As they do.

General Solution to Problem

All philosophers execute the same algorithm (which doesn’t work):

Procedure phil()
  repeat
      think for a random time
      take_chopstick(left)
      take_chopstick(right)
      
      eat for a random time
      
      putDown_chopstick(left)
      putDown_chopstick(right)
  forever
End

Procedure phil()
  repeat
      think for a random time
      take_chopstick(left)
      take_chopstick(right)
      
      eat for a random time
      
      putDown_chopstick(left)
      putDown_chopstick(right)
  forever
End

What’s Wrong With This Approach?

Suppose all of the philosophers pick up their left chopsticks at the same time. As all chopsticks have been picked up, no philosopher can subsequently pick up a right chopstick, so all will starve to death. This is considered a Bad Thing.

A Few More Attempts at a Solution

In an attempt to “fix” the previous algorithm, the following solutions may be suggested…

• First pick up the left chopstick, then check if the right one is available. If not, then delay (sleep? block?) for a random period of time and try again.
  • Easy to implement in the take_chopstick routine.
  • Exercise: what’s the obvious flaw with this?
• Put the first chopstick back if the second is unavailable
  • Complicates the take_chopstick routine. After a philosopher has put the chopstick back, then what?
• One philosopher (but which one?) picks up the right chopstick first!
  • Provides an untidy, unsymmetrical solution.
  • Does it work anyway???
• Only allow (n-1) philosophers to sit down at a table set for n philosophers. In our case, only allow 3 philosophers at the table set for 4.
  • This works, but adds an extra restriction that wasn’t in the original specification.
  • In other words, it’s not in the “spirit” of the problem as stated.

Solution using Semaphores

Specify one semaphore per philosopher, and in this:

Semaphores: 0, 1, 2, 3 all initialised to 1

1  Procedure phil(i)   //phil(i) uses chopstick i and chopstick i+1
2     repeat
3         think(random)
4         down(i)
5         down(i+1)

6         eat(random)

7         up(i)
8         up(i+1)
9     forever
10 End

Semaphores: 0, 1, 2, 3 all initialised to 1

1  Procedure phil(i)   //phil(i) uses chopstick i and chopstick i+1
2     repeat
3         think(random)
4         down(i)
5         down(i+1)

6         eat(random)

7         up(i)
8         up(i+1)
9     forever
10 End

What’s Wrong With This?

This solution is the same as the first stupid suggestion. If all philosophers execute a down on their left chopstick at the same time (ie. context switches all happen immediately after the down(s[i])), they will still all starve – with a left chopstick in their hands.

A Workable Solution using Semaphores

Instead of specifying one semaphore per philosopher, use a single mutex semaphore to ensure only one philosopher is attempting to pick up chopsticks at any time. All philosophers execute the same algorithm:

Procedure phil()  // philosopher(i) uses chopstick i and chopstick i+1
    repeat
        think(random)
        down(mutex)
        take_chopstick(i)
        take_chopstick(i+1)
        eat(random)
        putDown_chopstick(i)
        putDown_chopstick(i+1)
        up(mutex)
    forever
End.

Procedure phil()  // philosopher(i) uses chopstick i and chopstick i+1
    repeat
        think(random)
        down(mutex)
        take_chopstick(i)
        take_chopstick(i+1)
        eat(random)
        putDown_chopstick(i)
        putDown_chopstick(i+1)
        up(mutex)
    forever
End.

Interestingly, this solution is correct – no philosopher will starve to death. However, it has the problem that only a single philosopher can be eating at a time, which is obviously wasteful of system resources. A still-better solution is needed!

Solution Using MUTEX

As well as a semaphore per philosopher (organized as an array from s[0] to s[n-1] for n philosophers), we introduce different states for each – they can be THINKING, HUNGRY, or EATING. These values are stored in shared memory, therefore accessible to all of the philosophers. We also have a single mutex semaphore.

Procedure phil()  // main program for philosopher(i)
    repeat
        think(random)
        take_chopsticks(i)
        eat(random)
        putDown_chopsticks(i)
    forever
End.

Procedure phil()  // main program for philosopher(i)
    repeat
        think(random)
        take_chopsticks(i)
        eat(random)
        putDown_chopsticks(i)
    forever
End.