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

Groups > comp.programming.threads > #1439

Re: deadlock detection

Show all headers | View raw

On Tuesday, March 19, 2013 9:09:26 PM UTC-5, Michael Podolsky wrote:
> On Mar 19, 8:17 pm, Aaron Brady <castiro...@gmail.com> wrote:
> > On Tuesday, March 19, 2013 12:38:49 AM UTC-5, Michael Podolsky wrote:
> > > 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."
> 
> I see these words in the context of Banker's algorithm only. Also
> deadlock "avoidance" and
> deadlock "detection" are different things. For instance, if thread 1
> locks mutex A, then mutex B and thread 2 locks mutex B, then mutex A,
> to avoid deadlocks may mean not to allow for the thread 2 to lock even
> B, if A is already locked by the 1st thread.

My interpretation of it is: "The Banker's alg. requires X.  For many systems X 
is impossible.  Therefore deadlock avoidance is often impossible."  It's missing 
the premise that the Banker's alg. is the only method for avoiding it, which 
would make the conclusion true if it was true, but it's not.  I don't want to 
stifle your interest; but this should probably be pursued on the WP Talk page 
for the article.

> As for your arguments that "deadlocks correspond 1-to-1 with cycles in
> the lock graph" - I totally agree. Still, this works for mutexes and
> RW-locks,
> but I am quite unsure if there may be done some kind of deadlock
> detection for semaphores or condition variables.
> > [snip]

Well I'm flattered.  But I'm still skeptical.  How could we set about proving 
it?  If there is little or no interest in the program as it is, I won't be as 
interested in adding the others.  I would guess semaphores would fit in, but 
events can be set from any thread, so we'd need additional information: what 
threads might set the event at any time in the future.

When and if deadlock is detected, any thread in the cycle can be retroactively 
refused the lock it's waiting for, since it would resume in the same place under 
the same conditions.  Threads could specify their own priorities at some point, 
including in the calls to "acquire", and the error could be raised in the lowest 
priority one.  It might not be common for them to have different priorities, but 
it still might be useful in the cases where they do.  If events are included, 
when the last branch that can set an event misses its last chance to do it, and 
other threads are in a deadlock without it, then one of the threads in rest of 
the cycle would need to be thrown the error: presumably the last to call 
"acquire" or the lowest priority one.

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