Deadlock-free Mutexes and Directed Acyclic Graphs
If you need to ensure that a particular piece of data is only ever modified by one thread at once, you need a mutex. If you need more than one mutex, you need to be wary of deadlocks. But what if I told you that there’s a trick to avoid ever reaching a deadlock at all? Just acquire them in the right order!
First of all, let’s define a deadlock. With two mutexes, foo and bar and two workers, alice and bob, we can have the following scenario:
Now both workers are waiting for each other and neither can complete. Let’s see now how to fix this. The key is that we want to always acquire all of our mutexes in a consistent order.1 In this case, if, whenever we need both foo and bar, we make sure to always acquire foo before bar, we can never deadlock. Of course, as a code base and its number of mutexes grows, this becomes harder and we need to formalize and automate this.
We can model the acquisition of mutexes as a graph problem, where all mutexes are nodes and we add an edge between them when we acquire a mutex while holding another. The problem then becomes: is this graph free of cycles?
