Messages in this thread |  | | Date | Thu, 8 Aug 1996 10:29:55 -0500 | From | "Ray Van Tassle-CRV004" <> | Subject | RE: I/O request ordering |
| |
To: linux-kernel@vger.rutgers.edu From: Van Tassle-CRV004 Ray on Thu, Aug 8, 1996 10:25 AM Subject: RE: I/O request ordering
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
|  |