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