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