Алгоритм двойников
Алгоритм двойников (англ. Buddy memory allocation) — алгоритм динамического распределения памяти, при котором память поделена на блоки размером и при запросе выделяется блок, размер которого максимально приближен к требуемой памяти. Согласно Дональду Кнуту, алгоритм двойников впервые был предложен Гарри Марковицем в 1963 году[1].
Алгоритм[править | править код]
- Память выделяется блоками размером
- Когда требуется выделить память, ищем блок минимального подходящего размера . Если блок найден, то используем этот блок для размещения памяти. Если блок подходящего размера не найден, то находим ближайший блок большего размера и делим его до тех пор, пока не получим блок нужного размера.
- При освобождении памяти проверяем, свободен ли соседний блок (двойник). Если свободен, то сливаем 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