I/OスケジューラとブロックI/O層

ブロックI/O層という中間管理職

アプリの read/write はシステムコールを経てカーネルに入り、ページキャッシュを通り抜けると最終的にブロックデバイスへの要求になります。この変換と整流を担うのがブロックI/O層です。ファイルの論理オフセットはファイルシステムが物理ブロック番号（LBA）へ翻訳し、その結果が bio という構造体に詰められます。bio は「どのセクタへ、どのメモリページの内容を、読むか書くか」を表すI/Oの最小単位です。

ブロックI/O層の核心は、この bio をそのままデバイスへ流さない点にあります。間にI/Oスケジューラ（エレベータ）を挟み、要求を**マージ（併合）し並べ替え（リオーダ）**してからデバイスへ渡す。なぜそんな手間をかけるのか——その答えは回転ディスクの物理にあります。

なぜ並べ替えが効くのか：シークの物理

HDDは磁気ヘッドを目的トラックへ動かし（シーク）、目的セクタが回ってくるのを待ちます（回転待ち）。シークは機械動作なのでミリ秒単位で、1回のI/Oの大半を占める固定費です。要求がLBA順にバラバラだと、ヘッドは内周と外周を往復し続けて時間を浪費します。

ここで並べ替えが効きます。届いた要求をLBA順にソートして近い順に処理すれば、ヘッドの移動距離を劇的に減らせる。さらに隣接・連続するセクタへの要求は1つの大きな要求にマージでき、コマンド発行のオーバーヘッドも下がります。これがI/Oスケジューラの存在理由です。

エレベータアルゴリズム

並べ替えの古典がエレベータアルゴリズムです。ビルのエレベータが上昇中は上の階だけ拾い、最上階で折り返すのと同じく、ヘッドを一方向に掃引しながら通り道の要求を順に処理します。

• SCAN：端まで進んでから逆方向へ折り返す。両端が有利になりがち。
• C-SCAN：端まで行ったら並べ替えず一気に逆端へ戻り、再び同方向へ。位置による不公平を均す。
• C-LOOK：最遠の要求まで行ったら（端ではなく）戻る。実装上の定番。

ヘッド位置 →          現在地
LBA軸:  |--A----C--[H]--E------G--|   要求 A,C,E,G
C-LOOK掃引:        [H]→E→G （右端の要求まで）
              戻って →A→C   （ラップして再掃引）

純粋なエレベータの弱点は**飢餓（スターベーション）**です。遠いLBAへの1件は、近場に要求が来続ける限り永久に後回しになりかねません。この公平性の欠如を埋めるために、後続のスケジューラが生まれました。

旧世代（シングルキュー）の三役

blk-mq以前のLinuxは、デバイスごとに1本の要求キューを1つのロックで守る設計（レガシーブロック層）でした。そこに載った代表的スケジューラが次の3つです。

Deadline は要求をLBAソート済みキューと期限（FIFO）キューの両方に登録します。通常はソート順に処理してシークを減らしますが、ある要求が期限（既定で読み500ms・書き5s）を超えたら、その要求を最優先で割り込ませる。これでエレベータの飢餓を構造的に防ぎます。読みを書きより短い期限にするのは、読みが同期的でアプリを待たせるからです。

CFQ（Completely Fair Queuing） はCPUスケジューラのCFSと同じ「公平」の発想をI/Oへ持ち込み、プロセスごとにキューを与えタイムスライスを回します。アイドリング（同じプロセスの次要求を少し待つ）でシーク局所性も稼ぎますが、その待ちと多数キューの管理が高IOPSデバイスでは純粋な足かせになりました。

SSD・NVMeが壊した前提とblk-mq

SSDにはヘッドが無く、シークも回転待ちもありません。並べ替えで得られる利得は激減し、代わりに内部の多数チャネルを同時に叩く並列性が性能の源になります。NVMeに至っては最大65535本のハードウェアキュー、各深さ65536を規格で許します。

この世界で旧来の「1キュー＋1ロック」は致命的でした。全CPUコアが1本のロックを奪い合い、せっかくの並列デバイスへ要求を直列にしか注げない。ロック競合がデバイス性能の前にCPUを飽和させます。

そこで導入されたのが blk-mq（マルチキューブロック層） です。キューを2段に分けます。

• ソフトウェアキュー：CPU（コア）ごとに1本。要求はまず自コアのキューに入るので、コア間のロック競合が原理的に消える。
• ハードウェアディスパッチキュー：デバイスが持つ実キューに対応。ソフトウェアキューの要求をここへ流し込みデバイスへ発行する。

 CPU0  CPU1  CPU2  CPU3      ← ソフトウェアキュー（コア毎・競合なし）
   \    |     |    /
    [ hctx 0 ]  [ hctx 1 ]   ← ハードウェアディスパッチキュー
         |           |
      NVMe HW-Q0   NVMe HW-Q1 ← デバイスの実キュー

コアとハードウェアキューを対応づければ、割り込みの完了処理も発行したコアで受けられ、キャッシュ局所性が効きます（割り込みとI/O参照）。Linuxは5.0でレガシー層を撤廃し、blk-mqへ一本化しました。

blk-mq時代のスケジューラ

blk-mqでは「並べ替えはもう不要」かというと、そうでもありません。遅延の保証やプロセス間の公平性はSSDでも価値があるため、軽量な新スケジューラが用意されています。

Kyber は発想が独特です。読み・書きそれぞれの完了遅延（レイテンシ）を実測し、目標値を超えそうならデバイスへ同時に出す要求数（トークン）を絞る。並べ替えで最適化するのではなく、詰め込みすぎを抑えて遅延の裾を切るフィードバック制御で、NVMeのような高速デバイスに合います。

BFQ（Budget Fair Queueing） はCFQの正統後継で、時間スライスの代わりにセクタ予算でプロセスへI/Oを配分します。対話プロセスを検知して優先するなど応答性に強い反面、計算コストが高く、最高IOPSを狙うNVMeでは none に劣ることがあります。用途で選ぶのが鉄則です。

まとめ