Part 4 of 5 · 2 min read
Breaking a deadlock, and preventing one in advance
Detection reacts after the fact by aborting a victim; prevention avoids the situation from ever arising.
Breaking a deadlock, and preventing one in advance
Think of two approaches to the narrow-alley standoff. One: a traffic officer eventually arrives and orders one driver to reverse out. The other: a rule, agreed in advance, that cars always enter these alleys in a fixed order, so the standoff could never have happened at all.
In plain words: once a deadlock is detected via a cycle in the wait-for graph, the database breaks it by choosing one of the deadlocked transactions, called the victim, and aborting it, releasing its locks so the remaining transaction or transactions can proceed. Deadlock prevention takes a different approach entirely: rather than detecting and reacting to a deadlock after it forms, it imposes a rule in advance, such as requiring every transaction to acquire locks in a fixed, agreed-upon order, that makes the specific circular-wait pattern needed for a deadlock structurally impossible to form.
A worked example. After detecting the earlier A-and-B deadlock, the database aborts transaction B as the victim, releasing B's lock on Y, letting transaction A finally acquire it and proceed; a prevention-based system, by contrast, would have required both A and B to request locks on X before Y in the first place, never allowing the circular wait to form.
The key lines. No new SQL; victim selection and prevention ordering rules are internal policies of the database's lock manager.
Deadlock victim, deadlock prevention
A deadlock victim is the transaction the database chooses to abort to break a detected deadlock, releasing its locks; deadlock prevention imposes a rule in advance, such as a fixed lock-acquisition order, that makes a circular wait impossible to form.
Example: a traffic officer ordering one driver to reverse is detection-and-victim-selection; a pre-agreed entry order for the alleys is prevention.
Remember this
Detection reacts after a deadlock has already formed, aborting a victim to break it; prevention avoids the circular-wait pattern from ever being possible in the first place, usually at the cost of some flexibility in lock-acquisition order.
Quick notes
- A deadlock forms when transactions each hold a lock the other needs, waiting on each other forever.
- A wait-for graph has one node per transaction and an edge for each wait-on relationship.
- A cycle in the wait-for graph proves a deadlock exists among the transactions on that cycle.
- Deadlock detection breaks a found deadlock by aborting one transaction, the victim, to release its locks.
- Deadlock prevention imposes a rule in advance that makes the circular-wait pattern structurally impossible.