Open Source Web Development Tutorials - Dev Shed

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

デッドライン（実行期限付き）I/Oスケジューラ

　2.4 I/Oスケジューラおよび従来のエレベーターアルゴリズム全般の問題を解消すべく導入されたのが、デッドラインI/Oスケジューラです。Linusエレベーターは、保留中のI/O要求を並べ替えたリストを保持しています。そして、次に実行するのは待ち行列の先頭にある I/O要求です。デッドライン I/Oスケジューラも待ち行列を保持しますが、2つの待ち行列を追加することで状況を改善します。2つの待ち行列とは、読み出しFIFO待ち行列と書き込みFIFO待ち行列です。これらの待ち行列に入っている要求は、提出された時間（事実上、最初に待ち行列に入った要求が最初に待ち行列を出ます）の順序に従って並べ替えられています。名前から推測できるように、読み出しFIFO待ち行列には読み出し要求だけが入っており、書き込みFIFO待ち行列には書き込み要求だけが入っています。これらFIFO待ち行列に入っている要求には、おのおの、実行期限値が指定されています。読み出しFIFO待ち行列の実行期限値は500ミリ秒、書き込みFIFO待ち行列の実行期限値は5秒です。

　新規のI/O要求が提出されると、標準の待ち行列には挿入整列され、（読み出しあるいは書き込み）FIFO待ち行列には最後尾に配置されます。ハードドライブには、通常、標準整列した待ち行列の先頭からI/O要求が送られます。標準待ち行列は（Linusエレベーターの場合と同じく）ブロック番号順に整列しているため、シークが最小限に抑制され、全体的なスループットが最大となります。

　ところが、FIFO待ち行列の先頭にある要求が関連付いた実行期限値より古くなると、I/Oスケジューラは標準待ち行列からI/O要求を送り出すことを止め、FIFO待ち行列に入っている要求－先頭の要求、および追加的に2～3件の要求－を実行します。I/Oスケジューラが照合して処理するのは、提出時からもっとも長い時間が経過している待ち行列先頭の要求だけです。

　このようにして、デッドラインI/Oスケジューラは、I/O要求に対する「ソフト（非厳密な）デッドライン」を実行します。I/O要求が確実に実行期限時前に実行されるとは限りませんが、一般的に、実行期限時付近で実行されます。したがって、デッドラインI/Oスケジューラは、要求を許容し難い長時間にわたってスターブすることなく、全体的に良好なスループットを継続的に実現します。読み出し要求には短時間の実行期限が与えられるため、「ライト・スタービング・リード」の発生は最小限に抑制されます。

予測I/Oスケジューラ

　デッドラインI/Oスケジューラは良好に動作しますが、完ぺきではありません。読み出し要求を実行するときの従属性を思い出してください。デッドラインI/Oスケジューラの場合、一連の読み出しの最初の読み出し要求は、実行期限時あるいは実行期限時前に、迅速に実行されます。その後、I/Oスケジューラは標準待ち行列にあるI/O要求の実行に戻ります。ここまでは、問題ありません。しかし、アプリケーションから次の読み出し要求が舞い降りてきたらどうでしょうか？最終的にはその要求の実行期限も近づいて、I/Oスケジューラは要求をディスクに提出します。ディスクはシークを実行して遅滞なく要求を処理し、その後、シークを再実行して標準待ち行列の要求に戻り、処理を続けます。このようなシーク動作の往復は多くのアプリケーションに共通した動作ですから、しばらくの間は継続可能です。レイテンシは最小限に維持されますが、次々と読み出し要求が入り続けてディスクがシークの往復を強いられと、全体的なスループットは下降します。ディスクがちょっと休憩して標準待ち行列へ戻るのを止め、次の読み出しを待つ方が性能は向上するはずです。しかし、残念ながら、従属する後続の読み出し要求がスケジュールに入り、提出されたときには、I/Oスケジューラは休む間もなく次の行動に移っているのです。

　ここでも、問題の源は読み出しの従属性です。すなわち、前の読み出し要求が戻るまで、次の新規読み出し要求を出すことはできません。ところが、読み出しのデータを受け取って、実行予定を立て、読み出し要求を提出したときには、I/Oスケジューラはもう次に作業に進んで、ほかの要求の実行を開始しているわけです。ディスクは読み出しのためにシーク動作を行い、要求を実行し、再度シーク動作で元の作業に戻るのですから、1つの読み出しにつき2回のシーク動作が消耗されることになります。何らかの方法で「ディスクの同じ部分にもうすぐ次の読み出しが提出される」とI/Oスケジューラが知る－予測する－ことさえできれば、あちこちでシーク動作を行う代わりに、次の読み出しまで予測待機することができます。骨の折れるシーク動作を省略できるのであれば、絶対、数ミリ秒待機する価値はあります。

　これこそ、予測I/Oスケジューラの動作です。予測I/Oスケジューラは、もともとデッドライン式であったI/Oスケジューラに予測メカニズムを付加したものです。読み出し要求が提出されると、通常どおり、予測I/Oスケジューラは実行期限内に要求を実行します。しかし、デッドラインI/Oスケジューラと異なるのは、6ミリ秒間、そのまま何もせずに待機する点です。この6ミリ秒の間に、ファイルシステムの同一部分からの読み出しが要求される可能性は大いにあります。次の読み出し要求が出された場合は、直ちに実行し、再度待機します。6ミリ秒の間に読み出し要求が出されなかった場合、予測I/Oスケジューラは予測が外れたと判断して、前の作業（つまり、標準待ち行列の実行）の続きに戻ります。予測どおりに発生する要求件数が中程度であっても、1回の読み出しに付き2回のコスト高なシーク動作という多大な時間の節約につながります。大多数の読み出しは従属性ですから、ほぼあらゆる場合に、予測はメリットを実現します。

前のページ 1 2 3 4 次のページ