Deadlock detection

[Duncan Grisby]

In article <mailman.7255.1102355098.5135.python-list at python.org>,
Josiah Carlson  <jcarlson at uci.edu> wrote:
>
>Duncan Grisby <duncan-news at grisby.org> wrote:

>> Does anyone know of a deadlock detector for Python?  I don't think it
>> would be too hard to hook into the threading module and instrument
>> mutexes so they can be tested for deadlocks. I've googled around but I
>> haven't found anything.
>
>I'm not aware of a deadlock dector for any language.  I propose that a
>completely working deadlock detector is NP-Complete, as it would, I
>believe, necessitate solving the halting problem.

As Paul Du Bois has pointed out, NP complete is much easier than the
halting problem (i.e. the halting problem simply can't be done in
general, no matter how much time you have).

Aside from that, you're right that statically analysing code for
deadlocks is equivalent to the halting problem, and therefore
impossible. What I'm looking for, though, is a dynamic detector that
detects deadlocks at run-time when they happen. Doing that is well
understood, and there are plenty of systems that do it. I just haven't
been able to find one for Python.

Cheers,

Duncan.

-- 
 -- Duncan Grisby         --
  -- duncan at grisby.org     --
   -- http://www.grisby.org --