CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 5 of 8 · 3 min read

Recovery

A found deadlock must be broken. There are three ways.

Stop threads. The simplest is to terminate all the deadlocked threads. It surely works, but it throws away all their work. A gentler way is to stop them one at a time, and run the detection again after each, until the cycle is gone. This costs a detection run per stop.

Roll back a thread. If a thread saves checkpoints, copies of its state at known good points, it can be sent back to an earlier checkpoint, and released from the resources it took after that point. Databases do this with transactions: the lost transaction is aborted, its changes are undone, and the client is told to try again. MySQL's InnoDB engine detects deadlocks and rolls back a transaction, and the manual says it tries to pick the one that has changed the fewest rows.

Preempt a resource. The system takes one resource from a deadlocked thread and gives it to another, then sends the loser back to a safe state. This works only for resources that can be taken away without harm, such as memory pages that can be saved to disk.

In plain words: Whichever method is used, the system must choose a victim: the thread to stop, roll back, or rob. The common rules for the choice are:

  • the thread that has done the least work, so the least is lost
  • the thread that holds the fewest resources
  • the thread that needs the most more resources before it can finish
  • the thread that is cheapest to restart, for example one that has not changed shared data

There is a danger. If the same thread is picked each time, it may be rolled back forever, and it starves. A standard cure is to count the rollbacks in the cost, so that a thread that has been picked often becomes expensive to pick again.

The Linux kernel uses a simple rule for record locks. TLPI reports that when a fcntl(F_SETLKW) request would close a cycle, the kernel makes one of the blocked calls fail with EDEADLK. On Linux, the process that made the most recent call is chosen, but this is not guaranteed by the standard. A program that uses F_SETLKW must be ready for that error. A test with two processes that lock byte 0 and byte 1 of a file in opposite order showed it: the second request returned error 35, "Resource deadlock avoided", and when the loser released its lock, the other process finished.

Victim

A victim is the thread that the system stops, rolls back, or robs of a resource in order to break a deadlock, chosen so that the cost of recovery is as low as possible and no thread is chosen again and again.

Example: in a database, the transaction that has changed the fewest rows is chosen as the victim and aborted.

Check yourself: 1. What is the difference between stopping a thread and rolling it back? 2. Name two rules for choosing a victim. 3. Why can choosing the same victim each time be harmful?