Deadlock Prevention | Database Management System

Deadlock Prevention | Database Management System

Deadlock prevention protocols ensure that the system will never enter into a deadlock State. Some strategies:

>> Require that each transaction locks all its data items before it begins execution (pre declaration).

>> Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order (graph-based (tree) protocol).

>> Others include wound-wait and wait-die Strategies that use time stamps to determine transaction age and determine if a transaction should wait or be rolled back on a lock conflict.

Wound-Wait and Wait-Die Strategies

Wait-Die scheme – non-preemptive

>> Older transaction may wait for younger one to release data item. Younger transactions never wait for older ones; they are rolled back instead.

>> A transaction may die several times before acquiring needed data item.

Wound-Wait scheme – preemptive

>> Older transaction wounds (forces rollback) of younger transaction instead of waiting for it. Younger transactions may wait for older Ones.

>> May cause fewer rollbacks than wait-die scheme.

Wound-Wait and Wait-Die (2)

Both in wait-die and in wound-wait schemes, a rolled back transaction is restarted with its original timestamp. Older transactions thus have precedence over newer ones, and starvation is hence avoided.

Timeout-Based Schemes

In a Timeout-Based Schemes:

>> A transaction waits for a lock only for a specified amount of time. After that, the transaction times out and is rolled back.

>> Thus deadlocks are not possible.

>> Simple to implement, but starvation is possible.

>> Also difficult to determine good value of the timeout interval.

  • Too short-false deadlocks (unnecessary rollbacks)
  • Too long – wasted time while system is in deadlock

Deadlock Detection & Recovery

lf deadlocks are not prevented, then a detection and recovery procedure is needed to recover when the system enters the deadlock state. An algorithm is run periodically to check if the system is in deadlock.

>> If the system is in deadlock, then transactions are aborted to resolve the deadlock. Deadlock detection requires the System:

>> Maintain information about currently allocated locks.

>> Provide an algorithm to detect a deadlock State.

>> Recover from deadlock by aborting transactions efficiently.

Wait-for Graphs

Deadlocks can be detected using a wait-for graph, which consists of a pair G = (V, E):

>> V is a set of vertices (all the transactions in the System).

>> E is a set of edges; each element is an ordered pair Ti —> Tj.

>> If Ti-Ti is in E, then there is a directed edge from Tito Ti, implying that Ti is waiting for Tito release a data item.

________________________