エレベーターアルゴリズム

世の中にはエレベーターアルゴリズムというものがあるらしい。


これは、ビルなどの建物についているエレベータのかごの動きを制御するためのアルゴリズムである。
各階にランダムにお客さんが来る。そのお客さんは上または下のボタンを押して自分の行きたい階の方向を指定する。
エレベーターのかごは複数ある場合があるので、となりのかごと連携をとりながら、お客さんの待ち時間が最短になるように、最短時間で目的の階にたどり着けるように移動を制御する。
これはエレベータの開発会社にとっては機密事項になるほど主要なアルゴリズムらしい。
確かに、
お客さんはかごに載るまでは上か下かの指示しか出さない。
乗ってから、何階に行きたいか指示を出す。
のでとっても複雑なロジックだと思う。
このアルゴリズムが、ハードディスクのヘッダの移動の制御にも使われているらしい。
確かに、
OSからどのトラックに書き込む読み出すのかランダムに指示が来る。またそのアクセス量にも限界がある。
できるだけスムーズにヘッダを動かしたほうがアクセス速度は速くなる。
という部分はエレベータと同じである。
エレベータにとって下の階が、HDのトラックの内側、
エレベータにとって上の階が、HDのトラックの外側、
と考えればいいのである。
うーん。世の中意外なところでつながっているのね。
てなことを考えていたら、あらら、今仕事でやっているプロジェクトにもエレベータロジックって応用できるのね。ってことに今更気が付いた。
修行が足りませんなぁ。

「エレベーターアルゴリズム」への3件のフィードバック

  1. なるほど、SCSIやタグサポートのIDEは、エレベータと似ているな。
    ただ、
    ・エレベータは昇降の人数がわからないが、HDDの場合はわかる。
    ・HDDの場合は、セクタの回転待ちを考慮しないといけない。
    ・エレベータには裏コマンドがある(おそらく)
    HDDの場合、ハード特性(密度や回転数)が同じだと、
    ベンチマークでファームウェアのアルゴリズムの良し悪しがわかるが、
    エレベータの場合だと、どうやってアルゴリズムの良し悪しを判定するのだろう。
    (エレベータはそれほど他社との競争がないのか?)

  2. エレベーターアルゴリズム:頭の悪いエレベーター

    たまに、不具合だろっ、と言いたくなるような動きをするエレベーターを見かけます。そういえばどんなアルゴリズムで動作しているんだろう、と思い軽く調べてみました。

コメントを残す