Rev 77 | Rev 81 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 77 | Rev 79 | ||
|---|---|---|---|
| Line 97... | Line 97... | ||
| 97 | 97 | ||
| 98 | <title>Buddy allocator</title> |
98 | <title>Buddy allocator</title> |
| 99 | 99 | ||
| 100 | <para>In the buddy system, the memory is broken down into power-of-two |
100 | <para>In the buddy system, the memory is broken down into power-of-two |
| 101 | sized naturally aligned blocks. These blocks are organized in an array |
101 | sized naturally aligned blocks. These blocks are organized in an array |
| 102 | of lists, in which the list with index i contains all unallocated blocks |
102 | of lists, in which the list with index <emphasis>i</emphasis> contains all unallocated blocks |
| 103 | of size <mathphrase>2<superscript>i</superscript></mathphrase>. The |
103 | of size <emphasis>2<superscript>i</superscript></emphasis>. The |
| 104 | index i is called the order of block. Should there be two adjacent |
104 | index <emphasis>i</emphasis> is called the order of block. Should there be two adjacent |
| 105 | equally sized blocks in the list i<mathphrase />(i.e. buddies), the |
105 | equally sized blocks in the list <emphasis>i</emphasis> (i.e. buddies), the |
| 106 | buddy allocator would coalesce them and put the resulting block in list |
106 | buddy allocator would coalesce them and put the resulting block in list |
| 107 | <mathphrase>i + 1</mathphrase>, provided that the resulting block would |
107 | <emphasis>i + 1</emphasis>, provided that the resulting block would |
| 108 | be naturally aligned. Similarily, when the allocator is asked to |
108 | be naturally aligned. Similarily, when the allocator is asked to |
| 109 | allocate a block of size |
109 | allocate a block of size |
| 110 | <mathphrase>2<superscript>i</superscript></mathphrase>, it first tries |
110 | <emphasis>2<superscript>i</superscript></emphasis>, it first tries |
| 111 | to satisfy the request from the list with index i. If the request cannot |
111 | to satisfy the request from the list with index <emphasis>i</emphasis>. If the request cannot |
| 112 | be satisfied (i.e. the list i is empty), the buddy allocator will try to |
112 | be satisfied (i.e. the list <emphasis>i</emphasis> is empty), the buddy allocator will try to |
| 113 | allocate and split a larger block from the list with index i + 1. Both |
113 | allocate and split a larger block from the list with index <emphasis>i + 1</emphasis>. Both |
| 114 | of these algorithms are recursive. The recursion ends either when there |
114 | of these algorithms are recursive. The recursion ends either when there |
| 115 | are no blocks to coalesce in the former case or when there are no blocks |
115 | are no blocks to coalesce in the former case or when there are no blocks |
| 116 | that can be split in the latter case.</para> |
116 | that can be split in the latter case.</para> |
| 117 | 117 | ||
| 118 | <para>This approach greatly reduces external fragmentation of memory and |
118 | <para>This approach greatly reduces external fragmentation of memory and |