Deadlock prevention algorithms

Once upon a time, I was interviewed for a database engineering position. I was asked about what deadlock prevention algorithms do I know. I could not name a few (besides detection and randomization) and I was rejected. It was an unsatisfying experience because the ideas behind those algorithms happened to be pretty simple and the algorithms are small. There is nothing special to it.

However, besides that simplicity alone, the databases contain a lot of different algorithms that work together. They are combined in a non-trivial manner and it is hard to catch the whole picture. In this article, I offer a view on how the concurrency control algorithms work together with the deadlock prevention algorithms in a graphical way.

Many concurrency control (CC) [2] algorithms may run into a deadlock situation [3] (2PL [4] and derivatives). There are 2 different approaches to solve that: detecting deadlocks and preventing deadlocks. Let’s take a look at how preventing deadlocks algorithms works with an arbitrary CC.

The system consists of a Transaction Manager (TM) that receives a stream of commands, feeds it into the concurrency control (CC) algorithm that outputs the list of actions to be performed. Resulted sequence of actions (scheduling history) is conflict serializable (CSR) and executed by the data manager (DM).

commands -> TM -> CC -> schedule -> DM

Let our CC be a classic 2PL (two-phase locking). The stream of the commands that we will be receiving will be:

Semantically correct locking of \(s\) for this figure is pretty straight forward. \({r_1(x), r_2(x)}\) will obtain shared read lock and the corresponding write operation will fail to upgrade it to exclusive lock.

Note. In simple words well-formed locking is a form of a schedule where all read and writes operations perform under corresponding shared or exclusive locks, locks and unlocks are semantically correct (\(lock_i(x) < op_i(x) < unlock_i(x)\)), plus there is no transitive redundancy of locks (no \(lock_i(x) < op_i(x) < lock_i(x) ...\) or \(unlock_i(x) < unlock_i(x)\)).

Note. Main 2PL property is that transaction acquires all lock before releasing them (no \(unlock_i(x) < lock_i(y)\)).

Deadlock is easy to see here highlighted with the red arrows:

The deadlock is \(lr_1(x) lr_2(x) lw_1(x) lw_2(x)\). Both \(t_1\) and \(t_2\) tries to upgrade their shared locks and block waiting for each other to release the \(x\).

Feeding a prefix \(prefix(s) = r_1(x) r_2(x)\) into the TM (and CC) will result into:

The next command that we will receive is \(w_3(x)\). \(w_3(x)\) must block, because \(t_1\) and \(t_2\) are holding shared lock. However, CC output will depend on the deadlock preventing algorithm.

There are at least 4 widely known deadlock prevention algorithms:

• wait-die - lock requester blocks on younger txs, young abort themselves
• wound-wait - lock requester aborts younger txs, young blocks
• immediate restart - restart if need to block
• running priority - block if lock-holder is not blocked, restart otherwise

Requester is a transaction \(t_i\) that requests a lock by issuing a locking command \(lr_i(x)\) or \(lw_i(x)\). Transaction \(t_j\) that holds the lock called holder. Then we set a total order of transactions \(ts\) in such a way that \(ts(t_i) < ts(t_j)\) if and only if \(t_i\) started before \(t_j\).

Wait-die

Receiving \(w_3(x)\) must block \(t_3\) for \(t_1,\ t_2\). However, \(ts(t_3)\ >\ ts(t_1) \land ts(t_3)\ >\ ts(t_2)\). Hence \(t_3\) can’t block and wait for \(t_1\) and \(t_2\) and our CC issues an abort command \(a_3\). Thus we are getting:

The same thing happens for the \(w_4(x) \in t_4\):

Then we receive \(w_1(x)\) from \(t_1\). \(ts(t_1)\ <\ ts(t_2)\) thus \(lw_1(x)\) (along the \(t_1\)) blocks waiting for the \(t_2\) to release shared lock on \(x\).

\(t_1\) is blocked, so \(c_1\) queued. Next command we receive is \(w_2(x)\). \(ts(t_2)\ >\ ts(t_1)\) and \(lw_2(x)\) can’t block waiting for \(t_1\). Thus \(t_2\) aborts:

Now, we can finish \(t_1\) because aborted \(t_2\) released shared lock:

(here we assume that transaction abort automatically releases all of its locks)

Wound-wait

Receiving \(w_3(x)\) must block \(t_3\) for \(t_1,\ t_2\). Indeed, \(ts(t_3)\ >\ ts(t_1) \land ts(t_3)\ >\ ts(t_2)\). Hence \(t_3\) is younger it will block and wait for \(t_1\) and \(t_2\) to release the lock. Thus we are still having:

The same thing happens for the \(w_4(x) \in t_4\):

Then we receive \(w_1(x)\) from \(t_1\). \(ts(t_1)\ <\ ts(t_2)\) thus \(lw_1(x)\) wounds \(t_2\) that holds shared lock by issuing \(a_2\):

(here we assume that transaction abort automatically releases all of its locks)

Now, the wait queue consist of \(t_3\) and \(t_4\):

Now we easily output \(lw_3(x) w_3(x)\):

Next comes in \(w_4(x)\).

\(ts(t_4) > ts(t_3)\) hence \(t_4\) blocks in favor of \(t_3\).

Luckily, the next command \(c_3\) commits \(t_3\) and we can finish \(t_4\):

Immediate restart

\(w_3(x)\) and \(w_4(x)\) must block for \(t_1,\ t_2\) so \(\{t_3, t_4\}\) abort:

Then we receive \(w_1(x)\) from \(t_1\), but \(w_1(x)\) can’t upgrade it’s sharing lock, because it is also obtained by the \(t_2\) so it must block. Instead of block, we issue abort:

(here we assume that transaction abort automatically releases all of its locks)

Now \(t_2\) can successfully finish:

Running priority

Receiving \(w_3(x)\) must block \(t_3\) for \(t_1,\ t_2\). Indeed, \(\{t_1, t_2\}\) are not blocked.

Next comes \(w_4(x)\) that must also block for \(t_1,\ t_2\) and again \(\{t_1, t_2\}\) are not blocked.

Now we receive \(w_1(x)\), but \(t_2\) holds shared lock on \(x\) and is not block, so \(w_1(x)\) queued:

Now we receive \(w_2(x)\). \(t_1\) holds shared lock on \(x\) and is blocked waiting for \(t_2\). Hence \(t_2\) can’t block on \(t_1\) and must be aborted:

(here we assume that transaction abort automatically releases all of its locks)

Now, the wait queue consist of:

\(t_1\) still holds the shared lock, so ongoing writes from \(\{t_3, t_4\}\) must be aborted:

And the \(t_1\) can now finish:

Theoretically, the CC could resort blocked transactions in favor of processing ones that has more locks first (\(t_1\)). In that case the transactions that are also blocked but have dependencies on others that are also blocked could have more chances to be committed without a restart.

Conclusion

Many concurrency control algorithms are subject to deadlocks situations. There are 2 approaches to avoid deadlocks: detection and prevention. There are different variants of those algorithms based on ordering or priorities. We have shown how various deadlock prevention algorithms work together with concurrency control algorithms in a graphical way, how deadlocks may appear in locking algorithms such as 2PL and how they can be resolved in real time.

References

• Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) 1st Edition.