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

動的再配置で分散する空き領域を集める問題【午前2 解説】

要点まとめ

• 結論：セグメント3（800kバイト）を右端の800kバイトの空き領域へ移動するだけで、必要なメモリアクセス時間は12.0ミリ秒となります。
• 根拠：1回のメモリアクセスは4バイト単位で読み書き各30ns、つまり1チャンクあたり$60$ns必要で、$800,000$バイトを移すと合計で$12.0$msになります。
• 差がつくポイント：移動対象を誤ってセグメント1や100kだけと考えると誤答になるため、配置図を読み取り「どのセグメントをどこへ移すか」を正確に判断することが重要です。

正解の理由

よくある誤解

• 「開放された100kだけを移動すればよい」と考える誤り：空きの集約は移動先・移動元の隣接関係を考えないと不十分です。
• 「セグメント1（500k）を移動すればよい」とする誤認：問題図を正しく把握すると、500kを動かす必要はなく、もっと大きな800kの移動が最小操作です。
• 1kの定義を1024バイトとする混同：設問で1k=1,000バイトと明記されている点を見落とすと計算がずれます。

解法ステップ

1. 図を読み、各領域の順序と大きさを確認する（500k, 100k(空), 800k, 800k(空)）。
2. 「空きを一つにする」ためにどのセグメントを移動すればよいかを検討する。隣接性からセグメント3を右の空きに移動するのが最小操作であると判断。
3. 移動するバイト数を求める：800kバイト = 800,000バイト。
4. 1アクセス当たりの処理時間を求める：4バイト単位で読み書き各30ns → 1チャンク当たり60ns。
5. 合計時間を計算：$\frac{800,000}{4}\times 60\text{ns}=12.0\text{ms}$。

選択肢別の誤答解説

• ア: 1.5
  • 1.5msは100kバイトだけを移動した場合の時間に相当します。計算は$\frac{100,000}{4}\times 60\text{ns}=1.5\text{ms}$で、対象を100kと誤認した場合の誤答です。
• イ: 6.0
  • 6.0msは400kバイトを移動した場合に相当します。中途半端に一部だけ移すとこうした値になり得ますが、空きの集約目標を満たしません。
• ウ: 7.5
  • 7.5msは500kバイト（セグメント1）を移動する想定の値で、$\frac{500,000}{4}\times 60\text{ns}=7.5\text{ms}$になります。セグメント1の移動は不要です。
• エ: 12.0（正解）
  • セグメント3の800k移動に対応する正しい計算結果です。

補足コラム

• なぜ「読み取り＋書き込み」を両方考慮するか：一般的なメモリコピーはソースから読み取り、デスティネーションへ書き込みを行うため、双方のアクセス時間を合算する必要があります。
• アクセス単位の重要性：4バイト単位でしかアクセスできない場合は、移動サイズが4の倍数であることを確認すると端数処理の誤りを避けられます。
• 実運用ではポインタの再設定や仮想アドレスでの再配置など、データを物理的に移動せずに断片化を解決する手法もありますが、本設問は純粋にメモリコピーの時間を問うものです。

FAQ