--- title: "Управление свободной памятью" description: "Когда вы в Go пишете make([]byte, 100) (и значение убегает в кучу) или в C вызываете malloc(100), кто-то должен найти в куче свободные 100 байт, отдать их вам, а потом, когда они…" canonical: https://graphlms.ru/os/book/free-space course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Управление свободной памятью > Источник: https://graphlms.ru/os/book/free-space — курс «Операционные системы», GraphLMS. ## Зачем вообще что-то «управлять» Когда вы в Go пишете `make([]byte, 100)` (и значение убегает в кучу) или в C вызываете `malloc(100)`, кто-то должен найти в куче свободные 100 байт, отдать их вам, а потом, когда они станут не нужны, принять обратно. Этот «кто-то» — **аллокатор памяти**. В C это код библиотеки (например, glibc), в Go — часть рантайма. Ядро ОС в этом почти не участвует: как мы видели в главе [API памяти](/os/book/memory-api), аллокатор берёт у ядра память большими кусками через `brk` или `mmap` и дальше распоряжается ею сам. Работа аллокатора похожа на работу администратора гостиницы, где номера можно нарезать произвольного размера. Он ведёт журнал свободных мест, по запросу находит подходящее и записывает, что оно занято, а когда гость уезжает (`free`), возвращает номер в журнал. Главная трудность — **фрагментация**: свободного места в сумме много, но оно раскидано мелкими кусками, и большой запрос разместить некуда. В гостинице свободны номера 1, 3, 5 и 7, но группе, которой нужны четыре соседних номера, поселиться негде. Эта глава — про то, как аллокатор ведёт учёт свободного места и принимает решения. Тесно связана с двумя соседними: - В главе [API памяти, стек vs куча](/os/book/memory-api) мы разобрали, *кто и когда* зовёт `malloc`/`free` и почему куча — это «ручной» режим. Здесь — *что происходит внутри* `malloc`. - В главе [Сегментация и фрагментация](/os/book/segmentation) фрагментация возникала на уровне физической памяти и сегментов. Здесь та же беда, но внутри одной кучи процесса, и та же задача: куда положить новый кусок. ## Free list: журнал свободных кусков Аллокатор хранит список свободных кусков памяти — **free list** (список свободного). Это связный список: каждый свободный кусок содержит свой размер и указатель на следующий свободный кусок. Сам список живёт *прямо внутри* свободной памяти — ведь она всё равно никем не используется, почему бы не записать туда служебные данные. Представим кучу размером 30 байт. Заняты байты 10–19 (там лежит чей-то объект), а свободны 0–9 и 20–29. Free list выглядит так: ```text куча (30 байт), адреса 0..29 ┌──────────┬──────────────┬──────────┐ │ свободно │ ЗАНЯТО │ свободно │ │ 0..9 │ 10..19 │ 20..29 │ └──────────┴──────────────┴──────────┘ ▲ ▲ │ │ head ─┘ │ │ size=10 │ size=10 │ next ───────────────────┘ │ next = NULL └─► [блок A] [блок B] free list: head → A(addr=0,len=10) → B(addr=20,len=10) → NULL ``` Что здесь нарисовано: куча на 30 байт, посередине занятый кусок, а два свободных куска связаны в цепочку. `head` — точка входа аллокатора в список. Когда придёт запрос «дай N байт», аллокатор пойдёт по этой цепочке и будет искать подходящий кусок. ## Заголовки блоков: где спрятан размер Тут возникает хитрый вопрос. Вы вызываете `free(ptr)`, передавая только указатель. Откуда аллокатор узнает, *сколько* байт освобождать? Размер вы не передаёте. Ответ: аллокатор хранит размер сам — в **заголовке блока** (header), расположенном чуть *перед* тем указателем, который он вам вернул. Когда вы просите N байт, аллокатор на самом деле отрезает `N + размер_заголовка`, в начале пишет заголовок, а возвращает указатель уже *после* заголовка. ```text что выделил аллокатор при malloc(20): ┌────────────────────┬───────────────────────────────┐ │ HEADER (напр.16) │ ваши данные (20 байт) │ │ size=20 │ │ │ magic=0x1234567 │ <─ ptr, который вы получили │ └────────────────────┴───────────────────────────────┘ ▲ ▲ │ │ ptr-16 ptr (free(ptr) читает ptr-16, находит size и magic) ``` Что здесь нарисовано: реальный блок состоит из заголовка и пользовательских данных. `free(ptr)` просто отступает назад на размер заголовка, читает оттуда размер и кладёт весь блок (header + данные) обратно в free list. `magic` — это контрольное число. Если при `free` оно не совпало, значит, программа испортила память до начала блока (классический buffer overflow) или передала не тот указатель. Так аллокаторы ловят порчу кучи. Вывод: в аллокаторе с заголовками каждая аллокация стоит дороже, чем кажется. Просите 20 байт, а тратится 20 + заголовок (часто 8–16 байт) + выравнивание. Миллион мелких `malloc(8)` может потратить на заголовки больше памяти, чем на данные. (Ниже увидим, что аллокаторы с классами размеров, включая аллокатор Go, у мелких объектов заголовков не хранят и узнают размер иначе.) ## Splitting: отрезаем кусок от большого Что если в free list лежит кусок на 20 байт, а просят всего 1 байт? Если отдать весь кусок, 19 байт пропадут. Аллокатор делает **splitting** (расщепление): отрезает от большого блока ровно нужный кусочек, а остаток оставляет в списке. ```text ДО splitting — просим 4 байта, в списке два куска по 10 (заголовки в этом примере не учитываем, чтобы не загромождать числа): head → [A: addr=0, len=10] → [B: addr=20, len=10] → NULL аллокатор берёт, скажем, кусок B, режет его: ┌─────────────────────────────────────────┐ │ B был: addr 20 ......... 29 (len=10) │ │ режем: [20..23]=отдаём [24..29]=остаток │ └─────────────────────────────────────────┘ ПОСЛЕ splitting: head → [A: addr=0, len=10] → [B': addr=24, len=6] → NULL ▲ остаток в списке а адреса 20..23 ушли пользователю. ``` Что здесь нарисовано: из свободного куска на 10 байт отрезали 4 байта пользователю, а 6 байт «обрезок» остались в free list под новым адресом. Так список не теряет память, но кусков становится больше и они мельче — зародыш фрагментации. ## Coalescing: склеиваем соседей Обратная операция. Освобождаешь кусок, а рядом в куче уже лежит свободный сосед. Если просто кинуть освобождённый блок в список, получится два мелких соседних свободных куска — и большой запрос между ними не влезет, хотя физически место смежное. Поэтому при `free` аллокатор проверяет соседей и **coalescing** (склеивает) смежные свободные куски в один большой. ```text ДО coalescing — освободили средний блок: ┌──────────┬──────────┬──────────┐ │ свободно │свободно→ │ свободно │ │ len=10 │ len=10 │ len=10 │ └──────────┴──────────┴──────────┘ free list: 3 отдельных куска по 10 (макс. запрос = 10!) ПОСЛЕ coalescing — три соседа смежны, склеиваем: ┌──────────────────────────────────┐ │ свободно len=30 │ └──────────────────────────────────┘ free list: 1 кусок на 30 (теперь влезает запрос до 30) ``` Что здесь нарисовано: три смежных свободных куска по 10 байт сливаются в один на 30. До склейки мы не могли выдать даже 11 байт подряд, после — можем выдать до 30. Это лечит **внешнюю фрагментацию**. ## Внутренняя vs внешняя фрагментация Это два разных вида потерь, их часто путают, а на собеседовании любят спросить разницу. **Внешняя фрагментация (external)** — свободная память есть, но разбита на мелкие несмежные куски, и большой непрерывный запрос разместить негде. Это та самая «гостиница с разбросанными пустыми номерами». Лечится склейкой (coalescing) и удачным выбором куска. **Внутренняя фрагментация (internal)** — аллокатор выдал больше, чем просили, и лишнее внутри блока простаивает. Например, аллокатор работает блоками фиксированного размера 16 байт, а вы попросили 9: 7 байт внутри блока пропадут. Сюда же относятся накладные расходы на заголовки и выравнивание. ```text ВНЕШНЯЯ: место есть (4+4=8 свободно), но не подряд [занято][своб 4][занято][своб 4] <- запрос на 6 не влезает ВНУТРЕННЯЯ: выдали блок 16 под запрос 9 ┌────────────────────────────────┐ │ данные(9) │ ПРОСТОЙ(7) впустую │ └────────────────────────────────┘ ``` | Вид фрагментации | Где теряется | Причина | Чем лечат | |------------------|--------------|---------|-----------| | Внешняя | между блоками | мелкие несмежные дыры | coalescing, удачный выбор куска, компактизация | | Внутренняя | внутри блока | округление размера, заголовки, выравнивание | классы размеров поближе к запросам, мелкие заголовки | ## Стратегии выбора: first / best / worst fit Когда в free list несколько подходящих кусков, какой взять? Это и есть **стратегия размещения**. Разберём на одном примере. В списке есть куски: **10, 30, 20** (в порядке цепочки). Приходит запрос на **15** байт. ```text free list: head → [10] → [30] → [20] → NULL запрос: 15 FIRST FIT — берём первый, куда влезает: 10? нет. 30? да! → режем 30 на (15 отдаём)+(15 остаток) результат: head → [10] → [15] → [20] плюс: быстро (не сканируем весь список) минус: засоряет начало списка мелкими обрезками BEST FIT — сканируем ВЕСЬ список, берём самый маленький подходящий: подходят 30 и 20; меньший — 20 → режем 20 на (15)+(5) результат: head → [10] → [30] → [5] плюс: оставляет крупные куски целыми, малый остаток минус: медленно (полный обход), плодит крошечные обрезки (тут 5) WORST FIT — берём самый БОЛЬШОЙ кусок: самый большой — 30 → режем на (15)+(15) результат: head → [10] → [15] → [20] идея: остаток будет крупным и пригодным. на практике — худший: и список сканирует целиком, и крупные куски быстро мельчают ``` Что здесь нарисовано: один и тот же запрос три стратегии обслуживают по-разному и оставляют разный «мусор». First fit жертвует качеством ради скорости; best fit — наоборот; worst fit обычно проигрывает обоим. | Стратегия | Что выбирает | Плюс | Минус | |-----------|--------------|------|-------| | First fit | первый подходящий | быстро, не обходит весь список | мелкие обрезки копятся в начале | | Best fit | наименьший подходящий | бережёт крупные блоки | полный обход, плодит крошечные остатки | | Worst fit | наибольший кусок | (теоретически) крупный остаток | полный обход, на практике хуже всех | | Next fit | первый подходящий, но с места прошлого поиска | равномернее, быстро | как first, но без скоса в начало | На практике чистый best/worst fit почти не используют — слишком дорого сканировать список на каждый `malloc`. Реальные аллокаторы идут другим путём. ## Buddy-аллокатор: как ядро раздаёт страницы Есть приём, который делает склейку почти бесплатной. **Buddy-аллокатор** (buddy — «приятель») работает только с блоками размером в степень двойки. Именно так ядро Linux раздаёт физические страницы: блоками по 1, 2, 4, …, 1024 страницы (4 КБ … 4 МБ). Выделение. Пусть есть свободный блок 64 КБ, а просят 7 КБ. Запрос округляется до ближайшей степени двойки, 8 КБ. Блок делится пополам, пока половина ещё вмещает запрос: ```text 64 КБ ├── 32 КБ ├── 32 КБ (свободен) │ ├── 16 КБ │ │ │ ├── 8 КБ ← отдали │ │ │ └── 8 КБ (свободен) │ │ └── 16 КБ (свободен) │ Внутренняя фрагментация: 8 − 7 = 1 КБ ``` Две половины одного деления называются **приятелями** (buddies). Свободные блоки каждого размера лежат в своём списке. Освобождение. Когда блок освобождают, аллокатор проверяет, свободен ли его приятель. Если да, они склеиваются в блок вдвое больше, и проверка повторяется уровнем выше. Адрес приятеля вычисляется одной операцией: смещение блока XOR его размер. Блок 8 КБ со смещением 8 КБ (`0x2000`) имеет приятеля со смещением `0x2000 XOR 0x2000 = 0x0000`. Никакого поиска соседей по списку. Плата за простоту — внутренняя фрагментация от округления до степени двойки: запрос на 33 КБ получит 64 КБ. Поэтому buddy используют там, где запросы и так кратны странице. На Linux состояние buddy-аллокатора видно в `/proc/buddyinfo`: сколько свободных блоков каждого размера в каждой зоне памяти. Если блоков больших размеров почти нет, физическая память фрагментирована, и выделение, например, huge pages на 2 МБ (см. [TLB](/os/book/tlb)) может не удаться, хотя свободной памяти в сумме много. ## Как это устроено в реальных аллокаторах Один глобальный free list с перебором медленный и плохо масштабируется на многих ядрах: все потоки ждут одну блокировку. Промышленные аллокаторы вроде **tcmalloc** (Google) и **jemalloc** (вырос из FreeBSD, долго развивался в Facebook) используют три приёма. **Классы размеров** (size classes). Вместо «кусок любого размера» память делится на фиксированные классы: 8, 16, 24, 32, 48, 64, … байт. Запрос округляется вверх до ближайшего класса. Для каждого класса заводят страницы, нарезанные на одинаковые ячейки, и свой список свободных ячеек. Выделение — «снять первую ячейку из списка нужного класса», без перебора и без splitting. Заголовок с размером у каждого объекта не нужен: размер известен по странице, на которой лежит объект. Цена — внутренняя фрагментация от округления. **Локальные кэши потоков.** У каждого потока (в Go — у каждого `P`, логического процессора рантайма из главы [планирование на многоядерных](/os/book/multiprocessor-scheduling)) свой запас свободных ячеек. Большинство выделений обслуживается без блокировок. ```text tcmalloc/jemalloc, упрощённо: поток 1 ─► [локальный кэш: списки по классам 8/16/32/...] поток 2 ─► [локальный кэш: ...] пусто? взять пачку из ↓ ┌──────────────────────────┐ │ центральный пул (общий) │ └────────────┬─────────────┘ нет страниц? попросить у ↓ ┌──────────────────────────┐ │ ОС: mmap / brk │ └──────────────────────────┘ ``` Быстрый путь — локальный кэш потока, без блокировок. Если там пусто, поток берёт пачку ячеек из общего пула. Если и там мало, аллокатор просит у ОС новые страницы. **Slab в ядре.** Ядро Linux постоянно создаёт и удаляет объекты одних и тех же типов: `task_struct` для процессов, inode для файлов, структуры сокетов. Slab-аллокатор держит для каждого типа заранее нарезанные страницы с ячейками ровно под этот объект. Это те же классы размеров, только под конкретные типы. В современных ядрах реализация называется SLUB; статистика по кэшам видна в `/proc/slabinfo` и утилите `slabtop`. ## Связь с Go Аллокатор Go устроен как tcmalloc. У него 67 классов размеров для объектов до 32 КБ, локальный кэш на каждый `P` (`mcache`), центральные списки по классам (`mcentral`) и куча страниц (`mheap`), которую рантайм получает у ОС через `mmap`. Объекты больше 32 КБ выделяются сразу целыми страницами. Когда escape analysis (см. [API памяти](/os/book/memory-api)) решает, что объект уходит в кучу, его размер округляется до класса. Классы у Go идут так: 8, 16, 24, 32, 48, 64, 80, 96, … Отсюда практические следствия: - **Размер имеет значение.** Структура на 33 байта займёт ячейку класса 48: 15 байт внутренней фрагментации на объект. Если таких объектов миллионы, иногда стоит переупорядочить поля структуры, чтобы уменьшить выравнивание и попасть в класс поменьше. - **Мелкие частые аллокации дороги** не столько из-за выделения, сколько из-за сборщика мусора: больше объектов — чаще и дольше сборки. Отсюда `sync.Pool` для переиспользования буферов и `make([]T, 0, n)` вместо роста через `append`. - **RSS не падает сразу после освобождения объектов.** Освобождённые ячейки возвращаются в списки аллокатора, а ОС память отдаётся позже и целыми страницами (рантайм делает это в фоне). Страница, на которой остался хотя бы один живой объект, не возвращается. Подробнее про RSS — в главе [память в проде](/os/book/memory-cloud). > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/free-space ## Частые ошибки - Считать, что склейка (coalescing) соединяет любые свободные куски. Склеить можно только **смежные** по адресам. - Путать splitting с фрагментацией. Splitting — способ не терять остаток; мелкие остатки, которые никому не подходят, — уже внешняя фрагментация. - Думать, что `free` или освобождение объекта сборщиком мусора возвращает память ОС. Обычно память возвращается в аллокатор и переиспользуется процессом. ## Проверьте себя 1. Free list: куски 12, 7, 25 (в этом порядке). Запрос на 6. Какой кусок возьмут first fit, best fit и worst fit? Что останется в списке после best fit? 2. Аллокатор с заголовком 16 байт. Сколько байт реально уйдёт на `malloc(20)`, если блоки выравниваются по 16 байт? 3. Buddy-аллокатор, свободен блок 128 КБ, запрос на 20 КБ. Какой блок отдадут и сколько будет внутренней фрагментации? 4. Блок 16 КБ со смещением 48 КБ освобождается. По какому смещению лежит его приятель? Ответы. (1) First fit — 12, best fit — 7, worst fit — 25. После best fit: 12, 1, 25 (от 7 отрезали 6, остался 1). (2) 20 + 16 = 36, с выравниванием по 16 — 48 байт. (3) Блок 32 КБ (128 → 64 → 32), фрагментация 12 КБ. (4) 48 КБ XOR 16 КБ = 32 КБ: `0xC000 XOR 0x4000 = 0x8000`. ## Что спрашивают на собесе - **В чём разница между внутренней и внешней фрагментацией?** Внешняя — свободное место разбито на несмежные куски, большой запрос не влезает. Внутренняя — выдали больше, чем просили (округление до класса, заголовок, выравнивание), и лишнее простаивает внутри блока. - **Как `free(ptr)` узнаёт размер освобождаемого блока, если ему дали только указатель?** В классическом аллокаторе — из заголовка перед `ptr` (там же magic для проверки порчи). В аллокаторах с классами размеров — по странице, на которой лежит объект: все ячейки на ней одного размера. - **Что такое splitting и coalescing и зачем они нужны?** Splitting режет большой свободный кусок под мелкий запрос (чтобы не терять остаток). Coalescing склеивает смежные свободные куски в один большой (лечит внешнюю фрагментацию). - **Сравните first fit, best fit, worst fit.** First — первый подходящий, быстро, но засоряет начало списка. Best — наименьший подходящий, бережёт крупные блоки, но медленный и плодит крошечные обрезки. Worst — наибольший, на практике худший. - **Почему промышленные аллокаторы (tcmalloc/jemalloc/аллокатор Go) используют size classes и per-thread кэши?** Классы размеров убирают поиск и splitting (выделение за O(1)), per-thread кэши убирают борьбу за блокировку на каждом `malloc` — это критично для многопоточности. - **Почему миллион мелких аллокаций — это дорого?** Накладные расходы на заголовки и выравнивание, рост внутренней фрагментации, давление на GC, потеря локальности кэша процессора. - **Как работает buddy-аллокатор и где он используется?** Блоки степеней двойки, деление пополам при выделении, склейка с «приятелем» (адрес через XOR) при освобождении; так ядро Linux раздаёт физические страницы. ## Вопросы для самопроверки **Квиз «Управление свободной памятью»** 1. Чем внешняя фрагментация отличается от внутренней? - Внешняя — свободное место разбито на несмежные куски; внутренняя — выдали больше, чем просили, и лишнее простаивает внутри блока (верно) - Это два названия одного и того же явления - Внешняя бывает только в ядре, внутренняя только в user space - Внешняя — потери внутри блока, внутренняя — между блоками - Пояснение: Внешняя — свободная память есть, но раскидана мелкими несмежными кусками, и большой непрерывный запрос не влезает. Внутренняя — внутри выданного блока часть байт простаивает (округление до класса размера, заголовок, выравнивание). 2. Откуда free(ptr) узнаёт, сколько байт освобождать, получив только указатель? - Аллокатор сканирует кучу и считает - Размер передаётся в глобальной переменной - Освобождается всегда фиксированный размер - Из заголовка блока, лежащего непосредственно перед ptr (верно) - Пояснение: Аллокатор хранит размер (и часто magic-число для проверки порчи) в заголовке прямо перед возвращённым указателем. free отступает назад на размер заголовка и читает оттуда метаданные. 3. Что делает coalescing (склейка)? - Переносит занятые блоки, чтобы убрать дыры - Режет большой свободный кусок под мелкий запрос - Склеивает смежные свободные куски в один большой, борясь с внешней фрагментацией (верно) - Сжимает данные внутри блока - Пояснение: При free аллокатор проверяет соседей и сливает смежные свободные куски в один крупный. Это лечит внешнюю фрагментацию: после склейки можно выдать больший непрерывный блок. 4. В free list лежат куски 10, 30, 20 (в этом порядке). Приходит запрос на 15. Какой кусок выберет best fit? - 20 (верно) - 10 - первый подходящий — 30 - 30 - Пояснение: Best fit обходит весь список и берёт наименьший подходящий. Подходят 30 и 20; меньший из них — 20. (First fit взял бы 30 — первый, куда влезает; worst fit — 30 как самый большой.) 5. Какие приёмы используют промышленные аллокаторы (tcmalloc, jemalloc, аллокатор Go) ради скорости и масштабируемости? - Per-thread / per-P кэши блоков, чтобы не брать блокировку (верно) - Size classes (фиксированные классы размеров со своими списками) (верно) - Slab-подход: заранее нарезанные массивы объектов одного типа (верно) - Полный обход единого глобального free list на каждом malloc - Пояснение: Классы размеров убирают поиск и splitting (выделение за O(1)), локальные кэши потоков убирают борьбу за блокировку, slab держит готовые объекты фиксированного типа. А вот полный обход единого списка — как раз то, чего эти аллокаторы избегают. 6. Сколько байт внутренней фрагментации даст запрос на 33 байта, если аллокатор округляет до классов размеров 8, 16, 32, 48, 64? - Ответ: 15 - Пояснение: 33 округляется вверх до ближайшего класса — 48. Простаивает 48 − 33 = 15 байт. Это и есть внутренняя фрагментация от округления размера.