新型 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
  • 高级微控制器总线结构完美解析

    高级微控制器总线结构AdvancedMicrocontrollerBusArchitecture(AMBA)定义了高性能嵌入式微控制器的通信标准。可以将RISC

    11-24
  • 详解:汽车电子技术之汽车仪表盘MCU

      随着汽车电子技术的飞速发展,传统的车用机械仪表盘已呈现出向数字仪表过度的趋势,与之对应的全部功能显示也将被渲染后的高清画面所取代。而引起这一巨大变革的根源,

    11-24
  • 为物联网应用选择合适的8位MCU通信接口

      SiliconLabs已经在"采集、计算和通信"的指导思想下开发出各类兼容8051内核的8位MCU。在之前的文章中,我们已经对模拟采集接口和8051计算引擎

    11-24
  • 基于msp430单片机定时器的使用方法解析

    通过计算设置周期。#includevoidmain(void){//StopwatchdogtimertopreventTImeoutresetWDTCTL=W

    11-24
  • 如何利用51单片机同时扩展RAM和ROM

    下面这个系统中,8051同时扩展片外程序存储器和数据存储器,两片存储器的片选信号都接地,即同时有效,也就是说,这两片存储器无需选择。51同时扩展RAM和ROM下

    11-24
  • PICOCAP 测量原理介绍

    1 前言电容传感器在很多工业和消费类产品中都有非常广泛的应用,因其小尺寸和低功耗以及高精度等方面的特性,在很多领域广受青睐。而对于电容传感器的测量来说,传统的电

    11-23
  • 为什么要选择学习STM32?进来看看了解

    [导读]我对未来的规划是以功能性为主的,在功能和面积之间做以平衡是我的首要选择,而把运算放在第二位,这根我的专业有关系。里面的运算其实并不复杂,在入门阶段想尽量

    11-22
  • STM32学习之启动代码很重要!

    [导读]最近在写一个人机界面,由于硬件同事布板的问题,必须要用到串口4,先开始我还觉得没什么,就是把USART1改成4以及改下开启时钟和配置引脚。但是事实证明我

    11-22
  • STC89c51单片机的定时器T2

    [导读]定时器T2的功能比T1、T0都强大,但描述它的资料不多,可能是使用得比较少的缘故吧。它是一个16位的具有自动重装和捕获能力的定时/计数器,它的计数时钟源

    11-22
  • 怎样混好电子这行?(MCU、ARM、DSP,嵌入式)

    [导读]很多初学者,甚至是混了好几年的老手,都在抱怨,电子这行怎么竞争这么大啊? 颓废,这完全在抹杀自己的激情,没了激情,搞电子,完全就是在浪费生命。其实,竞争

    11-22
  • MCU引脚输出模式中推挽输出与开漏输出电路原理区别

    [导读]开漏输出:输出端相当于三极管的集电极. 要得到高电平状态需要上拉电阻才行. 适合于做电流型的驱动,其吸收电流的能力相对强(一般20ma以内).推挽结构一

    11-22
  • 基于DSPIC30F6014A单片机的智能家居音频信号分析仪的设计 (1)

    目前,大多数音频信号处理仪不但体积大而且价格贵,在一些特殊方面难以普及使用,而嵌入式系统分析仪具有小巧可靠的特点,所以开发基于特殊功能单片机的音频分析仪器是语音识别的基础,具有很好的现实意义。信号分析原理是将信号从时间域转换成频率域,使原始信号中不明显特性变得明显,便于分析处理。对于音频信号来说,其主要特征参数为幅度谱、功率谱。该音频信号分析仪的工作过程为:对音频信号限幅放大、模数转换、快速傅里叶...

    11-22
下载排行榜
更多
广告