Аллокатор (англ. Allocator) или распределитель памяти в программировании — специализированный класс, реализующий и инкапсулирующий малозначимые (с прикладной точки зрения) детали распределения и освобождения ресурсов компьютерной памяти.

Желательная прелюдия (про segregated free lists, segregated fits)

Плюс в целом желательно, чтобы вы ознакомились с понятием аллокатора и какими-то основами этой темы (первые слайдов 10-15 из презентахи с последней практики)

Метод близнецов

Одна из версий алгоритма распределения друзей была подробно описана Дональдом Кнутом в первом томе книги «Искусство компьютерного программирования».

Используется в составе многих современных операционных систем для динамического распределения памяти в ядре системы, драйверах или в других ответственных компонентах системы, критичных к скорости работы.

Ядро линукса основано на методе двоичных близнецов (с модификациями, конечно) !

• Основная идея - segregated fits, каждый класс - степень двойки
• Всего в куче $2^m$ слов
• Держим список для блоков размером $2^k$, 0 ≤ k ≤ m
• Изначально у нас один блок размером $2^m$
• Большая и понятная картинка

Виды близнецов (доп нагрузка)

Пример

Это часть примера с вики, полностью смотреть тут

• Хотим выделять блоки размером $2^k$
• Надо найти первый доступный блок размером $2^j,$ k ≤ j ≤ m