Messages in this thread | | | Date | Tue, 15 Apr 2008 10:22:36 +0200 | From | Jens Axboe <> | Subject | Re: [RESEND][RFC] BFQ I/O Scheduler |
| |
On Tue, Apr 01 2008, Fabio Checconi wrote: > [sorry for reposting, wrong subject] > > Hi, > we are working to a new I/O scheduler based on CFQ, aiming at > improved predictability and fairness of the service, while maintaining > the high throughput it already provides. > > The patchset, too big for lkml posting, is available here: > http://feanor.sssup.it/~fabio/linux/bfq/patches/ > > The Budget Fair Queueing (BFQ) scheduler turns the CFQ Round-Robin > scheduling policy of time slices into a fair queueing scheduling > of sector budgets. More precisely, each task is assigned a budget > measured in number of sectors instead of amount of time, and budgets > are scheduled using a slightly modified version of WF2Q+. The > budget assigned to each task varies over time as a function of its > behaviour. However, one can set the maximum value of the budget > that BFQ can assign to any task. > > The time-based allocation of the disk service in CFQ, while having > the desirable effect of implicitly charging each application for > the seek time it incurs, suffers from unfairness problems also > towards processes making the best possible use of the disk bandwidth. > In fact, even if the same time slice is assigned to two processes, > they may get a different throughput each, as a function of the > positions on the disk of their requests. On the contrary, BFQ can > provide strong guarantees on bandwidth distribution because the > assigned budgets are measured in number of sectors. Moreover, due > to its Round Robin policy, CFQ is characterized by an O(N) worst-case > delay (jitter) in request completion time, where N is the number > of tasks competing for the disk. On the contrary, given the accurate > service distribution of the internal WF2Q+ scheduler, BFQ exhibits > O(1) delay. > > We made several tests to measure the aggregate throughput, long-term > bandwidth distribution and single-request completion time guaranteed > by CFQ and BFQ; what we present here was obtained with an outdated > version of the code, we are in the process of collecting data for > the current one (see [1]). > > In the first type of tests, to achieve a higher throughput than CFQ > (with the default 100 ms time slice), the maximum budget for BFQ > had to be set to at least 4k sectors. Using the same value for the > maximum budget, in the second type of tests, BFQ guaranteed a maximum > deviation from the desired bandwidth distribution in the order of > 3% over all the experiments. On the contrary CFQ exhibited a maximum > deviation of 28% in consequence of the different positions of the > files on the disk. > > Slowest task's bw (MB/s) Fastest task's bw (MB/s) > ------------------------------------------------------------------- > BFQ (2 files) 9.81 +/- 0.47 9.95 +/- 0.43 > CFQ (2 files) 8.61 +/- 0.67 11.92 +/- 0.44 > ------------------------------------------------------------------- > BFQ (5 files) 4.29 +/- 0.10 4.31 +/- 0.09 > CFQ (5 files) 4.01 +/- 0.17 5.24 +/- 0.14 > > Finally, we set up a VLC video streaming server to stream an > increasing number of movies in presence of disturbing ON/OFF random > file readers. Each test ended when a 1% packet loss was reached > (a packet was deemed as lost if transmitted with a delayed of more > than 1 second). With BFQ it was possible to transmit at most 24 > movies in parallel (again with a 4k sectors maximum budget), against > 15 movies with CFQ (with a time slice of 20 ms). This is likely > to be a consequence of the higher jitter of CFQ. > > Nr. of movies Aggr. bw (MB/s) > --------------------------------------------------------------- > BFQ (max_budget=4096) 24.00 +/- 0.00 7.56 +/- 0.87 > BFQ (max_budget=16384) 18.70 +/- 9.45 12.78 +/- 5.64 > CFQ (slice_sync=20) 14.35 +/- 1.40 12.59 +/- 2.12 > > More stuff related to BFQ (extended results, the test programs used > and the setup for the tests, a document describing the algorithm in > detail and so on) can be found at: > > [1] http://algo.ing.unimo.it/people/paolo/disk_sched/ > > We would greatly appreciate any sort of feedback from you, comments, > suggestions, corrections and so on. Thank you for your attention.
Fabio, I've merged the scheduler for some testing. Overall the code looks great, you've done a good job!
I didn't touch patches 2 and 3, but I rewrote #1 somewhat. See the result here:
http://git.kernel.dk/?p=linux-2.6-block.git;a=commitdiff;h=973a02c4ea1c324c41e45b69c074b13d3bfa97de;hp=a985aabe4d7a720b109c2b63549f8641676a9c88
I'm sure you'll agree with the hlist_sched_*() functions. I also killed the ->bfq_ioprio_changed modification, what exactly was the purpose of that?
The code is now in the 'bfq' branch of the block git repo.
-- Jens Axboe
| |