Linux io調(diào)度器有很多種，大多數(shù)調(diào)度器都經(jīng)受住了各種市場環(huán)境的長時間驗證，穩(wěn)定性、性能得到各種用戶的認可，但新的調(diào)度器依然展露頭角，在4.12內(nèi)核中出現(xiàn)了一個新的bfq調(diào)度器，這個調(diào)度器將取代曾經(jīng)的輝煌的cfq調(diào)度器。社區(qū)對待大的改動都是很謹慎的，為什么社區(qū)最終接受未經(jīng)市場考驗過的bfq調(diào)度器呢，本文結(jié)合bfq代碼對此做個介紹。

一、bfq是什么

bfq全稱Budget Fair Queueing，是Paolo Valente在2010年提出的一個IO調(diào)度器，目標是取代cfq。這里的“Budget”是指磁盤扇區(qū)sector，“Budget Fair”是指存儲設(shè)備公平地對待每個進程，為各個進程服務(wù)相同數(shù)量的sector。圖1描述了bfq的內(nèi)部邏輯，這張圖可以快速了解bfq調(diào)度器的特點。

圖1 BFQ 邏輯圖

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

1) 實線箭頭代表IO請求的路徑方向。這與其他的調(diào)度器一樣，都是通過add_request類函數(shù)，將IO請求插入到進程的IO隊列中，然后通過調(diào)度器的調(diào)度，由 dispatch函數(shù)下發(fā)到驅(qū)動處理。

2) 虛線箭頭代表bfq特有的budget特性。每個進程被分配了一定數(shù)量的budget，當該進程被bfq選擇執(zhí)行io時，最多只能訪問這么多個budget。沒訪問一個sector，budget減1，budget用完了，bfq就會選擇其他的進程執(zhí)行io。執(zhí)行io請求的進程由于某種原因過期時（budget用完了是一種原因），會基于上一次用了多少個budget重新估算下一次的budget數(shù)量。

3) “Next active application selection”邏輯是每個IO調(diào)度器都有的核心功能，bfq中的這個功能與其他調(diào)度器不一樣，其他的調(diào)度器會在系統(tǒng)中所有的IO隊列中選擇一個調(diào)度執(zhí)行，而bfq只會在“eligible”屬性的IO隊列中選擇一個調(diào)度執(zhí)行（“eligible屬性隊列集”是“系統(tǒng)所有IO隊列集”的子集），bfq的這個特性非常重要，是后面提到的bfq優(yōu)勢的理論基礎(chǔ)。

二、bfq優(yōu)勢

調(diào)度器的設(shè)計離不開兩個核心指標：高吞吐量、快速響應(yīng)，但這兩個指標是矛盾的，如何平衡這兩個指標成了調(diào)度器首先要考慮的事。

bfq通過Budget based Worst-case Weighted fair Queueing (b-wf2q+)算法盡可能地最優(yōu)化這兩個指標，自動識別出batch類進程、交互式進程，確保交互式進程快速響應(yīng)的前提下，盡可能地保證batch類進程的高吞吐量。

我們測試了有后臺負載的情況下（3線程讀，1線程寫）冷啟動高德地圖的時間，在4個測試的調(diào)度器中，bfq表現(xiàn)最優(yōu)。

（測試命令：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個順序?qū)?r5w-seq）bfq的吞吐量優(yōu)于或基本持平其他調(diào)度器。

圖3調(diào)度器吞吐量

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學(xué)習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?

三、bfq優(yōu)于其他調(diào)度器的原因

沒有什么黑科技，原因有3個：

1）簡單的“budget fair”策略（主要原因）

bfq選擇進程執(zhí)行io，有的進程只需少量的budget就能完成數(shù)據(jù)需求，有的進程則需要大量的budget才能完成數(shù)據(jù)需求，對于只消耗了少量的budget進程，必須頻繁調(diào)度該進程才能保證它的budget公平。因交互式進程只需少量的budget，所以該策略可以保證交互式進程的快速響應(yīng)特性。

每個進程被調(diào)度執(zhí)行io時，有一個budget變量控制該進程最多能訪問多少磁盤sector，每當進程訪問了一些sector，budget就減去相應(yīng)的sector數(shù)值，如果budget為0，該進程expire，bfqq選擇新的進程執(zhí)行io。

2）權(quán)重管理（輔助原因）

進程權(quán)重越大，budget增長越慢（意味著調(diào)度更頻繁）。

3）新進程權(quán)重臨時提升（輔助原因）

新進程創(chuàng)建時，短時間內(nèi)會有大量IO請求，比如加載lib庫、讀寫配置文件等等，臨時提升權(quán)重有助于讓新進程能有更多的時間訪問存儲設(shè)備，從而加快進程啟動速度。

4）deceptive idleness（輔助原因）

進程發(fā)送一個同步io請求后，需要等待該io完成，才能發(fā)送下一個io請求。如果在等待期間，將當前進程expire掉，然后執(zhí)行其他進程的io，這會影響當前進程的吞吐量。bfq的做法是同步io發(fā)送后，等待一小段時間Twait，看看有沒有新的io到來。

結(jié)合代碼對上述幾點做個說明，bfq的算法偽代碼如下：

1）add request將request插入到bfq中

line1~2每個進程都有一個bfq隊列，一個時刻只有一個進程占有存儲設(shè)備的使用權(quán)，這個進程叫做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，已經(jīng)不是active狀態(tài)；第2，隊列正處于deceptive idleness，等待下一個請求的到來，是active狀態(tài)）需要做一些處理。若appl不是active_appl，調(diào)用b?wf2q+_insert插入bfq調(diào)度器紅黑樹管理結(jié)構(gòu)中，若appl處于deceptive idleness狀態(tài)，停止定時器計時。

2）dispatch request分發(fā)request給驅(qū)動處理

line24~38 當前active_appl的remaining budget小于即將處理的next req的大小，說明當前active_appl已經(jīng)用完了分配給它的budget，需要更新相關(guān)狀態(tài)并重新插入到bfq管理結(jié)構(gòu)中。

line27~28 更新進程的vfinishtime，算法很簡單，簡單地對vfinishtime做個增長，增長值為基于權(quán)重、實際訪問的磁盤sector數(shù)算出的一個虛擬值。該策略確保權(quán)重大的進程vfinishtime小，能夠被調(diào)度的更頻繁。

line30~34 由于該進程是用完了分配給它的budget，說明這次分配的budget少于實際需求，下一次需要分配更多的budget，代碼中按BUDG INC STEP做了增量，但最大值不能超過active_appl.max_budget。該策略確保batch類進程每次處理較大的數(shù)據(jù)量，保證高吞吐需求。

line39~43 選擇一個新的active_appl。

line45~49 選擇下一個要處理的request，并將remaining budget值減去next_request.size。

line50~51 處理deceptive idleness場景，設(shè)置一個定時器，等待Twait時長。該策略確保連續(xù)發(fā)送同步io進程的吞吐量不下降。

line54 更新系統(tǒng)以及服務(wù)的budget數(shù)量。

line56 返回request，這個request即將被驅(qū)動處理。

3）b?wf2q將進程隊列插入到bfq管理數(shù)據(jù)結(jié)構(gòu)

V是存儲器件累計訪問的budget數(shù)，任何進程訪問了磁盤sector，都會增加V，比如訪問了n個sector，那么V = V + n。

進程的appl.F（bfq中叫finish time）會根據(jù)權(quán)重對實際訪問的sector數(shù)量做個轉(zhuǎn)換，作為該進程本次增長的budget數(shù)量。

進程的appl.S（bfq中叫做start time）一般情況下等于appl.F（這是一種簡單的近似方法，如果用精確的方法，bfq作者認為太復(fù)雜）。

如果appl.S < V，那么這個進程是eligible屬性，bfq會在eligible屬性的進程中選擇一個執(zhí)行io。

四、結(jié)語

bfq的主算法思想極其簡單：一個進程被調(diào)度執(zhí)行，如果消耗完了分配給它的budget，那么就增加下一次的budget數(shù)量，反之則減少，類似于一個自適應(yīng)算法。

bfq代碼中還有很多trick，比如權(quán)重提升機制，peak rate估算方法等等，這許多機制使得bfq能夠適應(yīng)各自復(fù)雜的場景。

目前google chrome，F(xiàn)edora等大公司已經(jīng)在采用了bfq，預(yù)計一兩年后會有越來越多的公司采用bfq調(diào)度器。

原文作者：內(nèi)核工匠