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