Как устроен аллокатор памяти и почему свободных байтов может не хватить

Интерактивная статья ведёт от malloc и free к своему аллокатору. Сетка байтов позволяет видеть каждый запрос.

Карта разбора:
1. Простейший аллокатор выдаёт следующий участок, но не возвращает память: он не хранит границы блоков;
2. Универсальный хранит адрес и размер, а при освобождении объединяет соседние участки;
3. 6 свободных байтов не спасают, если они разбиты на два участка по 3 байта;
4. Минимальный блок в 4 байта в показанном примере снижает внешнюю фрагментацию, но при запросах по 1 байту оставляет неиспользованными 75% памяти.

Материал Memory Allocation стоит читать тем, кто хочет написать свой аллокатор. Выбирать способ распределения памяти нужно под размеры и порядок запросов программы: один алгоритм не подходит всем нагрузкам.