BFQ: simple elevator

[Raymond Jennings]

On Sat, Mar 23, 2013 at 7:38 AM, Matthias Brugger
<matthias.bgg at gmail.com> wrote:
> 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?

Your guess is as good as mine.  I've never even heard of it.

My description was very much made up on the fly.