Two request threads each need two account locks. One thread locks Account A and waits for Account B. At the same time, the other locks Account B and waits for Account A.

Neither thread can continue:

Neither thread is broken on its own. The problem exists only in the loop between them, which is why deadlocks are invisible when you read either thread's code in isolation.

This is a deadlock: a set of execution contexts cannot make progress because each is waiting for an event that only another member of the same waiting set can cause.

More CPU time does not help. Neither thread is slow, and the required event is not arriving from an external device. Progress requires changing the resource-allocation state, terminating or rolling back work, or preventing the cycle from being created.

Ordinary blocking is temporary:

A thread waits for a disk request, the device completes it, and the thread becomes runnable again.

The event source can make progress independently of the waiter.

In a deadlock, the event sources are themselves waiting:

Both threads may remain asleep forever. If they spin instead of block, they may consume CPU forever without useful progress. Deadlock is defined by the dependency cycle, not by whether waiters sleep or spin.

A long wait is not automatically a deadlock. The owner may be performing slow work and eventually release the resource. Diagnosis must establish that the dependency set has no path to progress.

Suppose two functions acquire the same mutexes in opposite orders:

Many schedules complete successfully. The failure requires a particular interleaving:

Each thread still owns its first lock while waiting for the second. Neither can reach its unlock calls.

The bug can remain hidden during light testing because one thread often acquires both locks before the other begins. Increased concurrency makes the vulnerable interleaving more likely but does not create the underlying defect.

Four conditions must hold simultaneously for this form of resource deadlock. They are often called the Coffman conditions.

Mutual exclusion

At least one resource can be held by only one participant at a time.

In the example, each mutex has one owner. If Account A's protected operation could be performed concurrently without exclusion, waiting for that lock would be unnecessary.

Hold and wait

A participant holds one resource while waiting to acquire another.

Thread 1 keeps Account A locked while requesting Account B. Thread 2 does the reverse.

No preemption

Resources cannot be safely taken away from their owners by an external actor. The owner releases them voluntarily after restoring the protected invariant.

Another thread cannot repair the situation by forcibly unlocking a POSIX mutex it does not own. Doing so violates the mutex contract and can expose partially updated state.

Circular wait

A closed chain of waiting participants exists:

Longer cycles are possible:

All four conditions are necessary. A prevention strategy works by ensuring that at least one cannot hold.

A thread can deadlock with itself by relocking a non-recursive mutex it already owns:

The dependency is:

A thread that owns a mutex then waits for that same mutex is deadlocked against itself.

Error-checking mutexes can report this specific misuse with EDEADLK. Normal or default mutex behavior should not be relied upon to diagnose it.

Changing to a recursive mutex may hide this one acquisition mistake, but it does not solve cycles involving different locks or threads. It can also obscure unclear ownership boundaries. The better repair is usually to define whether the helper requires the caller to hold the lock and make that contract explicit.

A resource-allocation graph represents both participants and resources.

Use:

The two-lock example becomes:

Written as one cycle:

Following the arrows from T1 leads through Lock B to T2, through Lock A, and back to T1.

If every resource type has one instance, a cycle means the participants in that cycle are deadlocked.

With multiple instances of a resource type, a cycle is necessary but may not be sufficient. Another instance held outside the cycle might be released and satisfy one request, allowing the cycle to dissolve.

The graph must model actual allocation semantics. Treating a ten-permit pool as one exclusive resource loses information and can produce an incorrect conclusion.

For single-owner locks, the resource nodes can be removed to create a wait-for graph.

Each node is a thread or transaction. An edge from A to B means A is waiting for a resource currently owned by B.

The two-thread deadlock is:

Deadlock detection becomes cycle detection in a directed graph.

A depth-first traversal can mark each node with three states:

Following an edge to a visiting node finds a cycle in the current traversal path:

Strongly connected component algorithms can identify entire groups in which every participant is reachable from the others. The graph must be updated as resources are acquired, requested, released, or abandoned.

A mutex implementation can know that threads are waiting, but a general operating system does not necessarily understand every application's higher-level resource graph.

The dependency might cross several systems:

No single user-space mutex sees the full cycle.

Database engines can detect transaction deadlocks because they manage lock ownership and transaction rollback. A language runtime may track selected managed locks. The Linux kernel can validate dependencies among kernel lock classes when its lock-debugging facilities are enabled.

There is no universal detector that can infer the meaning of every mutex, queue slot, connection, callback, remote request, and application state transition.

Linux lockdep records dependencies between classes of kernel locks.

If one execution path acquires Lock B while holding Lock A, lockdep learns an edge from Lock A to Lock B. If another path later establishes the reverse order, adding an edge from Lock B back to Lock A, the combined dependency graph contains a cycle. Lockdep can warn about the possibility even if the machine has not experienced the exact simultaneous wait.

This is different from observing a live deadlock:

Early detection is valuable because a problematic pair of lock orders may execute many times without receiving the schedule that makes both threads block.

Lockdep depends on kernel configuration and runtime coverage. It cannot learn a path that never executes, and it does not understand application locks outside the kernel.

Deadlock avoidance uses a stronger distinction than detection.

A safe state has at least one ordering in which every participant can receive its remaining resources, finish, and release what it holds.

An unsafe state has no guaranteed completion ordering under the declared maximum demands. It is not necessarily deadlocked now; participants may request less than their maximum or release resources in a favorable pattern.

A deadlocked state already contains participants that cannot progress because their current waits depend circularly on one another.

Avoidance refuses some requests that are currently satisfiable because granting them would move the system into an unsafe state.

Banker's algorithm models reusable resources with multiple instances. It grants a request only when the resulting allocation remains safe.

For each process, the system knows:

It also knows the currently available resource vector.

The safety test uses a temporary Work vector:

If every process can finish in this simulated sequence, the state is safe. The algorithm does not actually run or terminate the processes during the test.

Consider five processes and three resource types:

Subtracting allocation from maximum gives:

Start with:

P1 can finish because [1, 2, 2] <= [3, 3, 2]. Simulating its completion returns its allocation:

The test can then choose:

One safe sequence is:

The sequence need not match the actual runtime schedule. Its existence proves that a complete order is possible under the declared maximum demands.

Suppose P4 requests [3, 3, 0].

The request is no larger than P4's remaining need and the resources are currently available. A system that checks only current availability could grant it.

After a tentative grant:

Compare every remaining need with [0, 0, 2]:

No safe sequence begins from the tentative state, so Banker's algorithm delays the request.

The state would be unsafe, not necessarily already deadlocked. Avoidance refuses the risk before current waits prove a cycle.

Banker's algorithm requires information that many workloads cannot provide:

Backend requests often discover work dynamically. A request may not know how many locks, file descriptors, remote calls, or bytes of memory it will eventually need.

The algorithm can also delay work even when the requested resources are idle, because it reserves enough flexibility to preserve a safe sequence.

Banker's algorithm remains important because it precisely explains safe-state avoidance. Practical systems more often use targeted policies such as fixed lock ordering, transaction detection and rollback, capacity limits, or restricted acquisition protocols.

Because all four Coffman conditions are necessary, eliminating any one prevents resource deadlock in the protected design.

Reduce mutual exclusion

Immutable data, ownership partitioning, and operations that do not require exclusive state can remove some locks.

Mutual exclusion cannot always be eliminated. Two threads cannot safely perform an indivisible update to the same invariant without some coordination.

Eliminate hold and wait

A participant can acquire every required resource before beginning, or release what it holds before requesting another.

Acquiring everything up front works only when the complete resource set is known. It may also hold scarce resources earlier and longer than necessary.

A try-acquire protocol can release earlier resources when a later acquisition fails, then restart from a clean state. The complete protocol must preserve the operation's invariants and define how retries make progress.

Permit preemption or rollback

Some resources can be reclaimed. A database can abort one transaction, undo its tentative changes, and release its locks. A scheduler can preempt CPU time because execution state is saveable.

An ordinary mutex-protected in-memory update usually cannot be revoked safely at an arbitrary instruction. Recovery requires cooperation or a rollback boundary.

Eliminate circular wait

Assign every lock a stable rank and require nested acquisitions to follow increasing rank:

A cycle would require at least one path to move backward in the order, so enforcing the order prevents the cycle.

Account transfers should lock by a stable account ID, not by transfer direction:

Both A-to-B and B-to-A transfers acquire the lower ID first. The business operation retains its direction, but lock acquisition follows one global order.

The example assumes account IDs are unique and stable. When no natural key exists, define an explicit lock rank rather than comparing unrelated C object pointers.

The function focuses on lock ordering. A production financial system also needs overflow handling, persistence, transaction semantics, and appropriate error recovery.

A lock order prevents deadlock only when every path follows it.

Useful engineering practices include:

Fine-grained locking can improve parallelism, but it also creates more nodes and possible edges in that graph. The design cost is not only the number of mutex operations; it is the number of acquisition relationships developers must keep consistent.

A service that stops making progress may have every affected thread blocked in a lock path.

On Linux, inspect thread state and wait locations:

Trace futex activity:

Several threads remaining in futex waits is evidence of lock waiting, not proof of a cycle. The lock owners may still be running.

A debugger can capture every thread's stack:

Then:

Look for threads stopped in lock acquisition and identify which locks they request. Then determine which threads own those locks and what those owners are waiting for.

Attaching a debugger changes timing and may require ptrace permission. In production, language runtime thread dumps, core dumps, structured lock telemetry, or watchdog-triggered stack capture may be safer.

A lock timeout can keep a request from waiting forever, but expiration proves only that the wait exceeded a duration.

Possible causes include:

Timeouts are still useful as containment and observability tools. A timeout should capture enough ownership and stack information to reconstruct the dependency graph.

Retrying the same operation without changing resource acquisition can recreate the same cycle. A timeout policy must define cleanup, rollback, and whether retrying is safe.

Once a deadlock exists, normal completion cannot break the cycle. Recovery must change the participating set or resource state.

A system can:

Choosing a victim should consider rollback cost, work already completed, resource ownership, retry safety, and user-visible impact.

Database transactions provide a clean recovery boundary because tentative work can be rolled back. Arbitrary application threads usually do not. Forcibly terminating one thread or unlocking its mutex can leave shared memory inconsistent.

Restarting a process releases its kernel-managed resources and resets its address space, but it does not automatically undo external effects already sent to databases, files, or remote services. Recovery design must account for those partial effects.

Deadlock occurs when a set of execution contexts waits on dependencies that only members of the same set can satisfy. Mutual exclusion, hold and wait, no preemption, and circular wait must all hold simultaneously.

Resource-allocation and wait-for graphs make those dependencies explicit. Cycle detection can find current or potential deadlocks when ownership is known. Banker's algorithm instead avoids unsafe states by granting a request only when a complete safe sequence still exists.

Practical prevention usually relies on reducing shared ownership, avoiding hold-and-wait, supporting rollback where possible, and enforcing one global lock order. Recovery must preserve invariants; arbitrary forced unlock is not a safe substitute for a designed transaction or restart boundary.