Удача та невдача TLB & Прогулянка багаторівневою таблицею сторінок

Чому Віртуальна Пам'ять Потребує Перекладу

Віртуальна пам’ять дає кожному процесу ілюзію власного приватного, безперервного адресного простору, ізольованого від інших процесів та часто значно більшого за фізично встановлений RAM, шляхом відображення цього віртуального простору на розкидані фізичні сторінки, зазвичай по 4 кілобайти кожна на системах x86. Ця індиректність і є тим, що забезпечує захист пам’яті: один процес не може виразити дійсний адрес, який вказує на пам'ять іншого процесу, і це робить прозорими такі функції, як перенесення сторінок на диск, копія з правом на зміну для дублювання (fork) та відображення файлів у пам’яті. Вартість полягає в тому, що кожен доступ до пам'яті, не лише випадковий, потребує перекладу віртуального адреси у фізичну перед тим, як система пам'яті може фактично отримати будь-який об'єкт, і це має відбуватися достатньо швидко, щоб не стати домінуючою вартістю кожного інструкції завантаження та збереження. Операційна система підтримує це відображення віртуальної в фізичну карту у вигляді таблиці сторінок для кожного процесу, але таблиця сторінок сама по собі є структурою даних, що знаходиться в пам'яті, тому безпосереднє звернення до неї на кожному доступі означало б множення затримки доступу до пам’яті у кілька разів, що неприйнятно. Ця напруга – необхідність перекладу при кожному доступі, але небажання платити затримку доступу до пам'яті для цього перекладу при кожному доступі – і є проблемою, яку було вирішено завдяки TLB, а розуміння цього пояснює величезну частину того, як працює продуктивність підсистеми пам’яті в реальності.

TLB: Кеш для Перекладів

TLB – це невеликий, високоасоціативний кеш, який зазвичай містить від 64 до 1536 записів, залежно від рівня та процесора, і зберігає безпосередньо в швидкому апаратних компонентах поблизу ядра CPU нещодавно використані відображення віртуального номера сторінки на фізичний кадр. Коли процесор здійснює доступ до пам'яті, він спочатку перевіряє, чи присутній у TLB відповідний віртуальний номер сторінки; якщо так, це – успішне відображення TLB (TLB hit), і фізична адреса стає доступною за приблизно один цикл, не повільніше, ніж типовий пошук в кеші. Якщо ж її немає, це – невдале відображення TLB (TLB miss), і необхідно виконати повний обхід таблиці сторінок, щоб знайти відображення, перш ніж доступ до пам'яті може відбутися, що додає потенційно десятки або сотні циклів затримки. Оскільки програми демонструють сильну локальність – повторний доступ до даних у межах одного невеликого набору сторінок протягом коротких проміжків часу – коефіцієнти успішних відображень TLB зазвичай дуже високі, часто перевищуючи 99% для добре поводиться робочих навантажень, що робить накладні витрати віртуальної пам'яті допустимими в практичному застосуванні. Сучасні процесори підтримують окремі TLB для інструкцій та даних, і часто невеликий, надзвичайно швидкий L1 TLB, підкріплений більшим, дещо повільнішим L2 TLB, що відображає ту ж багаторівневу стратегію кешування, яка використовується для кешів даних. Деякі архітектури також підтримують великі сторінки розміром 2 МБ або 1 ГБ замість стандартних 4 КБ, особливо тому, що одна запис TLB може покривати значно більше пам'яті, що суттєво зменшує ймовірність невдач відображення для великих, безперервних структур даних, таких як бази даних або наукові обчислювальні масиви.

Перегляд багаторівневої таблиці сторінок

При виникненні промаху TLB система повинна звертатися до фактичної таблиці сторінок, але окрема плоска таблиця, яка відображає всі можливі віртуальні сторінки безпосередньо, була б величезною. Для 64-бітної адреси з 4KB сторінками це було б неможливо реалізувати як один великий масив, якщо б використовувалися всі можливі адреси. Рішенням, яке використовується в практично кожній сучасній архітектурі, є багаторівнева, ієрархічна таблиця сторінок, часто звана структурою «корінь-дерево». Віртуальна адреса розбивається на кілька полів: найвищі біти вказують на верхній рівень таблиці сторінок, наступні біти вказують на другу рівневу таблицю, на яку посилається запис, знайдений на першому рівні, і так далі для будь-якої кількості рівнів, які визначає архітектура, зазвичай чотири на x86-64. Найнижчі біти використовуються як зміщення всередині фізичної сторінки. Кожен рівень пошуку вимагає одного фактичного читання пам'яті для отримання запису таблиці сторінок, тому чотирирівневий перегляд при повному промаху потребує до чотирьох послідовних, залежних доступів до пам’яті лише для обчислення фізичної адреси, перш ніж можна буде розпочати оригінальний доступ до пам'яті інструкції. Цей ієрархічний підхід є ефективним з точки зору використання пам’яті, оскільки цілі піддерева невикористаного віртуального адресного простору ніколи не потребують виділення відповідних таблиць сторінок. Якщо запис відсутній, пошук завершується достроково з помилкою сторінки, а не потрібно повністю заповнювати таблицю для всього адресного простору. Симуляція візуалізує саме цей ланцюговий пошук, показуючи таблицю кожного рівня, конкретний запис, обраний кожним полем адреси, та переслідування покажчиків, яке зрештою приводить до номера фізичного кадру.”]} Output strictly adheres to the JSON format. No markdown fences or additional text are included. The translation is fluent and uses standard Ukrainian scientific terminology. The key terms are rendered consistently with previous translations from mysimulator.uk. It accurately reflects the original meaning of the provided text. Note:

TLB miss

page fault

x86-64

physical frame number

radix tree structure

virtual address

memory access

hierarchical approach

address space

entry

pointer chase

cascade lookup

simulation

visualizes

levels

subtrees

dependent memory accesses

original instruction's own memory access

efficient use of memory

unallocated virtual address space

terminates the walk early

fully populated table

full miss

sequential

memory read

top-level page directory

second-level table

lowest bits

offset

physical page

visualizes exactly this cascading lookup

specific entry selected by each address field

pointer chase that ultimately lands on a physical frame number.

Помилки сторінки, атаки на TLB та реальні витрати

Проходження таблиці сторінок може закінчуватися двома зовсім різними способами. Якщо кожна вхідна інформація кожного рівня присутня та позначена як дійсний запис, то проходження успішне, процесор отримує фізичну адресу та зберігає цей новий переклад у TLB перед завершенням початкового доступу пам’яті. Але якщо якась вхідна інформація ланцюга позначена як відсутня – можливо, тому що сторінка ніколи не була виділена або була замінена на диск для звільнення фізичної пам’яті – апаратне забезпечення генерує помилку сторінки, перехоплення в операційну систему, яка повинна або виділити нову сторінку, завантажити необхідні дані знову з диска, або завершити процес через недійсний доступ, перш ніж повторити інструкцію. Помилка сторінки, що потребує читання з диска, є надзвичайно дорогою – потенційно в тисячі разів повільнішою за попадання в TLB, тому операційні системи наполегливо працюють над мінімізацією частоти помилок за допомогою таких технік, як передбачення та розумних політик заміни сторінок. Існує також друга, більш тонко виражена вартість, специфічна для багатоядерних систем – «атака на TLБ»: коли один процесор змінює запис у таблиці сторінок, наприклад, видаляє сторінку, кожен інший процесор може все ще мати в своєму TLB застарілу кешовану переклад цієї ж сторінки, тому операційна система надсилає міжпроцесну переривну інтервальну інформацію кожному іншому процесору, змушуючи його недійсним відповідний запис у TLB – синхронізаційну операцію, яка може бути досить дорогою на системах з великою кількістю ядер. Обидва ці витрати – помилки сторінок та атаки на TLB – виникають саме тому, що TLB є кешем, і кеші завжди створюють фундаментальну проблему підтримки узгодженості кешованих копій із джерелом правди.

Чому Зміна Моделі Доступу Має Значення

Індекс промаху TLB надзвичайно чутливий до того, як програма звертається до пам'яті, що й пояснює, чому одна й та сама алгоритм може працювати кардинально по-різному, навіть якщо обидва є логічно правильними. Послідовні або блоковані схеми доступу, такі як ітерація через масив у порядку або обробка матриці у кеш-дружні блоки, зазвичай звертаються до невеликого та стабільного набору сторінок у будь-який момент часу, підтримуючи робочий набір необхідних перекладів у межах того, що може вмістити TLB, що призводить до показників промаху близько 100 відсотків. Розсіяні, випадкові схеми доступу, такі як переслідування покажчиків через великий зв'язаний список або хеш-таблицю, розкидані по гігабайтах пам’яті, або ітерація через велику матрицю у неправильному порядку розмірів, можуть звертатися до нової, іншої сторінки майже при кожному доступі, перевантажуючи обмежений обсяг TLB та викликаючи потік дорогих промахів, кожен з яких запускає свіжий багаторівневий пошук. Це саме тому системи баз даних, бібліотеки наукових обчислень і високопродуктивні runtime так ретельно стежать за розміщенням даних, рішенням структура-масив проти масив-структура, алгоритмами без урахування кешу та великим використанням сторінок, а не тому, що змінюється основна обчислювальна задача, а тому що відповідний шаблон доступу до пам’яті безпосередньо визначає, як часто TLB потрібно буде пройти. У симуляції ви можете безпосередньо порівняти послідовну схему доступу з розсіяною на одному й тому ж обсязі даних і спостерігати різницю у тому, як часто запускається дорогий багаторівневий пошук, проти того, як часто використовується швидкий шлях промаху TLB.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте TLB Miss & Multi-Level Page Table Walk і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.