Boost logo

Threads-Devel :

From: Frank Mori Hess (fmhess_at_[hidden])
Date: 2007-07-24 17:37:17

On Tuesday 24 July 2007 03:23, Kai Brüning wrote:
> >That would avoid the potentially large overhead of analyzing my
> > directed graph for cycles. I wonder if there's a good way to
> > dynamically assign levels to mutexes as they are added to the graph.
> If I am not mistaken, dynamically assigning the levels changes the
> nature of this approach substantially.

I was only speculating (prematurely) on optimizing the DAG by storing some
additional "level" information in the nodes, which would have to be
updated as new edges and nodes are added (probably obliterating any

> With statically assigned levels, the programmer has to structure the
> locking needs of the code in levels based on his knowledge of program
> structure. While not bullet proof without 100% test coverage, I consider
> this idea a deadlock avoidance approach. I'd consider a level conflict
> more a bug than a normal runtime event - level checking might even be
> switched off in release mode.
> With dynamically assigned levels I'd expect that any change in the flow
> of control can result in a level conflict somewhere. This makes it hard
> to be confident that testing eliminated all potential deadlocks, which
> makes this more a deadlock detection approach in my eyes. That is, code
> will have to be able to recover from a would-be deadlock situation, e.g.
> by throwing an exception.

No, this is meant to be a bug-detection tool, definitely able to be
switched off for releases. Using a DAG to keep track of lock ordering can
be made to detect anything a leveled mutex scheme would find, it's just
more flexible and can work with less user effort. The downsides are it
takes O(num_nodes + num_edges) to verify the graph has no cycles, instead
of everything being constant time with a leveled mutex. Also, the DAG
scheme is more complicated.

To make the DAG scheme act just like the leveled mutex, you would do two
1) Allow the user to specify that multiple mutex objects should be
represented by a single node in the graph (all the mutexes with level N
would be one node).
2) Allow manual initialization of the graph with user-specified nodes and
edges. Actually, the user could just execute an otherwise useless
sequence of mutex locking at program startup to initialize the graph.

However, the DAG would additionally allow the user to manually specify as
much or as little of the locking heirarchy at initialization as he likes.
Mutexes with no level specified could still be added to the DAG and
checked as they are encountered. Or, the user could specify that a group
of mutexes are all the same level without bothering to specify what that
level is exactly, which would just make every mutex in the group share the
same node in the DAG.


Threads-Devel list run by bdawes at, david.abrahams at, gregod at, cpdaniel at, john at