> > the bottom, move to
> > > the top, and repeat. This algorithm is the most fair to the
> > entire disk.
> > > Here's a sample request sequence to show you:
> > >
> > > Initial queue:
> > > <10> <5> <20>
> > >
> > > Sorted by Elevator:
> > > <5> <10> <20>
> > >
> > > Sorted by C-Scan:
> > > <5> <10> <20>
> >
> > Your version of the 2 way elevator resorts all not yet
> > serviced requests.
> This is exactly how an elevator (in real life) behaves. If it is on its way
> and has sufficient capability to stop (most elevators have to be at least a
> floor away, some high speed elevators need to be farther away) it will
> insert the query at the appropriate spot.
The big problem with the elevator analogy, is that if the elevator is
filled on the ground floor, with people who are going to the top floor,
people on the floors in between may have to wait for it to make a complete
round trip to get on.
> Most things which read "track-at-a-time" have a built-in cache which starts
> at the current head position, so you still have track-backwards reading. In
> addition, you have lots of head movement switching (read forward, skip back,
> read forward, skip back) on the down side.
>
> That said, I'm still not convinced that your algorithm has a better normal
> case situation. It has the same worst normal case (one full seek in one
> direction, but a pendantic situation could arrive which puts you at over one
> full seek--you need to put the first and last block on the list to arrive at
> this with other sorted blocks), but still benefits the middle more than the
> edges.
Ok, I've thought this out more thoroughly (sorry about spelling), and I
hope, completely. The problem with both methods is that you can't
guarantee the minimum time to service a request. With the circular method
(one way elevator) if you have a group of requests, of which the first is
for data in an area you've just passed, all of the other requests will be
filled first. In an unsorted system, that request would have been filled
first. Although you can guarantee that the request will be filled in one
sweep of the disk, you can't guarantee that the system isn't going to read
the _entire_ surface of the disk in that sweep before that early request
is granted. By not resorting requests that have already been sorted, and
by limiting the number of requests that will be sorted at one time, you
_can_ make some guarantees as to the maximum time to servicing a request.
> > At any rate, I beleive that two way elevators can be fair,
> > and not cause starvation at the edges.
There is some unfairness about all of these, the main idea, I think, is to
keep the disk channel as full as possible, which is what sorting does, and
makeing sure that you don't read the entire disk before you get around to
servicing an early request the get's sorted to the end.
Also, if you put a limit on the number of requests the will be sorted at
one time, it might be wise to make it adjustable. Fast disk systems might
do better with a large number of requests, while slower disk systems might
require smaller numbers.
> s/cause starvation/cause as much starvation/
> It is an interesting algorithm. I'll have to look at it more fully.
> However, like Larry said, it may get thrown out in the wash anyway. -- Ben
> Kosse bkosse@thecreek.com PC Support Analyst Coldwater Creek Inc. (208)
> 265-7114
------------------Mailed via Pegasus 2.53 & Mercury 1.30---------------
A.J.Scott@casdn.neu.edu Fax (617)373-2942
Andrew Scott Tel (617)373-5278 _
Northeastern University--138 Meserve Hall / \ /
College of Arts & Sciences-Deans Office / \ \ /
Boston, Ma. 02115 http://www.casdn.neu.edu / \_/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/