Re: [patch] Real-Time Preemption, -RT-2.6.9-rc4-mm1-U8

[Scott Wood <scott@timesys.com>]

On Thu, Oct 21, 2004 at 04:18:12PM -0400, john cooper wrote:
> Scott Wood wrote:
> >How would maintaining priority order make it faster to check for
> >recursive usage?  
> >
> It wouldn't. My point was an exhaustive traversal may be
> needed for other reasons with an insertion sort being
> near free.
> 
> Yet considering the cost to maintain these lists in priority
> order with multiple spinlock acquisition sequences due to how
> the aggregate data structure must be traversed/ordered,
> I haven't yet convinced myself either way.

Another issue is that if you keep them in order, you have to fix the
list whenever an owner of a listed mutex changes its priority.

> >On uniprocessor, one may wish to turn rwlocks into recursive non-rw
> >mutexes, where recursion checking would use a single owner field.
> >
> It isn't obvious to me how this would address the case of a
> task holding a reader lock on mx-A then blocking on mx-B.
> Another task attempting to acquire a reader lock on mx-A would
> block rather than immediately acquiring the lock.

Yes.  However, the contention case should not be optimized at the
expense of the common case, which can be faster for non-rwlock
implementations when PI is involved.  On SMP, you'd be introducing a
bottleneck by taking away rwlocks, but on UP it's only an issue when
you get preempted or block in a critical section.

There could be problems if some code tries to acquire read locks
out-of-order, believing that it can't deadlock that way (if the
writers don't nest), but that's a problem anyway unless there's a
reasonable way of implementing PI without limiting the number of
concurrent readers (they have to be stored somewhere, and the
alternatives of setting a hard limit on mutexes-per-thread or doing
dynamic allocation inside the lock function are worse).

-Scott