Deadlock in DBMS

Implementation of Demand Paging in OS

Deadlock

A deadlock occurs when two or more transactions in a database system are waiting for a data item that is locked by another transaction. Cycles in the wait chart can indicate deadlocks. This is a directed graph where nodes represent transactions and edges await pieces of data.

Deadlock in DBMS 

In this article, we will learn about Deadlock in DBMS.

  • Every process need some resource for its execution and these resources are  granted in sequential order
    1. First the process request some resource.
    2.  OS grants the resource to the process if it is available or else it places the request in the wait queue.
    3. The process uses it and releases on the completion so that it can be granted to another process
    4. Deadlock is a situation where two or more transactions are waiting indefinitely for each other to give up their locks.
Deadlock

Example:

Transaction T1 is waiting for transaction T2 to release the lock and similarly transaction T2 was waiting for transaction T1 to release Its lock, as a result, all activities come to halt state and remain at standstill .This continues until the DBMS detects that deadlock has occurred and abort some of the transactions.

Necessary conditions for Deadlocks 

Mutual Exclusion 

It implies if two processes cannot use the same resource at the same time.

Hold and Wait 

A process waits for some resources while holding another resource at the same time.

No pre-emption 

The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile.

Circular Wait 

All the processes must be waiting for the resources in a cyclic manner so that the last process is waiting for the resource which is being held by the first process.

Deadlock avoidance 

  • Whenever a database is stuck in a deadlock it’s better to abort the transactions that are resulting deadlock but this is a waste of resources and time

  • Deadlock avoidance mechanism used to detect any deadlock situation in advance by using some techniques like WEIGHTS FOR GRAPH but this wait for graph method is suitable only for smaller databases, for large databases other prevention techniques are used

Deadlock detection (Wait for Graph) 

  • Whenever a transaction waits indefinitely to obtain a lock DBMS should check whether the transaction is involved in a deadlock or not .For this purpose a lock manager maintains wait-for graph for the detection of deadlock cycles
  • Wait for graph method is suitable only for smaller databases

Steps 

  1. In this method, a graph is created based on transactions and their locks
  2.  While Creating the graph if a cycle or closed loop is encountered then there is a deadlock

This wait for graph is maintained by the system for every transaction that is waiting for some resource held by others

Wait for Graph

Deadlock prevention 

  • Prevention techniques are used for larger databases .
  • Resource allocation is done in such a way that deadlock never occurs
  • DBMS analyse the transactions to determine whether any deadlock situation can arise or not, if there is any possibility then DBMS never allows such transaction for execution

Wait-Die scheme 

  • Whenever there is a conflict of resource between transactions DBMS simply check the timestamp of both the transactions
  • There are two transactions Ti and Tj and let TS(T) is a timestamp of any transaction T
  •  If T2 holds a lock by some other transaction and T1 is requesting for resources held by T2 then the following actions are performed by DBMS

Check if TS(Ti) < TS(Tj) :

  • If Ti is older transaction and Tj has some resource held then Ti is allowed to wait until data item is available for execution
  • Simply if older transaction is waiting for a resource which is locked by younger transaction then older transaction is allowed to wait for resource until it is available

Check if TS(Ti) < TS(Tj) 

  • If Ti is older transaction and has held some resource and if Tj is waiting for it, then Tj is killed and restarted later with the random delay but with the same timestamp.

Wound wait scheme 

  • Whenever an older transaction request for a resource which is held by a younger transaction, older transaction forces the younger transaction to kill its transaction and release the resource to the elder one
  • After minute delay younger transaction is restarted within the same timestamp
  • Whenever older transaction has held a resource which is requested by the Younger transaction, then the younger transaction is asked to wait until older releases it.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription