 |
| Deadlock in DBMS |
Deadlock in DBMS
When two or more transactions are waiting endlessly for each other to release locks, it is called a deadlock. One of the most feared DBMS issues is deadlock, which occurs when a process never finishes and is stuck in a waiting state indefinitely.
When two or more transactions in a database management system (DBMS) are waiting for one another to release resources—like locks on database objects—that they require to finish their activities, a deadlock occurs. They become stopped or "deadlocked" as a result of none of the transactions being able to move forward.
When two or more concurrent transactions attempt to access the same data in a different order while executing in multi-user scenarios, a deadlock may occur. In the event that this occurs, a resource that is needed by one transaction might be locked by another, and a resource that is needed by the first transaction might be locked by the second.
Example
Transaction T1 needs to update specific rows in the grade table and holds a lock on specific rows in the student table. Concurrently, transaction T2 must update the rows in the Student table held by transaction T1, and it retains locks on certain rows in the grade table.
This is when the big issue appears. At this moment, transaction T1 is waiting for transaction T2 to release its lock, and transaction T2 is the same way around. Every activity pauses and comes to a complete stop. Until the DBMS recognizes the impasse and aborts a transaction, it will remain at a standstill.
Deadlock Handling in Centralized Systems
Three traditional methods exist for managing deadlocks, which are as follows:
• Deadlocks Prevention
• Deadlock Avoidance.
• Deadlocks Detection and Removal
In both distributed and centralized database systems, all three strategies can be used.
Deadlock Prevention
The strategy of deadlock prevention prevents any transaction from acquiring locks that could cause deadlocks. It is customary for only one transaction to be given the lock when many requests are made to lock the same data item.
Pre-acquiring all of the locks is one of the most often used strategies for preventing deadlocks. With this approach, a transaction obtains all locks prior to initiating execution and maintains those locks for the life of the transaction.
A transaction must wait until all the locks it requires are available if it requires any of the locks that have previously been acquired. Since none of the pending transactions are holding a lock, this strategy keeps the system from becoming deadlocked.
Two schemes are suggested by the deadlock prevention mechanism:
• Wait-Die Method: Under this scheme, the database management system (DBMS) merely compares the timestamp of the two transactions and permits the older transaction to wait until the resource is ready for execution if a transaction requests a resource that has been blocked by another transaction.
Let's say there are two transactions, T1 and T2, and that any given transaction T has a timestamp of TS (T). Now, if T1 is demanding resources held by T2 and T2 is locked by another transaction, the DBMS executes the subsequent actions:
Verifies whether TS (T1) < TS (T2); if T1 is the more recent transaction and T2 has held a resource, T1 is permitted to wait until the resource is ready to be executed. This implies that a transaction that is older is permitted to wait for a resource until it becomes accessible if a younger transaction has locked it and the older transaction is awaiting it.
In the event that T2 is waiting for an older transaction, T1, which has held some resources, and T1, it terminates and is restarted later with an arbitrary delay and the same timestamp.
As an example, if the younger transaction is waiting for a resource that the older transaction has held, it will be destroyed and restarted with the same timestamp after a very short delay.
The younger transaction is killed by this strategy, but the elder one is allowed to wait.
• Wound Wait Method: Under this scheme, a younger transaction is forced to kill the older transaction and relinquish the resource if the older transaction demands access to a resource that it is holding. With a minute's delay, the younger transaction is resumed with the same timestamp. The younger transaction is requested to wait until the older one releases the resource if it is being requested by the older one.
Deadlock Avoidance
One method of anticipating deadlocks is deadlock avoidance. In smaller databases, deadlocks can be found using techniques like the Wait-For graph; but, in larger databases, deadlock prevention techniques must be employed.
Avoid utilizing a database that has reached a stalemate rather than stopping or restarting the database server because doing so squanders time and resources.
It is preferable to avoid a database in a deadlock situation as opposed to restarting or aborting the database. This is a time and resource waster.
Any deadlock condition can be anticipated thanks to the deadlock avoidance method. To identify a deadlock scenario, a technique similar to "wait for graph" is employed; however, this approach is limited to smaller databases. The deadlock prevention strategy can be used to larger databases.
Deadlock Detection and Removal in DBMS
The strategy known as "deadlock detection and removal" involves periodically running a deadlock detection algorithm and removing any instances of deadlock. A transaction requesting a lock does not cause it to check for deadlock. Upon receiving a lock request from a transaction, the lock manager verifies its availability. The transaction is allowed to wait if it is not available, in which case it can lock the data item.
Certain transactions might be stalled because no safety measures were taken while approving lock requests. The lock management frequently examines whether the wait-for graph contains cycles in order to identify deadlocks.
The lock manager selects a victim transaction from each cycle if the system is deadlocked. The victim is stopped, rolled back, and then continued at a later time.
Among the techniques employed in victim selection are
Select the transaction that is the youngest.
Select the transaction with the fewest data points.
Select the transaction that has had the fewest modifications.
Select the transaction that requires the least amount of restarts.
Select the transaction that is shared by at least two cycles.
This method works best in systems with few transactions that require a quick response to lock requests.
Disadvantages
o System outage: Deadlocks can lead to system outages, which can cost companies that depend on the DBMS money and productivity.
o Resource waste: Transactions that are awaiting resources do not utilize them, which wastes resources and reduces system performance.
o Decreased concurrency: A deadlock may cause the system's concurrency to drop, which may cause transaction processing to move more slowly and throughput to drop.
o Complex resolution: System administrators may need to step in and manually break deadlocks, which can be a difficult and time-consuming procedure.
Features of Deadlock in a DBMS
• Mutual Exclusion: Only one transaction at a time may hold a resource; all other transactions must wait for the resource to be released.
• Hang & Wait: While requesting resources, transactions might hold onto those that have already been allotted to them.
• No Preemption: Resources cannot be withdrawn from a transaction against its will; instead, they must be released willingly.
• Circular Wait: In a circular chain, transactions are waiting on resources held by the subsequent transaction in the chain. This is known as a circular wait.
• Indefinite Blocking: No transaction can move forward while resources are being reserved for transactions that are blocked indefinitely.
• System Stagnation: When there is a deadlock, the system cannot move forward and no transaction can be completed.
• Inconsistent Data: If transactions fail and the database enters an intermediate state, deadlock may result in inconsistent data.
Applications
• Transaction Delayed: Transactions that are delayed can result from deadlocks because they impede the flow of resources that other transactions require. Users may experience longer wait times and slower response times as a result.
• Lost Transactions: Deadlocks occasionally result in the loss or cancellation of transactions, which can lead to inconsistent data or other problems.
• Decreased Concurrency: When transactions are halted as they wait for resources to become available, deadlocks can cause a decrease in concurrency in the system. Reduced overall throughput and slower transaction processing may result from this.
• Increased Resource Utilization: Transactions that are stopped while they wait for resources to become available can continue to use system resources, which can lead to deadlocks and an increase in resource usage. Increased resource contention and performance loss may result from this.
• Decreased User Happiness: Deadlocks might cause users to feel as though the system is operating slowly and therefore lower their level of satisfaction with the program. Adoption and retention of users may suffer as a result.
Deadlock Detection in Distributed System
Distributed database management systems (DBMSs), several components dispersed throughout various computing devices coordinate and communicate with one another to give the user the impression of a single system. Another name for this is distributed computing.
Deadlocks in distributed systems cannot be avoided or prevented due to their large scale. Therefore, the only solution available is deadlock detection. The prerequisites for distributed systems deadlock detection are as follows.
Progress: All of the system's deadlocks ought to be detectable by the method.
Safety: No phantom or false deadlocks should be detected by the procedure.
Approaches to detect deadlock in the Distributed System
• The centralized Approach: The simplest and most straightforward method of detecting deadlocks because it relies solely on one resource to do it. However, it also has drawbacks of its own, like placing an undue amount of stress on a single node and reducing system reliability by having just one point of failure.
• Distributed Technique: In contrast to the centralized approach, the detection of deadlock is the responsibility of several nodes. The utilization of numerous nodes in this strategy results in appropriate load balancing and eliminates the possibility of a single point of failure, hence expediting the process of discovering deadlock.
• Hierarchical Approach: This method combines distributed and centralized methods to detect deadlocks. In this, a single node is designed to manage a specific, chosen group of nodes in charge of detecting
