Strategies for Preventing and Avoiding Deadlocks in Databases

This assignment addresses the concept of deadlocks in database management systems (DBMS). A deadlock is defined as a situation where two or more transactions are blocked indefinitely, waiting for each other to release resources. The solution then explores strategies to deal with deadlocks. The document discusses deadlock prevention techniques, focusing on timestamp ordering mechanisms like Wait-Die and Wound-Wait schemes. In the Wait-Die scheme, the older transaction waits, while the younger one dies and restarts. The Wound-Wait scheme allows the newer transaction to wait but forces the older transaction to abort the newer one. The assignment also covers deadlock avoidance using a wait-for graph, detailing approaches to prevent or resolve resource contention. Overall, the assignment provides a comprehensive understanding of deadlocks and methods to manage them within a database environment.

Q) What is a deadlock, and how can it be avoided? Discuss several strategies for dealing with
deadlocks.
Ans:
Deadlock:
Deadlock situation occur when there is a multiple processes are processed simultaneously by
system. Deadlock is a situation that arises in a shared resource environment, where a process
waits for a resource for indefinite time because that resource is already occupied by another
process. This situation comes under deadlock. For example: There are n number of transactions
like t1, t2...tn. T1 requires a resource that is x to complete its process or a task. But Resource x is
held by T2, and T2 is waiting for a resource y, which is held by T3. T3 is waiting for resource z,
which is occupied by T1. So, all the transactions are waiting for each other to release resources
to complete their processes. So being in this situation no transaction can complete their task or
process. This point of situation is called deadlock.
Strategies to deal with deadlock:
1. Deadlock Prevention: to prevent deadlock situation in the system, the DBMS inspects all the
operations and determine whether transactions can create a deadlock situation. If there is any
possibility for deadlock situation, then tat transaction is never allowed to be executed. Here are
some scheme explained to prevent deadlock which uses timestamp ordering mechanism for
transactions in order to predetermine a deadlock situation.
A) Wait-Die: according to this scheme, this allows the transaction requests to lock a resource
which is already held with a conflicting lock by another transition. Here are two possibilities
 If TS(Tx) < TS(Ty) − that is Tx, which is requesting a conflicting lock, is older than Ty − then
Tx is allowed to wait until the resource is available.
 If TS(Tx) > TS(ty) − that is Tx is younger than Ty − then Tx dies. Tx is restarted later with a
random delay but with the same timestamp.
 This method permits the older transaction to wait for resource and to complete its process
but kills newer one.

B) Wound-Wait Scheme
According to this method, if a transaction requests to lock a resource, which is already held with
conflicting lock by some another transaction, then there are two possibilities–
 If TS(Tx) < TS(Ty), then Tx forces Ty to be rolled back − that is Tx wounds Ty. Ty is
restarted later with a random delay but with the same timestamp.
 If TS(Tx) > TS(Ty), then Tx is forced to wait until the resource is available.
This method allows the newer transaction to wait; but when an older transaction requests a
resource held by a newer one then the older transaction forces the newer one to abort start of
execution and release the resource. Both cases force the newer transaction to abort.
2. Deadlock Avoidance
This technique can be applied where transactions are lightweight and having fewer instances of
resource. But deadlock prevention techniques may good for rest of cases.
A)Wait-for Graph
According to this solution the system keeps the graph (wait for graph) for each
transactions and resources that is occupied by those transactions. If there is a transaction
Tx that want a resource j , but this j resource is held by another transactions that is Ty. A
directed edge is created form Tx to Ty. If Ty releases resource j then the edge between
them is dropped and Tx locks the resource.
Here are two following approaches:
 First, do not allow any request for a resource, which is already locked or held by
another transaction. This is not feasible and may cause starvation, where a
transaction indefinitely waits for a resource and can never occupy.
 The second option is to roll back any one of the transactions. This is not feasible
solution to roll back the newer transaction. It may be important than the older
transaction. But this problem can be resolve with some relative algorithms, a

transaction is chosen, which is to be aborted. This transaction is known as
the victim and the process is known as victim selection.