Part 2 of 8 · 2 min read
The method
Think of it this way. A city does not forbid all traffic jams. It sends a traffic officer when one forms, and the officer makes a car back out. This costs nothing on a normal day. The analogy stops in one place: an officer can see the whole junction at once, while a program can see a deadlock only by running a check over its tables.
In plain words: The method has three duties. The system keeps track of who holds and who requests each resource. At some times it runs a detection algorithm over this record. If a deadlock is found, it runs a recovery step to break it. In the best case, the cost on a normal day is the bookkeeping only.
What is the right choice for a given system? MOS puts it as a matter of numbers. If deadlocks happen once in five years, but the machine fails once a week for other reasons, then paying a large cost to prevent deadlocks is hard to defend. The simplest policy, which MOS calls the ostrich algorithm, is to do nothing and hope. Many systems choose this for rare resources. Where a deadlock is common or costly, as in a database that serves many users, the system detects and recovers.
Deadlock detection and recovery
Deadlock detection and recovery is a method in which the system places no restriction on how threads request resources, periodically runs an algorithm to find deadlocked threads, and breaks each deadlock by stopping a thread, rolling it back, or taking a resource away.
Example: a database lets transactions lock rows in any order, finds a cycle of waiting transactions, and aborts one of them.
Check yourself: 1. What are the three duties of a system that uses detection and recovery? 2. When can the "do nothing" policy be the best engineering choice? 3. Why is detection free of cost on days without deadlocks only in the best case?