INTRODUCTION

DATA MODELS

RELATIONAL LANGUAGE AND RELATIONAL MODEL

DATABASE CONSTRAINTS AND NORMALIZATION

FILE STRUCTURE AND HASHING

QUERY PROCESSING AND OPTIMIZATION

TRANSACTION PROCESSING AND CONCURRENCY CONTROL-DBMS

CRASH RECOVERY

ADVANCED DATABASE CONCEPT

PRACTICAL-LAB WORK DBMS

PRACTICE QUESTION - ER DIAGRAM

OLD QUESTION BANK-DBMS-IOE

7.5. Deadlock handling and Prevention

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. 

Characteristics of Deadlock

1) Mutual Exclusion: There must be at least one resource that is in a non-shareable mode. Thus, only one transaction can access the resource at one time.

2) Hold and Wait: A transaction is holding one resource and waiting for other resources held by other transactions.

3) No Preemption: A resource could not be removed from a transaction forcefully that is holding it. System must wait until the transaction releases it voluntarily.

4) Circular Wait: Circular wait for transactions always exists. Here, each transaction holds a resource on which the next one needs to hold. A waits for B, B waits for C, and so on, until a transaction waits on A.

1. Deadlock Prevention

Wait-Die Scheme

In the Wait-Die Scheme, when a transaction requests a resource that is currently held by another transaction, the system checks the timestamp of both transactions. If the requesting transaction is older (has a smaller timestamp), it can wait.

If it is younger, the transaction is aborted, effectively "dying." By forcing younger transactions to give up their resources, the system prevents circular waits from occurring, thereby preventing Deadlocks.

Wound Wait Scheme

The Wound-Wait Scheme works in the opposite way. When a transaction requests a resource held by another transaction, if the requesting transaction is older, it forces the younger transaction to release the resource, or "wound" it.

If the requesting transaction is younger, it waits. This approach also eliminates the possibility of a circular wait by ensuring that older transactions are prioritised and younger transactions either wait or are aborted.

2. Deadlock Detection:

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

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.

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.