Subj : Re: Deadlock theorem To : comp.programming.threads From : David Hopwood Date : Fri May 06 2005 12:20 am David Schwartz wrote: > "David Hopwood" wrote: > >>>>I'm currently extending it for detecting violations of the theorem (ie. >>>>an automatic deadlock detector conditionally compiled only in debug build. >>>>IMO it even could be used in release build since the overhead seems not >>>>that much). > >>> It's very expensive to do this in a release build, but it's *great* >>>for a debug build. > >>Automatic deadlock detection is not expensive. > > Granted, but we're talking about violations of the locking hierarchy > whether or not they cause deadlocks. > >>First let's consider the case of global deadlock, where *all* threads >>of a program are waiting on locks. There is no significant performance >>overhead involved in detecting this state (i.e. the state when the >>scheduler has no runnable threads and no thread is blocked for another >>reason, such as I/O). The complexity cost of doing so is also very >>small. So there is no excuse at all for concurrent systems not to provide >>this level of deadlock detection for all builds. > > Agreed. I'm glad we're agreed about this. Too often I hear excuses for not supporting deadlock detection (or not using it in release builds) based on vague handwaving about performance overhead, when in fact the overhead is not even measurable. >>Detecting mutual deadlock between some subset of threads, as opposed to >>global deadlock (i.e. where it would be impossible for the threads that >>are still running to resolve the deadlock) is a bit more complicated. >>However, it need not be more expensive, because of the following >>observation: > > Not all violations of a locking hierarchy result in deadlock. The point > is to detect violations, not deadlocks. Well, detecting deadlock is still useful, even if it isn't quite as good as automatically ensuring a design constraint that always prevents deadlocks. For the latter, what you really want is a static analysis, which by definition has no runtime cost (although it could be quite complicated). For example, the effects-based type system described at can ensure absence of data races. It would be possible, I think, to extend it to also enforce hierarchical locking, and therefore absence of deadlock (although hierarchical locking isn't expressive enough for it to be the only approach supported by a language). -- David Hopwood .