Алгоритм двойников

Алгоритм двойников (англ. Buddy memory allocation) — алгоритм динамического распределения памяти, при котором память поделена на блоки размером ${\displaystyle 2^{n}}$ и при запросе выделяется блок, размер которого максимально приближен к требуемой памяти. Согласно Дональду Кнуту, алгоритм двойников впервые был предложен Гарри Марковицем в 1963 году^[1].

Алгоритм

• Память выделяется блоками размером ${\displaystyle 2^{n}}$
• Когда требуется выделить память, ищем блок минимального подходящего размера ${\displaystyle 2^{x}}$. Если блок найден, то используем этот блок для размещения памяти. Если блок подходящего размера не найден, то находим ближайший блок большего размера и делим его до тех пор, пока не получим блок нужного размера.
• При освобождении памяти проверяем, свободен ли соседний блок (двойник). Если свободен, то сливаем 2 блока в блок большего размера и повторяем это до тех пор, пока у получившегося блока есть свободные двойники.

Использование

Ядро Linux использует этот алгоритм в модифицированном виде для минимизации фрагментации блоков памяти, а также ряд других алгоритмов для управления памятью внутри блоков^[2].

jemalloc — это современный аллокатор памяти, использующий, среди прочего, алгоритм двойников^[3].

См. также

• Менеджер памяти
• Динамическое распределение памяти