Алгоритмы поиска свободного блока в менеджерах памяти

ФУНДАМЕНТАЛЬНАЯ ПОСТАНОВКА ПРОБЛЕМЫ

Определение: Задача выделения блока памяти размера n из пула свободных блоков сводится к нахождению такого блока B в множестве свободных блоков F, что:

size(B) ≥ n (достаточность)
B минимизирует некоторую функцию стоимости C(B, n) (оптимальность)

Множество свободных блоков представляется как:

F = {B_i = (addr_i, size_i) | B_i свободен, 0 ≤ i < m}

где addr_i — адрес начала, size_i — размер блока.

Но, давай сначала разберемся что такое стек и куча.

1. Концептуальное разделение: Менеджер vs. Местонахождение

Память физически хранится в RAM и процессор обращается к ней по адресам. Термины "стек" (stack) и "куча" (heap) — это не физические области чипов, а логические модели организации доступа к памяти внутри виртуального адресного пространства процесса.

Стек — это модель LIFO (Last In, First Out), тесно связанная с потоком исполнения (thread). Его главная задача — хранить контекст вызовов функций: аргументы, локальные переменные, адреса возврата. Его структура предсказуема и управляется компилятором и аппаратным обеспечением (регистр указателя стека — SP/ESP/RSP).
Куча — это модель произвольного доступа (random access). Её задача — предоставлять блоки памяти, время жизни которых не привязано к вложенности вызовов функций. Ей управляет программист (через malloc/free, new/delete) или среда исполнения (сборщик мусора).

2. Почему аллокатор (менеджер памяти) оперирует понятием "куча"?

Потому что "куча" — это пул неструктурированной, свободной для распределения памяти внутри адресного пространства процесса. Аллокатор — это менеджер этого пула.

Алгоритмы, которые мы разберем чуть посже (First-Fit, Buddy System), — это именно стратегии управления этим пулом: поиск свободного куска, его разметка (сплиттинг), объединение освобождённых кусков (коалесценция), борьба с фрагментацией.

Стек же управляется по принципиально другим правилам, не требующим такого "менеджера":

Выделение: При входе в функцию компилятор вычисляет общий размер всех локальных переменных и просто сдвигает указатель стека (SP) на нужное количество байт вниз. Это одна ассемблерная инструкция (SUB). Никакого поиска свободного блока.
Освобождение: При выходе из функции указатель стека сдвигается обратно вверх (ADD или просто загрузка сохранённого значения из кадра). Никакого слияния, список свободных блоков не ведётся.
"Фрагментация" стека — это просто "дырка" между SP и концом стека, которая мгновенно исчезает, как только SP движется вверх при возврате из функций. Это не фрагментация в классическом смысле, а просто неиспользуемая в данный момент область.

У стека нет проблемы поиска свободного блока. У него есть только одна "свободная" область — та, что выше текущего SP.

3. Важное уточнение: "Владеет" — в каком смысле?

Здесь ключевая тонкость. Когда мы говорим, что "аллокатор владеет кучей", это не значит, что ОС или процесс ему её "отдали".

Уровень ОС: При запуске процесса ОС выделяет ему виртуальное адресное пространство. Часть этого пространства зарезервирована под стек(и) каждого потока. Другая большая непрерывная область (часто растущая) отводится под "кучу процесса" (например, область, из которой sbrk или mmap могут выделять память).
Уровень рантайма (аллокатора): Стандартная библиотека языка (например, glibc's malloc) "подкапывается" под ОС. При первом вызове malloc() она запрашивает у ОС большой блок памяти (например, 128KB через sbrk или mmap). Этот блок и становится её первичным пулом, её "кучей" в контексте менеджера.
Уровень программы: Когда вы вызываете malloc(100), вы обращаетесь не к ОС, а к этому менеджеру. Он ищет свободные 100 байт внутри своего пула, используя те самые алгоритмы (First-Fit, Segregated Lists). Если в его пуле нет места, он идёт к ОС за ещё одним большим блоком, чтобы расширить свой пул.

Таким образом, "куча" на уровне аллокатора — это его внутренний пул памяти, который он сам и организует. ОС же просто предоставляет ему сырые страницы виртуальной памяти по запросу.

2. КЛАССИФИКАЦИЯ СТРАТЕГИЙ ПОИСКА

2.1 First-Fit (Первый подходящий)

Суть: Свободные блоки организованы в список (чаще всего двусвязный). Метаданные (указатели next/prev) хранятся в теле свободного блока. При поиске аллокатор проходит по списку с головы до первого блока, размер которого size >= N. Этот блок изымается из списка свободных. Если size значительно больше N, выполняется сплиттинг: создается выделенный блок размера N, а остаток (новый свободный блок) вставляется обратно в список.

Псевдокод

function FIRST_FIT(F, n):
    for each B in F in address order:
        if size(B) ≥ n:
            return B
    return NULL

Но, давай вспомним что такое процесс и поток

Процесс и поток — это разные абстракции ядра ОС для исполнения кода.

Процесс

Технически — это контейнер ресурсов. У каждого процесса есть:

Собственное виртуальное адресное пространство (изолированная таблица страниц).
Таблица открытых файлов и дескрипторов (файлы, сокеты, пайпы).
Учетные данные и права доступа (UID, GID, capabilities).
Сигналы и их обработчики.
Как минимум один поток исполнения.

Ключевое: Процессы изолированы. Память одного процесса по умолчанию не видна другому (для обмена нужны механизмы IPC).

Причем, если бы не было аппаратной виртуальной памяти, то изоляция процессов в её современном понимании была бы невозможна. Тоесть, изоляция процессов фундаментально и аппаратно обеспечена виртуальной памятью.

Что такое виртуальная память?

Представьте, что физическая память (RAM) — это огромный склад с миллионами одинаковых ячеек (байтов).

Без виртуальной памяти все программы получают единый план этого склада с реальными номерами ячеек. Если одна программа скажет "положить значение в ячейку №12345", она положит его в реальную ячейку №12345. Другая программа, читая "ячейку №12345", получит это значение. Никакой изоляции.

Виртуальная память — это фундаментальная абстракция, которая заставляет каждый процесс думать, что он один владеет всей физической памятью компьютера, хотя на самом деле память разделяется между многими процессами и ОС.

Абстракция адресов:
- Процесс работает с виртуальными адресами (например, от 0x00000000 до 0xFFFFFFFF в 32-битной системе).
- Аппаратура (CPU + MMU — Memory Management Unit) транслирует эти виртуальные адреса в физические адреса реальных модулей RAM.
- У каждого процесса своя полная и независимая виртуальная адресная область. Виртуальный адрес 0x1000 в Процессе A указывает на другую физическую ячейку, чем тот же адрес 0x1000 в Процессе B.
Таблица страниц (Page Table):
- Трансляция адресов происходит через иерархические таблицы (Page Tables), уникальные для каждого процесса.
- Запись в таблице (Page Table Entry, PTE) содержит физический адрес страницы и управляющие биты (присутствует в RAM, доступна на чтение/запись и т.д.).
Страничная организация (Paging): _ Память делится на фиксированные блоки — страницы (обычно 4 KiB). - KiB — это «кибибайт» (Kibibyte). 1 KiB = 1024 байта. Это важное уточнение, потому что в контексте памяти и ОС всегда используются степени двойки, а не степени десятки - Виртуальное адресное пространство — это линейная последовательность виртуальных страниц. Физическая память — это набор физических страниц (page frames). _ Таблица страниц задает отображение: Виртуальная Страница N → Физический Кадр M.
Механизм подкачки (Swapping/Paging):
- Если физической памяти не хватает, ядро ОС может выгрузить (swap out) редко используемые страницы на диск (в специальную область раздела или файл подкачки).
- PTE такой страницы помечается "не присутствует в памяти". При попытке доступа к ней возникает исключение — page fault.
- Обработчик page fault в ядре находит нужную страницу на диске, загружает её в свободный физический кадр (возможно, выгрузив другую страницу), обновляет PTE и возобновляет выполнение процесса.

Поток

Технически — это единица планирования на CPU (CPU scheduling entity). У каждого потока есть:

Собственный регистровый контекст (значения регистров CPU, включая указатель стека SP и инструкций IP).
Собственный стек вызовов (но в рамках адресного пространства процесса).
Приоритет и состояние планировщика (running, waiting, ready).

Ключевое: Потоки одного процесса разделяют всё адресное пространство и ресурсы из списка выше. У них общая куча, общие файлы, общие глобальные переменные.

Аналогия

Представьте компьютер с виртуализацией:

Процесс — это виртуальная машина (VM). У неё своя виртуальная память, свои виртуальные диски, свои сетевые интерфейсы.
Поток — это виртуальное ядро CPU (vCPU) внутри этой VM. Несколько vCPU работают внутри одной VM, разделяя все её ресурсы.

2.2 Best-Fit (Наилучший подходящий)

function BEST_FIT(F, n):
    best = NULL
    min_waste = ∞
    for each B in F:
        if size(B) ≥ n:
            waste = size(B) - n
            if waste < min_waste:
                min_waste = waste
                best = B
    return best

Теорема о худшем случае: Best-Fit минимизирует внешнюю фрагментацию в статическом сценарии, но:

Сложность поиска: O(m)
Создает максимальное количество остаточных блоков минимального размера

2.3 Worst-Fit (Наихудший подходящий)

function WORST_FIT(F, n):
    worst = NULL
    max_size = 0
    for each B in F:
        if size(B) ≥ n and size(B) > max_size:
            max_size = size(B)
            worst = B
    return worst

Инвариант: Стремится оставлять большие свободные блоки, что теоретически уменьшает вероятность невозможности выделения для больших запросов

Чанки/Арены

1. Чанк — атомарная единица управления

Чанк — это не просто "кусок памяти". Это контейнер с метаданными, единица аллокации и освобождения.

Структура чанка (на примере dlmalloc/ptmalloc):

+----------------+ <-- Указатель, возвращаемый пользователю (mem)
| size (with     |
| flags)         |   <-- Заголовок (metadata). Скрыт от пользователя.
+----------------+ <-- Указатель, которым управляет аллокатор (chunk)
| Полезные данные|
| (пользователь- |
| ская память)   |
| ...            |
+----------------+
| size (with     |
| flags)         |   <-- Футер (только у свободных чанков)
+----------------+

Футер (Footer) в контексте менеджера памяти — это дополнительный блок метаданных, размещаемый в конце чанка (блока памяти).

Ключевые особенности:

Размер хранится в заголовке вместе с флагами (например, бит P — предыдущий чанк свободен, бит M — выделен через mmap, бит A — принадлежит не-main арене).
Выравнивание: Адрес чанка выровнен (обычно на 8/16 байт). Пользовательский указатель (mem) смещён относительно него.
Граничные теги (boundary tags): Размер хранится в начале и в конце чанка. Зачем в конце? Чтобы при освобождении, имея указатель на предыдущий чанк, можно было узнать его размер и проверить, свободен ли он — для коалесценции.
У свободного чанка поле "полезных данных" используется для хранения указателей fd (forward) и bk (backward) в двусвязный список свободных чанков соответствующего размера (бин).

2. Арена — домен памяти для параллелизма

Арена — это изолированный пул памяти (набор чанков), управляемый собственным набором структур данных (бинаризированных куч, списков).

Проблема, которую решают арены:

В традиционном malloc с одной глобальной кучей все потоки синхронизируются на одной блокировке. Поток 1 выделяет память → захватывает глобальный мьютекс → потоки 2, 3, ... ждут → contention, падение производительности.

Решение: Разделить кучу на независимые арены. Потоки, работающие с разными аренами, не мешают друг другу.

Архитектура арен (как в glibc's ptmalloc):

+---------------------+      +---------------------+
|   Главная арена     |      |   Арена 1           |
|  (Main Arena)       |      |  (Non-Main Arena)   |
|                     |      |                     |
|  +--------------+   |      |  +--------------+   |
|  | Куча (heap)  |   |      |  | Куча (heap)  |   |
|  | (sbrk/mmap)  |   |      |  |   (только    |   |
|  +--------------+   |      |  |    mmap)     |   |
|  | Бинлисты     |   |      |  +--------------+   |
|  | (bins)       |   |      |  | Бинлисты     |   |
|  +--------------+   |      |  | (bins)       |   |
|  | Мьютекс       |   |      |  +--------------+   |
|  | (lock)       |   |      |  | Мьютекс       |   |
|  +--------------+   |      |  | (lock)       |   |
+---------------------+      +---------------------+
         ^                              ^
         | (thread 1)                   | (thread 2)

Главная арена (Main Arena): Единственная, использующая sbrk() для расширения кучи. Существует всегда.
Неосновные арены (Non-Main Arenas): Создаются по мере необходимости. Каждая — это независимый регион памяти, полученный через mmap() (обычно 1MB или больше).
Каждая арена имеет:
- Свою кучу (один или несколько mmap-регионов).
- Свои бинлисты (массивы списков свободных чанков, отсортированных по размеру: fast bins, small bins, large bins, unsorted bin).
- Свой мьютекс.

Стратегия распределения потоков по аренам:

При первом выделении памяти в потоке, malloc() пытается найти свободную (незаблокированную) арену и привязать поток к ней.
Если свободных арен нет — создаётся новая.
Далее поток по возможности использует "свою" арену, минимизируя contention.
Но если в "своей" арене нет свободной памяти нужного размера, поток может украсть (steal) память из другой арены (через глобальную синхронизацию).

Это trade-off: Полная изоляция невозможна, так как приведёт к неэффективному использованию памяти (одна арена переполнена, другая пуста). Поэтому есть периодическая перебалансировка.

*в тексте могут быть ошибки