エンベデッドシステムスペシャリスト 2021年午前2 問09

問題文

三つの媒体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の割当て量	Bの割当て量	Cの割当て量
90 Mバイト	A	90	0	0
30 Mバイト	B	90	30	0
40 Mバイト	C	90	30	40
40 Mバイト	B	90	70	40
70 Mバイト	C	90	70	110
30 Mバイト	B	90	100	110

最初は空き領域が同じなので、同点時の規則に従ってAに90 Mバイトを割り当てます。その後は、割当て済み領域が最も少ない媒体を選びます。

最終的な割当て量は、Aが90 Mバイト、Bが100 Mバイト、Cが110 Mバイトです。したがって、大きい順はC、B、Aとなり、該当する選択肢はエです。

解法ステップ

各媒体の容量を同じ値と考えます。容量が同じなら、空き領域が最大の媒体は、割当て済み領域が最小の媒体です。
90 Mバイトの要求は同点のため、規則によりAに割り当てます。
次の要求からは、割当て済み領域が最も少ない媒体を選び、要求サイズを加算します。
すべての要求を処理した後、各媒体の割当て量を大きい順に並べます。

選択肢別の誤答解説

ア（A、B、C）：実際の割当て量はAが最小で、Cが最大です。大きい順に並べた結果とは逆になります。
イ（A、C、B）：Aを最大としている点が誤りです。Aの割当て量は90 Mバイトです。
ウ（B、A、C）：BとAの順序も、Cを最後にしている点も誤りです。Cの割当て量が最大です。
エ（C、B、A）：割当て量はCが110 Mバイト、Bが100 Mバイト、Aが90 Mバイトなので、この順序が正しいです。

よくある誤解

要求サイズが最大のときに、空き領域が最大の媒体を選ぶと考えてしまうことがあります。媒体の選択は、要求サイズではなく、その時点での空き領域で決まります。
割当て先を一度決めたら、以後も同じ媒体を使うと誤解しがちです。各要求のたびに空き領域を比較し直します。
同じ空き領域なら任意の媒体を選んでよいと思いがちですが、この問題では同点時にA、B、Cの順で選ぶ規則があります。

補足コラム

この方式では、空き領域が最大の媒体を選んで割り当てるため、割当て後も媒体間の空き領域の差が変化していきます。今回のように各媒体の容量が同じであれば、割当て済み領域を管理するだけで選択先を判断できます。

FAQ

Q. なぜ空き領域の値を具体的に計算しなくてもよいのですか？
A. 各媒体の容量が同じだからです。容量から割当て済み領域を引いた値が空き領域なので、割当て済み領域が少ない媒体ほど空き領域が大きくなります。

Q. 同点時の規則はいつ使いますか？
A. 空き領域が等しい媒体が複数ある場合に使います。初回はA、B、Cが同点なので、Aが選ばれます。

関連キーワード: 空き領域、媒体選択アルゴリズム、逐次割当て、同点時の優先順位

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

\ せっかくなら /

エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！