F.6 Chapter [*]

Quick Quiz [*].1: 
But the definition of deadlock only said that each thread was holding at least one lock and waiting on another lock that was held by some thread. How do you know that there is a cycle?
 
Answer:
Suppose that there is not cycle in the graph. We would then have a directed acyclic graph (DAG), which would have at least one leaf node.

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:

  1. Thread 0 invokes delete(0), and reaches line 10 of the figure, acquiring the lock.
  2. Thread 1 concurrently invokes delete(0), and reaches line 10, but spins on the lock because Thread 1 holds it.
  3. Thread 0 executes lines 11-14, removing the element from the hashtable, releasing the lock, and then freeing the element.
  4. Thread 0 continues execution, and allocates memory, getting the exact block of memory that it just freed.
  5. Thread 0 then initializes this block of memory as some other type of structure.
  6. Thread 1's spin_lock() operation fails due to the fact that what it believes to be p->lock is no longer a spinlock.
Because there is no existence guarantee, the identity of the data element can change while a thread is attempting to acquire that element's lock on line 10!

Paul E. McKenney 2011-12-16