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

[john cooper <john.cooper@timesys.com>]

Ingo Molnar wrote:
> * john cooper <john.cooper@timesys.com> 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@timesys.com