8.1.2 Livelock

Figure: Abusing Conditional Locking
\begin{figure}{ \scriptsize
\begin{verbatim}1 void thread1(void)
2 {
3 retr...
...pin_unlock(&lock1);
26 spin_unlock(&lock2);
27 }\end{verbatim}
}\end{figure}

Although conditional locking can an effective deadlock-avoidance mechanism, it can be abused. Consider for example the beautifully symmetric example shown in Figure [*]. This example's beauty hids an ugly livelock. To see this, consider the following sequence of events:

  1. Thread 1 acquires lock1 on line 4, then invokes do_one_thing().
  2. Thread 2 acquires lock2 on line 18, then invokes do_a_third_thing().
  3. Thread 1 attempts to acquire lock2, but fails because Thread 2 holds it.
  4. Thread 2 attempts to acquire lock1, but fails because Thread 1 holds it.
  5. Thread 1 releases lock1, and jumps to retry.
  6. Thread 2 releases lock2, and jumps to retry.
  7. The livelock dance repeats from the beginning.

Quick Quiz 8.4: How can the livelock shown in Figure [*] be avoided? End Quick Quiz

Starvation is very similar to livelock. Put another way, a livelock is an extreme form of starvation where all threads starve.



Paul E. McKenney 2011-12-16