Part 3 of 8 · 2 min read
Livelock
In plain words: Page 3 offered pthread_mutex_trylock as a cure for deadlock: if the second lock is busy, give back the first and try again. The cure has a flaw. Suppose two threads each take their first lock, find the second lock held by the other, give back the first lock, and try again at once. They may repeat the same steps in the same rhythm, and never both get through. This is a livelock.
An experiment makes it concrete. Two threads each need two locks, taken in opposite order. Each takes its first lock, holds it for 0.1 ms, tries the second lock with trylock, and on failure unlocks the first lock and starts again. In one version the retry is immediate. In the other, the thread first sleeps for a random time between 0.1 and 1 ms. After 3 s, the number of completed operations was:
| Retry rule | Completed operations in 3 s (three runs) |
|---|---|
| Immediately | 88, 343 and 515 |
| After a random pause | 15,437, 15,611 and 16,142 |
The first version did not stop completely. By luck, now and then one thread got through. But it finished only about 0.5 to 3 per cent as many operations as the second, while the processors were busy all the time, with 18,000 attempts per thread. A person looking at top would have seen full processor use and no useful result.
The cure is to break the symmetry. A random pause makes it unlikely that the two threads will collide again and again. This is also what Ethernet does after a collision: each station waits a random time, and doubles the range after each repeated collision. Another cure is to give the threads different roles, so that one always gives way and the other always keeps going.
Livelock
A livelock is a condition in which threads keep changing state in response to each other, and so use processor time, but none of them makes progress toward finishing its work.
Example: two threads that each give back their lock and retry at once can keep colliding, as in the test above.
Check yourself: 1. How does a livelock differ from a deadlock in processor use? 2. Why did the random pause help? 3. In the first version, why did some operations still complete?