Open Source Web Development Tutorials - Dev Shed

適切なI/Oスケジューラの設定と最適化
（2009/03/31公開）

ユーザースペースでのI/Oスケジューリング

　多数にのぼるI/O要求を出して性能を極限まで酷使するI/O集約型アプリケーションでは、保留中のI/O要求を並べ替えたり併合することができます。Linux I/Oスケジューラと同じ働きです。*

　I/Oスケジューラがブロックの観点から要求を並べ替え、シーク動作を最小限に抑制し、ディスクヘッドの円滑な線的移動を実現してくれると分かっている時、どうして同じ作業を2度行う必要があるでしょうか？多数のI/O要求を並べ替えていない状態で提出するアプリケーションを考えてみましょう。これらの要求は、一般的に順不同でI/Oスケジューラの待ち行列に入ります。ここで、I/Oスケジューラが仕事を開始します。すなわち、要求を並べ替え、併合した後に、ディスクへと送り出すわけです。ところが、まだアプリケーションがI/Oを生成し、要求を提出している間に、要求がディスクをヒットし始めます。というのも、I/Oスケジューラが一度に並べ替えを実行できるのは小規模な要求セット（このアプリケーションから出されたほんの一握りの要求だけ）で、ほかのすべての要求は保留となるのです。つまり、アプリケーションから受け取る要求はバッチごとにきちんと並べ替えられますが、待ち行列がいっぱいになると、その後の要求は整列には加えられません。

　したがって、多数の要求を出すアプリケーションの場合－特に、対象となるデータがディスク全体に散在している場合－、要求を提出する前に並べ替えを行い、確実に望ましい順序でI/Oスケジューラに渡す方法が効果を上げます。

　一方、ユーザースペースアプリケーションはカーネルと同じ情報へアクセスすることはできません。I/Oスケジューラの最下レベルで、すでに、要求は物理ディスクのブロックの観点から特定されており、その並べ替えは取るに足りません。しかし、ユーザースペースでは、要求はファイルとオフセットの観点から特定されています。そこで、ユーザースペースアプリケーションは情報を捜査し、ファイルシステムのレイアウトを根拠に基づいて推測する必要に迫られます。

　特定のファイルに対するI/O要求リストを渡されて、シーク動作がもっともスムーズな順序付けを決定するにあたり、ユーザースペースアプリケーションにはいくつかの選択肢があります。すなわち、以下に基づいた並べ替えです。

・フルパス
・iノード番号
・ファイルの物理ディスクブロック

　どの選択肢にも、長所と弱点があります。簡単に見ていきましょう。

パスに基づく並べ替え：
　パス名に基づいた並べ替えは、ブロックでの並べ替えに近似するもっとも簡単、かつ、もっとも非効果的な方法です。大多数のファイルシステムに使用されているレイアウトアルゴリズムの結果、各ディレクトリ内のファイル－および、結果的に、親ディレクトリを共有しているディレクトリ－は、ディスク上で隣接している傾向があります。同じディレクトリ内のファイルはほぼ同時期に作成される確率が高いため、この特色はさらに増幅されます。

　したがって、パスによる並べ替えは、ディスク上のファイルの物理的な位置と大まかに近似します。同じディレクトリに存在するふたつのファイルは、ファイルシステムの大きく隔たった部分に存在するふたつのファイルに比べて、接近して存在する可能性が高い・・・正にそのとおりです。この方法の弱点は、断片化を考慮できないことです。ファイルシステムが断片化されていればいるほど、パスによる並べ替えは役に立ちません。たとえ断片化を無視するにしても、パスに基づく並べ替えは実際のブロックに基づいた順序付けの近似に過ぎません。一方、長所は、少なくともある程度、あらゆるファイルシステムに適用できることです。時間局所性の結果として、ファイルレイアウトの方法にかかわりなく、パスに基づく並べ替えは少なくとも軽度に正確であることが示されています。また、実行しやすい並べ替えでもあります。

iノードに基づく並べ替え：
　iノードは、個々のファイルと関連付いたメタデータを含んでいるUnix構成体です。ファイルのデータは複数の物理的ディスクブロックを消費する場合がありますが、各ファイルにはただひとつのiノードしかありません。このiノードにはファイルのサイズ、許可、オーナー、などの情報が納められています。iノードに関する詳細は第7章で解説します。この時点では、ふたつの事実を知っておいてください。すなわち、すべてのファイルには関連付いたひとつのiノードがあること、そのiノードには一意の番号が割り当てられていることです。

　以下の関係を想定してください。

  file i's inode number < file j's inode number

　これが、一般的に、以下を示唆するとすれば

  physical blocks of file i < physical blocks of file j

　iノードに基づく並べ替えは、パスに基づく並べ替えより優れています。

　ext2やext3などのUnix式のファイルシステムに関しては、正にそのとおりです。実iノードを使用しないファイルシステムでもあらゆることが可能とはいえ、iノード番号が（それがマッピングする対象にかかわりなく）優れた一次近似であることは確かです。

　これも第7章で解説しているとおり、iノード番号はstat()システムコールを利用して入手します。各I/O要求にかかわるファイルと関連付いたiノード番号が判明すると、要求がiノード番号の昇順で整列されます。

　以下は、特定のファイルのiノード番号を印刷するシンプルなプログラムです。

  #include <stdio.h>
  #include <stdlib.h>
  #include <fcntl.h>
  #include <sys/types.h>
  #include <sys/stat.h>
  /*
   * get_inode - returns the inode of the file associated
   * with the given file descriptor, or -1 on failure
   */
  int get_inode (int fd)
  {
          struct stat buf;
          int ret;
          ret = fstat (fd, &buf);
          if (ret < 0) {
                  perror ("fstat");
                  return -1;
          }
          return buf.st_ino;
  }
  int main (int argc, char *argv[])
  {
          int fd, inode;
          if (argc < 2) {
                  fprintf (stderr, "usage: %s <file>\n", argv[0]);
                  return 1;
          }
          fd = open (argv[1], O_RDONLY);
          if (fd < 0) {
                  perror ("open");
                  return 1;
          }
          inode = get_inode (fd);
          printf ("%d\n", inode);
          return 0;
  }

　get_inode()関数は非常に適応性があり、プログラムに合わせて簡単に利用できます。

　iノード番号は入手しやすい、並べ替えが容易、物理的ファイルレイアウトの良好な近似である．．．。これらは、iノード番号に基づく並べ替えの長所です。主要な短所は、断片化によって近似が低下する、近似は推測にすぎない、非Unixファイルシステムでは近似の正確性が劣る、などです。しかし、ユーザースペースにおけるI/O要求のスケジューリングにもっとも一般的に利用されている方法です。

物理ブロックに基づく並べ替え：
　用途に適したエレベーターアルゴリズムを設計する上でもっとも良い方法は、当然、物理ディスクのブロックに基づいた並べ替えです。前述したように、おのおののファイルは論理ブロックに分割されます。論理ブロックは、ファイルシステムの最小の割当単位です。論理ブロックサイズはファイルシステム依存であり、ひとつの論理ブロックがひとつの物理ブロックに位置します。したがって、ファイルを構成する論理ブロック数を特定し、それらの論理ブロックが位置する物理ブロックを特定して、並べ替えを実行できるわけです。

　カーネルには、ファイルの論理ブロック番号から物理ディスクのブロックを求める方法があります。すなわち、第7章で解説したioctl()システム・コールを利用し、FIBMAPコマンドを実行します。

  ret = ioctl (fd, FIBMAP, &block);
  if (ret < 0)
          perror ("ioctl");

　上記の例で、fdは当該ファイルのファイル記述子、ブロックは物理ブロックを特定しようとしている論理ブロックです。コールが成功すると、ブロックが物理ブロック番号に置き換わります。渡される論理ブロックは「ゼロインデックス付き」かつ「ファイル相対」です。つまり、8つの論理ブロックで構成されているファイルであれば、0から7までが有効値です。

　このように、論理ブロックと物理ブロックの位置付けは2段階を経て特定します。最初に、stat()システム・コールを利用して、ファイルのブロック数を特定する必要があります。次に、各論理ブロックに対するioctl()要求を出して、対応する物理ブロックを特定します。

　以下は、渡されたファイルに対して上記の内容を実行する、コマンドラインのプログラム例です。

  #include <stdio.h>
  #include <stdlib.h>
  #include <fcntl.h>
  #include <sys/types.h>
  #include <sys/stat.h>
  #include <sys/ioctl.h>
  #include <linux/fs.h>
  /*
   * get_block - for the file associated with the given fd, returns
   * the physical block mapping to logical_block
   */
  int get_block (int fd, int logical_block)
  {
          int ret;
          ret = ioctl (fd, FIBMAP, &logical_block);
          if (ret < 0) {
                  perror ("ioctl");
                  return -1;
          }
          return logical_block;
  }
  /*
   * get_nr_blocks - returns the number of logical blocks
   * consumed by the file associated with fd
   */
  int get_nr_blocks (int fd)
  {
          struct stat buf;
          int ret;
          ret = fstat (fd, &buf);
          if (ret < 0) {
                  perror ("fstat");
                  return -1;
          }
          return buf.st_blocks;
  }
  /*
   * print_blocks - for each logical block consumed by the file
   * associated with fd, prints to standard out the tuple
   * "(logical block, physical block)"
   */
  void print_blocks (int fd)
  {
          int nr_blocks, i;
          nr_blocks = get_nr_blocks (fd);
          if (nr_blocks < 0) {
                  fprintf (stderr, "get_nr_blocks failed!\n");
                  return;
          }
          if (nr_blocks == 0) {
                  printf ("no allocated blocks\n");
                  return;
          } else if (nr_blocks == 1)
                  printf ("1 block\n\n");
          else
                  printf ("%d blocks\n\n", nr_blocks);
          for (i = 0; i < nr_blocks; i++) {
                  int phys_block;
                  phys_block = get_block (fd, i);
                  if (phys_block < 0) {
                          fprintf (stderr, "get_block failed!\n");
                          return;
                  }
                  if (!phys_block)
                          continue;
                  printf ("(%u, %u) ", i, phys_block);
          }
          putchar ('\n');
  }
  int main (int argc, char *argv[])
  {
          int fd;
          if (argc < 2) {
                  fprintf (stderr, "usage: %s <file>\n", argv[0]);
                  return 1;
          }
          fd = open (argv[1], O_RDONLY);
          if (fd < 0) {
                  perror ("open");
                  return 1;
          }
          print_blocks (fd);
          return 0;
  }

　ほとんどの場合にファイルは隣接しており、また、出されたI/O要求を論理ブロックごとに並べ替えるのは（控えめに言っても）困難なので、ファイルの最初の論理ブロックの位置に基づいて並べ替える方法も理にかなっています。この場合、get_nr_blocks()を利用せずに、以下の戻り値に基づいた並べ替えが可能です。

  get_block (fd, 0);

　FIBMAPの短所は、CAP_SYS_RAWIO機能－事実上のルート特権が要求される点です。そのため、非ルートアプリケーションで使用することはできません。また、FIBMAPコマンドは標準化されていますが、その実行はファイルシステム次第です。ext2やext3などの共通システムはFIBMAPをサポートしますが、個性的なシステムではサポートされない可能があります。サポートされていない場合、ioctl()コールはEINVALを戻します。

　反面、FIBMAPの長所としては、実際にファイルが存在している物理ディスクのブロックを戻す点が挙げられます。正にこれこそ、ユーザーが欲する並べ替えの基盤です。ひとつのファイルに対するすべてのI/O をたったひとつのブロックの位置に基づいて並べ替えるにしても（カーネル実装のI/Oスケジューラは、ブロックごとにおのおのの要求を並べ替えます）、この方法は最適な順序付けに非常に近い成果を実現します。ただ、多くのユーザーにとって、ルート特権が若干出ばなをくじく障害と言えるでしょう。