RE: elevator algorithm bug in ll_rw_blk.c
Lyle Seaman (lyle@stormsystems.com)
Mon, 16 Nov 1998 09:47:28 -0500
You don't need to completely sort the dirty block list, you can get
away with maintaining a partial order. For instance, insert the dirty
blocks into a hash table (really, a bin sort) using the function
(blkno>>6)&&0x7f. This isn't O(n), it's O(1). Starvation won't occur
as long as you have some arbitrary limit on how deep you dig into the
current bin before progressing to the next one -- it doesn't even have
to be the same arbitrary limit for each bin.
You could do still better than that, at the cost of added complexity
(again, for example, you might want to sort the current bin before
transfering things to the request queue.)
The more tags the disk supports, the less critical the exact ordering
becomes -- you just let the disk optimize things.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/