If this leaf node was a lock, then we would have a thread that was waiting on a lock that wasn't held by any thread, which violates the definition. (And in this case the thread would immediately acquire the lock.)
On the other hand, if this leaf node was a thread, then we would have a thread that was not waiting on any lock, again violating the definition. (And in this case, the thread would either be running or blocked on something that is not a lock.)
Therefore, given this definition of deadlock, there must be a cycle in the corresponding graph.
Quick Quiz .2:
Can the transformation from
Figure to
Figure
be applied universally?
Answer:
Absolutely not!
This transformation assumes that the layer_2_processing() function is idempotent, given that it might be executed multiple times on the same packet when the layer_1() routing decision changes. Therefore, in real life, this transformation can become arbitrarily complex.
Quick Quiz .3:
But the complexity in
Figure
is well worthwhile given that it avoids deadlock, right?
Answer:
Maybe.
If the routing decision in layer_1() changes often enough,
the code will always retry, never making forward progress.
This is termed ``livelock'' (Section )
if no thread makes any forward progress or
``starvation'' (Section
)
if some threads make forward progress but other do not.
Quick Quiz .4:
How can the livelock shown in
Figure
be avoided?
Answer:
This is left as an exercise to the reader.
Figure
provides some good hints.
In many cases, livelocks are a hint that you should revisit your
locking design.
Or visit it in the first place if your locking design
``just grew''.
Quick Quiz .5:
What if the element we need to delete is not the first element
of the list on line 8 of
Figure ?
Answer:
This is a very simple hash table with no chaining, so the only
element in a given bucket is the first element.
The reader is invited to adapt this example to a hash table with
full chaining.
Quick Quiz .6:
What race condition can occur in
Figure ?
Answer:
Consider the following sequence of events:
Paul E. McKenney 2011-12-16