Comparison: ChainLocker vs. Heirarchical Mutexes

In “Concurrent Programming with Chain Locking,” Gigi Sayfan presents a C# class demonstrating chain locked operations on a hierarchical data structure. This reminded me of lock hierarchies described by Anthony Williams in the book C++ Concurrency in Action.

To take a step back for a moment, the overall goal is to create multithreaded code which doesn’t cause deadlocks, race conditions, etc.  Although it may seem like a confusion of metaphors, lock hierarchies are a type of hand-over-hand locking, which is basically defined lock ordering. I think it would be fair to call a “chain” a particular path of locking through a hierarchy. Defining lock ordering is what you do if you can’t do the better idea, which is to acquire two of more locks in a single operation, for instance with the C++11 std::lock() function.

As Herb Sutter pointed out in his article “Use Lock Hierarchies to Avoid Deadlock,” you may already have layers in your application (or at least the data in a certain context). This can be taken advantage of when making the software concurrency-friendly. The general idea is that a layer does not access code in layers above it. For mutexes, this means that a layer cannot lock a mutex if it already holds a mutex from a lower layer.

Anthony Williams has pointed out another benefit of lock hierarchies, which is that they can check at runtime if a fixed order is broken. Williams shows an example of a user-defined hierarchical mutex which does that (Listing 3.8 in his book). Then it’s up to you to make sure you use that mutex in adherence to your layering design. There isn’t a structure provided as with ChainLocker to route the chains through. However, the hierarchical mutex prevents deadlock. And even if you break your rules, it will throw an exception so you will quickly become aware of the crime. ChainLocker, on the other hand, doesn’t prevent deadlock or ensure adherence to the hierarchical design, unless you do something like the SchoolLocker trick shown of subclassing the generic class so that the template parameters are in a guaranteed order.

And of course the issue of remembering to release locks even if there’s an exception isn’t a problem in C++, e.g. by using std::lock_guard. I like the concept of using a Python script to auto-generate code (I’ve certainly done that myself in the past, for example to generate enums from data files at build time). But here it may get annoying to have to autogenerate all these different special generic (seems like an oxymoron) classes if the application is sufficient complicated. So, it seems to me that ChainLocker will not be too useful in practice, at least if implemented in C++.

On the other hand, the hierarchical mutex approach requires associating layer constants to every mutex, e.g.:

hierarchical_mutex high_level_mutex(10000);
hierarchical_mutex low_level_mutex(5000);

This assignment of numbers could get annoying. It reminds me a bit of the old BASIC interpreters that required line numbers, and you’d typically skip 100 between each one, and then when you realized you need to add some lines those would get inserted on the 10s, and so on with 5s, then 1s, resulting in a few weird line numbers like 4441 and 4442, and when you needed an integer in between those the annoyance level would reach a maximum. So there is something appealing about not having to rate everything with a constant int and instead using template parameters to set fixed orders. Perhaps there is some other flexible and generic way to set up the relative ordering—maybe at least auto-generate the layer numbers.

Tags: , , ,

Leave a Reply

You must be logged in to post a comment.