基本情報技術者 2011年 秋期 午前（科目A） 問14

磁気ディスク装置のヘッド移動総数【午前2 解説】

要点まとめ

• 結論: 現在ヘッドはシリンダ100で増加方向へ進むため、上方向の要求110→120→140を先に処理し反転して90→80→70→60を処理、総移動量は120シリンダです。
• 根拠: 要求をシリンダ番号順に並べ替え一方向にできるだけ進む「LOOK」ルールに従うと、移動経路は100→110→120→140→90→80→70→60であり各区間の差を足せば総移動距離が求まります。
• 差がつくポイント: 誤ってSCAN（端まで行く）やSSTF（最短探索優先）と混同しないこと。現在方向にある要求を先に完全消化してから反転する点を正確に理解すると得点できます。

正解の理由

よくある誤解

• LOOKとSCANを混同して端（最小0や最大トラック）までヘッドを移動したと考える誤り。SCANは端まで行くが、LOOKは最遠要求で反転します。
• 現在方向にある要求を無視して逆方向から処理を始める、またはSSTFのように常に最短移動を選ぶと誤答になります。
• 「処理順序を変えられるから結果は同じ」として、計算を単純化しすぎて反転位置を誤るパターン。

解法ステップ

1. 現在位置と移動方向を確認する: 現在100、方向は増加（大きい番号へ）。
2. 要求を2群に分ける: 現在位置以上（≥100）と現在位置未満（<100）。
   • ≥100: 110, 120, 140（昇順で処理）
   • <100: 90, 80, 70, 60（反転後に降順で処理）
3. 実際の移動順を決定する: 100→110→120→140（反転）→90→80→70→60。
4. 各区間の差を求めて合計する: $10+10+20+50+10+10+10=120$。
5. 以上より総移動量は120シリンダで確定。

選択肢別の誤答解説

• ア: 80 — もし「100から最大まで行かずに上方向だけで110,120,140を処理した後そこで終了」と誤解すると、100→140だけの40や別の短縮計算で80を導く誤りがあるが、反転して残りを処理する必要があるため不足です。
• イ: 120 — 正解。100→110→120→140→90→80→70→60の区間差を合計して120シリンダになります。
• ウ: 160 — 160 を選ぶ人は「上方向で140まで行った後、逆方向でさらに0まで行く（または別の最遠点まで余分に移動）」など端までの移動を無意味に加えた可能性があります。LOOKでは最遠要求までしか行きません。
• エ: 220 — 220 を導く誤りは、SCANで一方向の端（例えば最大または最小のトラック）まで移動する場合の計算ミスに由来することが多いです。今回の条件では端まで行く必要はありません。

補足コラム

• アルゴリズム名: 今回の条件は「LOOK」に相当します。LOOKはヘッドが端まで行かず、最遠要求で反転するため無駄な走行を削減します。
• 便利な計算式（増加方向スタートで上下に要求がある場合）: 総移動距離 = (max_up - start) + (max_up - min_down)
  • 今回は max_up=140, start=100, min_down=60 なので $(140-100)+(140-60)=40+80=120$。
• SCAN（エレベーター）では端まで移動するため、端の位置に依存して総移動量が増える点に注意してください。

FAQ