応用情報技術者 2010年春期午前2 問20

問題文

三つの媒体 A〜C に次の条件でファイル領域を割り当てた場合、割り当てた領域の総量が大きい順に媒体を並べたものはどれか。　〔条件〕　(1) ファイル領域を割り当てる際の媒体選択アルゴリズムとして、空き領域が最大の媒体を選択する方式を採用する。　(2) 割当て要求されるファイル領域の大きさは、順に 90, 30, 40, 40, 70, 30 (Mバイト)であり、割り当てられたファイル領域は、途中で解放されない。　(3) 各媒体は容量が同一であり、割当て要求に対して十分な大きさをもち、初めはすべて空きの状態である。　(4) 空き領域の大きさが等しい場合には、A, B, Cの順に選択する。

🖊️ 解答を隠して解いてみる

選択肢

ア：A, B, C

イ：A, C, B

ウ：B, A, C

エ：C, B, A（正解）

🔒 解説は解答すると表示されます

最大空き領域アルゴリズム【午前2解説】

正解の理由

与えられた割当方式は「空き領域が最大の媒体を選ぶ」方式（いわゆるワーストフィット）であり、媒体の容量が同じで初期は全て空であるため、各時点で「最も割当済み容量が小さい媒体」が選ばれます。各要求（90, 30, 40, 40, 70, 30）を順に適用すると、割当の最終合計は A=90, B=100, C=110 となり、合計が大きい順は C > B > A です。したがって正解はエ（C, B, A）です。

解法ステップ

アルゴリズムの要点：容量が同じなら「空きが最大＝割当済みが最小」。空きが等しい場合は A→B→C の順序で選ぶ。

順に割り当てて状態を更新します（ここでは各媒体の「割当済み合計」を示す）。

要求 90:
- 初期 A=0,B=0,C=0（全て同じ→優先順 A）
- 90 を A に割当 → A=90, B=0, C=0
要求 30:
- 割当済みが最小なのは B と C（0）。優先順で B を選択。
- 30 を B に割当 → A=90, B=30, C=0
要求 40:
- 最小は C（0） → C に割当
- 40 を C に割当 → A=90, B=30, C=40
要求 40:
- 現在の割当済みは A=90, B=30, C=40。最小は B（30）なので B を選択。
- 40 を B に割当 → A=90, B=70, C=40
要求 70:
- 現在 A=90, B=70, C=40。最小は C（40）なので C を選択。
- 70 を C に割当 → A=90, B=70, C=110
要求 30:
- 現在 A=90, B=70, C=110。最小は B（70）なので B を選択。
- 30 を B に割当 → A=90, B=100, C=110

最終合計：A=90, B=100, C=110。順序は C(110) > B(100) > A(90) → エ。

選択肢別の誤答解説

ア: A, B, C
誤り。A が最大、B が次、C が最小とする並びですが、実際は C が最終的に最大（110）です。途中の選択基準の適用ミス（例えば4回目の40を誤ってCに割当てるなど）に注意。
イ: A, C, B
誤り。C と B の最終合計を逆にしている解釈で、5〜6回目の割当判断順序を取り違えた可能性があります。
ウ: B, A, C
誤り。B を最大と見なしていますが、最終値は B=100、A=90、C=110 であり C が最大です。
エ: C, B, A
正しい。上記の手順で得られる最終合計に一致します。

（補足：4回目の40MB割当のように、各ステップで「現在の割当済みが最小の媒体」を確実に選ぶことが正解導出の鍵です）

よくある誤解

「空きが最大」＝「既に割当が大きい媒体を選ぶ」と誤解する
実際は同容量なら空きが最大なのは割当済みが最も小さい媒体です。逆に考えると誤答しやすいポイントです。
同値時の優先順を忘れる
初回などで全て同じ場合に A→B→C の順序ルールを適用しないと異なる枝分かれを生みます。
ステップごとの状態更新を省略する
各要求ごとに割当済み値を更新して判断することを怠ると、途中の選択で誤ることがあります。

補足コラム

この方式は一般に「ワーストフィット（Worst-fit）」と呼ばれ、断片化を避ける目的で用いられることがあります。対義語は「ベストフィット（空きが最小の場所へ）」や「ファーストフィット（先に見つかった空きへ）」です。今回の問題では容量が十分に大きく初期が空なので、割当判断は「割当済み合計の大小比較」と同義になります。実装上は各媒体の現在割当量を管理しておき、要求ごとに最小値（または優先順位での先頭）を選べば良いでしょう。

FAQ

Q1: 容量が異なる場合はどう判断しますか？
A1: 実際には「空き容量」を直接比較します（容量 − 割当済み）。今回のように総容量が十分大きく同一なら割当済みの最小値比較で同等です。

Q2: 解放（deallocation）があると結果は変わりますか？
A2: はい。解放があると各時点の空き量が変化するため、以降の割当先が変わり得ます。問題文で「途中で解放されない」と明記している点に注意してください。

Q3: 試験ではどのように速く解けばよいですか？
A3: 各媒体の現在割当合計だけを追えば良いので、紙に A,B,C の値を逐次更新していくと速く正確に解けます。特に同値時の優先ルールを先に確認しておくこと。

関連キーワード: 最大空き領域, ワーストフィット, メモリ割当て, ファイル配置, アルゴリズム

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！