View Source: DiningPhilosophers - Waikato Linux Users Group

Edit PageHistory Diff Info LikePages

A large class of [Synchronisation] problems attempt to deal with allocating a set number of resources among several processes. The DiningPhilosophers problem is an example of this:

    A number of philosophers seated around a circular table spend their lives alternating between thinking and eating.
    Between each pair of neighboring philosophers there is a fork.
    Each philosopher has access to the two forks at his left and right and needs to be in possession of both in order to eat.
    He may only pick up one fork at a time, and attempts to pick up the left one first and then the right one.
    Once done eating, a philosopher puts both forks back down and goes back to thinking.
    Since there are only as many forks as philosophers, it is not possible for everyone to be eating at the same time.

Two main problem classes have to be dealt with:

DeadLock::
    A DeadLock can occur when all philosophers have decided to lift up their right fork. They will try to lift up the left fork but block, since it is already taken. There is now circular dependency of waiting conditions on the resources, i.e. a DeadLock. If nobody puts down a fork, noone can eat.

Starvation::
    Starvation may occur when a number of philosphers conspire to keep eating or always pick up their forks before another philosopher gets the chance to acquire the resources.

In addition to deadlocks and starvation, there are many efficiency issues depending on the way the forks are allocated.

2 pages link to DiningPhilosophers:

Last edited on Monday, October 18, 2004 5:56:19 am by AristotlePagaltzis

Edit PageHistory Diff Info LikePages