最適適合方式の空き領域管理
出典: 令和5年度 春期 応用情報技術者試験 午前 問5 (IPA)
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合 (best-fit) アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。
- ア 空き領域のアドレスをキーとする 2 分探索木
- イ 空き領域の大きさが小さい順の片方向連結リスト
- ウ 空き領域の大きさをキーとする 2 分探索木
- エ アドレスに対応したビットマップ
正解と解説を見る
正解: ウ
- ア: アドレスをキーにした木では、大きさの条件で探すために全ての節点を調べる必要があります。
- イ: 連結リストは先頭から順にたどるしかないので、平均の処理時間は 2 分探索木より長くなります。
- ウ: 大きさをキーにすれば、要求量以上で最小の領域を木をたどるだけで見つけられます。正しい答えです。
- エ: ビットマップでは、連続した空きを端から順に調べるので時間がかかります。
ポイント
- 最適適合 (best-fit) では、「要求量以上で最も小さい空き領域」を探します。
- 空き領域の 大きさをキー にした 2 分探索木なら、木をたどるだけでこの領域を O(log n) で見つけられます。
- 大きさの順の連結リストでは、先頭から順にたどるので平均 O(n) かかります。