アルゴリズム (全101問中32問目)
No.32
記憶領域を管理するアルゴリズムのうち，ベストフィット方式の特徴として，適切なものはどれか。
出典：平成26年春期 問5
- 空きブロック群のうち，アドレスが下位のブロックを高い頻度で使用するので，アドレスが上位の方に大きな空きブロックが残る傾向にある。
- 空きブロック群のうち，要求された大きさを満たす最小のものを割り当てるので，最終的には小さな空きブロックが多数残る傾向にある。
- 空きブロックの検索にハッシュ関数を使用しているので，高速に検索することができる。
- 空きブロックをアドレスの昇順に管理しているので，隣接する空きブロックを簡単に見つけられ，より大きな空きブロックにまとめることができる。
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
ベストフィット方式は、メモリ割り当てを制御するアルゴリズムで、空き領域の大きさ順リストを先頭から探索し、要求サイズに最も合致する空きブロックを割り当てる方式です。("最も合致する"とは要求サイズよりも大きく、割り当て後の残り領域が最も小さくなること)
最もフィットする領域を使用するのでメモリ割り当てごとに小さい空き領域が生じ、最終的には使用するのが難しいほど小さな領域が残る傾向があります。
したがって正しい記述は「イ」です。
参考までに他の空き領域割り当てを制御するアルゴリズムの特徴を紹介しておきます。
最もフィットする領域を使用するのでメモリ割り当てごとに小さい空き領域が生じ、最終的には使用するのが難しいほど小さな領域が残る傾向があります。
したがって正しい記述は「イ」です。
参考までに他の空き領域割り当てを制御するアルゴリズムの特徴を紹介しておきます。
- ファーストフィット方式
- 空きブロックをメモリの先頭から検索していき、要求サイズ以上の空きブロックが見つかった時点でそれを割り当てるアルゴリズム
- ワーストフィット方式
- ベストフィットと同様に空きブロック全体を検索後、最も大きな領域を割り当てるアルゴリズム
- ベストフィット方式では、メモリ全体から最も合致する領域を採用するので、どちらかに空きブロックが偏ることはありません。
- 正しい。
- リストを先頭から順番に探索するので、メモリサイズに比例して探索コストが掛かります。
- ベストフィット方式では、空きブロックを大きさ順リストで管理します。アドレス順リストで領域管理を行うのはファーストフィット方式です。