A deadlock-detecting mutex
All the code for this article can be found here.
Here’s an idea for you: wouldn’t it be nice if a mutex could warn us that we’re going to deadlock the very moment we’re trying to acquire it? It may sounds far-fetched but it is very doable but it is probably quite simpler than you imagine.
A bit of background
Traditionally, we define a deadlock as the situation in which each member of a group of threads is waiting on a resource held by another member of said group. For those more visually-inclined, here’s what it looks like through the lens of a resource allocation graph.
While explicit, this graph is a bit too much for what we’re going for in this article. Instead, we’ll use a version of this graph where the resource ownership is implicit. We thus end up with what is commonly referred to as a wait-for graph.
Once we have this graph, it naturally follows that we only have to find out if it contains at least a cycle to say if we’re going to deadlock or not.
The wait-for graph
To quickly prototype our idea, we’ll use the Boost Graph Library (BGL). Our chosen graph representation will be a labeled graph where each vertex is labeled by a thread ID.
In addition of an internal graph, the
WaitForGraph will also contain a mutex to moderate all the concurrent accesses it’ll be subjected to.
For the purpose of our demonstration, the
WaitForGraph instance we’ll use will be at the global scope. Such being the case, I went ahead and made it a singleton. This comes with the added bonus that it will be inherently thread-safe since the initialization of local static variables is thread-safe as per the C++ standard since C++11.
We’ll defer the insertion and deletion of a vertex to BGL.
Now for the fun part. When adding and edge between to vertices, we’ll want to make sure that doing so won’t introduce a cycle in the graph (i.e. we’re not creating a deadlock). Luckily for us, BGL offers a function that can detect the strongly connected components (SCCs) in a graph. For those lacking in graph theory, a SCC is a subgraph in which every vertex is reachable from every other vertex.
In the example above, we have two SCC. One is composed of the vertices 0,1 and 2 and the other one is made up of the vertices 4,5,6 and 7.
It’s quite plain to see that a SCC in a directed graph like ours means that there is a cycle in the graph.
While we could certainly be more clever in our management of deadlocks, our goal here is simply to warn the user that a deadlock is occuring in the application. Consequently, the message proposed here will do the job.
To build a deadlock-detecting mutex we’ll need three things. First, a real mutex to make it work (duh!). Second, we need a way to identify the current owner of the mutex such as an ID. And, finally, third, we need a structure that will tell us if the mutex is presently owned.
Going into the
Lock method, we’ll want to make sure that there is a vertex for the current thread in the
WaitForGraph. This will be done by unconditionally adding a vertex to the
WaitForGraph. Worry not, this won’t create duplicate vertices since a
boost::labeled_graph guarantees that no two vertices shall have the same label.
After this is done, if the mutex is currently owned by some other thread, we’ll add an edge between the vertices representing the owner thread and the current thread. This will fire the deadlock detection algorithm of the
WaitForGraph. If worst comes to worst, then we’ll be shout at that we’re creating a deadlock.
Afterwards, we can lock the
DDMutex and update its internal state to make it clear it’s owned by the current thread.
Unlock method will undo what the
Lock has done.
One thing to note is that I’ve chosen to bluntly remove the vertex representing the owner from the
WaitForGraph. I know could’ve been way smarter about my management of the
WaitForGraph but let’s say I decided to left it as an exercise to the reader.
Putting it to the test
if we run the following program:
This is what we can end up with: