BFQ: simple elevator

Raymond Jennings shentino at gmail.com
Mon Mar 25 14:19:52 EDT 2013


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.



More information about the Kernelnewbies mailing list