Information Technology Reference
In-Depth Information
Thread 1
Thread 1
Thread 2
lock.acquire()
lock.acquire()
waiting
for unlock
S1
S1
waiting
for unlock
waiting
for unlock
lock.acquire()
S2
S2
waiting
for signal
lock.acquire()
Thread 2
Figure6.4: Two examples of deadlock:mutuallyrecursivelocking(left) and
nestedwaiting(right).
Example: The Dining Philosophers.
The Dining Philosophers problem is a classic synchronization problem that
illustrates the challenge of deadlock. There is a round table with n plates
and n chopsticks arranged as illustrated in Figure 6.5. A philosopher sitting
at each plate requires two chopsticks to eat. Suppose that each philosopher
proceeds by grabbing the chopstick on the left, grabbing the chopstick on the
right, eating, and then replacing both chopsticks. If philosophers follow this
approach they can unfortunately, enter a deadlock: each philosopher can grab
the chopstick on the left but then be stuck waiting for the philosopher on the
right to release the chopstick she holds.
Deadlock v. starvation. Deadlock and starvation are both liveness con-
cerns. In starvation, some thread fails to make progress for an indefinite period
Definition: starvation
of time. Deadlock is a form of starvation but with the stronger condition that a
group of threads form a cycle where none of the threads make progress because
each thread is waiting for some other thread in the cycle. Thus, deadlock im-
plies starvation (literally, for the dining philosophers), but starvation does not
imply deadlock.
For example, recall the readers/writers example discussed in Section 5.6.8.
If instead of implementing a writers-preferred solution we implement a readers-
preferred solution where a reader only waits if a writer is currently active, then
Search WWH ::




Custom Search