Part 4 of 8 · 2 min read
How often
In plain words: Running the algorithm costs time, and a deadlock that is found late keeps threads and resources stuck. Two questions decide how often to run it: how often a deadlock is likely, and how many threads a deadlock is likely to hold up (OSC).
The choices:
| Rule | Cost | Delay in finding a deadlock |
|---|---|---|
| At every blocked request | Highest | None |
| At fixed intervals | Low | Up to one interval |
| When processor use falls (for example below 40%) | Low | Depends on when the machine looks idle |
OSC mentions the third rule as one example. It works because deadlocked threads sleep, so the machine does less work.
PostgreSQL uses a fourth rule: wait first, and check later. Its setting deadlock_timeout has a default of 1 s. A transaction that cannot get a lock goes to sleep at once, and runs the deadlock check only if it has waited for 1 s. The manual says the check is relatively expensive, and that most waits end before the timeout because the holder finishes. A lock wait that lasts 1 s is rare enough that the check can be run there without a visible cost. A deadlock is therefore found about 1 s after the transactions block.
The Linux kernel does a related thing for hung tasks. On the test machine, /proc/sys/kernel/hung_task_timeout_secs was 120, so the kernel reports a task that has been stuck in uninterruptible sleep for 120 s. The setting hung_task_panic was 0, so the machine does not crash because of it. It is an alarm for a person, and not a recovery.
Deadlock timeout
A deadlock timeout is a delay that a system waits, after a thread has blocked, before it runs the deadlock check, so that the check is skipped when the wait ends by itself.
Example: PostgreSQL waits 1 s on a blocked lock before it searches for a cycle.
Check yourself: 1. Why does PostgreSQL wait before it checks, and not check at once? 2. What is the cost of choosing a longer interval between checks? 3. What does the kernel do when a task has been stuck for 120 s on the test machine?