[GSoC]Overview on my GSoC project: Implement BFQ disk scheduling policy

[Brills Peng]

Hi, all:

My GSoC proposal "Improve dsched interfaces and implement BFQ disk
scheduling policy" has been accepted, while it does not mean the plan in
it is totally practical and nailed down. Suggestions/questions are
needed to help me revise the plan. So I will describe the whole thing in
this post.

1. What is the goal?
I will implement a BFQ (Budget Fair Queue)[1] scheduler on the basis of
dsched interfaces. The "improve dsched interfaces" part is not a
ultimate goal but one way to support the "dequeue" trigger needed by BFQ
(I will explain this later). 
Of course, the motivation of doing these is to improve the overall
performance of DFBSD.

2. Why BFQ?
Firstly, a scheduler emphasizes fairness is needed by DFBSD, for it can
improve the interactivity. Secondly, BFQ scheduler performs well in
benchmarks under Linux, both on fairness and the worst case performance,
compared to Linux's CFQ (Completely Fair Queue, a time slice based fair
queue scheduler) [2,3].

3. How to achieve the goal?
Currently, there are three phases:

A. Make dsched adapt to BFQ algorithm (or make BFQ adapt to dsched)

The initial idea is the "improve dsched interface" part -- implement
request polling mechanism for dsched, that is, the lower disk driver
will ask for further requests, instead of waiting for requests
dispatched by dsched. It includes modifying disk drivers and
implementing some new interfaces for dsched. I will ensure backwards
compatibility of the modified drivers and dsched: both request polling
and request dispatching is supported and a scheduler on dsched can
choose between them or both of them.
 
It is only a straightforward idea, and I do not know whether it can work
efficiently or any obstacle exists. Alex Hornung suggests I ask for
alternate (and wiser) way to implement BFQ without request polling. I
hope someone can give me suggestions on this point (or discussion on the
necessity of request polling).

B. Implement BFQ scheduler

As far as I can see, this part does not have problems if part A prepares
good interfaces for BFQ. I will start from scratch to write the whole
scheduler, under the guideline of the technical report written by the
inventor of BFQ[4].

C. Tune and benchmark BFQ scheduler

I think this can probably be the heaviest part of the project. Your
helping hands are needed to test the implementation under different
parameters and different hardware.


That's all. I am eagerly looking forward to your suggestions, especially
on part A the request polling part. I can start to figure out details
once this point is clear.

Sorry for the long post, and thank you.


[1] http://algo.ing.unimo.it/people/paolo/disk_sched/
[2] http://algo.ing.unimo.it/people/paolo/disk_sched/results.php
[3] http://kerneltrap.org/Linux/Budget_Fair_Queuing_IO_Scheduler
[4] http://algo.ing.unimo.it/people/paolo/disk_sched/bfq-techreport.pdf


---
Brills Peng