| 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> |