Deadlock Management in Multi-Process Systems

Posted on Jan 15, 2025 in Computers

In a multi-process system, a deadlock is an undesirable situation that occurs in a shared resource environment. It happens when a process waits indefinitely for a resource held by another process.

For example, consider a set of transactions {T₀, T₁, T₂, …,T_n}. T₀ needs resource X, which is held by T₁. T₁ waits for resource Y, held by T₂. T₂ waits for resource Z, held by T₀. All processes are waiting for each other, and none can finish. This is a deadlock.

Deadlocks are detrimental to a system. When a system is in a deadlock, the involved transactions are either rolled back or restarted.

Deadlock Prevention

To prevent deadlocks, the DBMS rigorously inspects all operations before transactions execute. It analyzes if they could lead to a deadlock. If a potential deadlock is detected, the transaction is not allowed to execute.

Some deadlock prevention schemes use timestamp ordering of transactions to predict potential deadlocks.

Wait-Die Scheme

In this scheme, if a transaction requests a lock on a resource already held by another transaction with a conflicting lock, one of two things happens:

• If TS(T_i) < TS(T_j) (T_i is older than T_j), T_i waits until the resource is available.

• If TS(T_i) > TS(T_j) (T_i is younger than T_j), T_i dies and is restarted later with a random delay but the same timestamp.

This scheme allows older transactions to wait but kills younger ones.

Wound-Wait Scheme

In this scheme, if a transaction requests a lock on a resource already held by another transaction with a conflicting lock, one of two things happens:

• If TS(T_i) < TS(T_j), T_i forces T_j to roll back (T_i wounds T_j). T_j is restarted later with a random delay but the same timestamp.

• If TS(T_i) > TS(T_j), T_i waits until the resource is available.

This scheme allows younger transactions to wait. When an older transaction requests a resource held by a younger one, the older transaction forces the younger one to abort and release the resource.

In both cases, the transaction that enters the system later is aborted.

Deadlock Avoidance

Aborting a transaction is not always practical. Deadlock avoidance mechanisms can detect potential deadlocks in advance. Methods like the wait-for graph are suitable for systems with lightweight transactions and fewer resource instances. In larger systems, deadlock prevention techniques may be more effective.

Wait-for Graph

This method tracks potential deadlocks. A node is created for each transaction. When transaction T_i requests a lock on item X held by T_j, a directed edge is created from T_i to T_j. When T_j releases X, the edge is dropped, and T_i locks the item.

The system maintains this graph for every transaction waiting for resources. It checks for cycles in the graph.

Two approaches can be used:

• First, do not allow requests for items already locked by another transaction. This can cause starvation, where a transaction waits indefinitely for a resource.

• Second, roll back one of the transactions. It’s not always feasible to roll back the younger transaction, as it may be more important. An algorithm selects a transaction to abort, known as the victim, and this process is called victim selection.