TLB и подсчёт обращений к памяти

Зачем нужен TLB

При 4-уровневой таблице каждое обращение к памяти превратилось бы в пять. Программы стали бы в разы медленнее. Спасает TLB (Translation Lookaside Buffer) — маленький быстрый кеш трансляций внутри процессора.

виртуальный адрес │ ▼ ┌───────────────┐ попадание (≈99%) │ TLB │──────────────────────▶ физический адрес │ VPN → PFN, │ (0 доп. обращений) │ права │ └───────┬───────┘ │ промах ▼ обход таблиц: cr3 → ур.1 → ур.2 → ур.3 → ур.4 (4 обращения к памяти) → записать в TLB → физический адрес

Типичный TLB — десятки–сотни записей первого уровня и ~1–2 тысячи второго. Он работает потому, что программы обладают локальностью: обращаются к одним и тем же страницам много раз подряд.

Попадания и промахи

Попадание (hit): трансляция найдена в TLB — служебных обращений к памяти нет.
Промах (miss): MMU (на x86 — аппаратно) обходит таблицы страниц: по одному обращению на каждый уровень, затем записывает трансляцию в TLB, вытеснив какую-то старую запись (в задачах обычно — LRU).

На некоторых архитектурах (MIPS, старые SPARC) промах TLB обрабатывает ядро программно — тогда это ещё и исключение.

Эффективное время доступа

T = h · t + (1 − h) · (L + 1) · t, где h — доля попаданий в TLB, L — число уровней таблиц, t — время одного обращения к памяти.

При h = 0,98, L = 4, t = 100 нс: T = 108 нс.

Сброс TLB

Событие	Что происходит с TLB
смена процесса (запись в cr3)	сброс всех записей, кроме глобальных (G)
ядро изменило PTE (например, сбросило бит A или R/W)	нужно сбросить эту запись: `invlpg`
изменение отображения на многопроцессорной машине	сброс на других ядрах через межпроцессорное прерывание — TLB shootdown
PCID / ASID	записи помечены адресным пространством — сброс при переключении не обязателен

Методика подсчёта служебных обращений

Задачи вида «сколько лишних обращений к памяти сделает цикл» решаются по шагам.

Шаг 1. Выпишите все обращения к памяти за одну итерацию — в порядке выполнения. Переменные register — не память. Глобальные переменные — память. Указатель, объявленный как extern double *a;, — переменная в памяти: чтобы прочитать a[i], сначала нужно прочитать сам a.

Шаг 2. Определите страницы. Для массивов: сколько байт, сколько страниц минимум и максимум (смотрите, где начинается массив). Для отдельных переменных: могут лежать на одной странице или на разных.

Шаг 3. Промоделируйте TLB. Сколько разных страниц нужно на одной итерации? Если не больше числа записей TLB — промахи только при переходе на новую страницу. Если больше — при циклическом обходе с LRU промах на каждом обращении.

Шаг 4. Посчитайте. Служебные обращения = промахи × число уровней (+ чтения указателей, если они в памяти).

Шаг 5. Найдите минимум и максимум, меняя предположения о расположении: выравнивание массивов, страницы указателей, начальное состояние TLB.

Симулятор

Подставьте параметры задачи 7 и посмотрите, как меняется ответ: смещение массивов в странице, расположение указателей.

Попробуйте:

Указатели «на одной странице», смещения 0 и 0 — минимальный случай: каждый массив занимает 2 страницы, на итерацию нужны 3 страницы (указатели, a, b) — помещаются в TLB.
Указатели «на разных страницах», смещения 504 и 504 — максимальный: каждый массив на 3 страницах, на итерацию нужны 4 разные страницы, а в TLB 3 записи — промах на каждом обращении.
Указатели «в регистрах» — если считать, что компилятор прочитал a и b один раз до цикла.

Полный разбор задачи 7

С числами, предположениями и формулировкой ответа — в уроке «Разбор задачи 7» модуля «Подготовка к экзамену». Пройдите сначала задания этого урока: они содержат все шаги решения.

Итог

TLB кеширует трансляции «страница → кадр»; попадание бесплатно, промах стоит по одному обращению на уровень таблиц.
Смена cr3 сбрасывает TLB (кроме глобальных записей); PCID/ASID позволяют этого избежать.
Подсчёт: выписать обращения итерации → страницы → моделировать TLB (LRU) → промахи × уровни → минимум и максимум.
Если на итерацию нужно больше разных страниц, чем записей в TLB, при LRU промахивается каждое обращение.