[lkml]   [2006]   [Mar]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: PI patch against 2.6.16-rt9
On Wed, 29 Mar 2006, Thomas Gleixner wrote:

> On Tue, 2006-03-28 at 23:23 +0100, Esben Nielsen wrote:
> > > If you get to L(x) the underlying dependencies might have changed
> > > already as well as the dependencies x ... n. We might get false
> > > positives in the deadlock detection that way, as a deadlock is an
> > > "atomic" state.
> >
> > As I see it you might detect a circular lock graph "atomically". But is
> > that a "deadlock"? Yes, if you rule out signals and timeouts, this
> > situation does indeed deadlock your program.
> >
> > But if you count in signals and timeouts your algoritm also gives "false
> > positives": You can detect a circular lock but when you return from
> > rt_mutex_slowlock(), a signal is delivered and there is no longer a
> > circular dependency and most important: The program wouldn't be
> > deadlocked even if you didn't ask for deadlock detection and your task in
> > that case would block.
> >
> > I would like to see an examble of a false deadlock. I don't rule them out
> > in the present code. But they might be simple to fix.
> Simply the initial lock chain is L1->L2->L3->L4, which is no deadlock.
> Now in the course of your lock dropping L2 gets removed while you are at
> L3 and L5 gets added on top of L4. You follow the chain blindly and
> detect a dealock vs. L5, but its not longer valid. The L2 cleanup is
> blocked by yourself. There is no way to prevent this with your method.

Hmm, let me try to write it out

lock L1 lock L2 lock L3 lock L4
lock L2 lock L3 lock L4
traverse to C
is preempted
unlock L4
unlock L4
unlock L3
unlock L3 lock L4
unlock L2 lock L3
lock L3 lock L4

Continue from C

Ok, I see the problem for _deadlock detection_. There still is no problem
for PI.

> Your method is tempting, but I do not see how it works out right now.

It works for PI. It might give false positives for deadlock detection even
without signals involved. But that might be solved by simply checking
again. If it is stored on a task when they blocked on a lock it
could be seen if they had released and reobtained the task since the last

If I should choose between a 100% certain deadlock detection and
rescheduling while doing PI I would choose that latter as that gives a
deterministic RT system. Are there at all applications depending on
deadlock detection or is it only for debug perposes anyway?


> tglx
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to
> More majordomo info at
> Please read the FAQ at

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2006-03-29 01:37    [W:0.051 / U:1.092 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site