Алгоритм выделения памяти "Buddy System"

Введение

Компьютерный алгоритм

Метод распределения памяти "Buddy" — это алгоритм распределения памяти, который разделяет память на блоки, чтобы максимально точно удовлетворить запрос на выделение памяти. Эта система использует деление памяти пополам для достижения наилучшего соответствия. Согласно Дональду Кнуту, система "Buddy" была изобретена в 1963 году Гарри Марковицем и впервые описана Кеннетом К. Ноултоном (опубликовано в 1965 году). Распределение памяти методом "Buddy" относительно просто реализовать. Оно поддерживает ограниченное, но эффективное разделение и объединение блоков памяти.

Алгоритм

Существуют различные реализации системы "приятелей" (buddy system); наиболее простым и распространенным вариантом является тот, в котором каждый блок разбивается на два меньших блока. Каждый блок памяти в этой системе имеет порядок, который представляет собой целое число в диапазоне от 0 до определенного верхнего предела. Размер блока порядка *n* пропорционален 2<sup>*n*</sup>, то есть блоки вдвое больше блоков на один порядок ниже. Использование размеров блоков, являющихся степенями двойки, упрощает вычисление адресов, поскольку все "приятели" выровнены по границам адресов памяти, которые являются степенями двойки. При разделении блока большего размера он делится на два меньших блока, и каждый из этих меньших блоков становится уникальным "приятелем" для другого. Разделенный блок может быть объединен только со своим уникальным "приятелем", после чего восстанавливается больший блок, из которого они были разделены. Изначально определяется размер наименьшего возможного блока, то есть минимального блока памяти, который может быть выделен. Если бы нижнего предела вообще не существовало (например, были бы возможны выделения размером в бит), системе потребовалось бы значительное количество памяти и вычислительных ресурсов для отслеживания выделенных и невыделенных участков памяти. Однако может быть полезен относительно низкий предел, чтобы минимизировать средние потери памяти при выделении (в отношении выделений, размер которых не кратен размеру наименьшего блока). Обычно нижний предел выбирается достаточно малым, чтобы минимизировать среднее количество потерянного пространства при выделении, но достаточно большим, чтобы избежать чрезмерных накладных расходов. Размер наименьшего блока принимается за размер блока порядка 0, таким образом, все блоки более высоких порядков выражаются как кратные двойки этого размера. Программист должен определить или написать код для получения максимально возможного порядка, который поместится в оставшееся доступное пространство памяти. Поскольку общий объем доступной памяти в данной компьютерной системе может не быть кратным двойке минимального размера блока, максимальный размер блока может не охватывать всю память системы. Например, если система имеет 2000 КБ физической памяти, а размер блока порядка 0 составляет 4 КБ, верхний предел порядка будет равен 8, поскольку блок порядка 8 (256 блоков порядка 0, 1024 КБ) – это самый большой блок, который поместится в памяти. Следовательно, невозможно выделить всю физическую память одним блоком; оставшиеся 976 КБ памяти должны быть выделены меньшими блоками.

There are various forms of the buddy system; those in which each block is subdivided into two smaller blocks are the simplest and most common variety. Every memory block in this system has an order, where the order is an integer ranging from 0 to a specified upper limit. The size of a block of order n is proportional to 2n, so that the blocks are exactly twice the size of blocks that are one order lower. Power of two block sizes make address computation simple, because all buddies are aligned on memory address boundaries that are powers of two. When a larger block is split, it is divided into two smaller blocks, and each smaller block becomes a unique buddy to the other. A split block can only be merged with its unique buddy block, which then reforms the larger block they were split from. Starting off, the size of the smallest possible block is determined, i. e. the smallest memory block that can be allocated. If no lower limit existed at all (e. g., bit sized allocations were possible), there would be a lot of memory and computational overhead for the system to keep track of which parts of the memory are allocated and unallocated. However, a rather low limit may be desirable, so that the average memory waste per allocation (concerning allocations that are, in size, not multiples of the smallest block) is minimized. Typically the lower limit would be small enough to minimize the average wasted space per allocation, but large enough to avoid excessive overhead. The smallest block size is then taken as the size of an order 0 block, so that all higher orders are expressed as power of two multiples of this size. The programmer then has to decide on, or to write code to obtain, the highest possible order that can fit in the remaining available memory space. Since the total available memory in a given computer system may not be a power of two multiple of the minimum block size, the largest block size may not span the entire memory of the system. For instance, if the system had 2000 K of physical memory and the order 0 block size was 4 K, the upper limit on the order would be 8, since an order 8 block (256 order 0 blocks, 1024 K) is the biggest block that will fit in memory. Consequently, it is impossible to allocate the entire physical memory in a single chunk; the remaining 976 K of memory would have to be allocated in smaller blocks.

Реализация и эффективность

По сравнению с другими более простыми методами, такими как динамическое выделение памяти, система памяти "приятелей" характеризуется небольшим объемом внешней фрагментации и позволяет проводить компактизацию памяти с небольшими накладными расходами. Метод освобождения памяти "приятелем" выполняется быстро, при этом максимальное количество необходимых компактизаций равно O(наивысший порядок) = O(log2(общий размер памяти)). Как правило, система выделения памяти "приятелями" реализуется с использованием двоичного дерева для представления занятых или свободных блоков памяти. Адрес "приятеля" блока равен результату побитовой операции исключающего ИЛИ (XOR) между адресом блока и его размером. Однако проблема внутренней фрагментации все еще существует – память расходуется из-за того, что запрошенный объем памяти немного превышает размер малого блока, но значительно меньше размера большого блока. В силу особенностей работы метода выделения памяти "приятелями", программе, запрашивающей 66 КБ памяти, будет выделено 128 КБ, что приведет к потере 62 КБ памяти. Эту проблему можно решить с помощью slab-аллокации, которая может быть реализована поверх более грубого аллокатора "приятелей" для обеспечения более точного выделения памяти. Одна из версий алгоритма выделения памяти "приятелями" была подробно описана Дональдом Кнутом в первом томе "Искусства программирования". Ядро Linux также использует систему "приятелей" с дальнейшими модификациями для минимизации внешней фрагментации, а также различные другие аллокаторы для управления памятью внутри блоков. jemalloc – это современный аллокатор памяти, который, среди прочего, использует метод "приятелей".