エレベータに見るアルゴリズムの性能と公平性のバランス

現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。

1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。

エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人のところに行くというやり方を考えることができる。そのような方法ではエレベータは進行方向を頻繁に変えることになるけど、近くで待っている人がいるのに遠くに行くということがなくなるので、平均待ち時間は減ることが期待できる。

しかしこの「最も近い階に行く」方法は重大な欠点がある。ランダムな階に人が来るとして、エレベータが最も近い階に行くというやり方をすると、多くの場合どの階からもそれなりに近い中間層ばかりをジグザグすることになって、ビルの最上階や最下階ではいつまでたってもエレベータが来なくなってしまう。つまりこの方法では公平性が極端に悪化してしまうのだ。これがエレベータが僕らが知っている方法で制御されている主な理由である。

HDDはミニチュアのエレベータみたいなものだ。HDDにはデータが書き込まれた回転するディスクが入っていて、先端に磁気センサの付いたアームがその上にあり、データを読み書きしたい位置に合わせてアームが移動するという仕組みになっている。アームをごくわずかに動かすのは1ミリ秒くらいでできるけど、ディスクの端から端まで移動するのは15ミリ秒くらいかかる。つまりアームの移動時間は物理的な距離に依存していて、エレベータとよく似た性能特性を持っている。

複数のアプリケーションが複数のファイルを同時に読み書きしているとしよう。リクエストの平均待ち時間を最小化することを考えると、現在アームがある位置に最も近いディスク領域を読みに行くアルゴリズムが有利になるが、これはエレベータとまったく同じ理由で極端に不公平なアルゴリズムだ。つまり、偶然ディスクの端のほうに配置されてしまったデータのアクセスに極めて長い時間がかかるようになってしまう。待ち時間が極端にばらつくのは望ましくないのでこのアルゴリズムはあまりよろしくない。

よりよいアルゴリズムはエレベータの制御方法と同じものである。実際これには「エレベータアルゴリズム」という名前がついている。エレベータアルゴリズムでは、一方向にアームを動かし始めるとそちら方向の読み書きリクエストがすべて満たされるまでは移動方向を変えたりしない。これにより若干平均待ち時間は伸びるものの公平性は飛躍的に改善することができる。

エレベータとHDDは物理的にはずいぶん大きさの違う存在だけど、意外なところで共通点が見つかるものだ。これは結構面白い話だと思う。

49

この記事が入っているマガジン

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。