Адресний простір

Навіщо це

Запустіть ту саму програму двічі й подивіться в обох процесах адресу однієї глобальної змінної. Вона виявиться однаковою, хоча в пам’яті це очевидно різні комірки.

Питання складніші. Як компілятор узагалі може зашити в код конкретну адресу, якщо невідомо, куди програму завантажать? І чому процес, який звернувся за чужою адресою, отримує SIGSEGV замість того, щоб прочитати чужі дані?

На всі три відповідь одна: адреса, якою оперує програма, не є адресою в мікросхемі пам’яті.

Передумови. MMU і режими виконання (модуль 2), секції адресного простору (модуль 6).

Дві адреси

Логічну адресу бачить і використовує процес, і формує її процесор під час виконання інструкції. Фізичну отримує контролер пам’яті.

Між ними стоїть MMU, блок керування пам’яттю. Це апаратура, яка перетворює одну адресу на іншу при кожному зверненні до пам’яті. Не ядро й не компілятор, а саме апаратура, мільярди разів на секунду.

З цього випливає все інше. Два процеси можуть мати ту саму логічну адресу, відображену на різні фізичні, і тому не бачать одне одного. Логічна адреса, для якої відображення не задано, дає апаратний виняток, звідки й береться SIGSEGV. А ядро може перемістити процес у пам’яті, просто змінивши відображення, і процес цього навіть не помітить.

Найпростіший MMU: база і межа

Історично першим апаратним рішенням були два регістри. Базовий зберігав фізичну адресу початку області процесу, межовий — її розмір.

На кожному зверненні апаратура робила дві дії:

якщо логічна_адреса >= межа  →  апаратний виняток
фізична_адреса = база + логічна_адреса

Однієї перевірки й одного додавання вистачає, щоб отримати одразу дві речі. Захист, бо процес не дотягнеться за свою межу. І переміщуваність, бо достатньо змінити базу, і процес поїде, нічого не помітивши. Самі регістри доступні лише в режимі ядра, тож підняти собі межу процес не може.

Обмеження в цієї схеми одне, зате серйозне: уся пам’ять процесу мусить лежати суцільним шматком. Звідси й починаються проблеми.

Розподіл суцільними ділянками

Якщо кожен процес потребує безперервної області, ядру доводиться її десь знаходити. Історично пробували два підходи.

Розділи фіксованого розміру ділять пам’ять наперед на N ділянок. Просто, але процес на 3 МБ у розділі на 8 МБ марнує п’ять мегабайтів. Такі втрати всередині виданої ділянки називають внутрішньою фрагментацією.

Розділи змінного розміру виділяють ділянку рівно за розміром запиту. Внутрішня фрагментація зникає, зате з’являється інша.

Зовнішня фрагментація

Найнеприємніша властивість зовнішньої фрагментації: система відмовляє в памʼяті, маючи її вдосталь. Проблема не в кількості вільної памʼяті, а в її розрізненості.

Процеси приходять і йдуть, лишаючи по собі дірки різного розміру. Через якийсь час вільної пам’яті стає багато, тільки вся вона розсипана на шматки, менші за будь-який осмислений запит.

Куди тоді класти новий процес, якщо дірок кілька? Класичних стратегій три:

Стратегія	Правило	На практиці
Перша відповідна	перша дірка, куди влізе	найшвидша, результат непоганий
Найкраща відповідна	найменша з достатніх	лишає багато крихітних непридатних дірок
Найгірша відповідна	найбільша	найгірша з трьох за всіма мірками

Назва «найкраща відповідна» звучить переконливо, а виграшу не дає: відрізаючи від найменшої достатньої дірки, ця стратегія щоразу лишає залишок, непридатний ні для чого. За щільністю заповнення пам’яті вони з першою відповідною йдуть приблизно врівень, зате перша помітно швидша — їй не треба щоразу переглядати весь список дірок.

Є ще ущільнення — зсунути всі процеси впритул і зібрати вільне місце в одну область. Працює, але коштує копіювання всієї зайнятої пам’яті й можливе лише тоді, коли адреси прив’язуються під час виконання. Для системи з гігабайтами пам’яті це неприйнятно дорого.

Висновок, з якого починається наступний модуль

Зовнішня фрагментація виникає не через поганий алгоритм. Вона неминуча, поки діє вимога безперервності.

Отже, прибирати треба саму вимогу: дозволити пам’яті процесу лежати розкиданою по фізичній пам’яті, а адресний простір лишити суцільним тільки на вигляд. Механізм, який це робить, називається пейджингом.

Як це насправді в Linux

cat /proc/self/maps

Відображення логічних адрес поточного процесу. Ліворуч — діапазони логічних адрес, далі права доступу, а праворуч — що саме за ними стоїть. Фізичних адрес тут немає взагалі: процесу вони недоступні.

sh -c 'cat /proc/self/maps | head -3'; sh -c 'cat /proc/self/maps | head -3'

Два запуски однієї програми дають різні базові адреси — це ASLR (модуль 16). Без нього адреси збігалися б.

cat /proc/meminfo | grep -E '^(MemTotal|MemFree|MemAvailable|Mapped)'

MemTotal — фізична пам’ять. Сума логічних адресних просторів усіх процесів може бути в рази більшою: адресний простір не є пам’яттю.

ps -eo pid,vsz,rss,comm --sort=-vsz | head -5

VSZ — розмір логічного адресного простору, RSS — скільки з нього фактично лежить у фізичній пам’яті. VSZ у десятки разів більший за RSS — норма, а не витік.

Типові помилки розуміння

«Адреса у вказівнику — це місце в мікросхемі пам’яті». Це логічна адреса. Що їй відповідає фізично, знає тільки MMU, і відповідь цілком може змінитися між двома зверненнями.

«VSZ показує, скільки пам’яті займає процес». Показує він розмір адресного простору, разом із тим, що ніколи не буде використане. Споживання пам’яті — це RSS, та й той завищений через спільні бібліотеки.

«Внутрішня і зовнішня фрагментація — те саме». Внутрішня є невикористаним залишком усередині виданої ділянки. Зовнішня — вільною пам’яттю між ділянками, надто дрібною, щоб її використати.

«Найкраща відповідна — найкраща стратегія». Назва оманлива: за заповненням памʼяті вона не краща за першу відповідну, а часу забирає більше, бо щоразу переглядає весь список дірок.

«Фрагментацію можна перемогти кращим алгоритмом». Не можна, поки пам’ять процесу мусить бути суцільною. Перемогли її тим, що скасували саму вимогу суцільності.

Перевір себе

1. Дві копії однієї програми показують ту саму адресу глобальної змінної. Чому вони не заважають одна одній?Ядро копіює змінну між процесамиЦе логічна адреса; MMU відображає її у різні фізичні адреси для кожного процесуЗмінна зберігається на дискуДруга копія отримує копію лише під час запису

2. Памʼяті вільно 180 МБ трьома ділянками по 60, 50 і 70. Процес просить 140 МБ. Що станеться?Процес отримає памʼять, ядро складе ділянки разомРозміщення неможливе без ущільнення — це зовнішня фрагментаціяПроцес отримає 70 МБ і працюватимеСпрацює файл підкачки

3. Що робить апаратура на кожному зверненні у схемі «база + межа»?Шукає адресу в таблиці сторінокПорівнює логічну адресу з межею і додає базуЗвертається до ядра за дозволомПеревіряє права доступу до файлу

4. Процес на 3 МБ розміщено в розділі фіксованого розміру 8 МБ. Як називаються втрачені 5 МБ?Зовнішня фрагментаціяВнутрішня фрагментаціяУщільненняВитік памʼяті

5. VSZ процесу — 12 ГБ, RSS — 200 МБ, фізичної памʼяті 8 ГБ. Це проблема?Так, процес перевищив обсяг памʼятіНі: VSZ — розмір адресного простору, а не спожитої памʼяті; реально зайнято 200 МБТак, потрібно збільшити swapНі, але процес обовʼязково впаде найближчим часом

6. Чому стратегія «найкраща відповідна» на практиці програє «першій відповідній»?Вона повільніша й лишає багато дрібних непридатних залишківВона не гарантує захисту памʼятіВона працює лише з розділами фіксованого розміруВона вимагає ущільнення після кожного виділення

Лабораторна

A4 — власний розподільник пам’яті. Реалізація malloc поверх mmap зі стратегіями «перша відповідна» і «найкраща відповідна», з вимірюванням фрагментації на реальному профілі запитів. Різниця між теорією і виміряним результатом тут зазвичай несподівана.

Джерела

OSTEP: Address Spaces, Address Translation, Free Space Management
Silberschatz, Operating System Concepts, розділ 9
man 5 proc — розділ про /proc/[pid]/maps і smaps