新型 IO 调度器 BFQ 简介
内核工匠 2022-09-29

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调度器。

声明: 本文转载自其它媒体或授权刊载,目的在于信息传递,并不代表本站赞同其观点和对其真实性负责,如有新闻稿件和图片作品的内容、版权以及其它问题的,请联系我们及时删除。(联系我们,邮箱:evan.li@aspencore.com )
0
评论
  • 相关技术文库
  • 单片机
  • 嵌入式
  • MCU
  • STM
下载排行榜
更多
评测报告
更多
广告