Information Technology Reference
In-Depth Information
Figure6.5: In this example of the dining philosophers problem, there are 8
philosophers, 8 plates, and 8 chopsticks.
writers could starve if the workload includes a large number of readers. Note
that such starvation would not be deadlock|the writers are waiting on the
readers, but the readers are not waiting on the writers.
Nondeterminism. Just because a system might suffer a deadlock or might
starve a thread does not mean that it always will. A system is subject to star-
vation if it is possible for a thread to starve in some circumstances. A system
is subject to deadlock if it is possible for a group of threads to enter deadlock
in some circumstances. Here, the cicumstances that affect whether deadlock or
starvation occurs may include a broad range of factors such as the choices made
by the scheduler, the number of threads running, the workload or sequence of
requests processed by the system, which threads win races to acquire locks, and
which threads are enabled in what order when signals or broadcasts occur.
A system that is subject to starvation or deadlock may be live in many or
most runs and only starve or deadlock for particular workloads or \unlucky"
interleavings. For example, in the mutually recursive locking example in Fig-
ure 6.4, the deadlock only occurs if the threads call the indicated functions at
about the same time, and for the Dining Philosophers problem, philosophers
may succeed in eating for a long time before hitting the unlucky sequence of
events that causes them to deadlock. Similarly, in the readers/writers example,
the readers-preferred solution will allow some writes to complete as long as the
rate of reads stays below some threshold.
