Information Technology Reference
In-Depth Information
Thread 0
Thread 0
waiting
for
owned
by
owned
by
waiting
for
Resource X
Resource X
Resource Y
Thread 1
Resource Y
owned
by
waiting
for
owned
by
owned
by
waiting
for
Thread 1
Thread 2
(a) Single instance of each resource
(b) Multiple instances of one of the resources
Figure6.12: In this graph used for deadlock detection, threads and resources are nodes, and
directed edges represent theownedbyandwaitingforrelationships among them.
before a transaction commits, it verifies that none of the objects it accessed
were modified by other transaction.
Optimistic concurrency control works well for most systems and workloads,
where different transactions usually access different subsets of data. In these
cases, the approach not only eliminates deadlock but also maximizes concur-
rency since threads do not wait for locks. On the other hand, if there are sig-
nificant numbers of conflicting, concurrent transactions, overheads from rolling
back and reexecuting transactions can be high.
Detecting deadlock
There are various ways to detect deadlock.
One simple approach used in some systems is to assume that any thread that
fails to make progress is part of a deadlock. This approach risks false positives
where a non-deadlocked thread is incorrectly classified as deadlocked, but for
some systems an occasional false positive may be an acceptable price to pay for
the simplicity of the approach.
If there are several resources and only one thread can hold each resource at
a time (e.g., one printer, one keyboard, and one audio speaker or several mutual
exclusion locks), then we can detect a deadlock by analyzing a simple graph
where each thread and each resource is represented by a node and where there
is a directed edge from a resource to a thread if the resource is owned by the
thread and a directed edge from a thread to a resource if the thread is waiting
for the resource.
See, for example, Figure 6.12-a.
There is a deadlock if and
only if there is a cycle in such a graph.
