Linux カーネルの物理メモリ割り当てに使われているバディ・システムに触れてみるために、D. Knuth The Art of Computer Programming, Vol. 1: Fundamental Algorithms p. 443 記載の Algorithm R (Buddy system reservation) と Algorithm S (Buddy system liberation) を ruby で記述してみました。 バディ・システムはフリー・リストによるメモリ管理方法のバリエーションの一つです。メモリ・アドレスに2進数を用いる計算機に向いたアルゴリズムで、2 ** m サイズの割り当てに用いる領域を2分割し、さらにそれを2分割し、と再帰的に分割していった 2 ** k (k = 0 .. m) のエクステントにして、それらのエクステントを割り当てに使うのが特