Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1436

Re: deadlock detection

Show all headers | View raw

On Tuesday, March 19, 2013 12:38:49 AM UTC-5, Michael Podolsky wrote:
> On Mar 15, 6:46 am, Aaron Brady <castiro...@gmail.com> wrote:
> > I have invented a deadlock detector.  The procedure is very simple and it 
> > would be very useful.  It must be broken or it would exist already.
> >
> > The Wikipedia article claims it's impossible [1].
> >
> > [1]http://en.wikipedia.org/wiki/Deadlock#Avoidance
> 
> Are you sure this article claims that deadlock detection is
> impossible?
> 
> I hope I understood the idea of your implementation. I recently made a
> kind of development in the same direction to analyze in runtime lock
> patterns which may lead to _potential_ deadlocks -- just by searching
> for cycles in a graph.
> 
> Supposing your system works perfectly as expected, one question should
> be asked here, in my opinion - what the application will do if it
> actually detects a deadlock i.e. what will it do if its lock request
> is rejected? Supposing our goal is to preserve its robustness, some
> methodology/framework should be defined here to allow it to survive
> and make further progress in execution.
> 
> And if you did not mean to make the application robust, what is then
> the primarily goal of your invention?
> 
> Regards, Michael

Hello Michael,

> Are you sure this article claims that deadlock detection is
> impossible?

The article is fairly clear.  "..[F]or many systems it is impossible to know in 
advance what every process will request. This means that deadlock avoidance is 
often impossible."

The principle behind the program is that deadlocks correspond 1-to-1 with cycles 
in the lock graph.  Cycle detection is still a finite problem, without knowing 
in advance, and therefore deadlock checking is also finite.  It remains to be 
proved or disproved.

> be asked here, in my opinion - what the application will do if it
> actually detects a deadlock i.e. what will it do if its lock request

I agree.  The information could be nearly useless.  But in my experience, which 
is limited, synchronization is so abstract, that many of the responses haven't 
been explored.

When the exception is raised, the calling thread is the last living thread that 
can release the resources that the other threads in the cycle are waiting for.  
None of the other threads in the loop are able to proceed, since none of *their* 
resources will become available without the caller releasing some.  So the 
options are still fairly limited: it could try another resource in a pool, or 
backtrack in a specific order, but it can't retry the same one.  Still, a 
graceful exit is preferable to the OS indiscriminately selecting a victim.

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

deadlock detection Aaron Brady <castironpi@gmail.com> - 2013-03-15 03:46 -0700
  Re: deadlock detection Michael Podolsky <michael.podolsky.69@gmail.com> - 2013-03-18 22:38 -0700
    Re: deadlock detection Robert Wessel <robertwessel2@yahoo.com> - 2013-03-19 01:03 -0500
      Re: deadlock detection Michael Podolsky <michael.podolsky.69@gmail.com> - 2013-03-19 19:14 -0700
      Re: deadlock detection Aaron Brady <castironpi@gmail.com> - 2013-03-21 22:59 -0700
    Re: deadlock detection Aaron Brady <castironpi@gmail.com> - 2013-03-19 17:17 -0700
      Re: deadlock detection Michael Podolsky <michael.podolsky.69@gmail.com> - 2013-03-19 19:09 -0700
        Re: deadlock detection Aaron Brady <castironpi@gmail.com> - 2013-03-20 09:07 -0700
  Re: deadlock detection Johann Klammer <klammerj@NOSPAM.a1.net> - 2013-03-19 20:24 +0100
  Re: deadlock detection Aaron Brady <castironpi@gmail.com> - 2013-03-26 17:18 -0700

csiph-web