phys169@csc.canterbury.ac.nz (06/05/91)
Here's a question somebody may be able to answer: If software on a PC was to order read requests in such a way as to reduce head movement (I think some file servers use this, called "elevator optimisation" or similar), with the fast disks in use today, how much improvement is possible? Or is the time required to calculate it significant compared to the head movement time. I could look up disk specs and write some sample programs, but what I need is some experience from people who have used it - is it generally a worthwhile exercise? I suspect that the ideal is for the controller cards to have the intelligence to do this, since some operating systems manage to get the CPU to do useful stuff while waiting for the disk, not DOS, of course! :-( Thanks in advance, Mark Aitchison, Physics, University of Canterbury, New Zealand.
rhyde@hubbell.ucr.edu (randy hyde) (06/06/91)
First of all, disk head seek optimizations are really only useful for multitasking operating systems. Sure, it might be of marginal benefit for single task OSes (like DOS) but a defragger would do a much better job for you. In a multitask OS, there is the optimal disk head scheduler, the shortest seek time first scheduler, and the SCAN/LOOK & C-SCAN/C-LOOK algorithms (there are others, but they generally aren't worth consideration unless you have special requirements [that wouldn't be general, now, would it?]). The optimal disk head scheduler is an O(N**2) or O(N**3) algorithm (I forget which, it's been a couple of years since I had combinatorics). It's known as the shortest path through a graph with positive weights. Except for small lists of requests, the time to compute the path (and recompute it every time you add a new request to the queue) overwhelms other concerns. Shortest seek time first suffers from one minor problem- starvation. It's quite possible that a request off to one end of the disk would never get serviced if a steady stream of requests keep coming in at the other end of the disk. The *average* seek time (and average response) time is pretty good (almost as good as the optimal in most cases), but a couple of processes could wind up waiting a *long* time. Scan processes requests from block zero to the last block, then processes requests from the last block to zero (LOOK is similar, except it doesn't go to the ends of the disk, only to the last request in each direction). C-SCAN/LOOK (Circular SCAN) processes the requests from block zero to the end of the disk, then moves the head back to zero and processes them towards the end. This may seem far worse than SCAN/LOOK, but if you consider that the disk head can move from beginning to end in only about five times the amount of time it takes to move from track to track, you can see why people do this. *** Randy Hyde
iverson@xstor.com (Tim Iverson) (06/07/91)
In article <1991Jun5.111750.951@csc.canterbury.ac.nz> phys169@csc.canterbury.ac.nz writes: >If software on a PC was to order read requests in such a way as to reduce head >movement (I think some file servers use this, called "elevator optimisation" or >similar), with the fast disks in use today, how much improvement is possible? DOS is single tasking. This means only one request for i/o happens at a time. If there is only one request, you have nothing optimize. If you are talking about a multitasking system on a PC (not DOS), then yes, you can improve by leaps and bounds over FIFO by using an algorythm that reduces seek distances and/or latency time - latency is very hard (impossible?) to reduce by scheduling and remain efficient. Typically, head schedulers run O(n log n), but since you can save several milliseconds by rescheduling just one movement correctly, it more than pays for itself. See your favorite OS text for an intro on head scheduling. >Mark Aitchison, Physics, University of Canterbury, New Zealand. - Tim Iverson iverson@xstor.com -/- uunet!xstor!iverson
iverson@xstor.com (Tim Iverson) (06/08/91)
In article <1991Jun07.024728.29844@xstor.com> iverson@xstor.com (Tim Iverson) writes: >you can improve by leaps and bounds over FIFO by using an algorythm that >reduces seek distances and/or latency time - latency is very hard >(impossible?) to reduce by scheduling and remain efficient. Argghh. I forgot about SCSI's modify data pointer: 0 latency by telling the host adapter what block is coming (perhaps different from the initially requested block) and then transferring the block under the head *now*. Above, I was referring to reducing latency via head scheduling - certainly possible, but probably prohibitively expensive in terms of calculation time. - Tim Iverson iverson@xstor.com -/- uunet!xstor!iverson