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

[Scott Wood]

On Thu, Oct 21, 2004 at 12:49:30PM -0400, john cooper wrote:
> It would seem a mutex ownership list still needs to be maintained.
> Doing so in unordered priority will give a small fixed insertion
> time, but will require an exhaustive search in order to calculate
> maximum priority. Doing so in priority order will require an
> average of #mutex_owned / 2 for the insertion, and gives a fixed
> time for maximum priority calculation. The latter appears to offer
> a performance benefit to the degree the incoming priorities are
> random.

If you keep it in priority order, then you're paying the O(n) cost
every time you acquire a lock.  If you keep it unordered and only
search it when you need to recalculate a task's priority after a lock
has been released (or priorities have been changed), you pay the cost
much less often.  Plus, the number of locks held by any given thread
should generally be very small.

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