Виртуальная память всерьёз: сколько на самом деле стоит промах страницы

В первом грейде мы разобрали форму: адрес, который видит программа, виртуален, MMU переводит его через таблицу страниц, а страница, которой нет в RAM, вызывает промах, и её подтягивают с диска. Это была карта. Теперь пройдём по маршруту: именно в деталях живёт и умирает производительность.

Первое, что скрывает карта, — MMU не может позволить себе читать таблицу страниц при каждом обращении. Четырёхуровневая таблица означает четыре зависимых чтения из RAM ещё до того, как вы дотронетесь до данных, то есть каждое обращение стало бы в пять раз медленнее. Поэтому процессор держит маленький кэш недавних переводов: TLB, обычно от 64 до 1536 записей, полностью ассоциативный, прямо возле конвейера. Попадание стоит один такт. Именно поэтому программа, трогающая 100 МБ с хорошей локальностью, работает почти на полной скорости, хотя таблица страниц огромна: за раз она использует всего несколько тысяч различных страниц.

Когда TLB промахивается и страницы нет в памяти, весь конвейер останавливается. Железо обходит таблицу страниц, видит снятый бит присутствия и поднимает исключение. Команда бросается на полпути, запускается обработчик, ядро находит или освобождает фрейм, читает 4 КиБ с устройства, обновляет таблицу страниц, ставит запись в TLB и возвращается, чтобы повторить команду — теперь она проходит. Железо делает лёгкую часть за наносекунды, программное обеспечение делает дорогую часть за микросекунды.

TLB hit: 1 cycle
walk: 3 or 4 reads
RAM: 30 ns
SSD: 0.1 ms
HDD: 8 ms

fault rate: 1/1000
0.001 x 0.1 ms = 100 ns
30 ns -> 130 ns per accessЛестница стоимостей. SSD достаточно быстр, чтобы низкая частота промахов была терпимой, а вращающийся диск — нет.

Когда нужен фрейм, а память полна, что-то надо вытеснить. Лучший возможный выбор, если бы вы видели будущее, — страница, которая понадобится позже всех: оптимальная политика Белади. Она нереализуема, но служит эталоном. Лучшее практическое приближение — LRU: вытеснить страницу, не использовавшуюся дольше всех. И вот существенная загвоздка: точный LRU тоже нереализуем. Он требует отметки времени при каждом обращении, то есть записи в память при каждом чтении — ровно того, чего TLB и существует, чтобы избежать. Поэтому настоящие ядра его приближают, и приближение это — алгоритм часов.

Алгоритм часов держит фреймы в кольцевом списке, у каждого по одному биту обращения. Железо ставит этот бит при каждом обращении, и делает это бесплатно. Когда нужен фрейм, стрелка движется: если бит стоит, страницу использовали недавно — сбросьте бит и дайте ей второй шанс; если бит снят, страница прошла полный круг нетронутой — вытесняйте. Второй шанс и есть самое умное: он отделяет страницы, тронутые один раз всплеском, от страниц, действительно входящих в рабочий набор, ценой одного бита и одного прохода стрелки.

for (;;) {
  frame = frames[hand];
  if (frame.ref_bit == 1) {
    frame.ref_bit = 0;
    hand = (hand + 1) % nframes;
  } else {
    evict(frame);
    break;
  }
}Алгоритм часов целиком. Стрелка идёт по кругу и даёт каждой недавно использованной странице ровно один дополнительный шанс.

А теперь свойство, из-за которого политики замещения вообще интересны. Стековый алгоритм — тот, у которого множество страниц в N фреймах всегда является подмножеством множества в N+1 фреймах. LRU стековый, поэтому больше памяти никогда не может дать больше промахов. FIFO — нет, и алгоритм часов тоже нет, и следствие этого — аномалия Белади: существуют последовательности обращений, на которых четыре фрейма дают больше промахов, чем три. Это не редкая диковинка, а прямой симптом политики, принимающей решения без глобального понятия «недавности», и именно поэтому продакшен-ядра заботятся об отслеживании возраста в духе LRU, а не о простом круговом обходе.

reference string   1 2 3 4 1 2 5 1 2 3 4 5

3 frames           9 faults
4 frames          10 faults

FIFO    more frames -> more faults
CLOCK   more frames -> more faults
LRU     more frames -> never worse
OPT     more frames -> never worseКлассическая строка обращений. Достаточно первых пяти промахов, чтобы четыре фрейма оказались хуже трёх.

Рабочий набор процесса — это множество страниц, которые он активно использует за окно времени. Если это множество помещается в выделенную ему память, частота промахов низка и почти не мешает. Если не помещается, у процесса беда: каждая вытесненная страница — та, что скоро понадобится снова, поэтому следующее обращение промахивается, промах вытесняет ещё одну нужную страницу, и так далее.

working set: 20 MiB
5 threads: 100 MiB
RAM: 64 MiB

resident set: 12 MiB
fault -> evict -> fault -> evictКонкретный случай: пять потоков по 20 МиБ каждый в контейнере с ограничением 64 МиБ RAM.

Это и есть пробуксовка (thrashing), и она объясняет симптом, который видели все, а назвать могут немногие. Машина выглядит полностью зависшей: мышь дёргается, ничего не отзывается, лампочка диска горит не мигая. Вы смотрите загрузку процессора — она вовсе не высокая. Причина в том, что промахивающийся процесс заблокирован, а не работает. Он сидит в очереди ожидания, пока работает устройство, поэтому CPU простаивает — а планировщик запускает другой процесс, тот немедленно промахивается на своих страницах, вытесняет страницы первого и тоже блокируется. Процессор простаивает, потому что каждый готовый к запуску поток ждёт чтения 4 КиБ, и система медленна не потому, что слишком много считает, а потому, что между двумя дисковыми операциями почти ничего не считает. Добавление процессов делает хуже — вопреки интуиции, что больше работы держит CPU занятым.

Две аппаратные заметки, меняющие числа. Первая — прозрачные огромные страницы: ядро может отображать части памяти страницами по 2 МиБ вместо 4 КиБ, что сокращает нужное число записей TLB в 512 раз. Для базы данных, сканирующей таблицу, это может быть большим выигрышем. Вторая, и в обратную сторону, — это может быть потерей: огромную страницу придётся записывать целиком, поэтому программа, испортившая 4 КиБ внутри такой страницы, платит за 2 МиБ ввода-вывода. Поэтому у ядра есть режимы always и madvise, и поэтому значение по умолчанию менялось от версии к версии.