Linux io调度器有很多种，大多数调度器都经受住了各种市场环境的长时间验证，稳定性、性能得到各种用户的认可，但新的调度器依然展露头角，在4.12内核中出现了一个新的bfq调度器，这个调度器将取代曾经的辉煌的cfq调度器。社区对待大的改动都是很谨慎的，为什么社区最终接受未经市场考验过的bfq调度器呢，本文结合bfq代码对此做个介绍。

一、bfq是什么

bfq全称Budget Fair Queueing，是Paolo Valente在2010年提出的一个IO调度器，目标是取代cfq。这里的“Budget”是指磁盘扇区sector，“Budget Fair”是指存储设备公平地对待每个进程，为各个进程服务相同数量的sector。图1描述了bfq的内部逻辑，这张图可以快速了解bfq调度器的特点。

图1 BFQ 逻辑图

图片引用自《High Throughput Disk Scheduling with Fair Bandwidth Distribution》

1) 实线箭头代表IO请求的路径方向。这与其他的调度器一样，都是通过add_request类函数，将IO请求插入到进程的IO队列中，然后通过调度器的调度，由 dispatch函数下发到驱动处理。

2) 虚线箭头代表bfq特有的budget特性。每个进程被分配了一定数量的budget，当该进程被bfq选择执行io时，最多只能访问这么多个budget。没访问一个sector，budget减1，budget用完了，bfq就会选择其他的进程执行io。执行io请求的进程由于某种原因过期时（budget用完了是一种原因），会基于上一次用了多少个budget重新估算下一次的budget数量。

3) “Next active application selection”逻辑是每个IO调度器都有的核心功能，bfq中的这个功能与其他调度器不一样，其他的调度器会在系统中所有的IO队列中选择一个调度执行，而bfq只会在“eligible”属性的IO队列中选择一个调度执行（“eligible属性队列集”是“系统所有IO队列集”的子集），bfq的这个特性非常重要，是后面提到的bfq优势的理论基础。

二、bfq优势

调度器的设计离不开两个核心指标：高吞吐量、快速响应，但这两个指标是矛盾的，如何平衡这两个指标成了调度器首先要考虑的事。

bfq通过Budget based Worst-case Weighted fair Queueing (b-wf2q+)算法尽可能地最优化这两个指标，自动识别出batch类进程、交互式进程，确保交互式进程快速响应的前提下，尽可能地保证batch类进程的高吞吐量。

我们测试了有后台负载的情况下（3线程读，1线程写）冷启动高德地图的时间，在4个测试的调度器中，bfq表现最优。

（测试命令：Hikey-Tester.sh-sched  noop/none/cfq/bfq  -r 3  -w 1）

图2 高德地图冷启动时间

另外，在不同的负载模型下（10个随机读10r-rand，10个顺序读10r-seq，5个随机读5个随机写5r5w-rand，5个顺序读5个顺序写5r5w-seq）bfq的吞吐量优于或基本持平其他调度器。

图3调度器吞吐量

三、bfq优于其他调度器的原因

没有什么黑科技，原因有3个：

1）简单的“budget fair”策略（主要原因）

bfq选择进程执行io，有的进程只需少量的budget就能完成数据需求，有的进程则需要大量的budget才能完成数据需求，对于只消耗了少量的budget进程，必须频繁调度该进程才能保证它的budget公平。因交互式进程只需少量的budget，所以该策略可以保证交互式进程的快速响应特性。

每个进程被调度执行io时，有一个budget变量控制该进程最多能访问多少磁盘sector，每当进程访问了一些sector，budget就减去相应的sector数值，如果budget为0，该进程expire，bfqq选择新的进程执行io。

2）权重管理（辅助原因）

进程权重越大，budget增长越慢（意味着调度更频繁）。

3）新进程权重临时提升（辅助原因）

新进程创建时，短时间内会有大量IO请求，比如加载lib库、读写配置文件等等，临时提升权重有助于让新进程能有更多的时间访问存储设备，从而加快进程启动速度。

4）deceptive idleness（辅助原因）

进程发送一个同步io请求后，需要等待该io完成，才能发送下一个io请求。如果在等待期间，将当前进程expire掉，然后执行其他进程的io，这会影响当前进程的吞吐量。bfq的做法是同步io发送后，等待一小段时间Twait，看看有没有新的io到来。

结合代码对上述几点做个说明，bfq的算法伪代码如下：

1）add request将request插入到bfq中

line1~2每个进程都有一个bfq队列，一个时刻只有一个进程占有存储设备的使用权，这个进程叫做active_appl。首次成为active_appl的进程，被分配了一个remaining_budget，表示该进程还允许访问多少个磁盘sector。进程访问磁盘N个sector后，remaining_budget需减去N，当remaining_budget=0时，bfq将选择新的进程做为active_appl。

line 5~18 将request插入到第i个进程的队列中appl.queue。

如果appl.queue是空队列（两个可能：第1，已经不是active状态；第2，队列正处于deceptive idleness，等待下一个请求的到来，是active状态）需要做一些处理。若appl不是active_appl，调用b−wf2q+_insert插入bfq调度器红黑树管理结构中，若appl处于deceptive idleness状态，停止定时器计时。

2）dispatch request分发request给驱动处理

line24~38 当前active_appl的remaining budget小于即将处理的next req的大小，说明当前active_appl已经用完了分配给它的budget，需要更新相关状态并重新插入到bfq管理结构中。

line27~28 更新进程的vfinishtime，算法很简单，简单地对vfinishtime做个增长，增长值为基于权重、实际访问的磁盘sector数算出的一个虚拟值。该策略确保权重大的进程vfinishtime小，能够被调度的更频繁。

line30~34 由于该进程是用完了分配给它的budget，说明这次分配的budget少于实际需求，下一次需要分配更多的budget，代码中按BUDG INC STEP做了增量，但最大值不能超过active_appl.max_budget。该策略确保batch类进程每次处理较大的数据量，保证高吞吐需求。

line39~43 选择一个新的active_appl。

line45~49 选择下一个要处理的request，并将remaining budget值减去next_request.size。

line50~51 处理deceptive idleness场景，设置一个定时器，等待Twait时长。该策略确保连续发送同步io进程的吞吐量不下降。

line54 更新系统以及服务的budget数量。

line56 返回request，这个request即将被驱动处理。

3）b−wf2q将进程队列插入到bfq管理数据结构

V是存储器件累计访问的budget数，任何进程访问了磁盘sector，都会增加V，比如访问了n个sector，那么V = V + n。

进程的appl.F（bfq中叫finish time）会根据权重对实际访问的sector数量做个转换，作为该进程本次增长的budget数量。

进程的appl.S（bfq中叫做start time）一般情况下等于appl.F（这是一种简单的近似方法，如果用精确的方法，bfq作者认为太复杂）。

如果appl.S < V，那么这个进程是eligible属性，bfq会在eligible属性的进程中选择一个执行io。

四、结语

bfq的主算法思想极其简单：一个进程被调度执行，如果消耗完了分配给它的budget，那么就增加下一次的budget数量，反之则减少，类似于一个自适应算法。

bfq代码中还有很多trick，比如权重提升机制，peak rate估算方法等等，这许多机制使得bfq能够适应各自复杂的场景。

目前google chrome，Fedora等大公司已经在采用了bfq，预计一两年后会有越来越多的公司采用bfq调度器。