ОС · Виртуализация памяти · 11 мин

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

Откуда растут ноги

В прошлой главе Аппаратная трансляция адресов мы научили процессор простому фокусу: на каждый процесс заводим одну пару регистров — base (база) и bounds (граница). Виртуальный адрес из программы превращается в физический по формуле физический = base + виртуальный, а bounds сторожит, чтобы процесс не вылез за свой кусок памяти.

Фокус рабочий, но у него есть жирный минус, ради которого и придумана эта глава. Вспомним, как выглядит адресное пространство процесса (про это была глава Адресное пространство):

Виртуальное адресное пространство процесса (один сплошной кусок)
 
0KB   ┌──────────────┐
      │   код        │  программа (инструкции)
1KB   ├──────────────┤
      │   куча (heap)│  растёт ВНИЗ ↓ (malloc / new)
2KB   ├──────────────┤
      │              │
      │  ОГРОМНАЯ    │  ← здесь почти всегда пусто
      │   ДЫРА       │
      │              │
14KB  ├──────────────┤
      │  стек (stack)│  растёт ВВЕРХ ↑ (вызовы функций)
16KB  └──────────────┘

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

А теперь засада. При схеме base-and-bounds мы кладём в физическую память весь этот кусок целиком, от 0 до 16KB, включая дыру. То есть физическая RAM реально занята пустотой. Если адресное пространство 4GB, а реально нужно 4MB — мы всё равно обязаны зарезервировать 4GB подряд. Это абсурдно расточительно.

Главная мысль главы: зачем класть в память то, чем процесс не пользуется?

Идея сегментации: не одна пара base/bounds, а несколько

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

Было: 1 пара регистров на весь процесс. Стало: 3 пары — отдельно на код, отдельно на кучу, отдельно на стек.

Теперь дыру между кучей и стеком в физическую память класть не надо. Мы размещаем только сами сегменты — там, где в RAM есть место, причём в разных местах. Посмотрим на физическую память:

Физическая память (3 сегмента разбросаны по свободным местам)
 
0KB    ┌──────────────┐
       │  (ОС)        │
16KB   ├──────────────┤
       │  СТЕК        │  ← base=16KB,  bounds=2KB
18KB   ├──────────────┤
       │  свободно    │
       ├──────────────┤
28KB   │  КОД         │  ← base=28KB,  bounds=1KB
29KB   ├──────────────┤
       │  свободно    │
34KB   ├──────────────┤
       │  КУЧА        │  ← base=34KB,  bounds=2KB
36KB   ├──────────────┤
       │  свободно    │
       └──────────────┘

Обратите внимание: дыры из виртуального пространства в физической памяти нет. Мы заняли ровно столько, сколько сегменты реально весят: 1KB + 2KB + 2KB = 5KB вместо 16KB. Сегменты лежат вразнобой, в любом порядке, в любых свободных местах. Аппаратура для каждого держит свою таблицу:

Сегмент	base (где лежит в RAM)	bounds (размер)
Код	28KB	1KB
Куча	34KB	2KB
Стек	16KB	2KB

Как адрес делится на «номер сегмента + смещение»

Возникает вопрос: процессор получает виртуальный адрес, например 4200. Как он поймёт, к какому сегменту тот относится и какую из трёх пар base/bounds брать?

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

Пусть виртуальные адреса 14-битные (диапазон 0..16KB). Отдадим 2 старших бита под номер сегмента (2 бита → 4 значения: 00, 01, 10, 11), а 12 младших — под смещение (12 бит → 4KB максимум на сегмент):

Разбор 14-битного виртуального адреса
 
 13  12 │ 11 10  9  8  7  6  5  4  3  2  1  0
┌───────┼──────────────────────────────────┐
│  SEG  │            OFFSET                 │
│ 2 бит │            12 бит                 │
└───────┴──────────────────────────────────┘
   │                    │
   │                    └─ смещение внутри сегмента (0..4095)
   └─ номер сегмента:
         00 → код
         01 → куча
         10 → стек

Разберём конкретный адрес кучи. Куча в виртуальном пространстве начинается с 4KB, программа обратилась по адресу 4200. В двоичном виде:

4200 = 01 0000 0110 1000
       └┬┘ └──────┬─────┘
      SEG=01    OFFSET=104
     (куча)
 
Шаги аппаратуры:
1. SEG = 01  → это куча → берём base=34KB, bounds=2KB
2. OFFSET = 104 байта
3. Проверка: 104 < 2KB (bounds)?  ДА → доступ разрешён
4. Физический адрес = base + offset = 34KB + 104 = 34920

Если бы смещение оказалось больше bounds (например, программа полезла на 3000 байт в кучу размером 2KB), аппаратура поймала бы выход за границу и сгенерировала аппаратное прерывание — печально известный segmentation fault (сегфолт). Да, то самое слово родом отсюда: «нарушение границ сегмента».

Стек растёт назад: бит направления

Маленькая, но важная деталь. Код и куча растут «вперёд» (в сторону бóльших адресов), а стек растёт назад — в сторону меньших адресов. Чтобы аппаратура правильно считала физический адрес, для каждого сегмента хранят ещё один бит — направление роста. Для стека формула другая: смещение отсчитывается от верхней границы вниз, поэтому в физический адрес подставляется отрицательное смещение. Деталь техническая, но на собесе любят спросить «а почему стек особенный».

Бонус: защита и разделяемая память

Раз у каждого сегмента своя строчка в таблице, туда легко добавить биты прав доступа (protection bits): чтение, запись, исполнение. Код логично пометить как «read + execute, но НЕ write» — тогда даже сама программа не сможет случайно (или злонамеренно) переписать свои инструкции.

А ещё это открывает разделяемую память (sharing). Если два процесса запускают один и тот же бинарник, их сегменты кода идентичны. Зачем держать две копии? Можно указать у обоих base на один и тот же физический сегмент кода (с правами read-only) — и сэкономить RAM. Именно так в реальных ОС одна копия libc в памяти обслуживает сотни процессов.

Тёмная сторона: внешняя фрагментация

Всё выглядело отлично, пока сегменты были одинаковыми. Но сегменты — разного размера (код 1KB, куча 2KB, стек 7KB...). А когда в память кладут и забирают куски произвольного размера, физическая память постепенно дробится на лоскутки. Это и есть внешняя фрагментация (external fragmentation): свободная память есть, но она раскидана мелкими несмежными дырами, и большой непрерывный запрос не помещается, хотя суммарно места хватает.

Бытовая аналогия: парковка. Машины уезжали и приезжали, и теперь свободно 5 мест, но все по одному между занятыми. Приезжает автобус, которому нужно 3 места подряд — и ему некуда встать, хотя «суммарно» свободно целых пять.

Посмотрим на до/после. Сначала память почти забита, потом несколько процессов освободили свои сегменты:

ДО (память плотно занята)
 
0KB   ┌──────────────┐
      │  сегмент A    │ 8KB
8KB   ├──────────────┤
      │  сегмент B    │ 8KB
16KB  ├──────────────┤
      │  сегмент C    │ 8KB
24KB  ├──────────────┤
      │  сегмент D    │ 8KB
32KB  └──────────────┘
 
ПОСЛЕ (A и C освободились → две дыры по 8KB)
 
0KB   ┌──────────────┐
      │  СВОБОДНО 8KB │ ← дыра 1
8KB   ├──────────────┤
      │  сегмент B    │
16KB  ├──────────────┤
      │  СВОБОДНО 8KB │ ← дыра 2
24KB  ├──────────────┤
      │  сегмент D    │
32KB  └──────────────┘
 
Свободно ВСЕГО 16KB. Но приходит запрос на сегмент 12KB —
и ему НЕ ХВАТАЕТ места: ни одна дыра не даёт 12KB подряд!

Вот она, фрагментация в чистом виде: 16KB свободно, а 12KB разместить негде, потому что память изрезана на куски по 8KB.

Компактизация и почему она дорогая

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

КОМПАКТИЗАЦИЯ: сдвинули B и D вверх
 
0KB   ┌──────────────┐
      │  сегмент B    │  (переехал, base обновлён)
8KB   ├──────────────┤
      │  сегмент D    │  (переехал, base обновлён)
16KB  ├──────────────┤
      │              │
      │ СВОБОДНО 16KB │  ← теперь одна большая дыра
      │              │
32KB  └──────────────┘
 
Запрос на 12KB ТЕПЕРЬ влезает.

Звучит хорошо, но цена кусается. Компактизация — это физическое копирование мегабайтов памяти. Пока оно идёт, процессы стоят (память переезжает у них из-под ног). На большой машине это ощутимая пауза, и делать её часто нельзя. Можно ещё играться с алгоритмами выбора дыры (best-fit, worst-fit, first-fit — это тема главы Управление свободной памятью), но они лишь смягчают проблему, а не убирают: при кусках произвольного размера фрагментация неизбежна.

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

Корень всех бед — переменный размер кусков. Пока мы режем память на блоки разной величины, дыры будут разной величины, и большой запрос рано или поздно не влезет.

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

Свойство	base-and-bounds	Сегментация	Страницы (далее)
Регистров на процесс	1 пара	по паре на сегмент	таблица страниц
Дыра внутри адр. пр-ва	в RAM, впустую	НЕ в RAM ✅	НЕ в RAM ✅
Размер кусков	весь процесс	переменный	фиксированный
Внешняя фрагментация	—	есть ❌	нет ✅
Защита по областям	нет	есть ✅	есть ✅
Разделяемая память	трудно	легко ✅	легко ✅

Проверь себя· Сегментация и фрагментация

Зачем сегментация даёт каждому куску (код/куча/стек) свою пару base/bounds вместо одной на процесс?

Виртуальный адрес 14-битный: 2 старших бита — номер сегмента, 12 младших — смещение. Адрес 4200 = 01 0000 0110 1000. Какое смещение внутри сегмента?

Что такое внешняя фрагментация?

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

Какие из утверждений про сегментацию верны?

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

Какую проблему base-and-bounds решает сегментация? Перестаёт класть в физическую память неиспользуемую дыру между кучей и стеком — занимаем только реальные сегменты, а не всё адресное пространство целиком.
Как из виртуального адреса достаётся номер сегмента? Старшие биты адреса — номер сегмента (выбор пары base/bounds), младшие — смещение внутри сегмента. Умей разобрать конкретный адрес на биты руками.
Что такое внешняя фрагментация и чем она отличается от внутренней? Внешняя (фишка сегментации) — свободная память раздроблена на мелкие несмежные дыры, большой запрос не влезает, хотя суммарно места хватает. Внутренняя — потеря внутри выделенного блока (актуальна для страниц/аллокаторов).
Откуда взялось слово segmentation fault? Аппаратура поймала смещение больше bounds сегмента — обращение за его границу — и сгенерировала прерывание.
Почему отказались от сегментации в пользу страниц? Куски переменного размера порождают внешнюю фрагментацию; компактизация дорогая (стоп + копирование RAM). Страницы фиксированного размера убирают внешнюю фрагментацию совсем.
Чем стек особенный при сегментации? Растёт в сторону меньших адресов, поэтому хранят бит направления роста и смещение считают «вниз» от границы.

← Аппаратная трансляция адресов: base-and-bounds Управление свободной памятью →