99,18 → 99,18 |
|
<para>In the buddy system, the memory is broken down into power-of-two |
sized naturally aligned blocks. These blocks are organized in an array |
of lists, in which the list with index i contains all unallocated blocks |
of size <mathphrase>2<superscript>i</superscript></mathphrase>. The |
index i is called the order of block. Should there be two adjacent |
equally sized blocks in the list i<mathphrase />(i.e. buddies), the |
of lists, in which the list with index <emphasis>i</emphasis> contains all unallocated blocks |
of size <emphasis>2<superscript>i</superscript></emphasis>. The |
index <emphasis>i</emphasis> is called the order of block. Should there be two adjacent |
equally sized blocks in the list <emphasis>i</emphasis> (i.e. buddies), the |
buddy allocator would coalesce them and put the resulting block in list |
<mathphrase>i + 1</mathphrase>, provided that the resulting block would |
<emphasis>i + 1</emphasis>, provided that the resulting block would |
be naturally aligned. Similarily, when the allocator is asked to |
allocate a block of size |
<mathphrase>2<superscript>i</superscript></mathphrase>, it first tries |
to satisfy the request from the list with index i. If the request cannot |
be satisfied (i.e. the list i is empty), the buddy allocator will try to |
allocate and split a larger block from the list with index i + 1. Both |
<emphasis>2<superscript>i</superscript></emphasis>, it first tries |
to satisfy the request from the list with index <emphasis>i</emphasis>. If the request cannot |
be satisfied (i.e. the list <emphasis>i</emphasis> is empty), the buddy allocator will try to |
allocate and split a larger block from the list with index <emphasis>i + 1</emphasis>. Both |
of these algorithms are recursive. The recursion ends either when there |
are no blocks to coalesce in the former case or when there are no blocks |
that can be split in the latter case.</para> |