Loading article…
エレベーターアルゴリズム、またはSCANとは、ディスクの読み取りおよび書き込み要求を処理する際に、ディスクのアームとヘッドの動きを決定するためのディスクスケジューリングアルゴリズムである。
このアルゴリズムは、建物のエレベーターの動作にちなんで名付けられました。エレベーターは、乗客が空になるまで現在の方向（上昇または下降）に移動し続け、乗客を降ろすため、または同じ方向に向かう新しい乗客を乗せるためにのみ停止します。
実装の観点から見ると、ドライブは保留中の読み書き要求のバッファを保持し、要求に関連付けられたシリンダ番号も保持します。一般的に、シリンダ番号が小さいほどシリンダがスピンドルに近いことを示し、番号が大きいほどシリンダがスピンドルから遠いことを示します。
このアルゴリズムはデータストレージにはほとんど使われなくなっている。現在の世代の磁気ディスクでは、ディスク上の特定のデータの位置を知ることは不可能であり、ソリッドステートメモリデバイスは位置に関係なく一定のシーク時間を持つ。[ 1 ]
このアルゴリズムに関する最も初期の発表は、ドナルド・クヌースの古典的名著『コンピュータプログラミングの技法第1巻』で、カリフォルニア工科大学の数学棟にある1台のエレベーターの理論的なシミュレーションを記述し、コルーチンと二重リンクリストについて論じている。1980年代までに、この問題はn台のエレベーターに拡張された。現在では、ソフトウェアエンジニアリングとプログラミング言語の形式仕様の古典的な問題と考えられている。[ 2 ]
ドライブがアイドル状態のときに新しい要求が到着すると、最初のアーム/ヘッドの動きは、データが格納されているシリンダの方向（入力または出力）になります。追加の要求が到着すると、アームがディスクの端に到達するまで、現在のアームの動きの方向でのみ要求が処理されます。これが起こると、アームの方向が反転し、反対方向に残っていた要求が処理され、これを繰り返します。[ 3 ]
この方式のバリエーションの一つでは、すべての要求が一方向のみで処理されるようにします。つまり、ヘッドがディスクの外縁に到達すると、先頭に戻り、この一方向のみで新しい要求を処理します（またはその逆）。これは「円形エレベーターアルゴリズム」またはC-SCANとして知られています。戻りシークに時間はかかりますが、ヘッドからの期待距離が常に最大距離の半分であるため、すべてのヘッド位置でより均等なパフォーマンスが得られます。これは、中央のシリンダが最も内側または最も外側のシリンダよりも最大で2倍の頻度で処理される標準のエレベーターアルゴリズムとは異なります。
その他のバリエーションとしては、以下のようなものがあります。
以下は、SCANアルゴリズムとC-SCANアルゴリズムの両方について、平均ディスクシーク時間を計算する方法の例です。
SCANとC-SCANは、キューに登録された最後のトラックに到達するまで、どちらも同じように動作します。この例では、SCANアルゴリズムが現在、より低いトラック番号からより高いトラック番号へと移動していると仮定します（C-SCANも同様です）。どちらの方法でも、次のトラック要求と現在のトラックとの間の大きさ（つまり絶対値）の差を取ります。
この時点で、両方とも最高位（末尾）のトラック要求に到達しました。SCANは方向を反転して次に近いディスク要求（この例では20）を処理し、C-SCANは常にトラック0に戻ってより高いトラック要求の処理を開始します。
C-SCANアルゴリズムを使用して6回のシークが実行されたにもかかわらず、実際に行われたI/Oは5回のみだった。
エレベーターアルゴリズムのどちらのバージョンにおいても、アームの動きは総シリンダー数の2倍未満であり、応答時間のばらつきも小さくなっています。また、アルゴリズム自体も比較的単純です。
エレベーターアルゴリズムは、最適解にやや近い最短時間優先アルゴリズムよりも常に優れているとは限らず、応答時間のばらつきが大きく、新しいリクエストが既存のリクエストよりも優先的に処理される場合は、飢餓状態になる可能性さえあります。最短時間優先アルゴリズムには、最大応答時間を保証するための飢餓防止技術を適用できます。