buddy system

这是一个很著名的算法，它的思想如下：
首先将一系列连续的page frame看作一个block，然后每次需要allocation时，都会将一个block分成一半，一半用来满足需求，另一半则是free的，kernel中用一个list，来记录所有可用block。在
linux中，这个list的名字是free_area array，数组的大小是11，即1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and 1024 contiguous page frames.合并的时候需要满足3个条件：
1.Both blocks have the same size, say b.
2.They are located in contiguous physical addresses
3.The physical address of the first page frame of the first block is a multiple of 2 x b x pow(2,12)(一个页面的大小）
free_area只将block的第一个page frame连接在一起，而且被连接的每个block的第一个page frame的结构里有个private域，用来指明此block的order,也就是数组的index=log(block's size)。up to Linux 2.6.10, the kernel used 10 arrays of flags to encode this information.所以这个private极大地简化了算法。
2009/02/03 二