バディシステムについて

バディシステムについて学習したため、そのまとめとしてここに整理する。

バディシステムとは

• Linuxカーネルにおけるページフレーム割当の際、メモリ断片化を解決するためのアルゴリズム。

ページフレーム

• CPU内に内蔵される「仮想アドレスから物理アドレスに変換する回路」を利用するために、RAMを一定の大きさごとに分割したもの。

メモリ断片化

• 連続したページフレームの獲得・開放が繰り返し行われると、各ページフレームの隙間に小さな空きページフレームが存在することになってしまうこと。
• 空きページが十分残っていたとしても、連続したページフレームを確保できない状態になってしまう。

バディシステムの処理 (ページフレーム獲得時)

• すべてのページフレームを1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024個のブロックに分類し、各ブロックごとに連結リストを作る
• 獲得要求があった場合、必要のなるページフレームの個数を満たすブロックを空きが見つかるまで順番に探す
  • 例: 256個の連続したページフレームの獲得要求があった場合
    • 256個のブロックから順番に1024個のブロックまで探す
• 空きが見つかった場合ページフレームを獲得し、残りのページフレームを分割して同じ大きさのブロックの連結リストに繋げる
  • 例: 256個の連続したページフレームを獲得要求に対し、1024個のブロックで空きが見つかった場合
    • 1024個のブロックから256個獲得し、残り768個のブロックを512個と256個に分割し、それぞれ512個と256個の連結リストに繋げる
• 空きが見つからなかった場合、エラーを返す

バディシステムの処理 (開放時)

• ページフレーム解放後、条件を満たす2つのブロックがある場合、バディブロックとしてまとめる
• バディブロックとなる条件
  • 2つのブロックが同じ大きさの場合
  • 2つのブロックが連続している場合
  • 先頭ブロックの物理アドレスが、2 * b * 2 ^ 12の倍数となっている
• 上記の手順をバディブロックが見つかる限り続ける