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

Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

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

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

Примечания

[править | править код]
  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