lkml.org 
[lkml]   [2003]   [Feb]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: stochastic fair queueing in the elevator [Re: [BENCHMARK] 2.4.20-ck3 / aa / rmap with contest]
    On Mon, 10 Feb 2003, Rik van Riel wrote:
    > On Sun, 9 Feb 2003, Andrea Arcangeli wrote:
    >
    > > The only way to get the minimal possible latency and maximal fariness is
    > > my new stochastic fair queueing idea.
    >
    > "The only way" ? That sounds like a lack of fantasy ;))

    Took about 30 minutes, but here is an alternative algorithm.
    One that doesn't suffer from SFQ's "temporary unfairness due
    to unlucky hashing" problem, which can be made worse with SQF's
    "rehashing once every N seconds" policy, where N is too big
    for the user, say 30 seconds.

    It requires 2 extra fields in the struct files_struct:
    ->last_request and
    ->request_priority

    where ->last_request is the time (jiffies value) when a
    process associated with this files_struct last submitted
    an IO request and ->request_priority is a floating average
    of the time between IO requests, which can be directly used
    to determine the request priority.

    The floating priority is kept over (1 << RQ_PRIO_SHIFT) requests,
    maybe 32 would be a good value to start ? Maybe 128 ?

    The request priority of the files_struct used by the current
    process can be calculated in a simple O(1) way every time a
    request is submitted:

    {
    struct files_struct *files = current->files;
    unsigned long interval = jiffies - files->last_request;

    files->request_priority -= (files->request_priority >> RQ_SHIFT_PRIO);
    files->request_priority += interval;
    }

    The request_priority gets assigned as the priority of the
    currently submitted request (or the request gets submitted
    in the queue belonging to this priority range). We don't
    change the priority of already submitted requests, except
    maybe when merging requests.

    This idea should adapt faster to changing IO usage of tasks
    and is O(1) scalable. Dunno if it'll be better than SFQ in
    practice too, but it just shows that SFQ isn't the only way. ;)

    have fun,

    Rik
    --
    Bravely reimplemented by the knights who say "NIH".
    http://www.surriel.com/ http://guru.conectiva.com/
    Current spamtrap: <a href=mailto:"october@surriel.com">october@surriel.com</a>
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 13:33    [W:0.021 / U:1.272 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site