Пейджинг

Навіщо це

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

Ідея банальна до простоти: поділити і логічний, і фізичний простір на шматки однакового розміру. Тоді будь-який шматок влізе в будь-яке вільне місце, і питання «куди покласти» зникає разом із фрагментацією.

Платити доводиться таблицею, у якій треба зберігати, який шматок куди поклали. Уся складність пейджингу зосереджена саме в цій таблиці.

Передумови. Логічні й фізичні адреси, MMU (модуль 10), кеші процесора (модуль 2).

Сторінки і фрейми

Сторінкою називають шматок логічного адресного простору, фреймом — шматок фізичної пам’яті такого самого розміру. Типово це 4 КіБ.

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

Транслюється лише номер сторінки. Зсув проходить наскрізь незмінним — саме тому розмір сторінки мусить бути степенем двійки.

Зовнішня фрагментація зникає повністю, бо будь-яка вільна сторінка підходить для будь-якої потреби. Натомість повертається внутрішня, зате в мінімальному розмірі: втрачається невикористаний хвіст останньої сторінки процесу, у середньому півсторінки. За розміру 4 КіБ це два кілобайти на процес, із чим цілком можна жити.

Запис таблиці сторінок

У записі лежить не тільки номер фрейма. Кожен несе ще й біти, на яких тримається половина решти курсу:

Біт	Що означає	Де використовується
номер фрейма	куди відображено	трансляція
дійсності (valid)	чи є відображення взагалі	сторінковий виняток
права (r/w/x)	що дозволено робити	захист, SIGSEGV
користувач/ядро	чи доступна сторінка процесу	ізоляція ядра
звернення (accessed)	чи зверталися з останньої перевірки	алгоритми заміщення
зміни (dirty)	чи писали в сторінку	чи треба зберігати перед витісненням

На біті дійсності побудована вся віртуальна пам’ять: скинувши його, ядро змушує апаратуру повідомити про будь-яке звернення до цієї сторінки. А біт зміни економить запис на диск, бо незмінену сторінку можна просто викинути — копія на диску й так актуальна.

Проблема розміру

Порахуймо для 32-бітної системи з чотирикілобайтними сторінками. Зсув займає 12 біт, на номер сторінки лишається 20, а це 2²⁰ = 1 048 576 записів. По 4 байти на запис — і виходить 4 МіБ таблиці на кожен процес. Сто процесів з’їдять 400 МіБ самими лише таблицями.

Для 64-бітної системи порахуйте самі. x86-64 використовує 48 значущих біт адреси, з них 12 на зсув, тож номер сторінки займає 36 біт: 68 719 476 736 записів по 8 байтів — 512 ГіБ таблиці на кожен процес. Таблиця, більша за пам’ять, яку вона описує.

Рятує ситуацію одне спостереження: адресний простір майже порожній. Процес використовує кілька областей — код, купу, стек, бібліотеки, — а між ними тягнуться гігабайти нічого. Зберігати записи для порожнечі безглуздо.

Багаторівневі таблиці

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

На x86-64 адреса розкладається на чотири індекси по 9 біт плюс 12 біт зсуву, а кожна таблиця займає рівно одну сторінку, тобто 512 записів по 8 байтів. Якщо цілий піддіапазон адрес не використовується, таблиця нижнього рівня для нього просто не створюється, і мільйони порожніх записів фізично не існують.

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

Альтернативи, які не прижилися

Інвертована таблиця зберігає один запис на фізичний фрейм, а не на логічну сторінку, тож її розмір залежить від обсягу пам’яті, а не від кількості процесів. Проблема в тому, що пошук іде за вмістом, а не за індексом, тому потрібне хешування, та й спільна пам’ять реалізується важко. Хешовані таблиці розв’язують пошук, але додають обробку колізій. Обидва підходи застосовувалися в PowerPC та IA-64 і програли багаторівневим саме через складність.

TLB

Буфер трансляції адрес (translation lookaside buffer) — це маленький асоціативний кеш усередині MMU, який зберігає кілька десятків чи сотень готових пар «номер сторінки → номер фрейма».

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

Уся практична ефективність пейджингу тримається на частці влучань, і висока вона завдяки локальності: програма звертається до невеликої кількості сторінок протягом тривалого часу. Типово влучань понад 99%.

У профілюванні це видно так: код, який обходить велику структуру даних у випадковому порядку, повільний не лише через промахи кеша даних, а й через промахи TLB. Це різні кеші й різні лічильники.

Окрема проблема — контекстне перемикання. Таблиці нового процесу інші, тож старий вміст TLB недійсний, а скидати TLB повністю дорого. Тому сучасні процесори тегують записи ідентифікатором адресного простору, на x86 це PCID, і записи різних процесів спокійно співіснують.

Великі сторінки

Кількість записів у TLB фіксована. За 4 КіБ на запис буфер на 1500 записів покриває близько 6 МіБ, тоді як робочий набір бази даних вимірюється гігабайтами. Промахи стають постійними.

Великі сторінки, 2 МіБ або 1 ГіБ на x86-64, розв’язують саме це: один запис TLB покриває у 512 разів більше пам’яті, і виграш для баз даних та віртуальних машин помітний одразу.

Платити доводиться грубою гранульованістю. Внутрішня фрагментація рахується вже мегабайтами, та й витіснити на диск 2 МіБ дорожче, ніж 4 КіБ. Тому великі сторінки вмикають вибірково, а не всюди підряд.

Сегментація

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

Приваблива вона тим, що межі збігаються з логічними межами програми. Вихід за кінець масиву в окремому сегменті ловить апаратура, а права доступу природно задаються на всю ділянку.

От тільки недолік у неї той самий, що й у розділів змінного розміру, — зовнішня фрагментація. Тому x86 у 32-бітному режимі поєднував обидва механізми: сегментація зверху, пейджинг знизу.

У 64-бітному режимі сегментацію фактично скасували. Бази сегментів примусово нульові, від усього механізму лишилися крихти на кшталт FS і GS для локальної пам’яті потоку. Пейджинг переміг.

Пейджинг — не свопінг

Ці дві речі легко сплутати через схожі слова, хоча спільного в них мало. Пейджинг є механізмом трансляції адрес: розбиття простору на сторінки і відображення їх на фрейми. Він працює завжди, навіть коли вільної пам’яті вдосталь, а диск не задіяний узагалі. Свопінг — це переміщення даних між оперативною пам’яттю і диском, коли пам’яті бракує. Один про адресацію, другий про нестачу.

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

getconf PAGESIZE

Розмір сторінки в байтах. На x86-64 це 4096; на ARM64 буває 16384 і 65536.

grep -E 'Huge|AnonHugePages' /proc/meminfo

Стан великих сторінок. AnonHugePages — скільки пам’яті вже покрито прозорими великими сторінками, які ядро зводить автоматично.

grep Hugepagesize /proc/meminfo; grep -o pdpe1gb /proc/cpuinfo | head -1

Hugepagesize — типовий розмір великої сторінки, на x86-64 це 2 МіБ. Окремого прапорця для них шукати не треба: у 64-бітному режимі вони є завжди. А от pdpe1gb справді показує, чи вміє процесор сторінки на 1 ГіБ.

Прапорець `pse` тут ні до чого

Його часто наводять як ознаку підтримки двомегабайтних сторінок, і це непорозуміння: pse (page size extension) стосується сторінок на 4 МіБ у 32-бітному пейджингу. На будь-якому сучасному процесорі він стоїть завжди, тому нічого й не перевіряє.

awk '/^Rss|^Pss|^AnonHugePages/ {s[$1]+=$2} END {for (k in s) print k, s[k]" kB"}' /proc/self/smaps

smaps дає розбивку по кожному відображенню. Pss — частка спільних сторінок, поділена на кількість користувачів: чесніша оцінка споживання, ніж Rss.

perf stat -e dTLB-load-misses,dTLB-loads,cache-misses -- sh -c 'i=0; while [ $i -lt 200000 ]; do i=$((i+1)); done'

Промахи TLB і промахи кеша даних окремо. На послідовному обході перших майже немає; на випадковому доступі до великої структури вони стають помітною статтею витрат.

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

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

«Таблиця сторінок зберігається в процесорі». Лежить вона в оперативній пам’яті. У процесорі є тільки регістр з адресою кореня таблиці, CR3 на x86, і кеш готових трансляцій, тобто TLB.

«TLB кешує дані». TLB кешує трансляції, а дані кешуються в L1, L2 і L3. Це різні кеші, промахуються вони незалежно, і в perf для них різні лічильники.

«Більший розмір сторінки завжди краще». Промахів TLB справді менше, зате внутрішня фрагментація більша, а витіснення дорожче. Виграш буде там, де робочий набір великий і суцільний, а от дрібним процесам великі сторінки тільки шкодять.

«Пейджинг усуває фрагментацію». Усуває зовнішню. Внутрішня нікуди не дівається, просто зменшується в середньому до півсторінки на процес.

«Сегментація застаріла і не потрібна». Сама ідея захищати ділянки за призначенням жива й здорова: вона перейшла в біти прав доступу в записі таблиці сторінок. Не прижилася саме сегментація як спосіб розподілу пам’яті.

Перевір себе

1. Чому розмір сторінки обовʼязково є степенем двійки?

Так зручніше рахувати людиніЩоб логічна адреса ділилася на номер сторінки і зсув простим розрізанням бітів, без діленняЦього вимагає стандарт POSIXЩоб сторінка вміщалася в кеш процесора

2. 32-бітна система, сторінки 4 КіБ, записи по 4 байти. Якого розміру одиночна таблиця сторінок на процес?

4 КіБ1 МіБ4 МіБ4 ГіБ

3. Чим багаторівнева таблиця сторінок економить памʼять?

Стискає записиДля невикористаних діапазонів адрес таблиці нижнього рівня просто не створюютьсяЗберігає таблицю на дискуВикористовує менші сторінки

4. Що саме кешує TLB?

Дані з памʼятіГотові пари «номер сторінки → номер фрейма»Інструкції процесораВміст файлів

5. У чому різниця між пейджингом і свопінгом?

Це синонімиПейджинг — механізм трансляції адрес, працює завжди; свопінг — переміщення даних на диск при нестачі памʼятіПейджинг для файлів, свопінг для процесівПейджинг апаратний, свопінг теж апаратний

6. База даних із робочим набором у кілька гігабайтів страждає від промахів TLB. Що допоможе найбільше?

Зменшити розмір сторінкиУвімкнути великі сторінки: один запис TLB покриватиме 2 МіБ замість 4 КіБЗбільшити файл підкачкиДодати рівнів у таблицю сторінок

Лабораторна

A5 — симулятор трансляції та заміщення. Перша частина: реалізувати багаторівневу таблицю сторінок і TLB, виміряти частку влучань на реальному трасі звернень. Друга частина — у модулі 12.

Джерела

• OSTEP: Paging: Introduction, Faster Translations (TLBs), Smaller Tables
• Silberschatz, Operating System Concepts, розділ 9
• Documentation/mm — керування пам’яттю в Linux
• man 2 mmap, man 5 proc (розділ smaps)