is it possible to go ahead and use the one way elevator for writes (which
can be buffered so as long as you have the RAM delays don't matter) and
some other method fow reads which stop programs until they are completed?
David Lang
On Thu, 19 Nov 1998, Andrew J. Scott wrote:
> Date: Thu, 19 Nov 1998 09:26:51 -0500
> From: Andrew J. Scott <A.J.Scott@casdn.neu.edu>
> To: Ben Kosse <BKosse@thecreek.com>, linux-kernel@vger.rutgers.edu
> Subject: RE: elevator algorithm bug in ll_rw_blk.c
>
> On 18 Nov 98, at 9:17, Ben Kosse wrote:
>
> > > 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/
>
-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv
iQEVAwUBNlS3wj7msCGEppcbAQFP7Qf8DvOqgg4kHSTPZ0olxzhI6GXPxfZckGHb
fQzSuB0q49SElb1lhJoH/EEFUeFAwoxm//FBJ6R00l2lykIwVW3x08P5XVCqRjW7
u0oZH6LYfOlKGlTRb5EFAoUuEIxqUaDQx8hYK4kRl2WMcn33O+IpupO/e8ml6oiN
FXTKgc4nz4Pk+rqEftSgLdGeisiIzO5Rx3U0Qofk7BtKcvZU8DvOsY44kLk0mMSe
QdA8jXqnw1hy+cP99KFwPtQCm+FHkigjvjgpjdd/r7WtumVC+qhPUjfSnohaSgFj
Oi1jYcN3n5jKEltT0+BpPK+/kZm2wV/zXbHT+RxjA3++wnejdJvU9g==
=zZnf
-----END PGP SIGNATURE-----
-
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/