Алгоритм двойников (Glikjnmb ;fkwuntkf)

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

Алгоритм

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

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

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

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

См. также

Примечания

↑ Kenneth C. Knowlton. A Fast storage allocator. Communications of the ACM 8(10):623–625, Oct 1965. also Kenneth C Knowlton. A programmer's description of L6. Communications of the ACM, 9(8):616–625, Aug. 1966
↑ Mauerer, Wolfgang (October 2008). Professional Linux Kernel Architecture. Wrox Press. ISBN 978-0-470-34343-2.
↑ Evans, Jason (16 April 2006), A Scalable Concurrent malloc(3) Implementation for FreeBSD (PDF) Архивная копия от 4 сентября 2011 на Wayback Machine, pp. 4–5

[1] Kenneth C. Knowlton. A Fast storage allocator. Communications of the ACM 8(10):623–625, Oct 1965. also Kenneth C Knowlton. A programmer's description of L6. Communications of the ACM, 9(8):616–625, Aug. 1966

[2] Mauerer, Wolfgang (October 2008). Professional Linux Kernel Architecture. Wrox Press. ISBN 978-0-470-34343-2.

[3] Evans, Jason (16 April 2006), A Scalable Concurrent malloc(3) Implementation for FreeBSD (PDF) Архивная копия от 4 сентября 2011 на Wayback Machine, pp. 4–5

[1]

[2]

[3]