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

[john cooper]

Scott Wood wrote:

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

> Plus, the number of locks held by any given thread
> should generally be very small.
I agree, it is likely in the noise. The list length and
manipulation of the mutex waiter list overshadows this.

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