Game Development Reference
In-Depth Information
Figure 20.3
The dining philosophers.
Starvation and deadlock is a condition where one or more threads gains access to a
shared resource and continually blocks access to the starving thread. The classic illus-
tration of this problem is called the dining philosophers
problem, first imagined by
Tony Hoare, a British computer scientist best known for creating the Quicksort algo-
rithm. It goes like this. Five philosophers sit around a circular table, and they are
doing one of two things: eating or thinking. When they are eating, they are not
thinking, and when they are thinking, they are not eating. The table has five chop-
sticks, one sitting between each philosopher. In order to eat, each person must grab
two chopsticks, and he must do this without speaking to anyone else.
You can see that if every philosopher grabbed the chopstick on his left and held onto
it, none of them could ever grab a second chopstick, and they would all starve. This
is analogous to a deadlock.
If they were eating and thinking at different times, one philosopher could simply get
unlucky and never get the chance to get both chopsticks. He would starve, even
though the others could eat. That is similar to process starvation.
The solution to the dining philosophers problem might sound familiar since I men-
tioned something about it in Chapter 5,
'
If you
want to avoid deadlock in any shared resource situation, always ask for resources in a
particular order and release them in the reverse order.
With the dining philosophers, things are a little more complicated because of their
arrangement and how the resources are used. The solution involves numbering the
“
Game Initialization and Shutdown.
”
