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

[Scott Wood]

On Thu, Oct 21, 2004 at 02:09:19PM -0400, john cooper wrote:
> Scott Wood wrote:
> >If you keep it in priority order, then you're paying the O(n) cost
> >every time you acquire a lock. 

I partially take this back; depending on how it's implemented, you
can get away with only adding it to the list once contention occurs.

> That's true for the case where the current priority is
> somewhere else handy (likely) and we don't need to traverse
> the list for other reasons such as allowing/disallowing
> recursive acquisition of a mutex by a given task.

How would maintaining priority order make it faster to check for
recursive usage?  You'd be looking for a specific mutex rather than
the highest priority blocker.  You could also check the per-mutex
list of owners (which you'll need to implement PI on rwlocks), to
avoid needing to add to the locks-held list in non-contended cases.

On uniprocessor, one may wish to turn rwlocks into recursive non-rw
mutexes, where recursion checking would use a single owner field.

Also, keeping it in priority order would introduce yet another place
that assumes of a linear priority scheme.  At some point, it may be
desireable to implement other schemes, such as maintaining per-CPU
priorities to deal with inheriting from CPU-bound tasks without
introducing said tasks' priorities on other CPUs.

-Scott
-
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/