DATABASE MANAGEMENT SYSTEM

DEADLOCK IN DBMS

Deadlock handling and prevention in Database Management Systems (DBMS) are critical to ensure smooth operation and consistency of databases. Deadlocks occur when two or more transactions are waiting indefinitely for resources locked by each other. 

 

1. Deadlock Prevention

1. Wait-Die Method: The wait-and-die method is a deadlock prevention strategy used in DBMS. This method is based on the principle of non-preemption and uses transaction timestamps to decide whether a transaction should wait or be aborted when a conflict occurs. 

• Timestamps Assignment: Each transaction is assigned a unique timestamp when it starts. This timestamp determines the transaction’s age; the smaller the timestamp, the older the transaction.
• Conflict Resolution: When a transaction Ti​ requests a resource held by another transaction Tj​, the decision is made based on their timestamps:

2. Wound-Wait Scheme: In this preemptive approach, older transactions preempt (abort) younger ones instead of waiting for them, but younger transactions can wait for older ones. This also avoids circular wait.

3. Deadlock Detection: Detection mechanisms are used to identify deadlocks after they have occurred.

4. Wait-For Graph Analysis: The wait-for graph method is suitable for deadlock detection. In this method, a graph is constructed based on transactions and their locks. If this graph contains a cycle or a closed loop, it indicates a deadlock. The system maintains a wait-for graph for each transaction that is waiting for data held by other transactions. The system continuously checks this graph for any cycles to detect deadlocks.

 

 

Question: Draw a Wait for Graph for the following Resource Allocation Graph. And Check whether there is deadlock or not.

Solution:

Here a cycle if formed , hence there is a deadlock.

Practice:

Draw a Wait for Graph for the following Resource Allocation Graph. And Check whether there is deadlock or not.

2. Deadlock Detection Algorithms: Implement specific algorithms to check for deadlocks. These algorithms usually involve the construction of a resource allocation graph and checking for cycles.

 

3. Deadlock Recovery: Once a deadlock is detected, a DBMS must recover from it.

1. Transaction Rollback: Abort one or more transactions to break the deadlock cycle. The choice of transaction to abort can be based on criteria such as transaction age, the number of resources held, or the transaction's priority.
2. Cascading Rollback: Abort a set of transactions and undo their operations until the system reaches a consistent state. This can cause other transactions to abort, leading to a cascading effect.
3. Resource Preemption: Temporarily revoke some resources from transactions and assign them to other transactions to resolve the deadlock.

4. Deadlock Avoidance

Avoidance Methods: These methods require additional information about transactions to dynamically decide whether to allow transactions to proceed.

1. Wait-For Graph: Construct a wait-for graph where nodes represent transactions and directed edges represent waiting dependencies. Regularly check for cycles in this graph; a cycle indicates a deadlock.
2. Banker's Algorithm: Similar to Dijkstra's Banker's Algorithm used in operating systems. It ensures that a system remains in a safe state by checking the resource allocation graph to determine if resource allocation will lead to a safe state.