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

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

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

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

容量の等しい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となる。毎回いちばん空いている媒体が選ばれるため、使用量が均される。

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

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

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

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

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

• 仮想記憶方式において、セグメンテーション方式と比較した場合のページング方式の長所はどれか。

  正解：主記憶の外部断片化が発生しない。

  要点：固定長ページのページング方式は外部断片化が起きない

  ページング方式は主記憶を固定長のページ単位で管理するため、空き領域が「使えるが小さすぎる」細切れの形で散らばる外部断片化が起こらない。プログラムの論理的な区切りで可変長に分けるセグメンテーション方式では、割当てと解放を繰り返すうちに外部断片化が生じる。

  出典：令和6年度 秋期 高度共通_午前I試験 am1 問6（IPA）