On Thu, Oct 21, 2004 at 12:49:30PM -0400, john cooper wrote:That's true for the case where the current priority is
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 threadI agree, it is likely in the noise. The list length and
should generally be very small.