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    [from the cache]
©2003-2011 Jasper Spaans