Buddy memory allocationの仕組み
Buddy memory allocationは、僕がまだ駆け出しのプログラマだった30年以上前に先輩に教わったもので、かなり名のあるアルゴリズムかと思っていたのですが、日本語版Wikipediaには載っていないみたいで、本家英語版で見つけました。それによりますとBuddy memory allocationが考案されたのは1963年とのこと、50年以上前に作られたアルゴリズムなんですね。
Buddy memory allocationが管理する対象は2^L個の連続したメモリ・ブロック。ブロックの大きさは任意で、これを最小単位として確保／解放が行われます。ブロック数2^LのLをlevelまたはorderと呼び、orderが10の場合2^10=1024個の連続したメモリ・ブロックを扱うことになります。1blockが1KBなら1MBのメモリ・プールです。
Buddy memory allocationが行うのはメモリ・ブロックの確保と解放すなわち：
- 確保：プログラムから要求されたブロック数をnとするとき、このnより小さくない最小の2^x個の未使用連続ブロックを確保してプログラムに返すこと
- 解放：プログラムが使用を終えたブロックを未使用状態とし、以降の確保に備えること
確保時のふるまいが特徴的です。確保するブロック数が2のベキになっています。場合によっては無駄に大きな領域が確保されることがありますが、この"縛り"のおかげで確保／解放に要する時間を小さく抑えることができます。そのカラクリを解説します。
order-4, 64KB/blockのBuddy memory allocationで説明しましょう。order-4ですからblock数は2^4=16、64KB/blockなら扱うメモリの総量は16*64=1024KBです。
（1）まず初期状態：order-4（16個）のblockを未使用状態にしておきます（□は未使用block）。
1： □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ 初期状態
（2）プログラムAが34KBのメモリ確保を要求しました。34KBなら必要なblock数は1、すなわちorder-0のblockです。この時点で管理領域にあるのはorder-4のblock1つ。これでは要求される量より大きすぎるので、これを半分に切り分けorder-3のblock2つに分割します。2つに分割されたblockの組をbuddy（相方／相棒）と呼ぶことにします。
2.1： □ □ □ □ □ □ □ □|□ □ □ □ □ □ □ □ 分割
order-3ではまだ大きい。左のblockをさらに2分割。
2.2： □ □ □ □|□ □ □ □|□ □ □ □ □ □ □ □ 分割
さらにもう一回。
2.3： □ □|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 分割
まだ大きいのでもう一回。
2.4 ： □|□|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 分割
これでようやく要求されたサイズを満たす最小のblockができました。左端のblockを使用中（■）とし、その位置（=0）をプログラムAに返します。
2.5： ■|□|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 確保（0）
（3）プログラムBが66KBの確保を要求してきました。64KB/blockですから必要なblock数は2、order-1のblockです。管理領域にはorder-1の未使用blockがあるので、これを使用中としプログラムBに返します。
3： ■|□|■ ■|□ □ □ □|□ □ □ □ □ □ □ □ 確保（2-3）
（4）さらにプログラムCが35KBの確保を要求。block数1、つまりorder-0ですね。プログラムAに貸し出したblockのbuddy（相方）が未使用なのでこれを返しましょう。
4： ■|■|■ ■|□ □ □ □|□ □ □ □ □ □ □ □ 確保（1）
（5）プログラムDが67KBを要求します。order-1のblockです。order-1のblockは全部使用中で空きがありません。未使用のorder-2のblockを分割しorder-1を2つ作ります。
5.1： ■|■|■ ■|□ □|□ □|□ □ □ □ □ □ □ □ 分割
order-1のblockが2つできたので、その一つをプログラムDに返します。
5.2： ■|■|■ ■|■ ■|□ □|□ □ □ □ □ □ □ □ 確保（4-5）
（6）プログラムBが（3）で確保したメモリを開放します。order-1のblockが1つ空きました。
6： ■|■|□ □|■ ■|□ □|□ □ □ □ □ □ □ □ 解放（2-3）
（7）プログラムDが（5）で確保したメモリを返します。order-1のblockがもう一つ空きました。
7.1： ■|■|□ □|□ □|□ □|□ □ □ □ □ □ □ □ 解放（4-5）
すると、お互いがbuddyの関係にある2つのorder-1 blockが空いたので、これを1つにまとめてorder-2にします
7.2： ■|■|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 結合（4-7）
（8）プログラムAが（2）で確保したメモリを解放します。
8： □|■|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 解放（0）
（9）プログラムCが（4）で確保したメモリを開放します。
9.1 ： □|□|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 解放（1）
order-0の空きが2つあるのでまとめます
9.2： □ □|□ □|□ □ □ □|□ □ □ □ □ □ □ □ 結合（0-1）
それによってorder-1の空きが2つできました。まとめます。
9.3： □ □ □ □|□ □ □ □|□ □ □ □ □ □ □ □ 結合（0-3）
もう一度。
9.4 ： □ □ □ □ □ □ □ □|□ □ □ □ □ □ □ □ 結合（0-7）
さらにもう一度。これで最初の状態に戻りました。
9.5： □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ 結合（0-15）
……こんなダンドリ。半分ずつに切り分け（orderを下げる）て確保し、解放時はできるだけまとめる（orderを上げる）ことを繰り返します。一度の分割／結合でblockの大きさが半分／二倍になるのですから、確保／解放に要する時間はlogNのオーダーとなりますね。
未使用領域を線型リストで管理する方法では未使用blockが数珠つなぎになるために、空き領域の検索に要する時間は分断された未使用blockの数Nに比例しますし、小さなblockの確保／解放がランダムに繰り返されると未使用blockのところどころに歯抜け（fragmenentation：分断化）が起こりやすくなります。Buddy memoru allocationだと2のベキに切り分けることで分断化が起こりにくくなります。
Buddy memory allocationは確保／解放のスピードが大きな利点ですが、最大の欠点はorderが大きなblockの確保時に無駄が大きくなりがちなことです。確保するblock数が2のベキであれば問題ないけど、例えば9blockの確保要求に対しては16block確保するので、ほぼ半分の領域が無駄になっちゃいます。
