エレベータアルゴリズム

エレベータアルゴリズムは、ハードディスク内のヘッドの動きを制御するスケジューリングアルゴリズムの1つである。SCAN ともいう。

このアルゴリズムは、上昇中は、上で待っている人や降りる人がいる限り上昇し続け、同様に、下降中は、下で待っている人や降りる人がいる限り下降し続けるという、エレベータの上下の動作と似ているため、エレベータアルゴリズムと呼ばれている。

実装上は、読み取り/書き込み要求のバッファと、そのシリンダ（トラック）番号を保持し、その要求はエレベータの待っている人/降りる人に対応する。シリンダ番号は軸受に近いほど小さい値である。

説明

アイドル状態のハードディスクが要求を受信すると、まずヘッドはその要求されたデータが格納されているシリンダ方向に動く。次の要求を受信すると、その要求は現在の移動方向と同じならば処理される。アームの現在の移動方向で処理可能な要求がなくなると、アームは逆側に動き始め、残りの要求を順に処理する。

変種

ヘッドが常に外（内）側に向い、ディスクの最も外（内）側に到達すると、最も内（外）側に戻り再度外（内）側に向いながら処理を行う手法もある。この手法では一方向のみで要求に答えることとなる。この手法は循環（Circular）エレベータアルゴリズムまたは C-SCAN と呼ばれる。最も内（外）側へと戻るリターンシークの時間は無駄であるが、一般的なエレベータアルゴリズムでは最も内外側のシリンダへの到達平均時間が長くなるが、循環エレベータアルゴリズムでは全てのシリンダに対して同等の性能が得られる。

他にも

• FSCAN （2つの命令キューを持つSCAN）
• LOOK (C-LOOK)
• N-Step-SCAN

などの種類が存在する

動作例

以下の例で、エレベータアルゴリズムと循環エレベータアルゴリズムの平均ディスクシーク時間を計算手法を示す。

• 要求されるシリンダ番号：100, 50, 10, 20, 75
• ヘッドの初期位置：35
• 要求されたシリンダ番号を昇順に並べると10, 20, 50, 75, 100である。

エレベータアルゴリズムも循環エレベータアルゴリズムも最外周に移動するまでは同じように動作する。ヘッドの初期位置35に対して最初の要求は100であるため、まずヘッドは外側に動く。どちらの手法でも、50, 75, 100の順に要求を処理し、シーク時間はそれぞれ

• シーク 1: 50 − 35 = 15
• シーク 2: 75 − 50 = 25
• シーク 3: 100 − 75 = 25

である。

ここで、エレベータアルゴリズムは降順に処理を開始し次に20の処理を行う。一方、循環エレベータアルゴリズムは最内周へと移動する。

• シーク 4 (SCAN): 20 − 100 = 80
• シーク 5 (SCAN): 10 − 20 = 10
• 合計 (SCAN): 155
• 平均シーク時間 (SCAN): 155 ÷ 5 = 31

• シーク 4 (C-SCAN): 0 − 100 = 0 ヘッドが循環して移動するため、0の位置と100の位置はほぼ0である。
• シーク 5 (C-SCAN): 10 − 0 = 10
• シーク 6 (C-SCAN): 20 − 10 = 10
• 合計 (C-SCAN): 85
• 平均シーク時間 (C-SCAN): 85 ÷ 5 = 17

注：循環エレベータアルゴリズムでは6回のシークを行っているが、実際にデータを処理する要求は5回である。

ただしここで、循環エレベータアルゴリズムではヘッドがリターンシークする時間を無視している。

シリンダは円形のリストとして扱われるため、100から0への移動はヘッドの移動とはみなされない。ヘッドの移動とみなす場合は合計シークは185となり、平均シーク時間は37となる。さらに、ヘッドの移動方向を2度も変更しているため、さらに長い時間がかかる。

解析

エレベータアルゴリズムはヘッドの動きを常にシリンダ数の2倍未満に抑え、応答時間のばらつきが小さい利点があり、アルゴリズムは非常に簡単である。

しかし、エレベータアルゴリズムは shortest seek first より常に良いとは限らない。この手法は最適に近いが、新しい要求が既存の要求よりも前に処理する位置に入り続ける場合に応答時間のばらつきが大きくなり、最悪の場合リソーススタベーションを起こす。

最適な応答時間を保証するために、 shortest seek time first アルゴリズムでは、リソーススタベーション防止技術が盛り込まれている。

関連項目

• FIFO