Выравнивание и разделение
Делайте блоки пригодными для использования и аккуратно организуйте их.
«Выравнивание и разделение» — бесплатный урок C Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
Почему выравнивание важно
Для каждого типа требуется определённое выравнивание: его адрес должен быть кратен некоторой степени двойки. Для double обычно требуется выравнивание по границе 8 байт.
Поскольку malloc не знает, что именно вы будете хранить, он должен возвращать указатели, выровненные для самого требовательного типа — обычно по границе 16 байт в 64-разрядных системах.
#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t); /* often 16 */Приём align_up
Округление размера вверх до следующего кратного выравниванию, являющемуся степенью двойки, — классический побитовый приём: прибавьте a - 1, затем замаскируйте младшие биты.
Это работает только когда a является степенью двойки, а именно таковы все реальные выравнивания.
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1);
}
/* align_up(13, 8) == 16, align_up(16, 8) == 16 */Проверяем работу математики
Проверим align_up с помощью рабочей программы. Она округляет несколько размеров вверх до границ 8 и 16 байт и выводит результаты.
#include <stdio.h>
#include <stddef.h>
static size_t align_up(size_t n, size_t a) {
return (n + a - 1) & ~(a - 1);
}
int main(void) {
printf("%zu\n", align_up(13, 8)); /* 16 */
printf("%zu\n", align_up(16, 8)); /* 16 */
printf("%zu\n", align_up(1, 16)); /* 16 */
printf("%zu\n", align_up(33, 16)); /* 48 */
return 0;
}Выравнивание запрошенных размеров
Внутри распределителя первым шагом для каждого запроса является округление запрошенного размера вверх до значения, соответствующего выравниванию. Это гарантирует, что следующий блок тоже начнётся с правильным выравниванием.
Байты дополнения — это внутренняя фрагментация, плата за универсальное выравнивание.
#define ALIGN 16
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
/* now find a block of this aligned size */
/* ... */
return NULL;
}Проблема повторного использования целого блока
На предыдущем уроке мы возвращали целый свободный блок даже для крошечных запросов. Свободный блок размером 4000 байт, выданный для запроса на 16 байт, расходует впустую всё остальное пространство.
Разделение делит блок на используемую часть и остаток, который остаётся свободным.
Разделение блока
Если выбранный блок намного больше необходимого, мы размещаем новый заголовок в конце запрошенной области. Оставшаяся часть становится меньшим свободным блоком в списке.
Мы разделяем блок только тогда, когда остаток достаточно велик, чтобы вместить заголовок и некоторую полезную нагрузку; иначе фрагмент бесполезен.
void split(block_t *b, size_t size) {
size_t rem = b->size - size;
if (rem < sizeof(block_t) + ALIGN) return; /* too small */
block_t *nb = (block_t *)((char *)(b + 1) + size);
nb->size = rem - sizeof(block_t);
nb->free = 1;
nb->next = b->next;
b->size = size;
b->next = nb;
}Выделяем, выравниваем, разделяем
Теперь полный путь выделения выравнивает размер, находит подходящий блок, отделяет крупный остаток и помечает блок как занятый.
Это позволяет сохранять блоки компактными и оставляет после них пригодное для использования свободное пространство.
void *my_alloc(size_t size) {
size = align_up(size, ALIGN);
block_t *b = first_fit(size);
if (!b) return NULL;
split(b, size);
b->free = 0;
return (void *)(b + 1);
}Выравнивание самого пула
Для корректной работы начальный адрес пула и размер заголовка также должны соответствовать выравниванию, чтобы каждая полезная нагрузка попадала на нужную границу.
Использование alignas для статического буфера гарантирует, что вся схема начинается с правильным выравниванием.
#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */Рабочее выровненное выделение
Эта программа выделяет память из выровненного пула и выводит остаток от деления возвращённого адреса на 16, показывая, что он всегда равен нулю, то есть адрес правильно выровнен.
#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>
static size_t align_up(size_t n, size_t a){ return (n+a-1)&~(a-1); }
alignas(16) static unsigned char pool[1024];
static size_t off = 0;
void *alloc16(size_t s){ off=align_up(off,16); if(off+s>sizeof(pool)) return NULL; void*p=&pool[off]; off+=s; return p; }
int main(void){
void *a = alloc16(1);
void *b = alloc16(20);
printf("a %% 16 = %lu\n", (unsigned long)((size_t)a % 16));
printf("b %% 16 = %lu\n", (unsigned long)((size_t)b % 16));
return 0;
}Разделение и объединение
Разделение и объединение — противоположные процессы, уравновешивающие друг друга. При выделении большие блоки делятся на меньшие, а при освобождении маленькие блоки объединяются в большие.
Вместе они позволяют одному пулу обслуживать меняющийся набор запросов разных размеров без утечки пространства и постоянной фрагментации.
От учебного примера к настоящему распределителю
Теперь у вас есть все четыре основы: источник памяти, выровненные заголовки, повторное использование через список свободных блоков с объединением и разделение. Настоящие распределители добавляют корзины классов размеров, кэши потоков и взаимодействие с OS ради скорости и масштабируемости.
Но основные идеи, которые вы здесь реализовали, лежат в основе каждой реализации malloc.
Быстрая проверка
Подумайте, зачем блоки разделяются при выделении.
Итоги
Выравнивание округляет размеры вверх с помощью побитового приёма (n + a - 1) & ~(a - 1), поэтому каждая полезная нагрузка подходит для любого типа. Разделение вырезает из слишком больших свободных блоков занятую часть и свободный остаток, а объединение при освобождении выполняет обратное действие.
Вместе эти четыре основы образуют полноценный корректный распределитель памяти.
Часто задаваемые вопросы
Урок «Выравнивание и разделение» бесплатный?
Да — полный текст урока «Выравнивание и разделение» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Выравнивание и разделение»?
Делайте блоки пригодными для использования и аккуратно организуйте их. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Выравнивание и разделение»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Как работает malloc
- Простой линейный распределитель
- Списки свободной памяти и повторное использование
- Выравнивание и разделение