もわの台所

■ I/O scheduler とは何か

ハードディスクをはじめとする block device に対して、 各プロセスが別個に read と write のI/O命令発行した場合、 アクセスされるデータのディスク上の位置は、大抵の場合連続していない。 それらの要求を要求された順番に処理した場合、 ディスクの性質から予想出来るとおり、大幅な性能低下が予想される。

この性能低下を回避するため、 I/OをFIFO的に処理するのではなく、 「今アクセスしている位置に近いデータへアクセスする要求をまとめる」 といった処理を行い、 システム全体のスループットを向上させるのが I/O scheduler の当初の役割である。

I/O schedulerにおける極めて基本的なアルゴリズムは「エレベータ」などと呼ばれる。 すなわち、ディスクのヘッダをエレベータを動かすアルゴリズムになぞらえ、 同じ「階」、次の「階」近くのデータを優先的に処理するのである。

Linux Kernel 2.4 系ではその名の通り The Linus Elevator という I/O scheduler が標準であったそうだ。 このとき、 各プロセスからのI/O要求を一括して保持しておく構造を、 request queue と呼ぶことにする (おそらく一般的な用語である)。 request queue 内に入る際、 各要求はその block device 上での位置を元にソートされる。 場合によっては、複数の要求が一つの要求にマージされることもある。 各アクセス要求は発行された順には処理されなくなるため、 特定のアクセス要求の処理が少し遅れたりすることはあるが、 シーク(ディスクヘッダの移動)距離自体は小さくなり、 全体のスループットは上がるはずである。

ここでの大きな仮定は、シークにオーバーヘッドがある、というものである。 フラッシュメモリ等も block device であるが、 シークのオーバーヘッドはHDDのそれとは全く異なる性質を持つ。

シンプルな「エレベータ」アルゴリズムは、 ユーザの感じる応答性能ではなく、全体のスループットを最優先とするものである。 そのため、現在のLinuxの用途には必ずしも適合しない。 現在の主要な要求は 「ユーザの実感する応答速度をなるべく下げず、全体のスループットを向上させる」 である。

Linux Kernel 2.6では、現在4種類の I/O scheduler が用意されている。 「はじめに」で述べたとおり、この I/O scheduler のデフォルト実装が、 2.6.18で変更になった。

■ Linux に実装された4種類の I/O scheduler

■ Deadline I/O Scheduler

block deviceへの write 時、request queue にその要求が送られた後は、 プログラムが書き込み処理の完了自体を待つ必要はない。 書き込んだ結果として、プログラム自体が新たに得るデータはないからである (当然、エラーが起きた場合はこの限りではない)。 よって、I/O scheduler から要求を受けとったという意味での戻り値を受けとれば、 後は別の処理を再開して構わない。 いわゆるasynchronous I/O である。

一方、read要求の場合、プログラムはデータが到着するまで待たなくてはならない。 read要求の場合、読み込んだデータが次の処理に必要である。 synchronous でなければならない。

request queueにある要求を read と write の区別なく処理した場合、 read処理を多く行なったプログラムの性能に悪い影響を与える。 この問題を解決するための一つ目の解が Deadline I/O scheduler である。

Deadline I/O scheduler は、 従来のrequest queueの他、read と write にそれぞれFIFOキューを持つ。 平素は request queue を「エレベータ」的に処理するが、 read と write の各要求にはデッドラインが設けられている。 read/writeのFIFO queueの先頭にある要求がそのデッドラインを「超えると」 (デッドラインが近くなると、ではない)、 request queue よりもその FIFO queue 先頭の要求が優先される。 デッドラインという言葉が 「ソフトリアルタイム」「ハードリアルタイム」 等で論じられる時とは異なる意味で使われていることに注意を要する。

Deadline I/O schedulerでは、 readとwriteのデッドラインはそれぞれデフォルトで500ミリ秒、5秒となる。 このデッドラインの違いにより、read優先を実現している。

■ Anticipatory I/O Scheduler

Deadline I/O scheduler は、 FIFO queue の処理が完了すると、 本来の request queue の処理に即座に戻ろうとする。 ここでディスクヘッダの移動が無駄に多く発生する。

Anticipatory I/O schedulerは、 FIFOの処理終了後、まだその周辺のデータに対するアクセスがあるだろうと期待する。 即座に元の位置に処理を戻さず、その位置で何もせずにしばらく待機するのである。 このとき、その近辺へのアクセス要求が新たにあれば、それを優先的に処理する。 これによってディスクヘッダの移動を抑え、高速化を図る。 英単語 anticipate には「予期する、期待する」といった意味がある。

待機時間中に近辺へのアクセスがまったくない場合、無駄な空白期間が発生する。 しかし一般には、むしろその近辺へのアクセスが増える傾向にあるから、 この方法により高速化と応答性能向上が期待できる。

以前はこれがデフォルトの I/O scheduler だった。

■ CFQ(Complete Fair Queuing) I/O Scheduler

今まで紹介したI/O schedulerはプロセス間の平等性は確保されない。 あるプロセスのI/Oが大量に発行されている状態で、別のプロセスがread要求を発行しても、 たくさんのアクセス要求の内の一つとして処理されるため、処理が遅れることになる。 待たされるプロセスが音楽再生を行っていた場合、音が飛ぶ。

Deadline, Anticipatory と異なり、 CFQ I/O scheduler では、request queueの前にプロセス毎のqueueがあり、 特定のプロセスにI/Oが占有されないように調整される。 プロセス毎のI/Oが完全に平等にqueueに入るという意味で Complete Fair Queuing なのである。

これが Linux Kernel 2.6.18 のデフォルトとなった。

■ Noop I/O Scheduler

今までの I/O scheduler はシークにオーバーヘッドがあることを仮定していたが、 現在はフラッシュメモリ等、この仮定自体があてはまらない block device もある。 noop I/O scheduler はそのような device にとって有用かもしれない。

■ 何故デフォルトの I/O scheduler が CFQ になったか

Anticipatory I/O scheduler はサーバ用途に向くとされ、 CFQ I/O schedulerはマルチメディアアプリケーションを実行するといった場合に向いているとされる。 デフォルト設定で利用するユーザはデスクトップユースが主、という判断だろう。

システム全体のスループットとユーザに対する応答性能は、 このレイヤにおいてはある程度はトレードオフの関係にあり、 用途によってはシンプルなエレベータの実装が良い場合もある。 CFQがどのような面においても最良のI/O schedulerだから、 デフォルトに選ばれたわけではない。

■ I/O scheduler をどう変更するか

Linux Kernel 2.6.18 では、make menuconfig等で以下から見ることが出来る。

Block layer -> IO Schedulers

コンパイル時に含めてあれば、ブート時に変更することも可能である。

■ I/O scheduler の ソースはどこにあるか

現在はソースコードのルート下、blockフォルダにある。以前と場所が変わったようだ。

追記

ブート時の変更方法は現在調査中。 ソースに該当部分がない。……出来ない可能性がある？

ちなみにブート後に動的に変える方法は公式に存在し、 Documentation/block/switching-sched.txt に記載されている。Linux Kernel 2.6.10 より使用可能とのこと。

フロッピーディスクドライブに対しての変更例を以下に掲載する。

root# cat /sys/block/fd0/queue/scheduler
noop [anticipatory] deadline cfq 
root# echo noop > /sys/block/fd0/queue/scheduler
root# cat /sys/block/fd0/queue/scheduler
[noop] anticipatory deadline cfq 

通常はこれで十分だと思うが。