BFQ: simple elevator

[Matthias Brugger]

On 03/20/2013 10:41 PM, Raymond Jennings wrote:
> On Wed, Mar 20, 2013 at 2:03 PM,  <Valdis.Kletnieks at vt.edu> wrote:
>> On Thu, 21 Mar 2013 02:24:23 +0700, Mulyadi Santosa said:
>>
>>> pardon me for any possible sillyness, but what happen if there are
>>> incoming I/O operation at very nearby sectors (or perhaps at the same
>>> sector?)? I suppose, the elevator will prioritize them first over the
>>> rest? (i.e starving will happen...)
> This is actually why I proposed to enforce forward progress by only
> looking for further requests in one direction at a time.
>
> Suppose you have requests at sectors 1, 4, 5, and 6
>
> You dispatch sectors 1, 4, and 5, leaving the head parked at 5 and the
> direction as ascending.
>
> But suddenly, just before you get a chance to dispatch for sector 6,
> sector 4 gets busy again.
>
> I'm not proposing going back to sector 4.  It's behind us and (as you
> indicated) we could starve sector 6 indefinitely.
>
> So instead, because sector 4 is on the wrong side of our present head
> position, it is ignored and we keep marching forward, and then we hit
> sector 6 and dispatch it.
>
> Once we hit sector 6 and dispatch it, we do a u-turn and start
> descending.  That's when we pick up sector 4 again.
>
> When we're going up, we ignore what's below us, and when we're going
> down we ignore what is above us.
>
> We only switch directions when there's nothing in front of us the way
> we were going.  In theory, given that disk capacity is itself finite,
> so too is the amount of time one has to wait before getting reached by
> the elevator.
>
> Anyway, does this clarification answer your concerns about starvation?
>
>> And this, my friends, is why elevators aren't as easy to do as the average
>> undergrad might hope - it's a lot harder to balance fairness and throughput
>> across all the corner cases than you might think.  It gets really fun
>> when you have (for example) a 'find' command moving the heads all over
>> the disk while another process is trying to do large amounts of streaming
>> I/O.  And then you'll get some idiot process that insists on doing the
>> occasional fsync() or syncfs() call.  Yes, it's almost always *all*
>> corner cases, it's very rare (unless you're an embedded system like a Tivo)
>> that all your I/O is one flavor that is easily handled by a simple elevator.
> In my case I'm just concerned with raw total system throughput.
>
> I called it "BFQ" for a reason.

It sounds to me like the LOOK disk scheduling algorithm from 1970? Or do 
I miss something?