Article Outline
バディシステムについて
バディシステムについて学習したため、そのまとめとしてここに整理する。
バディシステムとは
- Linuxカーネルにおけるページフレーム割当の際、メモリ断片化を解決するためのアルゴリズム。
ページフレーム
- CPU内に内蔵される「仮想アドレスから物理アドレスに変換する回路」を利用するために、RAMを一定の大きさごとに分割したもの。
メモリ断片化
- 連続したページフレームの獲得・開放が繰り返し行われると、各ページフレームの隙間に小さな空きページフレームが存在することになってしまうこと。
- 空きページが十分残っていたとしても、連続したページフレームを確保できない状態になってしまう。
バディシステムの処理 (ページフレーム獲得時)
- すべてのページフレームを1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024個のブロックに分類し、各ブロックごとに連結リストを作る
- 獲得要求があった場合、必要のなるページフレームの個数を満たすブロックを空きが見つかるまで順番に探す
- 例: 256個の連続したページフレームの獲得要求があった場合
- 256個のブロックから順番に1024個のブロックまで探す
- 例: 256個の連続したページフレームの獲得要求があった場合
- 空きが見つかった場合ページフレームを獲得し、残りのページフレームを分割して同じ大きさのブロックの連結リストに繋げる
- 例: 256個の連続したページフレームを獲得要求に対し、1024個のブロックで空きが見つかった場合
- 1024個のブロックから256個獲得し、残り768個のブロックを512個と256個に分割し、それぞれ512個と256個の連結リストに繋げる
- 例: 256個の連続したページフレームを獲得要求に対し、1024個のブロックで空きが見つかった場合
- 空きが見つからなかった場合、エラーを返す
バディシステムの処理 (開放時)
- ページフレーム解放後、条件を満たす2つのブロックがある場合、バディブロックとしてまとめる
- バディブロックとなる条件
- 2つのブロックが同じ大きさの場合
- 2つのブロックが連続している場合
- 先頭ブロックの物理アドレスが、2 * b * 2 ^ 12の倍数となっている
- 上記の手順をバディブロックが見つかる限り続ける