cfqスケジューラ
Linuxカーネルは、ブロックI/Oの処理効率を向上させるさせるための仕組みとして、I/Oスケジューラと呼ばれる機能を提供しています。I/OスケジューラはI/O要求の順序を入れ替えることにより、スループットを向上させたり、特定のI/O要求を優先して実行させたりします。実際のブロックデバイスのセクタに対するアクセス（つまり読み書き）を、要求された順序ではなく、I/Oを最も効率よく行うためにその順序を並び替えるというアイデアは、初期のUNIXの実装から採用されていました。それは、セクタ番号順序に並び替えてI/Oを実行するという単純なものです。ディスク面上を移動するヘッドの動きがエレベータに似ているため、このアルゴリズムはエレベータアルゴリズムなどと呼ばれていました。
現在のLinuxカーネルでは、そのころのアルゴリズムより洗練されたスケジューリング方式を採用しており、目的に応じて4種類のアルゴリズムの中から選択することが可能です（Linux2.6.23時点）。これらをI/Oスケジューラと呼びます。今回はそのI/Oスケジューラのうち、Linux2.6.23カーネルでデフォルトで選択されるcfqスケジューラを選び、そのベストエフォートクラスと呼ばれるアルゴリズムの動作概要について解説します。
I/Oスケジューラの位置づけ
I/Oスケジューラは、ブロックI/O共通レイヤとブロックデバイスドライバの間に位置します。ファイルシステムから出されたブロックI/O要求は、ブロックI/O共通レイヤに渡され、その後I/Oスケジューラに渡されます。I/Oスケジューラは、複数のブロックI/O要求を最も適切な順序に並び替えた後、下位のブロックデバイスドライバ（SCSIドライバやIDEドライバなど）に渡します。”適切な順序に並び替え”と述べましたが、適切な順序を決めるポリシーは、4種類あるI/Oスケジューラ毎に異なっています。
ちなみにLinuxカーネルはデバイスマッパ（※1）と呼ばれる機能を持っていますが、この機能は、I/Oスケジューラより前段で呼び出されるようになっています。ブロックI/O共通レイヤにフックがあり、そこからデバイスマッパのモジュールが呼び出されます。デバイスマッパでは、I/O対象デバイスやセクタ番号を変換したり、あるいはI/O要求を複製したりすることができます。I/Oスケジューラに渡されるI/O要求はそれらの変換が行われた後のもの、つまり必ず実デバイスに対するI/O要求そのものとなっています。
I/O要求形式：BIOとrequest
ファイルシステムからは、ブロックI/O要求はBIOと呼ばれるデータ構造を用いて行われます。一方、ブロックI/O共有レイヤからブロックデバイスドライバの間では、requestと呼ばれるデータ構造を用いてブロックI/O要求を管理します。
requestと呼ばれる別のデータ構造を利用する目的のひとつは、複数のBIOを束ねることにあります。ブロックI/Oデバイス（ディスクなど）の特徴として、I/O回数を減らせば減らすほどスループットを向上させることができます。I/Oスケジューラには数多くのI/O要求が蓄えられるため、これらI/O要求を互いに結合し、１つにまとめられる可能性が高くなります。
cfqスケジューラ：I/O優先度毎のリスト
cfqスケジューラは、I/O優先度をサポートしており（※2）、そのI/O優先度に応じた、requestを登録するためのリストを用意しています。非同期のI/O要求については、システム全体のプロセスが同じリストを共有し、同期的なI/O要求については、プロセス単位でリストを用意します。
高いI/O優先度用のリストに登録されたrequestほど、優先的にI/Oが実行されます。
各I/O優先度のリストにはそれぞれ持ち時間が付与されており、一度その優先度のリストが選択された場合、その持ち時間の範囲でrequestをiorequestキューに繋ぎかえる権利を与えられます。（デバイスドライバは、このiorequestキューからrequestを取り出して、実際のI/Oを行います。）I/O優先度に応じた持ち時間を与えることにより、高いI/O優先度のリストが優先的にI/O対象とされることになります。
cfqスケジューラ：セクタ番号をキーとするツリーと、時系列順リスト
cfqスケジューラのrequestを登録用のリストは二つあります。各requestは、両方のリストに同時に登録されます。一つはセクタ番号をキーとするツリーであり、requestのI/O対象となるセクタ番号順にrequestを管理します。このリストはスループットを確保するためのものであり、この順序でI/Oを実行するとディスクヘッドのシーク時間を最小限にすることができます。
もう一つのリストは時系列リストであり、I/O要求が発生した順にrequestを登録します。セクタ番号をキーとするツリーのみだと、運が悪いと長時間I/Oを実行されないことになるrequestが発生する可能性があるため、その救済のために用意されたリストです。一定時間以上滞留しているrequestを検出し、優先的に選択し実行するために用いられます。
cfqスケジューラ動作概要
I/O要求の発生
- ファイルシステムから渡ってきたI/O要求（BIO）が、既にcfqスケジューラのリスト上にあるrequestと結合できないか試みます。隣り合ったセクタに対するI/O要求で、I/Oの種類（READまたはWRITE）が同じであれば、ひとつのrequestにまとめることができます。
- ブロックI/O要求（BIO）を、requestと呼ばれる形式のI/O要求に変換し、I/O優先度に応じたcfqスケジューラのリストに登録します。この時、セクタ番号をキーとするツリーと、時系列順リストの両方に登録します。
I/Oを要求すべきrequestの選択
- どのI/O優先度のリストから選ぶか判断します。前回選んだI/O優先度のリストに、まだ持ち時間が残っていれば、そのリストを選択します。
- 前回選んだI/O優先度のリストに、まだ持ち時間が残っていれば、そのリストを選択します。
- 前回選んだI/O優先度のリストに、持ち時間が残っていなければ、次の優先度のリストを選びます。ラウンドロビン方式で順番に選択します。
- リストからrequestをひとつ外します。
- 時系列リストの先頭のrequestが、このリストに登録してから一定時間以上を経過している場合、そのrequestを選択します。
- セクタ番号をキーとするツリーから、前回選択したrequestのセクタに最も近いセクタへのI/O要求を持つrequestを選択します。原則セクタ番号が増える方向にあるrequestを選択しますが、すぐ近くであれば、セクタ番号が小さくなる方向にあるセクタを選ぶこともあります。
- 選択したrequestを、iorequestキューの最後に繋ぎます。
I/Oの実行
デバイスドライバ（SCSIドライバなど）は、iorequestキューの先頭からrequestを選び、実際のI/O処理を実行していきます。
sysfsによる制御
I/Oスケジューラの選択
/sys/block/<デバイス名>/queue/schedulerにI/Oスケジューラの名称を書き込むことにより、デバイスごとに利用するそのI/Oスケジューラを設定できます。Linux2.6.23では、noop、anticipatory、deadline、cfqが選択可能です。
#echo cfq > /sys/block/<デバイス名>/queue/scheduler
/sys/block/<デバイス名>/queue/schedulerを読み出すと、現在選択されているI/Oスケジューラが下記のように表示されます。
#cat /sys/block/<デバイス名>/queue/scheduler noop anticipatory deadline [cfq]
cfqスケジューラのパラメータ変更
cfqスケジューラを選択してる時、/sys/block/<デバイス名>/queue/ioschedにcfqスケジューラ制御用のファイルが現れます。そのうち、重要なファイルについて説明します。
- slice_sync、slice_async
各優先度毎のリストの持ち時間計算のベースとなる値です。この値にI/O優先度の高低を加味して、実際に与える持ち時間を決定します。tick値（タイマ割り込み回数）で指定します。同期的なI/Oと非同期的なI/Oに対して、各々値を設定できます。 - fifo_expire_sync、fifo_expire_async
I/O要求（request）の最大滞留可能時間を設定します（tick値で指定）。この時間を過ぎたI/O要求は優先的に処理されます。同期的なI/Oと非同期的なI/Oに対して、各々値を設定できます。
- ※1 デバイスマッパについては、別の機会に説明できればと考えています。LVMやソフトウェアRAID、マルチパスドライバなどは、デバイスマッパとして実現されています。
- ※2 I/O優先度の設定方法に関しては、ionice(1)コマンドのマニュアルを参照するといいでしょう。