Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

50年前に作られたメモリ管理アルゴリズム「Buddy memory allocation」

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2016/04/20 14:00

 4月ですねー、この世界に身を置いて三十数年目の春です。当時のノートを読み返すと、組み込み用途のメモリ管理ルーチンをアセンブラで書いたりしてました。黄ばんだノートの覚え書きの中から、メモリ確保/解放のスピードを重視したメモリ管理アルゴリズム:Buddy memory allocationを紹介しましょうか。

目次

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確保するので、ほぼ半分の領域が無駄になっちゃいます。


  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • επιστημη(エピステーメー)

    C++に首まで浸かったプログラマ。 Microsoft MVP, Visual C++ (2004.01~) だったり わんくま同盟でたまにセッションスピーカやったり 中国茶淹れてにわか茶人を気取ってたり、 あと Facebook とか。 著書: - STL標準講座 (監修) -...

All contents copyright © 2006-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5