[lkml]   [2004]   [Aug]   [2]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    SubjectRe: [PATCH] V-3.0 Single Priority Array O(1) CPU Scheduler Evaluation
    William Lee Irwin III wrote:
    > 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

    And with a smaller constant than my do_promotions(). :-)

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

    OK. Now I understand.

    The main reason that I didn't do something like that is that
    (considering that real time tasks don't get promoted) it would complicate:

    1. the selection (in schedule()) of the next task to be run as it would
    no longer be a case of just finding the first bit in the bitmap,
    2. determining the appropriate list to put the task on in
    enqueue_task(), etc., and
    3. determining the right bit to turn off in the bit map when dequeuing
    the last task in a slot.

    As these are frequent operations compared to promotion I thought it
    would be better to leave the complexity in do_promotion(). Now that
    you've caused me to think about it again I realize that the changes in
    the above areas may not be as complicated as I thought would be
    necessary. So I'll give it some more thought.

    Thanks for the suggestion
    Peter Williams

    "Learning, n. The kind of ignorance distinguishing the studious."
    -- Ambrose Bierce
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to
    More majordomo info at
    Please read the FAQ at

     \ /
      Last update: 2005-03-22 14:04    [W:0.027 / U:1.080 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site