HOME/Articles/

バディシステム

Article Outline

バディシステムについて

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


バディシステムとは

  • 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の倍数となっている
  • 上記の手順をバディブロックが見つかる限り続ける