Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!psuvax1!rutgers!ucsd!ucrmath!hubbell!rhyde
From: rhyde@hubbell.ucr.edu (randy hyde)
Newsgroups: comp.sys.ibm.pc.misc
Subject: Re: Disk seek optimisation
Message-ID: <15006@ucrmath.ucr.edu>
Date: 5 Jun 91 18:02:12 GMT
References: <1991Jun5.111750.951@csc.canterbury.ac.nz>
Sender: news@ucrmath.ucr.edu
Reply-To: rhyde@hubbell.ucr.edu (randy hyde)
Lines: 33

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