Interesting comments and analyses--just what I was hoping for. Usenet at
it's finest.
As Linus (and others) brought to light, the killer for a true elevator
algorithm is a burst of requests to the same area of the disk, but not in
the same direction that the elevator (or sawtooth) is moving. You'd really
like to have shortest-latency first for these. The trick is knowing when to
_stop_, so that others don't starve.
Other than this, a true elevator would seem to give the best mix between
short latency and fairness. Note that you only need to consider the current
request (i.e., the current position of the heads) for this "shortest-seek",
because a new request will be automatically put in the optimal order if it
fits in further down the list.
Some of the ideas that people tossed in were WAAAAAAAAY too complicated, but
did give me an idea which should be simple to implement and avoid the
possibility of starving some requests:
1) real elevator-ordering, but
2) if a new request is within X sectors (or cylinders) of the CURRENT
request, insert it near the front. IOW, there would be a small clustering
of new requests (ordered perhaps by smallest distance between requests (i.e.,
shortest latency)) right after the current request. X would be chosen to
represent a seek of half-a-dozen cylinders or less.
This would catch a flurry of I/O to a small area--such as loading an
executable--no matter which way the overall elevator was going.
3) To prevent starvation, there would be a flag to say to NOT do step #2.
This would get set when all the I/O request blocks were in use (or some
other easy-to-determine event), and get cleared when the overall elevator
hit the end and reversed direction.
4) [optional] Maybe only _reads_ would be considered in step #2.
Yes, I can't stress enough that this must be THROUGHLY tested and
benchmarked.
My thoughts here are to do all these:
1) make dep
2) make clean zImage
3) umsperf
4) Bonnie
5) multiple greps (as suggested by Linus)
6) untar the kernel
7) emacs a large file, and immediately quit
All these should be run 5-10 times. Average time should be better than
current sawtooth, and there should not be any large (i.e., bad) peak.
Regards,
Ray