BFQ: simple elevator

[Raymond Jennings]

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.