Dining- Philosophers Problem

Dining-Philosophers-Problem:

  • The Dining philosophers problem is an illustrative example of a common computing problem in concurrency. It is a classic multi-process synchronization problem.

Problem:

  • The dining philosophers problem is summarized as five silent philosophers sitting at a circular table doing one or two things: eating or thinking. While eating, they are not thinking, and whire thinking, they are not eating.
  • A large bowl of spaghetti is placed in the center, which requires two forks to serve and to eat (the problem is therefore sometimes explained using rice and chopsticks rather than spagnetti and forks).
  • A fork is placed in between each pair of adjacent philosophers, and each philosopher may only use the fork to his left and the fork to his right. However, the philosophers do not speak to each other.

Issues:

Dead lock:

  • Deadlock would arise if every philosopher held a left fork and waited perpetually for a right fork (or vice versa). Originally used as a means of illustrating the problem of deadlock, this system reaches deadlock when there is a "Cycle of unwawarranted requests".
  • In this case philosopher P1 waits for the fork grabbed by philosopher P2 who is waiting for the fork of philosopher P3 and so fourth, making a circular chain.

Resource starvation:

  • It might also occur independently of deadlock if a particular philosopher is unable to acquire both forks because of a timing problem.
  • For example there might be a rule that the philosophers put down a fork after waiting five minutes for the other fork to become available and wait a further five minutes before making their attempt.
  • This scheme eliminates the possibility of deadlocks (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 sametime and each picks up the left fork at the same time the phiolosophers will wait five minutes until they all put their forks down and then wait a further five minutes before they all pick them up again.

Mutual Exclusion:

  • It is the core idea of the problem, and the dining philosophers create a generic and abstract scenario useful for explaining issues of this type.
  • These issues are studied in the branch of Concurrent Programming. The original problems of Dijkstra were related to external devices like tape drives.
  • However, the difficulties studied in the Dining Philosophers problem arise far more often when multiple processes access sets of data that are being updated.
  • Systems that must deal with a large number of parallel processed, such as operating system kernals, use thousands of locks and synchronizations that require strict adherence to methos and protocols if such problems as deadlock, starvation, or data corruption are to be avoided.

Dining-Philosophers-Problem - Presentation:

 

 

From the Web

Suggestions: (1)
Loading...

See few results | more results

Search: [Press Enter]

Share |