私事ですが，この前買ったVAIO Pro 13 | mk2のカーネルをZENパッチセットを適用したlinux-zenにしました．
ArchLinuxではなぜか公式レポジトリ入りしてるのでバイナリが降ってきます．
それ以前はlinux-drm-intel-nightlyから自分でビルドした4.4rcのカーネルを一瞬使ってましたが，このマシンで発生しているチラつきや不安定な挙動の解決に有効ではなかったようなのでやめました．
閑話休題
pfパッチセットやZENパッチセットではI/OスケジューラにBFQが採用されています．
ckパッチセットではデフォルトではないもののBFQが使えるようです．
さて，そこでBFQスケジューラについて調べ，まとめました．
Manjaro，OpenMandriva，ArchLinux ARMのデフォルトI/Oスケジューラになっている模様です．(ManjaroはCPUスケジューラにBFS，I/OスケジューラにBFQをつかってるみたいですね．)
ホントかよ？と思いますが，ここに挙げられているテスト結果を引用すると[1]，
たとえばSeagateのHDDにおいてスループットのテスト(上図，高いほど良い)やxtermの起動時間テスト(下図，小さいほど良い)でとても良い結果を出していますが，
この図のようにOpenOffice Writerの起動時間テストでは他のスケジューラに大きく差を付けて悪い結果を出してしまっていたり，
また，PLEXTORのSSDにおいて，
スループットが他のスケジュールとほぼ差がなかったり(やや負けている)しています．
ただ，PLEXTORのSSDでのxtermの起動時間とOpenOffice Writerの起動時間は，
けっこう良いみたいですね．
ほかにもサイトにはToshibaの1.8" HDDやTranscendのmicroSDHC，SamSungのeMMCなどのテスト結果が掲載されています．
OpenOffice WriterがHDDで起動がかなり遅い問題については，複合的要因によるらしく，その要因として考えられる事項がサイトにて挙げられています．
ストレージデバイスは2つのI/Oリクエストを受ける． 連続的なセクタに対しての読み込みと書き込みである． リクエストはシーケンシャルかランダムで，これは最初のセクタへのリクエストは，他のリクエストの最後のセクタへのリクエストの直後に位置するかしないかという事になる．
リクエストはNコのアプリケーションにより発行される． このアプリケーションは実システム上でストレージアクセスの終了を競合する，たとえばプロセスやスレッドを指す． ここで，アプリケーションの保留されているリクエストを，アプリケーションのバックログと定義する． バックログが空でないアプリケーションは，バックログしているアプリケーションと言う． バックログしていない状態をアイドルと言う．
まとめると，アプリケーションのシーケンシャル/ランダムのリクエストは以前のリクエストに関連して発行される場合がほとんどである．また，リクエストが完了した場合のみに次のリクエストを発行する時は同期的なアプリケーションで，そうでない場合は非同期的である． ストレージデバイスがリクエストを受けているとき，そのリクエストを発行したアプリケーションはストレージデバイスよりサービスを受けていると言う．
add_request()によりリクエストがキューイングされる．
各アプリケーションはリクエストキュー(request queue)を持っており，このキューはバックログである．つまり，空である場合アイドル，空でない場合にバックログされていると言う．
一度にストレージデバイスにアクセス可能なのは一つのアプリケーションのみであり，このアクセスしているアプリケーションをサービス中のアプリケーションという．各アプリケーションはサービスにアサインされるための予算(Budget)を持っており，予算の尺度はセクタ数である． アプリケーションがサービスに入った場合，予算が尽きるかバックログが空になるまで排他的にサービスを受け，アイドルになる． そしてBFQは次のサービスを受けるアプリンを選び出す．つまり，予算が尽きるかバックログが空になるという2つのイベントが発生するまでプリエンプティブではない． BFQがバックログされているアプリケーションを持たない状態から最低1つ持つ状態に変更するのはapplication service loopが行なう．このループは次のような順の処理を行う．
このループの中で，このスケジューラが一番利益を出すために最も負担になる部分は，B-WF²Q+が予算のサイズにかかわらず(断片的な)スループットを保証するためにアプリケーションをアサインする所である．
これは直感的で，大きな予算が割り当てられたアプリケーションはその分長くデバイスを使えるため，B-WF²Q+のアプリケーションの選択が全体と各々のスループットのバランスを左右する．
^[2]: Paolo Valente and Arianna Avenzini ``Evolution of the BFQ Storage-I/O Scheduler'' Techinical Paper, http://algo.ing.unimo.it/people/paolo/disk_sched/mst-2015.pdf
^[3]: John C.R. Bennett and Hui Zhang ``WF²Q: Worst-case Fair Weighted Fair Queueing'' INFOCOM'96 24-28 Mar 1996, 1, 120-128, link
^[4]: Tobey J. Teorey and Tad B. Pinkerton ``A comparative analysis of disk scheduling policies'' Communication of the ACM Mar 1972, 15, 3, 177-184 link
ArchLinuxではなぜか公式レポジトリ入りしてるのでバイナリが降ってきます．
それ以前はlinux-drm-intel-nightlyから自分でビルドした4.4rcのカーネルを一瞬使ってましたが，このマシンで発生しているチラつきや不安定な挙動の解決に有効ではなかったようなのでやめました．
閑話休題
pfパッチセットやZENパッチセットではI/OスケジューラにBFQが採用されています．
ckパッチセットではデフォルトではないもののBFQが使えるようです．
さて，そこでBFQスケジューラについて調べ，まとめました．
BFQスケジューラとは
- BFQ = Budget Fair Queueing
- インタラクティブなアプリのための低遅延なsched
- マルチメディアのようなsoft real timeなアプリのための低遅延なsched
- 高スループット(CFQに比べHDDで30%高速)
- 強い公平性
ホントかよ？と思いますが，ここに挙げられているテスト結果を引用すると[1]，
たとえばSeagateのHDDにおいてスループットのテスト(上図，高いほど良い)やxtermの起動時間テスト(下図，小さいほど良い)でとても良い結果を出していますが，
BFQのアルゴリズム
テクニカルペーパーより[2]．モデルと用語の定義
ストレージデバイスとNコのアプリケーション集合，そしてその間にBFQスケジューラがあるという構成のストレージシステムを考える． ストレージデバイスは連続的なシーケンス，固定長セクタ，そして各シーケンス中の位置が識別されるものとする．ストレージデバイスは2つのI/Oリクエストを受ける． 連続的なセクタに対しての読み込みと書き込みである． リクエストはシーケンシャルかランダムで，これは最初のセクタへのリクエストは，他のリクエストの最後のセクタへのリクエストの直後に位置するかしないかという事になる．
リクエストはNコのアプリケーションにより発行される． このアプリケーションは実システム上でストレージアクセスの終了を競合する，たとえばプロセスやスレッドを指す． ここで，アプリケーションの保留されているリクエストを，アプリケーションのバックログと定義する． バックログが空でないアプリケーションは，バックログしているアプリケーションと言う． バックログしていない状態をアイドルと言う．
まとめると，アプリケーションのシーケンシャル/ランダムのリクエストは以前のリクエストに関連して発行される場合がほとんどである．また，リクエストが完了した場合のみに次のリクエストを発行する時は同期的なアプリケーションで，そうでない場合は非同期的である． ストレージデバイスがリクエストを受けているとき，そのリクエストを発行したアプリケーションはストレージデバイスよりサービスを受けていると言う．
アルゴリズム
 |
| 図1. BFQの論理スキーム |
一度にストレージデバイスにアクセス可能なのは一つのアプリケーションのみであり，このアクセスしているアプリケーションをサービス中のアプリケーションという．各アプリケーションはサービスにアサインされるための予算(Budget)を持っており，予算の尺度はセクタ数である． アプリケーションがサービスに入った場合，予算が尽きるかバックログが空になるまで排他的にサービスを受け，アイドルになる． そしてBFQは次のサービスを受けるアプリンを選び出す．つまり，予算が尽きるかバックログが空になるという2つのイベントが発生するまでプリエンプティブではない． BFQがバックログされているアプリケーションを持たない状態から最低1つ持つ状態に変更するのはapplication service loopが行なう．このループは次のような順の処理を行う．
- 次のサービスを受けるアプリケーションの選択
B-WF²Q+という公平なキューイングスケジューラが次のバックログされているアプリケーションを選択 - リクエストのディスパッチ
ループはOSによるdispatch()を待つ．これが発行された時，次が発生する．
a ) C-LOOKアルゴリズムによるローカルなスケジューラがアプリケーションのキューからリクエストを取り出す
b) ディスパッチされたリクエストのサイズだけ予算を減らす
c) 予算が尽きたかバックログが空になるまでステップ2を繰り返す．どちらかが発生したら次のステップへ - アプリケーションのサービスを停止し，予算を再計算する
おわりに
ほぼ公式ページをそのままうつしただけになってしまった上に，肝心のB-WF²Q+についてまで論文を読む時間と気力がなかった．B-WF²Q+はどうやらINFOCOM'96で発表された，パケット等のスケジューリングに使われるWF²Qがベースっぽい[3]．もっとちゃんと調べておこうと思う．C-LOOKアルゴリズムも調べておきたい[4]．参考文献
^[1]: Budget Fair Queueing (BFQ) Storage-I/O Scheduler - Test result http://algo.ing.unimo.it/people/paolo/disk_sched/results.php^[2]: Paolo Valente and Arianna Avenzini ``Evolution of the BFQ Storage-I/O Scheduler'' Techinical Paper, http://algo.ing.unimo.it/people/paolo/disk_sched/mst-2015.pdf
^[3]: John C.R. Bennett and Hui Zhang ``WF²Q: Worst-case Fair Weighted Fair Queueing'' INFOCOM'96 24-28 Mar 1996, 1, 120-128, link
^[4]: Tobey J. Teorey and Tad B. Pinkerton ``A comparative analysis of disk scheduling policies'' Communication of the ACM Mar 1972, 15, 3, 177-184 link