Re: [patch] Real-Time Preemption, -RT-2.6.10-rc1-mm2-V0.7.1

[john cooper]

Ingo Molnar wrote:
> * john cooper <john.cooper@xxxxxxxxxxx> wrote:
>
>
> > > plus there's the 'priority inheritance dependency-chain closure' bug
> > > noticed by John Cooper - that should only affect the latency of RT 
> > > tasks though.
> >
> > This is a fairly gnarly problem to address.  The obvious solution is
> > to hold spinlocks in the mutexes as the dependency tree is atomically
> > traversed.  However this will deadlock under MP due to the
> > unpredictable order of mutexes traversed.  If the dependency chain is
> > not traversed (and semantics applied) atomically, races exist which
> > cause promotion decisions to be made on [now] stale data.
>
>
> is the order of locks in the dependency chain really unpredictable? If
> two chain walkers get two locks in opposite order, doesnt that mean that
> the lock ordering (as attempted by the blocked tasks) is deadlock-prone
> already? I.e. this scenario should not happen.

There does appear to be hope here.  If the per-task mutex ownership
list is maintained in strict order of acquisition sequence and
reader-mutex acquisition sequence is policed this would seem to remove
the possibly of chain traversal deadlock.

As an implementation note, single-owner hard spinlocks seem
excessive for the chain walk.  An approach allowing maximum
concurrency during traversal would be a reader-reference acquired
per node during the walk which would need to upgrade to an exclusive
writer-reference to effect promotion (waiter list priority reorder),
and then downgrade to a reader-reference to continue the traversal.

-john


--
john.cooper@xxxxxxxxxxx
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/