|
|
Threads-Devel : |
From: Kai Brüning (kai_at_[hidden])
Date: 2007-07-25 17:52:15
[snip]
>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
>things:
>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.
Ok, got it. Thanks for the clarification.
Assuming that the DAG scheme is made available as a ready to use library, the higher complexity should not matter. And as a debug-only tool performance does not matter too much, either.
The only remaining benefit of a leveled mutex scheme might be the structure it brings to the mutexes used in a program. This may make it easier for the user to reason about which locking operations/orders are ok and which not. Your suggestion to integrate levels in the DAG scheme seems indeed to combine the benefits of both schemes.
Kai