Re: elevator algorithm bug in ll_rw_blk.c

Ben Kosse (bkosse@thecreek.com)
Mon, 16 Nov 1998 12:20:52 -0800

> According to Alan Cox:
> > Chip:
> > > But that's a *one-way* elevator. Ideal elevators are
> > > two-way, aren't they?
> > If you go for the shortest movement alone you starve the
> > edges of the disks.
> I said "two-way", not "shortest movement".
Doesn't matter. It still starves the disk edges. This isn't a problem for
people, because it actually becomes a shortest, same direction seek. This
minimizes the time people spend in the elevator, but not necessarily the time
people spend in the hall outside the elevator. A C-Scan on an elevator would,
indeed, minimize the time people spend waiting to get to their destination, if
you assume that people spread out evenly and somewhat randomly through the
building. However, this would put people on the elevator longer, which if
you've been in any typical college elevator, you'll know why this is a bad
thing. :)

> > If you watch a real elevator you'll see they too use
> > the elevator algorithm
> They stop for passengers going up _or_ down.
Actually, what we use is not the "elevator algorithm" per se. We do the
"C-Scan" algorithm (circular scan?). That is, we start at 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>

During the read of <5>, these requests come in:
<6> <1> <2> <3> <4> <30> <15> <21> <22> <40> <41> <42>

Sorted by Elevator:
<6> <10> <15> <20> <21> <22> <30> <40> <41> <42> <4> <3> <2> <1>

Sorted by C-scan:
<6> <10> <15> <20> <21> <22> <30> <40> <41> <42> <1> <2> <3> <4>

During the read of <22> these requests come in:
<5> <6> <7> <10> <15>

Sorted by Elevator:
<30> <40> <41> <42> <15> <10> <7> <6> <5> <4> <3> <2> <1>

Sorted by C-Scan:
<30> <40> <41> <42> <1> <2> <3> <4> <5> <6> <7> <10> <15>

During the read of <40> these requests come in:
<20> <22> <14>

Sorted by Elevator:
<41> <42> <22> <20> <15> <14> <10> <7> <6> <5> <4> <3> <2> <1>

Sorted by C-Scan:
<41> <42> <1> <2> <3> <4> <5> <6> <7> <10> <14> <15> <20> <22>

See how Elevator gives substantial bonuses to the middle blocks? This is why
C-Scan is the most prevelant seek method to date.

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