起動するまでの長い道のり メモリ管理編(4) メモリ管理考察の巻

　前回でページング機能を有効にすることまではできた。今回はこれを活用してメモリを管理する部分を考察する。因みに、まだ考察するだけ(汗)。

メモリ管理とは

　メモリ管理とは、ぶっちゃけ以下の2点に集約される。

• 必要とされるメモリを割り当て、使えるようにする。
• 使わなくなったメモリを回収し、別の場所でまたいつか使えるようにする。

　これをいかに速く、無駄なく行うか。これがメモリ管理だ。
　メモリの割り当て・回収について、C言語を使ったことのある人なら馴染みが深いと思う。つまりmalloc/free関数だ。メモリ管理を実装するとは、malloc/freeを自分で実装するという意味だ。だから、外から見えるインターフェイスとしては極めて単純なものだ。
　しかしその中身は極めて複雑になる（汗）。メモリ管理について、いまだ人類が決定的な解決策を見出していないいくつかの問題があるのだった。（おおげさ）

断片化の問題

　プログラムやOSのカーネルが一度に要求するメモリの量はバラバラだ。凄く大きいサイズで要求されることもあれば、それこそ1バイト2バイトしか要求されない事もある。
　バラバラにメモリを要求されると、メモリもバラバラにならざるを得ない。用途別に色分けするとモザイク状になったりするだろう。そしてメモリの回収もバラバラに起きる。細かい空きメモリが点在する、いわば歯抜け状態になる。
　歯抜け状態だとどうなるか。たとえ空きメモリの合計がたくさんあっても、大きなサイズのメモリ要求に応えられなくなってしまう。なぜなら、大きなサイズのメモリ要求とは、実は、大きなサイズの連続したメモリ要求だからだ。空きメモリが合計でいくらあっても、連続していないとダメだ。
　これにどう対処するか。バラバラに回収されるメモリの断片を可能な限りまとめ、連続した領域として管理するという方法がある。また、前々回辺りに書いた気がする通り、ページングを使えばある程度バラバラなメモリもまとまったものとして扱える。
　しかし、物理的に連続しているメモリの方がアクセスが速かったり、入出力バッファ等では物理的に連続したメモリが必要になったりする。
　だから、ページングを活用する場合でも、なるべくページが連続している状態を保っておく必要がある。また、4KB未満の断片化についてページングは無力だ。

断片化の回避

　断片化の問題は、原理的に言って無くす事はできない。極端な話1バイトずつ要求されて、それがランダムに返却された場合、どうしたってメモリはひどく断片化する。だが、ある程度それを抑えることはできる。
　断片化を抑える方法として、以下のような手段がある。

• 返却されたメモリの断片を管理し、小さなサイズのメモリ要求に対して、なるべくサイズの合う断片を見つける。(通称 最小一致?)
• 連続した断片が返却されたらまとめ、大きな断片に再構成する。(通称 バディ・システム？)
• 小さなサイズのメモリについて、予め大きい領域を割り当てて断片を何個もプールしておく。メモリ要求があったら、プールされている断片を渡す。断片が返却された場合は、プールに戻す。(通称 スラブ・アロケータ？)

　通称に関しては一般的なものかどうかあまり自信がない(汗)。最小一致のアルゴリズムはあまり見かけない気がする……。断片が膨大だと一致するものの検索に時間が掛かったり、膨大な回数の要求と返却があった後だと結局大きなサイズの要求に応えられなくなるせいだろうか。
　というわけで、バディ・システムとスラブ・アロケータについて解説しようと思う。なぜなら、この2つは両方とも使うつもりだからだ。

バディ・システム

　バディ(Buddy)とは、相棒とか片割れという意味らしい。バディ・システムでは、メモリの断片をペアで考える。ペアが両方とも回収された時に大きな断片にまとめ、1段階大きなペアとして管理する。
　例えば8MBの連続したメモリがある状態で1MB要求された場合、8MBを4MBのペアに分割する。さらに4MBの断片の1つを2MBに、2MBの断片の1つを1MBに分割する。そしてこの1MBを渡す。バディ・システムには、4MBの断片・2MBの断片・1MBの断片が残る。
　この1MBが返却された場合、元からあった1MBの断片と連続した領域なので、2MBの断片にまとめられる。すると、この2MBの断片も元からある2MBと連続しているので、やはり4MBにまとめられる。すると、この4MBも……といった感じで、元の連続した8MBの断片が復活することになる。
　このバディ・システムには以下のような利点がある。

• 連続した任意のサイズのメモリを要求できる。
• それなりに高速らしい。

　欠点は以下の通り

• メモリ断片の最小サイズを大きく設定すると、無駄が多くなる。(1バイトの要求でも4KB消費してしまったり)
• メモリ・キャッシュを汚しまくる。
• 断片の先頭アドレスが必ず2のべき乗になり、その近辺にメモリアクセスが集中するので、キャッシュ効率が悪くなる。(らしい)

スラブ・アロケータ

　スラブ(slab)とは多分石版のことだ。死体置き台のことかもしれない。スラブ・アロケータは、予め大きなメモリ領域を確保しておき、それを一定サイズの断片に切り分けてプールし、メモリ要求に応じて渡していく。断片が返却されたらプールに戻す。
　スラブ・アロケータには以下のような利点がある。

• メモリ・キャッシュをあまり汚さない。
• 多分かなり高速。
• 断片の先頭アドレスが2のべき乗に集中したりしないので、キャッシュ効率が良い。
• メモリの無駄も少ない。

　欠点は以下の通り。

• 要求されるサイズを予め知っておかないといけないので、あまり汎用的に使えない。
• 連続した複数の領域を要求できない。たとえ2回連続して要求を行っても、前の領域と後の領域が連続しているとは限らない。
• メモリ断片を返却してもその時点ではプールに戻るだけで、すぐには別の用途に再利用できない。

合わせ技

　本OSでは、バディ・システムをページの管理に、スラブ・アロケータをオブジェクトの確保に使おうと思う。
　OS内部では、場合によって連続したページが必要になる。また、要求されるページ数はバラバラであまり一定していない。そのためバディ・システムが適している。
　クラス・オブジェクトについては、コンパイル時にサイズが決まっている(構造体と同じ)。それぞれのクラス・オブジェクトが連続していなくても困らないし、ページに比べて要求・確保が頻繁に行われるので、キャッシュ効率や速度も重要だ。そのためスラブ・アロケータが適している。
　スラブ・アロケータは、オブジェクトのプールを作るためにバディ・システムからページを確保する。つまり、バディ・システムとスラブ・アロケータの二段構えのメモリ管理を行う。

次回予告

　今回はコードなしだった（汗）。次回はページを管理するバディ・システムの実装に入る。かなりややこしくなる（滝汗）。

参考資料

詳解 Linuxカーネル 第3版

モダン オペレーティング システム 原書 第2版