リスト不使用バディ・アロケータ

記憶領域割り当ての一つ、 D. Knuth バディ・アロケータは、 空き区画同士を双方向リンク・リストでつないで管理します。 双方向リンクではなく、 ビット・マップで同種類のアロケータを作れないかと考えてみたこともあったのですが、 区画が最低でも 3 通りの状態をとる必要があるため、 ビット・マップでは作れないと自分の中では結論づけています。 2 ビットの配列をビット・パックしてマップにすると良いのかもしれません。

今回のアロケータは、 記憶領域ごとに 3 状態の状態変数をストレートに割り振ります。 空き (free)、 割り当て中 (used)、 他の領域長で管理中の 3 つです。 初期状態は、 一番長い領域長の 2つを空きにします。 下の図は、 横方向にメモリ区画が並んでいるものとし、 それを 2 のべき乗の長さの領域でどのように管理しているかを示したものです。 初期状態は長い空きが 2 つあるだけです。 右側にそれぞれの長さでの最初の空き領域の番号を記録しています。 空きがない長さには nil を入れることにしましょう。

初期状態

f                               f                                  0
.               .               .               .                  .
.       .       .       .       .       .       .       .          .
.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .      .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    .
................................................................   .

割り当て可能な領域は、 2 のべき乗の長さに限ります。 べき数のことを位数と呼びましょう。 長さ 1 の領域の位数はゼロ、 長さ 2 の領域の位数は 1 で、 上の例では長さ 32 の位数 5 まで扱えるものとします。

初期状態から、 位数ゼロ、 すなわち長さ 1 の領域を割り当てると、 次のように変化します。 先頭の領域が使用中 (used) に変化し、 それぞれの位数の番号 1 の領域が空き (free) になります。

.                               f                                  1
.               f               .               .                  1
.       f       .       .       .       .       .       .          1
.   f   .   .   .   .   .   .   .   .   .   .   .   .   .   .      1
. f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    1
uf..............................................................   1
^ 0 allocate(0)

続いて、 位数 1、 すなわち長さ 2 の領域を割り当てると、 位数 1 の空き領域が使用中に変化します。 この位数には他に空き領域がないので、 最初の空き領域の記録が nil になります。

.                               f                                  1
.               f               .               .                  1
.       f       .       .       .       .       .       .          1
.   f   .   .   .   .   .   .   .   .   .   .   .   .   .   .      1
. u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    .
uf..............................................................   1
  ^ 2 allocate(1)

続いて同じ長さの領域を割り当てます。 すると、 位数 2 の最初の空き領域が位数 1 による利用に変化し、 そこから領域をとってきて使用中にします。

.                               f                                  1
.               f               .               .                  1
.       f       .       .       .       .       .       .          1
.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .      .
. u u f . . . . . . . . . . . . . . . . . . . . . . . . . . . .    3
uf..............................................................   1
    ^ 4 allocate(1)

最初に割り当てたゼロの区画を開放すると、 相方の隣が空き領域なので一つにまとまって上の位数の空き領域に変化します。 位数ゼロで管理している空き領域がなくなるので、 先頭の空き領域の記録が nil になります。 位数 1 で管理している空き領域が一つ増えて、 先頭の空き領域の記録がそっちに変化します。

.                               f                                  1
.               f               .               .                  1
.       f       .       .       .       .       .       .          1
.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .      .
f u u f . . . . . . . . . . . . . . . . . . . . . . . . . . . .    0
................................................................   .
^ 0 free

Ruby によるプロトタイピングです。 Knuth のバディ・アロケータとは違い、 上の位数へ上がるときに、 アドレスを 2 で割っています。 Knuth の算法では、 アドレスは不変とし、 位数 k によるビット・シフト演算を使っていました。 ここでは位数ごとに長さが異なる割り当てマップを使うので、 アドレスを割って、 最下位ビット反転で相方を求めています。 最初の空き領域を探す find_next_spare では、 同じ番地を長い領域で管理している箇所を飛び越すことで、 探索回数を減らす工夫をしています。

# without Doubly-Linked List
class BuddyAllocator
  def initialize
    @freemap = (0 .. 5).map {|order| Array.new(1 << (6 - order), 0) }
    @spare = Array.new(6, nil)
    @freemap[5].fill(1)
    @spare[5] = 0
  end

  def allocate(k)
    j = k
    while j < @spare.size and @spare[j].nil?
      j += 1
    end
    j < @spare.size or raise "memory full"
    a = @spare[j]
    @spare[j] = find_next_spare(j, a + 1)
    while j > k
      @freemap[j][a] = 0
      j = j - 1
      a = a << 1
      b = a + 1
      @freemap[j][b] = 1
      @spare[j] = b
    end
    @freemap[j][a] = 2
    a << j
  end

  def free(a)
    k = 0
    while @freemap[k][a] != 2
      (k < @freemap.size and a.even?) or raise "invalid free address"
      a >>= 1
      k += 1
    end
    while k < @freemap.size
      b = a ^ 1
      if @freemap[k][b] != 1
        @freemap[k][a] = 1
        @spare[k] = [a, @spare[k] || a].min
        break
      elsif k == @freemap.size - 1
        @freemap[k][a] = 1
        @spare[k] = [a, b, @spare[k] || a].min
        break
      end
      @freemap[k][a] = @freemap[k][b] = 0
      @spare[k] = find_next_spare(k, @spare[k])
      a = a >> 1
      k = k + 1
    end
    nil
  end

  def find_next_spare(k, a)
    while a < @freemap[k].size
      return a if @freemap[k][a] == 1
      skip = 1
      if @freemap[k][a] == 0
        j, x = k, a
        while x.even? and j + 1 < @freemap.size
          j = j + 1
          x >>= 1
          if @freemap[j][x] != 0
            skip = 1 << (j - k)
            break
          end
        end
      end
      a += skip
    end
    nil
  end

  def report
    mark = ['.', 'f', 'u']
    (0 .. 5).reverse_each do |order|
      pad = " " * ((1 << order) - 1)
      @freemap[order].each {|x| print mark[x], pad }
      if @spare[order].nil? then print "   .\n" else printf "%4d\n", @spare[order] end
    end
  end
end

pool = BuddyAllocator.new
pool.report
puts
a0 = pool.allocate(0)
pool.report
print " " * a0, "^ ", a0, " allocate(0)\n"
puts
pool.free(a0)
pool.report
print " " * a0, "^ ", a0, " free\n"