平成27年度 春期 午前 問18

✓ これが正解イ読込み可能 読込み不可能

解説

入るかどうかは、連続した最大の空きで決まります。

設問は、500 k バイトの連続した空き領域へオーバレイ方式でモジュールを読み込み、最後の 120 k バイトが入るかどうかを、二つの読込み順序について答えさせています。割当てはファーストフィット方式、つまり先頭から見て最初に入る穴に置くやり方です。ですから見るべきは、空きの合計ではなく、続いた一つの穴が 120 に届くかどうかです。順序 A を追います。100 と 200 を置いてから 200 を解放すると、空いた場所が後ろの空きとつながって 400 の穴に戻ります。そこへ 150 を置き、先頭の 100 を解放し、80 を先頭側の穴に置くと、先頭側には 20 しか残りません。次の 100 は後ろの 250 の穴から取られ、その後ろに 150 が残ります。よって最後の 120 は入ります。順序 B も追います。200、100、150 と置き、100 を解放して 80 を置き、200 を解放してから 100 を置くと、残る穴は 100 と 20 と 50 の三つです。合計は 170 ありますが、続いた一つとしては 100 が最大なので、120 は入りません。同じモジュールを同じ数だけ読んでも、順序が変わると穴の残り方が変わります。こうして空きが細切れに散る現象をフラグメンテーションと呼び、詰め直すコンパクションをしない限り元には戻りません。

ほかの選択肢はなぜ違うのか

• ア読込み可能 読込み可能：空きの合計だけを見て、どちらの順序でも入ると判断した形です。後の順序では空きが三か所に散っていて、合計が足りていても、続いた一つの穴としては足りません。
• ウ読込み不可能 読込み可能：二つの可否をそっくり入れ替えた形です。先の順序で大きな空きが最後まで残り、後の順序で細切れになるという向きが、逆に読まれています。
• エ読込み不可能 読込み不可能：どちらも入らないと判断した形です。先の順序では、最後の読込みの直前に大きな空きが続けて残っているので、そこへ収まります。