Buddy Allocator — это алгоритм управления памятью, используемый в ядрах операционных систем Linux для выделения и освобождения физической памяти по запросу ядра. Этот аллокатор организует память в массив списков свободных блоков различных размеров, которые являются степенями двойки.
Про Buddy Allocator:
1. Блоки памяти могут иметь различные размеры: обычно они составляют от 2^0 (одна страница памяти) до 2^(PAGE_SHIFT + MAX_ORDER - 1), где PAGE_SHIFT обычно равен 12, т.е. размер страницы в bytes (4096 байт в архитектуре x86), а MAX_ORDER зависит от конфигурации системы и версии ядра. Типичное значение для MAX_ORDER — 11.
2. Максимальный выделяемый блок физической памяти равен 2^(PAGE_SHIFT + MAX_ORDER - 1). То есть, если PAGE_SHIFT равен 12 и MAX_ORDER равен 11, самый большой блок памяти, который может быть выделен с помощью Buddy Allocator, составляет 2^(12+11-1) байт, что равняется 2^22 байт или 4 МБ (а не 8 МБ) для одного блока. Об этом может дать разницу в MAX_ORDER или еще какие-нибудь системные ограничения.
3. Если процессу или подсистеме ядра требуется выделить память размером большим, чем максимально возможный одиночный блок, Buddy System может использовать несколько смежных блоков максимального размера, чтобы удовлетворить запрос. Это не один блок памяти, а несколько блоков, которые могут быть суммированы для получения требуемого объема.
Основной принцип работы Buddy Allocator следующий:
- Когда осуществляется запрос на выделение блока памяти определенного размера, Buddy Allocator ищет подходящий свободный блок минимально подходящего размера в соответствующем списке свободных блоков.
- Если такой блок найден, он отмечается как используемый и передается процессу/подсистеме, которая запросила память.
- Если свободного блока подходящего размера нет, более крупный блок может быть разбит на два "buddy" блока, из которых один используется для удовлетворения запроса, а другой возвращается в список свободных блоков соответствующего размера.
Алгоритм реализует эффективное перераспределение блоков памяти, минимизируя фрагментацию за счет поддержания свободных блоков в организованном виде, что позволяет быстро находить блоки нужного размера и уменьшает количество излишне занимаемых блоков памяти.