Open Source Web Development Tutorials - Dev Shed

Linux I/Oスケジューラ
（2009/03/25公開）

I/Oスケジューラの動作

　I/Oスケジューラは、基本的に「併合（merging）」と「並べ替え（sorting）」の2つの動作を実行します。併合は、隣接する複数のI/O要求を取り上げ、結合して、1つの要求にします。例えば、次の2つの要求を想定してみましょう。1つはディスクブロック5から読み出しを行う要求、もう1つはディスクブロック6～7から読み出しを行う要求です。これら2つの要求は、ディスクブロック5～7から読み出しを行う1つの要求として、併合できます。I/Oの総量は変わりませんが、I/O動作数は半分に削減されます。

　もっと重要な並べ替えは、保留のI/O要求をブロックの昇順に配列する動作です。例えば、52、109、7の各ブロックにI/O要求が出されている場合、I/Oスケジューラは7、52、109の順番に要求を並べ替えます。その後、ブロック81への要求が出されたら、ブロック52 とブロック109の間に挿入します。そして、待ち行列の順序－7、52、81、109の順－に従って、要求をディスクに送ります。

　このような方法で、ディスクヘッドの移動が最小限に抑制されます。ディスクヘッドは（ディスク上を右往左往して）無計画に移動する代わりに、滑らかな線状に移動することができます。シークはディスク I/Oでもっとも高く付く部分ですから、これらの措置は性能の改善を約束します。

読み出しの促進

　読み出し要求には、常に、最新のデータを戻す必要があります。したがって、要求されたデータがページキャッシュにない場合は、ディスクから読み出せるまで、読み出しプロセスをブロックしなくてはなりません。これには長時間が経過する可能性があり、読み出しレイテンシとして性能に影響が現れます。

　通常のアプリケーションでは、短時間に複数の読み出しI/O要求を起動する状況が予想されます。この場合、要求は個別に同期化されているため、後の要求は前の要求の完了に従属します。例えば、ディレクトリにある全ファイルを読み出す場合には、どうなるでしょうか？まず1つ目のファイルを開き、そのチャンクを読み出し、データを待ち、次のチャンクを読み・・・と、ファイル全体を読み出すまで続きます。次に、アプリケーションが再起動して、2つ目のファイルへと進みます。要求はシリアル化（直列化）となり、現行の要求が完了するまで後続の要求を出すことはできません。

　書き込み要求はまったく対照的です。（非同期化が標準設定の）書き込み要求では、ある時点まで、ディスクI/Oをまったく起動する必要がありません。したがって、ユーザースペースアプリケーションの観点から、書き込み要求はディスクの性能に阻害されないストリーム動作となり、読み出しの問題を悪化させる結果を招きます。書き込みのストリームがカーネルとディスクの能力を占有してしまうのです。writes-starving-reads（ライト・スタービング・リード：書き込みによって生じる読み出しのスターブ）と呼ばれる現象の発生です。

　I/Oスケジューラが、常に、新規の要求を挿入の順序に従って並べ替えるなら、はるか後方のブロックへの要求は無制限にスターブされる可能性があります。前述の例を考えてみましょう。例えば、50代のブロックに対する新規の要求が出され続けたら、ブロック109に対する要求は永久に実行されません。読み出しレイテンシには重大な意味がありますから、このような動作はシステム性能を大幅に損なうものです。そのため、I/Oスケジューラはスターブ防止メカニズムを採用します。

　（2.4 LinuxカーネルのI/Oスケジューラ「Linus エレベーター」が採用している*）シンプルな方法は、待ち行列に十分な数の古い要求が入っている場合、挿入－並べ替えを停止する方法です。その結果、要求ごとのフェアネスと引き換えに全体的な性能が提供され、読み出しの場合にはレンテンシが改善されます。しかし、問題は、この発見的問題解決法（ヒューリスティック）があまりに単純なことです。不備が認識されたため、2.6 LinuxカーネルからはLinusエレベーターが廃棄されて複数の新規I/Oスケジューラが実装されていますが、内容は明らかにされていません。