Subject: Operating System

Topic: Process Concurrency

Difficulty: High

Problem: Five philosophers live in a house, where a dining table has been laid for them. The five philosophers have agreed to eat only spaghetti considering the fact that it is the best for their lifestyle and health. All the philosophers require two forks to eat. The table is arranged as shown below:

The eating arrangements are as follows: a round table as above where five plates of spaghetti are kept for each philosopher and five forks.

• A philosopher who wishes to eat goes to his/her assigned place on the table and eats the spaghetti plate in front of him using the two forks before him.
• The Aim of the Dinging philosopher’s problem is to allow all the philosophers to eat.

• It must also satisfy the principles of mutual exclusion (no two philosophers can use the same fork at the same time) while avoiding deadlock and starvation.

  Solution (using Semaphores):

• Over here, each philosopher picks up the fork on his left first and then the fork on his right.

• After the philosopher finishes eating, the fork is replaced back on table.
• However if all the philosophers sit down together, and all pick up the left fork, and then reach out to the other fork which is not present for anyone and they go on waiting indefinitely (deadlock).
• To overcome this, we can buy five additional forks

OR

• We could place an attendant or helper (monitor) who allows only four philosophers at a time into the room.

Because of this monitor, at least one philosopher would get access to two forks.

• This can be implemented using a semaphore initialized to N-1 value where N is the number of philosophers present.
• The pseudocode can be given as:
  • Solution using monitors:

Solution using monitors:

• A monitor is used to control access to state variables and condition variables.
• The fork and the spaghetti are not part of the monitor.
• Monitor procedures are defined for the actions of obtaining the forks and putting them down.
• These are used as entry and exit segments for program segments (here philosophers) which actually use the forks.
• The number of the philosophers is given by NUM_PHILO.
• A philosopher can be one of the three states THINKING, EATING, HUNGRY.
• For each philosopher, there is going to be condition variables where the philosopher will WAIT if he/she is hungry but one or both of the forks are unavailable.
• If a philosopher wants to eat, he will check the state of his neighbours and will eat of both his neighbours are not eating. Else he will wait.
• A philosopher who has finished eating will give his neighbour a chance to eat, if they are hungry and their other chopstick is free.