Re: elevator algorithm bug in ll_rw_blk.c

Kai Henningsen (kaih@khms.westfalen.de)
16 Nov 1998 21:19:00 +0200


petersv@psv.nu (Peter Svensson) wrote on 15.11.98 in <Pine.LNX.4.04.9811151904210.645-100000@cheetah.psv.nu>:

> Normally you use a one-way scan. A two-way scan is unfair, it will service
> different parts of the disks diffrently. Specifically the edges will on
> average have a longer wait than the central parts.
>
> Imagine a request being placed just after the head passed the track. If it
> is in the central region it will at most wait for the head to seek
> 1/2+1/2=1 disk (seek to the edge and back). On the periphery it will have
> to wait at most 1+1=2.

But on the other hand, the opposite is true for *minimum* wait times (1
whole disk seek for the middle, no seek at all for the edge).

>From this it follows that the average wait time is the same, and your
claim that it is longer at the edges is obviously wrong.

(You can also see it by recognizing that the two-way scan is actually two
one-way scans, with opposite directions, interleaved with each other.
Every half is fair, they are equal, so combining the two *cannot* become
unfair. Not even if Linus claims it.)

> A long seek does not take that much longer than a medium one using a

This is of course true - if you have a decent ballistic algorithm (like,
say, Apple DOS had on the floppies) and not a braindead constant-low-speed
one (as MS-DOS tends to have on floppies, IIRC). And I'd expect modern
hard disk to have good ballistical algorithms.

> unidirectional scan lowers the max-norm of the wait.

I suspect that highly depends on the usage pattern.

The *real* reason two-way is a bad idea is that I strongly suspect that a
lot of modern disks react fairly suboptimal when asked for same-track
sectors in descending order. Which is a shame, because I've seen (and
improved) such an algorithm back in my Apple ][ days, sometime in the late
'80s (it could read from a floppy in real time, whatever sector was
requested and came under the head next, and it could write nearly in real
time, needing a little preprocessing). But it seems people don't
appreciate the performance boost this gives until they've actually
experienced it.

And since we can't reprogram the hard disk (yet), there's nothing we can
do about this.

MfG Kai

-
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/