lkml.org 
[lkml]   [2000]   [Sep]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    SubjectRe: An elevator algorithm (patch)
    From
    Date
    Andrea Arcangeli <andrea@suse.de> writes:

    > > The only disadvantage I can see is that the new patch doesn't handle
    > > consecutive insertions in O(1) time, but then again, the pre-latency
    >
    > We can still do that by trivially fixing a bit your code. You should first
    > check if the new inserted request is over the last in the current queue before
    > entering the tmp1/tmp2 logic.

    Yes this can be done, but it will affect where requests are inserted.
    Suppose the queue currently contains:

    100 200 300 400 10 20 30

    If request 150 is to be inserted, then with my previous patch it will
    be inserted between 100 and 200, but with the proposed change it will
    instead be inserted at the end. This is good for latency because there
    will be less reordering, but potentially harmfull for streaming
    performance because the total disk head traveling distance increases.

    Anyway, I tested a new patch with your suggestion, and indeed this
    change doesn't seem to cause too many extra seeks. I set the r/w
    latencies to 1000/5000, and the iozone and Bonnie test produced almost
    the same values as before.

    I also noted that I could (almost) play an mp3 file with a 48Kb
    buffer during "cp /dev/zero tmpfile". There is one rather large
    skip a few seconds after the copy starts, but after that there are
    only small occasional skips. I also ran iozone while playing the mp3,
    and there were no major sound skips, and iozone only ran 7% slower
    than without mpg123 running.

    Thanks again for you comments. Here is the new 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 Mon Sep 18 22:40:53 2000
    @@ -34,20 +34,57 @@
    struct list_head *real_head,
    struct list_head *head, int orig_latency)
    {
    - struct list_head *entry = real_head;
    - struct request *tmp;
    + struct list_head *last = real_head->prev;
    + struct list_head *insert_after = last;
    + struct list_head *entry;
    + struct request *tmp1, *tmp2;
    + int do_insert;

    req->elevator_sequence = orig_latency;

    - while ((entry = entry->prev) != head) {
    - tmp = blkdev_entry_to_request(entry);
    - if (IN_ORDER(tmp, req))
    + if (last == head)
    + goto out;
    +
    + entry = last;
    + tmp1 = blkdev_entry_to_request(entry);
    + if (IN_ORDER(tmp1, req))
    + goto out;
    + do {
    + tmp2 = tmp1;
    + entry = entry->prev;
    + tmp1 = blkdev_entry_to_request(entry);
    + if (!tmp2->elevator_sequence)
    break;
    - if (!tmp->elevator_sequence)
    + do_insert = 0;
    + if (entry == real_head) {
    + /*
    + * Since we don't know were the disk head is
    + * currently located, we can not really know
    + * if the request should be inserted here. The
    + * best bet is probably not to insert the
    + * request here, because otherwise the
    + * elevator would be unfair to sectors at the
    + * end of the disk.
    + */
    + } else if (IN_ORDER(tmp1, tmp2)) {
    + if (IN_ORDER(tmp1, req) && IN_ORDER(req, tmp2))
    + do_insert = 1;
    + } else {
    + if (IN_ORDER(tmp1, req) || IN_ORDER(req, tmp2))
    + do_insert = 1;
    + }
    + if (do_insert) {
    + insert_after = entry;
    + do {
    + entry = entry->next;
    + tmp1 = blkdev_entry_to_request(entry);
    + tmp1->elevator_sequence--;
    + } while (entry != last);
    break;
    - tmp->elevator_sequence--;
    - }
    - list_add(&req->queue, entry);
    + }
    + } 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:38    [W:0.028 / U:0.732 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site