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

Groups > comp.programming.threads > #1434

Re: deadlock detection

Show all headers | View raw

On Mon, 18 Mar 2013 22:38:49 -0700 (PDT), Michael Podolsky
<michael.podolsky.69@gmail.com> 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?


In general it's impossible (basically it reduces to the halting
problem).  But it is possible to detect many cases (just like you can
decide the halting problem for many specific programs).

But reliably detecting deadlock would at least be useful for
identifying and fixing the problem - even if the current run of the
application crashed.  And in many cases you can just kill one of the
lock holding processes (for example, if the deadlock were in a
database between two or more transactions - kill one and let it roll
back, and then continue with the rest).  In those cases you really
want *reliable* deadlock detection (you don't want to start killing
transactions just because the system is running a bit slow at the
moment), and again, you can generate good diagnostic information to be
logged (and hopefully acted on by development).

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