WA2. Deadlocks

Statement

• When a detection algorithm determines that a deadlock exists, the system must recover from the deadlock.
• The most common solution is to roll back one or more transactions to break the deadlock.
• List the three actions that need to be taken using figure 16.18 to discuss.

Solution

• The Deadlock Detection and Recovery technique; involves a process that periodically examines the state of the system and checks if a deadlock has occurred.
• The algorithm has 3 functions:
  • Save the current transactions state,
  • Detect a deadlock.
  • Recover from a deadlock when detected.
• According to the wait-for-graph presented in Figure 16.18 (Silberschatz et all, 2001, p.618), a deadlock is identified by a cycle between two or more edges in that graph.

• The cycle in the graph is broken by killing one of the transactions that participate in that cycle so it is broken.
• The algorithm takes 3 actions to detect and recover from a deadlock:
  1. Select transaction(s) to kill (rollback) to break the cycle. each transaction (including its history) is analyzed to decide a victim.
  2. The selected transaction is rolled back and restarted at a specific point in the future. The rollback may stop on the statement (of the rolled-back transaction) that breaks the deadlock or continues back to the beginning of the transaction.
  3. A transaction can be rolled back a few times; after that, it will never be rolled back; that’s to avoid starvation.

Conclusion

• The Deadlock Detection and Recovery algorithm is not perfect, but it does its job with less overhead than other techniques like Deadlock prevention (wait–die and wound-wait).
• The algorithm has been changed to rollback to the point that fixes the error instead of rolling back the entire system

References

• Silberschatz, A., Korth, H.F., & Sudarshan, S. (2001). Database System Concepts (4^th ed.). New York, NY: McGraw-Hill. Available at Database System Concepts 4^th Edition By Silberschatz-Korth-Sudarshan.pdf