[comp.sys.ibm.pc.misc] Disk seek optimisation

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