Messages in this thread Patch in this message |  | | Subject | Re: An elevator algorithm (patch) | From | Peter Osterlund <> | Date | 18 Sep 2000 23:53:30 +0200 |
| |
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/
|  |