Deadlocks

Sequence of transaction $(T_{1}, \dots, T_{n})$ where $T_{i}$ must wait for $T_{i + 1}$ to release locks, $1 \leq i < n$ , and where $T_{n}$ must wait for $T_{1}$ to release locks

Example

$r_{1} [x], r_{2} [y], w_{2} [x], w_{1} [y]$

$w_{2} [x]$ is blocked by $T_{1}$
$w_{1} [y]$ is blocked by $T_{2}$

Prevention

Deadlock Prevention (Active)

Locks granted only if they can’t lead to a deadlock
All other objects are ordered and locks granted in this order

Deadlock detection (Passive)

Use wait for graphs and cycle detection
System aborts one of the offending transactions

similar to Deadlock from CS 350