Differences between current version and previous revision of DiningPhilosophers.
Other diffs: Previous Major Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 3 | Last edited on Monday, October 18, 2004 5:56:19 am | by AristotlePagaltzis | |
| Older page: | version 2 | Last edited on Sunday, March 7, 2004 11:21:16 am | by AristotlePagaltzis | Revert |
@@ -1,10 +1,18 @@
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.
+
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 decide
to lift up their right fork, then trying
to lift up the left fork but block since the left fork
is already taken. If nobody puts down a fork, a
circular dependency of the
waiting condition
on the resources exists
, i.e. a deadlock
.
-;
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.
+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.
