ベストフィット方式は、要求量以上の空き領域のうち、最小の領域を選ぶメモリ割当て方式です。今回の割当てで生じる残りを小さくする方針ですが、将来の要求まで含めて常に最適とは限りません。
選ぶ手順
- 要求量を収容できる空き領域を候補にする。
- 候補の中で最小の領域を選ぶ。
- 必要量を割り当て、分割できる残りを空き領域として管理する。
要求量より小さい領域は、サイズが近くても選べません。同じサイズの候補が複数ある場合は、問題文の選択規則に従います。
3方式を具体例で比較
空き領域を調べる順が100・500・200・300KBで、180KBを一度だけ要求するとします。管理情報やアラインメントのための領域は無視し、残りを分割できる単純モデルです。
| 方式 | 選び方 | 選ぶ領域 | 選んだ領域に残る空き |
|---|---|---|---|
| ファーストフィット | 要求量以上の最初の領域 | 500KB | 320KB |
| ベストフィット | 要求量以上の最小の領域 | 200KB | 20KB |
| ワーストフィット | 要求量以上の最大の領域 | 500KB | 320KB |
この例ではファーストフィットとワーストフィットの結果が同じですが、選択規則が同じという意味ではありません。ファーストフィットは調べる順序に依存します。
外部断片化との関係
ベストフィットでは小さな残りが生まれ、後の要求に使いにくい断片になることがあります。空き容量の合計が十分でも、必要な連続領域がなければ割り当てられない状態が外部断片化です。
例えば互いに離れた空き領域が40KBと60KBなら、合計100KBでも連続した80KBの要求を満たせません。隣接した領域なら、解放時の結合でまとめられる場合があります。
探索コストと実装の違い
単純な未整列の空きリストでは、最小候補を見つけるために全体を調べることがあります。サイズ別の管理構造などを使う実装もあるため、常に全領域を走査する、とは限りません。
割当て要求の大きさや順番、解放の仕方で結果が変わります。「ベスト」という名前だけで、断片化・速度・全体の利用効率が必ず最良と判断しないようにしましょう。
確認問題：空き80・120・200KB、要求100KBなら？
120KBを選びます。80KBは要求を満たさず、200KBより120KBの方が小さい候補です。分割できるモデルなら20KBが残ります。
noteでメモリ管理の学習を広げる
空き領域の選び方を理解したら、仮想記憶教材でアドレス変換やページ置換など、別のメモリ管理の仕組みも学べます。ベストフィットは空き領域の割当て方で、ページを追い出す置換方式とは区別してください。
コメント