Re: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation

[William Lee Irwin III]

William Lee Irwin III wrote:
>> Hmm. Given do_promotions() I'd expect fenceposts, not iteration over
>> the priority levels of the runqueue.

On Tue, Aug 03, 2004 at 10:33:36AM +1000, Peter Williams wrote:
> I don't understand what you mean.  Do you mean something like the more 
> complex promotion mechanism in the (earlier) EBS scheduler where tasks 
> only get promoted if they've been on a queue without being serviced 
> within a given time?

An array of size N can be rotated in O(1) time if an integer is kept
along with it to represent an offset that has to be added to externally-
visible indices mod N to recover the true index.


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