Linux で最速を追求するハードディスクの最適化（1）

 スケジューリングと公平なキュー

インディーのレーシングカーに牽引されたトレーラーを想像してみよう。これはパフォーマンス的に1台のサーバーに複数のハードディスクを接続するのと同じような効果がある。ハードディスクは、接続速度を高めるために半導体の電子部品で構成されたコンピュータシステムに接続されるにもかかわらず、細心の注意を要する速度の遅い機械コンポーネントだからだ。

ディスクからデータを出し入れするには、ドライブヘッドが正しい位置に素早く移動し、ディスクの対象部分が回ってくるのを待つ必要がある。これには数百分の1秒という、RAM などに格納されたデータにアクセスする時間の何倍もの時間がかかってしまう。その結果、ディスクI/O サブシステムがデータにとって巨大なボトルネックになる可能性があり、このボトルネックの影響を最小限に抑えれば、サーバー全体のパフォーマンスを大幅に改善することができる。

なぜこのようになるのかを理解するために、ディスクからデータが出入りする様子を見てみよう。

簡単に説明すると、I/O サブシステムはデータをディスクから読み書きするための一連のリクエストを受け付け、それをキューの中に入れておく。たいていの場合、システムはスピードを上げるために、キューのなかの近い位置にあり、ディスクの同じ領域にある読み書きのリクエストをまとめてしまう。

一般に、リードリクエストのほうがライトリクエストよりも優先順位が高くなる。プロセスは書き込み処理の結果は待つ必要はないが、自分のリクエストしたデータが読み出されないと処理を先に進めことができないためだ。

また、サブシステムはデータがディスクからシーケンシャルに読まれていることをたいていの場合は検知し、リードリクエストのあったものの次のディスクブロックを「リードアヘッド」と呼ばれるテクニックを使って読み込んでキャッシュする。

これは、シーケンシャルリード時のシーク時間は短縮できるものの、ディスクの任意の部分からのリードを加速することは一切なく、サブシステムがランダム（つまり、シーケンシャルでない）リードを検知すると無効になる。

このシンプルなマージ作業が行われれば、I/O サブシステムがキューのなかのリクエストを先頭に到着する順番で処理できるが、たいていの場合そうなることはない。その代わりとして、スケジューラアルゴリズムを使ってリクエストの処理順を決めることで作業の高速化を試みる。

スケジューラは、ディスクヘッドに必要な移動距離を最小限に抑えるため、最も基本的なレベルでリクエストの順番を並べ替える。機械部分の処理に比較的時間を要するためだ。したがって、ディスクのあるエリアの読み込みをひとつのグループにまとめると、エリアを次々に移動してまとめていく。

スケジューラアルゴリズムの役割は、それをエレベータにたとえるとわかりやすい。

エレベータが忙しいビジネスエリアの1階に到着すると、多くの人が乗ってきて行き先階のボタンをバラバラに押す。いくらボタンが押された順番だからといって、最初に5階に行ってから40階に行き、そのあと2階に行ってから39階に行くなどというのは絶対理解できない。それよりも、2階、5階、39階、そして40階と昇順で各階に停止する方がはるかに効率的だ。上下に行ったり来たりするのではなく、一方向に移動することで、エレベータは最短時間で全員を目的階に降ろせるのだ。

しかし、このようなタイプのスケジューリングが I/O サブシステム（あるいはエレベータ）にとって必ずしも常に最適でないことも分かる。実際には弱点も多い。

エレベータのたとえ話に戻ると、最上階で仕事をしている人々は、1階から自分のオフィスに行くたびに数十階、将来的には数百階にもおよぶ途中階に停止して相当な時間を無駄にする。

このような理由から、低層階には一切止まらず上層階に直行するエレベータが多くの高層ビルには設置されている。上層階に勤務する会社員にとってはメリットだが、自分たちの階に停止するエレベータが減ってしまう低層階の会社員が犠牲になってしまう。

次へ 最良のスケジューラアルゴリズム  »

目次 1 スケジューリングと公平なキュー 2 最良のスケジューラアルゴリズム

Twitter	iPhoneアプリ / iPadアプリ		Androidアプリ
Facebook	RSS	ニュースメール