lkml.org 
[lkml]   [2000]   [Sep]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    SubjectRe: An elevator algorithm (patch)
    From
    Date
    Ragnar Kjørstad <reiserfs@ragnark.vestdata.no> writes:

    > If I understand the current code correctly, it works like this:
    [ example deleted ]
    > So we've ended up with a very silly queue....

    Indeed, the elevator logic is somewhat flawed. There are two problems
    with the current code:

    1. The test that decides if we have found a good spot to insert the
    current request doesn't handle the wraparound case correctly. (The
    case when the elevator reaches the end of the disk and starts over
    from the beginning.)

    2. If we can't find a good spot to insert the new request, we
    currently insert it as early as possible in the queue. If no good
    spot is found, it is more efficient and more fair to insert the new
    request last in the queue.

    The following patch fixes both problems. Here are the results from
    'iozone 100' and Bonnie with and without this patch.

    test8:
    ------

    iozone:
    4626750 bytes/second for writing the file
    7431438 bytes/second for reading the file

    bonnie:
    -------Sequential Output-------- ---Sequential Input-- --Random--
    -Per Char- --Block--- -Rewrite-- -Per Char- --Block--- --Seeks---
    Machine MB K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU /sec %CPU
    100 5278 60.6 7940 18.3 2876 9.7 5635 49.3 8344 16.7 179.3 2.0

    test8 + modified elevator:
    --------------------------

    iozone:
    4801172 bytes/second for writing the file
    7613088 bytes/second for reading the file

    bonnie:
    -------Sequential Output-------- ---Sequential Input-- --Random--
    -Per Char- --Block--- -Rewrite-- -Per Char- --Block--- --Seeks---
    Machine MB K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU K/sec %CPU /sec %CPU
    100 5727 66.6 8365 18.1 2921 9.2 5991 52.2 8171 16.0 171.0 2.0

    Here is the patch:

    --- linux-2.4.0-test8/drivers/block/elevator.c.orig Sun Sep 17 00:05:03 2000
    +++ linux-2.4.0-test8/drivers/block/elevator.c Sun Sep 17 00:06:31 2000
    @@ -34,20 +34,38 @@
    struct list_head *real_head,
    struct list_head *head, int orig_latency)
    {
    - struct list_head *entry = real_head;
    - struct request *tmp;
    -
    - req->elevator_sequence = orig_latency;
    -
    - while ((entry = entry->prev) != head) {
    - tmp = blkdev_entry_to_request(entry);
    - if (IN_ORDER(tmp, req))
    - break;
    - if (!tmp->elevator_sequence)
    - break;
    - tmp->elevator_sequence--;
    - }
    - list_add(&req->queue, entry);
    + struct list_head *last = real_head->prev;
    + struct list_head *insert_after = last;
    + struct list_head *entry;
    + struct request *tmp1, *tmp2;
    +
    + req->elevator_sequence = orig_latency;
    +
    + if (last == head)
    + goto out;
    +
    + entry = last;
    + tmp1 = blkdev_entry_to_request(entry);
    + do {
    + tmp2 = tmp1;
    + entry = entry->prev;
    + tmp1 = blkdev_entry_to_request(entry);
    + if (!tmp2->elevator_sequence)
    + break;
    + if (IN_ORDER(tmp1, tmp2) ?
    + (IN_ORDER(tmp1, req) && IN_ORDER(req, tmp2)) :
    + (IN_ORDER(tmp1, req) || IN_ORDER(req, tmp2))) {
    + insert_after = entry;
    + do {
    + entry = entry->next;
    + tmp1 = blkdev_entry_to_request(entry);
    + tmp1->elevator_sequence--;
    + } while (entry != last);
    + break;
    + }
    + } while (entry != head);
    +out:
    + list_add(&req->queue, insert_after);
    }

    int elevator_linus_merge(request_queue_t *q, struct request **req,

    --
    Peter Österlund Email: peter.osterlund@mailbox.swipnet.se
    Sköndalsvägen 35 f90-pos@nada.kth.se
    S-128 66 Sköndal Home page: http://home1.swipnet.se/~w-15919
    Sweden Phone: +46 8 942647

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 12:39    [W:0.029 / U:1.228 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site