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

エレベータアルゴリズム( SCAN ) は、読み取りおよび書き込み要求を処理する際にディスクのアームとヘッドの動きを決定する ディスクスケジューリングアルゴリズムです。

このアルゴリズムは、ビルのエレベーターの動作にちなんで名付けられました。エレベーターは、乗客が空になるまで現在の方向 (上または下) に移動し続け、乗客を降ろすとき、または同じ方向に向かう新しい乗客を乗せるときのみ停止します。

実装の観点から見ると、ドライブは、保留中の読み取り/書き込み要求のバッファと、要求に関連付けられたシリンダ番号を保持します。シリンダ番号が小さいほど、シリンダがスピンドルに近いことを示し、番号が大きいほど、シリンダがスピンドルから遠いことを示します。

ドライブがアイドル状態のときに新しい要求が到着すると、最初のアーム/ヘッドの動きは、データが保存されているシリンダの方向、つまり内側または外側になります。追加の要求が到着すると、アームがディスクの端に到達するまで、要求は現在のアームの動きの方向でのみ処理されます。これが起こると、アームの方向が反転し、反対方向に残っていた要求が処理されます。これを繰り返します。^[1]

この方法の 1 つのバリエーションでは、すべての要求が 1 方向のみで処理されることが保証されます。つまり、ヘッドがディスクの外側の端に到達すると、ヘッドは先頭に戻り、この 1 方向のみで新しい要求を処理します (またはその逆)。これは、「円形エレベーター アルゴリズム」または C-SCAN として知られています。戻りシークの時間は無駄になりますが、ヘッドからの予想距離が常に最大距離の半分になるため、すべてのヘッド位置でより均等なパフォーマンスが得られます。これは、中央のシリンダが最も内側または最も外側のシリンダの 2 倍の頻度で処理される標準エレベーター アルゴリズムとは異なります。

その他のバリエーションとしては、次のものがあります。

• FSCAN
• 見て
  • C-ルック
• Nステップスキャン

以下は、SCAN アルゴリズムと C-SCAN アルゴリズムの両方の平均ディスク シーク時間を計算する方法の例です。

• 保留中のディスク要求のリストの例 (トラック番号順にリスト): 100、50、10、20、75。
• 例の開始トラック番号は 35 になります。
• リストは、10、20、50、75、100 の昇順で並べ替える必要があります。

SCAN と C-SCAN は両方とも、キューに入れられた最後のトラックに到達するまで同じように動作します。この例では、SCAN アルゴリズムが現在、低いトラック番号から高いトラック番号に向かっていると仮定します (C-SCAN が行っているように)。どちらの方法でも、次のトラック要求と現在のトラック間の絶対値 (つまり、絶対値) の差を取得します。

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

この時点で、両方とも最高 (終了) トラック要求に到達しています。SCAN は方向を反転して、次に最も近いディスク要求 (この例では 20) を処理し、C-SCAN は常にトラック 0 に戻り、より高いトラック要求の処理を開始します。

• シーク4（スキャン）： 20 − 100 = 80
• シーク5（スキャン）： 10 − 20 = 10
• 合計（スキャン）: 155
• 平均（スキャン）： 155 ÷ 5 = 31
• シーク 4 (C-SCAN):シリンダーは循環リストとして扱われるため、ヘッドの移動は 0 − 100 = 0 になります (C-SCAN は常に最初のトラックに戻ります)
• シーク5（C-SCAN）： 10 − 0 = 10
• シーク6（C-SCAN）： 20 − 10 = 10
• 合計（C-SCAN）： 85
• 平均（C-SCAN）： 85 ÷ 5 = 17

C-SCAN アルゴリズムを使用して 6 回のシークが実行されましたが、実際に実行された I/O は 5 回のみでした。

スキャン アルゴリズム (プレフィックス合計アルゴリズムとも呼ばれます) は、コンピューター サイエンスにおいて、配列またはリスト内の一連の要素の累積合計または累積結果を計算する問題によく使用されます。このアルゴリズムは、リストを反復処理し、現在の要素までの累積結果を維持することで動作し、並列計算、操作の削減、大規模データの効率的な処理など、さまざまなシナリオで使用できます。

スキャン アルゴリズムが適用された実際の例を次に示します。

例: 株式市場分析におけるリアルタイム データ処理 時間の経過に伴う株式の価格変動を追跡し、任意の時点での株式の累積値または利益/損失を計算する金融取引アプリケーションを想像してください。

シナリオ: 特定の株式について、数日間にわたる毎日の株価変動 (プラスまたはマイナスの値) のリストがあります。スキャン アルゴリズムを使用すると、各日の累積利益または損失を計算し、開始からその日までの株価の合計変動を表示できます。

入力データ: 毎日の株価変動のリスト:

csharp コードをコピー [10, -5, 3, 7, -2] ここで:

10 は 1 日目に 10 ドルの利益、-5 は 2 日目に 5 ドルの損失、3 は 3 日目に 3 ドルの利益、7 は 4 日目に 7 ドルの利益、-2 は 5 日目に 2 ドルの損失を表します。ステップバイステップの実行 (スキャン アルゴリズム):

初期累積合計は 0 から始めます。その後の各日の変化を累積合計に追加します。1 日目: 0 + 10 = 10 (これまでの合計利益: $10) 2 日目: 10 + (-5) = 5 (これまでの合計利益: $5) 3 日目: 5 + 3 = 8 (これまでの合計利益: $8) 4 日目: 8 + 7 = 15 (これまでの合計利益: $15) 5 日目: 15 + (-2) = 13 (これまでの合計利益: $13) 出力: 各日の累積利益:

csharp コードをコピー [10, 5, 8, 15, 13] この累積リストは、期間中の各日における株式の総利益/損失のパフォーマンスを示しています。スキャン アルゴリズムを使用すると、データに対する 1 回のパスでこれらの累積結果を効率的に計算できます。

並列処理と最適化: データ セットが大きい実際のアプリケーション (複数の株式の株価を数千日間にわたって追跡するなど) では、このスキャン アルゴリズムを並列化して実行速度を上げることができます。たとえば、並列プレフィックス合計 (入力配列をチャンクに分割し、並列処理してからマージする) などの手法を使用すると、大規模なデータをより効率的に処理できます。

株式市場分析以外のユースケース: 画像処理: 畳み込みやぼかしフィルターなどのタスクの累積演算 (ピクセル強度など)。分散システム: 複数のノード間で値を集計して累積統計を計算します。データベース システム: 金融アプリケーションまたは分析で実行中の合計を効率的に計算します。スキャン アルゴリズムは、以前の計算に基づいてデータを処理または集計する必要があるシナリオで不可欠であり、その並列実装は、より大きなデータセットのスケールアップに役立ちます。

エレベーター アルゴリズムの両方のバージョンでは、アームの動きはシリンダーの総数の 2 倍未満であり、応答時間の変動は小さくなります。アルゴリズムも比較的単純です。

エレベーター アルゴリズムは、最適値にわずかに近づいた最短シーク ファースト アルゴリズムよりも常に優れているわけではありませんが、応答時間の変動が大きく、新しい要求が既存の要求よりも先に継続的に処理されると、スターベーションが発生することもあります。スターベーション防止テクニックを最短シーク ファースト アルゴリズムに適用して、応答時間を最大化することができます。

• FIFO (コンピューティングとエレクトロニクス)