Списки свободной памяти и повторное использование
Отслеживайте и повторно используйте блоки.
«Списки свободной памяти и повторное использование» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.
За пределами bump-распределителя
Чтобы освобождать отдельные блоки и использовать их повторно, нужны служебные данные. Список свободных блоков — это связный список доступных блоков, который распределитель просматривает перед запросом новой памяти.
Каждый блок содержит заголовок, благодаря которому распределитель может определить его размер и перейти к следующему блоку в цепочке.
Заголовок блока со ссылкой
Мы расширяем заголовок указателем next и флагом free. Вместе они превращают наш пул в список блоков, по которому можно перемещаться.
Полезная нагрузка располагается в памяти сразу после заголовка.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Инициализация одного большого свободного блока
При запуске весь пул представляет собой один огромный свободный блок. По мере выделения памяти мы разделяем его, а при освобождении помечаем блоки как доступные для повторного использования.
Головой списка является этот исходный блок, охватывающий всю область памяти.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}Поиск методом first-fit
Самая простая стратегия повторного использования — first-fit: пройти по списку и вернуть первый достаточно большой свободный блок. Это быстро и обычно оставляет маленькие блоки ближе к началу списка.
Альтернативы — best-fit (наименьший подходящий блок) и worst-fit; они жертвуют скоростью ради другого поведения фрагментации.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Выделение из свободного блока
Найдя подходящий блок, мы помечаем его как занятый и возвращаем указатель сразу после его заголовка. Пока мы передаём блок целиком; разделение появится в следующем уроке.
Возвращаемый указатель — это block + 1, поэтому заголовок скрыт от вызывающего кода.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Освобождение блока
Чтобы освободить блок, отступите от пользовательского указателя назад к его заголовку и измените флаг free. Теперь блок можно повторно использовать при следующем поиске.
Восстановление заголовка по полезной нагрузке использует тот же трюк с переходом указателя на один шаг, который мы видели ранее.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Объединение соседних свободных блоков
Одно лишь освобождение оставляет пул заполненным множеством маленьких свободных блоков. Объединение сливает освобождённый блок со следующим, если тот тоже свободен, восстанавливая крупные непрерывные области.
Это противодействует внешней фрагментации, поэтому будущие крупные запросы всё ещё можно удовлетворить.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Рабочая демонстрация списка свободных блоков
Эта полноценная программа инициализирует пул, выделяет два блока, освобождает первый, а затем повторно использует его для меньшего запроса, доказывая, что список свободных блоков работает.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}Цена поиска
При одном связном списке свободных блоков выделение имеет сложность O(n) по числу блоков. При большом количестве выделений это становится медленным.
Настоящие распределители используют раздельные списки свободных блоков (корзины по размеру) или деревья, чтобы приблизить поиск к O(1). Принцип повторного использования остаётся тем же.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Двойное освобождение и повреждение данных
Если дважды пометить блок как свободный или записать за пределами его размера, будут повреждены соседние заголовки. При следующем поиске программа перейдёт по недостоверному указателю next и завершится с ошибкой.
Поэтому ошибки памяти в C так опасны: собственные метаданные распределителя находятся непосредственно рядом с вашими данными.
Объединяем повторное использование
Рабочему распределителю со списком свободных блоков нужны инициализация, стратегия поиска подходящего блока, выделение, освобождение и объединение. Благодаря этому память循环ирует в пуле, а не растёт бесконечно.
Остаётся усовершенствовать разделение слишком больших блоков и соблюдение выравнивания — это тема заключительного урока.
Быстрая проверка
Подумайте, что не даёт списку свободных блоков сильно фрагментироваться.
Итоги
Список свободных блоков связывает блоки через заголовки, поэтому отдельные выделения можно освобождать и использовать повторно. Поиск методом first-fit находит блок, освобождение изменяет флаг, а объединение сливает соседние блоки, препятствуя фрагментации.
Линейный поиск имеет сложность O(n); промышленные распределители группируют блоки по размеру ради скорости. Далее мы добавим разделение и выравнивание.
Часто задаваемые вопросы
Урок «Списки свободной памяти и повторное использование» бесплатный?
Да — полный текст урока «Списки свободной памяти и повторное использование» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.
Чему я научусь в уроке «Списки свободной памяти и повторное использование»?
Отслеживайте и повторно используйте блоки. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать C Academy?
Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Списки свободной памяти и повторное использование»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке C Academy?
Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Как работает malloc
- Простой линейный распределитель
- Списки свободной памяти и повторное использование
- Выравнивание и разделение