応用情報技術者 2019年秋期午前2 問19

問題文

三つの媒体 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解説】

正解の理由

空き領域が最大の媒体を選ぶ方式では、各割当時に「これまで割り当てられた合計が最小の媒体」を選ぶことと等価です。与えられた順序で割り当てを行うと、最終的な各媒体への割当合計は A=90、B=100、C=110 となり、合計の大きい順は C、B、A です。したがって選択肢の中ではエ（C, B, A）が正しい並びになります。

解法ステップ

以下は各割当（要求サイズ順：90, 30, 40, 40, 70, 30）ごとの逐次選択と累計割当の記録です。初期は A,B,C の割当合計がすべて 0（空き等しい）で、空き等しい場合は A→B→C の優先順が適用されます。

1回目（90MB）
- 全て等しいため優先順で A を選択。
- 累計：A=90、B=0、C=0
2回目（30MB）
- B と C が最も空き（累計が最小）で同等、優先順により B を選択。
- 累計：A=90、B=30、C=0
3回目（40MB）
- 累計が最小なのは C（0） → C を選択。
- 累計：A=90、B=30、C=40
4回目（40MB）
- 現在の累計は A=90、B=30、C=40。最も累計が小さいのは B（30）なので B を選択（ここがしばしば誤る箇所）。
- 累計：A=90、B=70、C=40
5回目（70MB）
- 累計が最も小さいのは C（40） → C を選択。
- 累計：A=90、B=70、C=110
6回目（30MB）
- 累計が最も小さいのは B（70） → B を選択。
- 最終累計：A=90、B=100、C=110

以上より降順は C(110)、B(100)、A(90) で、選択肢はエに一致します。

選択肢別の誤答解説

ア: A, B, C
- Aが最も割当が多いとする並びですが、実際は A の累計は 90 に留まり、C と B の合計がそれより大きくなるため誤りです。
イ: A, C, B
- A を最上位にしている点が誤りです。割当過程で初回以外は A は追加割当を受けず合計が最小でもないため、最終順位は A が最下位になります。
ウ: B, A, C
- B を最上位にしていますが、最終累計は C(110) が最大であり、B は中位（100）なので誤りです。
エ: C, B, A
- 実際の逐次割当結果（A=90, B=100, C=110）と一致します。したがって正しい並びです。

よくある誤解

「常に最後に割り当てた媒体が最も割当が多くなる」と考える誤解：最後に大きな要求を割り当てても、それまでの累計によって選択が左右されるため、逐次の状況を正確に追う必要があります。
「同じ空きなら直前に使った媒体が優先される」と思う誤解：本問題では同空き時の優先順が A→B→C に固定されており、直前使用の有無は関係ありません。
「空きが最大を選ぶ＝最も割当が増える媒体を常に選ぶ」と混同する誤解：選択基準は“現在の空き（＝容量−累計）”であり、将来の要求を見越すものではありません。

補足コラム

本問題のアルゴリズムは「最大空き領域優先（largest free space first）」にあたり、負荷分散や断片化対策の一手法として使われます。等容量の媒体ばかりでかつ要求が途中で解放されない設定の場合、問題は「現在までの累計が最小の媒体を選ぶ」ことと同義になり、手計算では累計値を更新していく方法が最も確実です。実務では容量制限や解放の有無、要求分布によって挙動が変わるため、シミュレーションで挙動を確認すると安全です。

FAQ

Q: 同じ空きのときの優先順がなぜ重要ですか？
A: 同空き時の優先順で選ぶ媒体が確定しないと逐次選択があいまいになり、最終的な累計が変わります。本問は明示された優先順（A→B→C）を必ず適用して計算します。

Q: 容量が有限で割当不可になったらどう判断しますか？
A: 問題の条件で「十分な大きさ」とされているため発生しませんが、実際には割当前に選んだ媒体に対して容量チェックを行い、もし不足なら次に空きの大きい媒体を選ぶ実装になります。

関連キーワード: 最大空き領域優先、割当アルゴリズム、逐次割当、負荷分散、優先順ルール

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！