CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 2 of 8 · 2 min read

Telling them apart

Think of it this way. A restaurant can stop serving for different reasons. All waiters may stand at the kitchen door, each waiting for another to move (deadlock). Two waiters may step left, then right, then left again in the corridor, forever blocking each other (livelock). One table may be forgotten while the others are served again and again (starvation). The analogy stops in one place: in a restaurant a manager sees the whole room, while a program must be diagnosed from outside, with tools.

Three questions sort the cases:

Question Deadlock Livelock Starvation
What are the threads doing? Asleep, using no processor time Running, using processor time The victim waits; others run
Is anyone making progress? No No Yes, except the victim
Does waiting ever end? Never Only by luck Only if the load changes

In plain words: Look at the processor use of the hung program with top, and at the state of its threads. A program with zero processor use and threads in futex_do_wait (page 1) is a deadlock or a missed wake-up. A program that uses a full processor and prints nothing is a livelock or an endless loop. A program that is busy but one request never completes is starvation.

Starvation

Starvation is the condition in which a thread that is ready to run, or waiting for a resource, is passed over again and again so that it makes no progress, while other threads continue to run.

Example: a low-priority job that is always outranked by new high-priority jobs never gets the processor.

Check yourself: 1. Which of the three uses no processor time? 2. In which of the three does the rest of the system keep working? 3. What tool and what file would you look at first to tell a deadlock from a livelock?