I/O request ordering

Ray Van Tassle-CRV004 (Ray_Van_Tassle-CRV004@email.mot.com)
Mon, 5 Aug 1996 11:37:25 -0500


From: Van Tassle-CRV004 Ray on Mon, Aug 5, 1996 11:30 AM
Subject: I/O request ordering
To: linux-kernel@vger.rutgers.edu@INTERNET

This message was sent using a custom form that is not installed on your
server. Some information from the original message may not be displayed. To
view the complete message, ask your network manager to install the form on
your server.

For some time, I have had doubts about the I/O request ordering algorithm in
drivers/block/ll_blk_rw. Upon examination, it turned out that (as I
suspected) it is a sawtooth rather than an elevator. And it also
has a bug.
I rewrote it to accomplish a true elevator, ordered purely by sector
number. (It would be better to order by cylinder, but that's too hard to
get.) As an added benefit, the new code has a simpler inner loop.

Two trial runs are shown below, with random sector numbers. The 1st
is rising, the 2nd is falling. The bug in the original code is the
placement of sectors 245 & 251---they belong after 231 and not
at the end.

I'll be sending this patch to Linus shortly, after I've done some
benchmarking---rebuilding the kernel seems like a good benchmark.

Any comments??

Regards,
Ray Van Tassle
rayvt@comm.mot.com

Adding to empty queue:
166 231 148 61 50 131 0 57 126 223 44 245 138 251 24 113 86 215 196
Final Queue (original sawtooth):
166 196 215 223 231 0 24 44 50 57 61 86 113 126 131 138 148 245 251
Final Queue (elevator):
166 196 215 223 231 245 251 148 138 131 126 113 86 61 57 50 44 24 0

Adding to empty queue:
148 61 50 131 0 57 126 223 44 245 138 251 24 113 86 215 196 173 226
Final Queue (original sawtooth):
148 0 24 44 50 57 61 86 113 126 131 138 173 196 215 223 226 245 251
Final Queue (elevator):
148 138 131 126 113 86 61 57 50 44 24 0 173 196 215 223 226 245 251