Does prevention remove all waiting?

No. Tasks may still wait for resources. The goal is to exclude circular dependencies within the covered model.

Are wait-die and wound-wait identical?

No. They permit different waiting directions and abort different participants when priorities conflict.

Should an application still handle deadlock errors after improving lock order?

Yes. Other code paths, resources or engine behavior can introduce dependencies beyond the simplified rule.

AI Glossary / Data engineering and architecture / Intermediate

Deadlock prevention algorithms

Definition

Deadlock prevention algorithms are rules that stop a group of concurrent tasks from entering a circular wait in which none can proceed. In databases, they govern how transactions acquire locks, wait or restart. Their purpose is to prevent the blocking pattern before it forms, rather than discover and break an existing deadlock.

What it means

A lock protects a resource while a task uses it. Waiting for a lock is often normal: one transaction finishes, releases the lock and lets another continue. A deadlock is different because the waiting tasks depend on one another in a cycle.

For example, one task holds resource A while waiting for B, and another holds B while waiting for A. Neither voluntarily reaches the point where it releases its resource. Prevention changes the rules so that this pattern cannot arise within the resources and operations covered by the rule. The qualification matters: a database policy cannot automatically control unrelated application locks or external services.

How it works

One approach imposes a consistent order on resource acquisition. If every task requests A before B, the two-resource cycle described above cannot form. The order must be observed across all relevant code paths, including exceptional operations.

Database timestamp schemes instead assign transaction priorities. In wait-die, an older requester may wait for a younger holder, but a younger requester encountering an older holder aborts. In wound-wait, an older requester causes a younger holder to abort; a younger requester waits for an older holder. The permitted waiting direction cannot form a cycle when the rules are applied consistently.

These schemes trade waiting and repeated work for freedom from the covered deadlocks. Retaining the original timestamp on restart helps avoid continually making the same transaction the youngest. They do not mean that every database uses either scheme or exposes them as application settings.

Three practical examples

1. An inventory service updates two product rows in increasing product-ID order. Different purchase combinations follow the same ordering rule instead of locking whichever item a user selected first.

2. A database lock manager uses a timestamp policy to decide whether a conflicting transaction waits or restarts. The application must handle the resulting rollback correctly.

3. A multithreaded program documents an order for acquiring two internal mutexes. This applies the same ordering idea to application resources, although database transaction recovery does not manage those mutexes.

Think of it this way

Think of two maintenance teams needing both a ladder and a key. If each takes one and waits for the other, both are stuck. Requiring everyone to request the ladder first removes that particular circular dependency. The analogy is limited because software can have many lock modes, dynamically discovered resources and rollback costs that physical equipment does not capture.

Worked example

Suppose fictional tasks T1 and T2 both need exclusive access to records 10 and 20. Initially, T1 locks 10 while T2 locks 20. T1 then requests 20, and T2 requests 10. Each holds the item required by the other, so the wait forms a cycle.

Now require increasing record order. Both tasks must first request 10. If T1 receives it, T2 waits without holding 20. T1 can obtain 20, perform its work and release both records. T2 can then continue. The tasks still experience contention, but the described deadlock cannot form.

This example assumes these are the only relevant resources and that no later lock upgrade introduces another dependency. In a real system, developers must inspect the actual lock acquisition behavior, not merely the visual order of values in a query. A high-level request does not always reveal every lock acquired by the engine.

Illustrative case study

Fictional case: LockMeadow's booking service sometimes stalls when moving equipment between locations. The ordinary transfer path locks the source first, while a repair path locks the destination first. Under simultaneous use, the paths can request the same pair in opposite orders.

The team adopts one stable ordering rule for both paths and reviews the other operations touching those records. It also keeps transaction retry handling because additional database interactions may still generate deadlocks. Concurrent tests exercise opposing transfers rather than only isolated requests.

The lesson is that prevention depends on a shared rule across participating operations. Fixing one function does not prove that the wider application follows the same discipline.

Common misconceptions and mistakes

Do not confuse prevention with detection and recovery. A database that identifies a cycle and aborts a participant is resolving a deadlock after it forms. A timeout alone does not prove that a circular wait existed.

Avoid assuming that two-phase locking eliminates deadlocks; it can still allow conflicting transactions to wait cyclically. Do not treat freedom from deadlock as a guarantee of fairness, low latency or business correctness. Finally, repeating a failed transaction must account for external effects such as notifications that a database rollback cannot undo.

Business use

Prevention is useful where lock conflicts cause visible delays or repeated failed work. Start by understanding the resources, transaction boundaries and conflict patterns. Compare the cost of maintaining a consistent order with the cost of rollback and retry.

Measure completion time, retry volume and starvation symptoms under realistic contention. Keep transactions focused and avoid waiting for user input while holding locks. Choose techniques supported by the actual system; a textbook algorithm is not automatically an available database configuration option.

Check your understanding

Two tasks always acquire resources in opposite orders. Would a shorter timeout prove their deadlock risk has been removed?

Answer: No. It would shorten some waits but leave the conflicting acquisition pattern. A consistent ordering rule addresses the illustrated cause.

Related terms

Concurrency control
Two-phase locking
Mutex
Deadlock
lock
transaction
wait-for graph
starvation
rollback
retry

Learn next

Learn wait-for graphs next. Draw the tasks and resource dependencies for one concurrent operation, then examine how ordering or timestamp rules change the possible edges. Include retry behavior and any external effects in the review.

Sources

Carnegie Mellon University, Database Systems lecture on Two-Phase Locking, explains timestamp-based prevention and restart priorities: https://15445.courses.cs.cmu.edu/spring2026/slides/18-twophaselocking.pdf

PostgreSQL documentation, Explicit Locking, explains deadlock detection, consistent acquisition order and application retry considerations: https://www.postgresql.org/docs/current/explicit-locking.html

The relevant prevention slides and deadlock documentation were read. The numbered-record example and LockMeadow case are original illustrations.

Previous: De-skilling Next: Deadly triad in reinforcement learning