Сегментация и фрагментация

Проблема base-and-bounds

В главе про base-and-bounds у процесса была одна пара регистров: base (где в RAM начинается его память) и bounds (её размер). Физический адрес = base + виртуальный. Схема быстрая, но она кладёт в RAM всё адресное пространство целиком, включая пустоту между кучей и стеком.

Возьмём маленькое адресное пространство на 16 KB:

  Виртуальное адресное пространство (16 KB)
 
   0 KB ┌──────────────┐
        │ код (1 KB)   │
   1 KB ├──────────────┤
        │  (пусто)     │
   4 KB ├──────────────┤
        │ куча (2 KB)  │  растёт к большим адресам
   6 KB ├──────────────┤
        │              │
        │   пусто      │
        │   (8 KB)     │
        │              │
  14 KB ├──────────────┤
        │ стек (2 KB)  │  растёт к меньшим адресам
  16 KB └──────────────┘

Используется 5 KB, но base-and-bounds займёт в RAM все 16 KB. Для реального 64-битного процесса пропорция ещё хуже: используется несколько мегабайт из терабайтов адресов. Нужен способ не класть пустоту в физическую память.

Идея: пара base/bounds на каждую область

Адресное пространство состоит из нескольких логически разных кусков: код, куча, стек. Дадим каждому свою пару base/bounds. Такой кусок называется сегментом (segment): непрерывная область виртуальной памяти с одним назначением.

Теперь в RAM кладутся только сами сегменты, каждый в любое свободное место:

  Физическая память
 
   0 KB ┌──────────────┐
        │     ОС       │
  16 KB ├──────────────┤
        │ стек         │  2 KB
  18 KB ├──────────────┤
        │ свободно     │
  28 KB ├──────────────┤
        │ код          │  1 KB
  29 KB ├──────────────┤
        │ свободно     │
  34 KB ├──────────────┤
        │ куча         │  2 KB
  36 KB ├──────────────┤
        │ свободно     │
        └──────────────┘

Процесс занимает в RAM 1 + 2 + 2 = 5 KB вместо 16. Таблица сегментов, которую держит процессор (в регистрах) для текущего процесса:

У стека в качестве base указан верхний край, потому что стек растёт вниз; ниже разберём, как это считается.

Как по адресу понять сегмент

Процессор получил виртуальный адрес. Как узнать, к какому сегменту он относится? Простой приём: старшие биты адреса — номер сегмента, остальные — смещение (offset) внутри сегмента.

Адрес у нас 14-битный (2¹⁴ = 16 KB). Отдадим 2 старших бита под номер сегмента и 12 младших под смещение. Тогда один сегмент может быть не больше 2¹² = 4 KB, а адресное пространство делится на четыре четверти: 0–4 KB (сегмент 00), 4–8 KB (01), 8–12 KB (10, не используется) и 12–16 KB (11).

  13 12 │ 11 10  9  8  7  6  5  4  3  2  1  0
 ┌──────┼───────────────────────────────────┐
 │ SEG  │            OFFSET                 │
 └──────┴───────────────────────────────────┘

Пример: адрес в куче

Программа читает виртуальный адрес 4200.

4200 = 4096 + 104 = 01 0000 0110 1000
                    ── ──────────────
                    SEG=01  OFFSET=104
 
1. SEG = 01 → куча: base = 34 KB, размер 2 KB
2. проверка: 104 < 2048? да
3. физический адрес = 34 KB + 104 = 34816 + 104 = 34920

А адрес 7000 = 4096 + 2904 даст смещение 2904, больше размера кучи 2048. Процессор не будет считать физический адрес, а сгенерирует исключение, и ядро ОС пошлёт процессу SIGSEGV. Название segmentation fault пришло именно отсюда: «нарушение границ сегмента». Слово осталось, хотя сегментацию в этом виде давно не используют.

Пример: адрес в стеке

Стек растёт вниз: его «начало» — верхний край, виртуальный адрес 16 KB, которому соответствует физический 18 KB. Поэтому для стека смещение считают от верхнего края сегмента, со знаком минус.

Программа читает виртуальный адрес 15 KB = 15360:

15360 = 11 1100 0000 0000
        ── ──────────────
        SEG=11  OFFSET=3072
 
1. SEG = 11 → стек: верхний край 18 KB, размер 2 KB, растёт вниз
2. отрицательное смещение = OFFSET − максимальный размер сегмента
                          = 3072 − 4096 = −1024
3. проверка: |−1024| ≤ 2048? да
4. физический адрес = 18 KB − 1024 = 18432 − 1024 = 17408 (17 KB)

Проверка здравым смыслом: адрес 15 KB на 1 KB ниже верхнего края стека (16 KB), и физический результат на 1 KB ниже верхнего края сегмента в RAM (18 KB).

А адрес 13 KB = 13312 тоже попадает в сегмент 11, но со смещением 1024, то есть отрицательным −3072. Это за пределами 2 KB стека: SIGSEGV. Для этого в таблице сегментов и хранят бит направления роста.

Права доступа и общие сегменты

Раз у каждого сегмента своя строка в таблице, туда легко добавить биты прав: чтение, запись, исполнение. Код помечают «чтение и исполнение, без записи», и программа не может случайно переписать свои инструкции.

Права открывают и совместное использование (sharing). Если десять процессов запускают один бинарник, их сегменты кода одинаковы. Можно указать у всех base на одну физическую копию кода с правами «только чтение». Так же одна копия разделяемой библиотеки в RAM обслуживает много процессов; в современных системах это делается страницами, но идея та же.

Что делает ОС

Железо переводит адреса, а ОС отвечает за остальное:

• при переключении контекста сохраняет и загружает регистры сегментов процесса;
• когда куча растёт (malloc попросил ещё памяти через brk, см. API памяти), увеличивает размер сегмента кучи, если рядом в RAM есть место;
• ищет в физической памяти свободное место под новые сегменты.

Последний пункт и оказывается главной бедой.

Внешняя фрагментация

Сегменты разного размера. Когда в памяти постоянно размещают и освобождают куски разного размера, свободное место дробится на дыры. Внешняя фрагментация (external fragmentation): свободной памяти в сумме достаточно, но она разбита на несмежные куски, и непрерывный большой запрос не помещается.

ДО: память плотно занята             ПОСЛЕ: A и C освободились
 
 0 KB ┌──────────────┐                0 KB ┌──────────────┐
      │ сегмент A 8K │                     │ свободно 8K  │
 8 KB ├──────────────┤                8 KB ├──────────────┤
      │ сегмент B 8K │                     │ сегмент B    │
16 KB ├──────────────┤               16 KB ├──────────────┤
      │ сегмент C 8K │                     │ свободно 8K  │
24 KB ├──────────────┤               24 KB ├──────────────┤
      │ сегмент D 8K │                     │ сегмент D    │
32 KB └──────────────┘               32 KB └──────────────┘
 
Свободно всего 16 KB, но запрос на сегмент 12 KB не помещается:
ни одна дыра не даёт 12 KB подряд.

Аналогия — парковка: свободно пять мест, но все по одному между машинами, и автобусу, которому нужны три места подряд, встать некуда.

Компактизация и её цена

Прямое лечение — компактизация (compaction): остановить процессы, сдвинуть живые сегменты вплотную друг к другу, собрать свободное место в одну большую дыру и обновить регистры base.

 0 KB ┌──────────────┐
      │ сегмент B    │  переехал, base обновлён
 8 KB ├──────────────┤
      │ сегмент D    │  переехал, base обновлён
16 KB ├──────────────┤
      │ свободно 16K │  теперь одна дыра, запрос 12 KB влезает
32 KB └──────────────┘

Цена высокая: нужно физически скопировать мегабайты или гигабайты памяти, и пока идёт копирование, процессы стоят. Делать это часто нельзя. Можно аккуратнее выбирать дыру под новый сегмент (first fit, best fit и другие стратегии из главы управление свободной памятью), но при кусках произвольного размера фрагментация всё равно накапливается.

Почему перешли к страницам

Корень проблемы — переменный размер кусков. Если резать память на куски одинакового размера, любая свободная клетка подойдёт под любой запрос, и внешней фрагментации не будет. Этот подход называется страничной организацией (paging), ей посвящена следующая глава.

Сегментация в x86-64 почти выключена: в 64-битном режиме процессор игнорирует base и размеры основных сегментов и считает память одним плоским пространством. Остались два регистра, FS и GS, у которых работает только base. Ими пользуются для данных, локальных для потока: например, glibc хранит через FS адрес области thread-local storage текущего потока.

Частые ошибки

• Путать внешнюю и внутреннюю фрагментацию. Внешняя — дыры между выделенными кусками; внутренняя — неиспользуемый остаток внутри выделенного куска.
• Думать, что сегменты в RAM должны лежать в том же порядке, что и в виртуальном пространстве. Каждый лежит где угодно, порядок не важен.
• Считать смещение для стека так же, как для кучи. Стек растёт вниз, смещение отсчитывается от верхнего края.

Проверьте себя

1. Переведите виртуальный адрес 100 по таблице сегментов из главы.
2. Переведите адрес 6000. Что произойдёт?
3. Переведите адрес 15872 (15,5 KB).
4. Почему компактизацию нельзя делать при каждом освобождении памяти?

Что спрашивают на собесе

• Какую проблему base-and-bounds решает сегментация.
• Как из виртуального адреса достаётся номер сегмента и смещение; умейте разобрать конкретный адрес на биты.
• Что такое внешняя фрагментация и чем она отличается от внутренней.
• Откуда название segmentation fault.
• Почему отказались от сегментации в пользу страниц.
• Чем стек особенный при сегментации.