空き領域の割当てアルゴリズムとは？

空き領域の割当てアルゴリズムの意味

要求された大きさの領域を、複数ある空きのどこから切り出すかを決める規則。ファーストフィットは先頭から探して最初に見つかった空きを使い、探索が速い。ベストフィットは要求に最も近い空きを選ぶので無駄は小さいが、使いにくい細かな断片が残りやすい。ワーストフィットは空きが最大のものを選ぶため、残る断片が大きく再利用しやすく、複数の媒体に割り当てる場面では使用量が平均化される方向に働く。

空き領域の割当てアルゴリズムの具体例

容量の等しい3つの媒体A〜Cに「空きが最大のものを選ぶ」方式で90・30・40・40・70・30Mバイトを順に割り当てると、90はA、30はB、40はC、次の40はB、70はC、最後の30はBとなり、総量はA＝90、B＝100、C＝110となる。毎回いちばん空いている媒体が選ばれるため、使用量が均される。

空き領域の割当てアルゴリズムは試験でどう引っ掛けられる？

「空きが最大のものを選ぶ」＝結果として使用量も最大になる、と考えないこと。空いている媒体が優先されるので、最終的な使用量は最初に大きな要求を受けた媒体ほど少なくなることがある。また解放が起きない条件かどうかで結論が変わるので、条件文の「途中で解放されない」を見落とさない。

空き領域の割当てアルゴリズムと関連する用語

• メモリプール
• 静的メモリ割当て
• 動的メモリ確保の禁止
• メモリリーク

空き領域の割当てアルゴリズムが出た過去問

• ほとんどのプログラムの大きさがページサイズの半分以下のシステムにおいて、ページサイズを半分にしたときに予想されるものはどれか。ここで、このシステムは主記憶が不足…

  正解：ページ内の無駄な空き領域が減少するので、主記憶不足が緩和される。

  要点：ページを小さくすると内部断片化が減り主記憶を有効利用

  ページ方式では、プログラムの最後の半端な部分がページを埋めきらず、余りが使われないまま残る（内部断片化）。プログラムの大半がページサイズの半分以下という状況では、この無駄が特に大きい。ページサイズを半分にすれば1ページあたりの余りが減り、主記憶を有効に使えるようになるので、逼迫していた主記憶の不足が緩和される。

  出典：平成28年度 春期 エンベデッドシステムスペシャリスト試験 am2 問8（IPA）

• ほとんどのプログラムの大きさがページサイズの半分以下のシステムにおいて、ページサイズを半分にしたときに予想されるものはどれか。ここで、このシステムは主記憶が不足…

  正解：ページ内の無駄な空き領域が減少するので、主記憶不足が緩和される。

  要点：ページサイズ縮小は内部断片化を減らし主記憶不足を緩和

  ページ単位で割り当てるため、プログラムがページを使い切らない場合は末尾に未使用領域が残る（内部断片化）。プログラムの大きさがページサイズの半分以下なら、この無駄が特に大きい。ページサイズを半分にすればこの空き領域が減り、同じ主記憶でより多くのプログラムを収められるので、主記憶不足が緩和される。

  出典：令和1年度 春期 エンベデッドシステムスペシャリスト試験 am2 問9（IPA）

• 三つの媒体A～Cに次の条件でファイル領域を割り当てた場合、割り当てた領域の総量が大きい順に媒体を並べたものはどれか。〔条件〕(1) ファイル領域を割り当てる際の…

  正解：C, B, A

  要点：空き最大を選ぶ方式では使用量が均される方向に割り当たる

  毎回「空き領域が最大の媒体」を選ぶので、割当てのたびに使用量の少ない媒体が選ばれていく。順に追うと、90をA、30をB、40をC、次の40をB、70をC、最後の30をBに割り当てることになる。合計はA＝90、B＝100、C＝110となり、大きい順ではC、B、Aとなる。

  出典：令和3年度 秋期 エンベデッドシステムスペシャリスト試験 am2 問9（IPA）

• 可変区画方式を用いた主記憶管理において、最適適合アルゴリズムによって割り当てられる未使用領域はどれか。

  正解：十分な大きさをもつ最小の未使用領域

  要点：最適適合は要求を満たす中で最小の空き領域を選ぶ

  最適適合（ベストフィット）は、要求サイズを満たす未使用領域のうち最も小さいものを選ぶ方式である。ぴったりに近い領域を使うため大きな領域を無駄に削らずに済むが、割当て後に極めて小さな使いにくい断片が残りやすいという欠点もある。

  出典：令和6年度 秋期 エンベデッドシステムスペシャリスト試験 am2 問7（IPA）