За пределами физической памяти: page fault и вытеснение

Зачем выходить за пределы RAM

До этого момента мы делали вид, что вся память программы целиком лежит в физической RAM. Удобно для объяснения, но в жизни так не бывает. Представьте сервер с 16 ГБ оперативки, на котором крутятся десятки процессов, и каждый «думает», что у него есть огромное приватное адресное пространство (про эту иллюзию мы говорили в главе Адресное пространство). Если сложить всё, что хотят процессы, выйдет сильно больше 16 ГБ. Куда девать лишнее?

Ответ: часть страниц держать не в RAM, а на диске. Диск медленный, зато большой и дешёвый. ОС создаёт на диске специальную область — swap (своп, «область подкачки»). Туда складываются страницы, которые сейчас не нужны. Когда страница снова понадобится — её подгрузят обратно в RAM.

Аналогия: рабочий стол — это RAM, на нём помещается несколько открытых книг. Шкаф за спиной — диск (swap), книг в нём гораздо больше. Когда нужна книга из шкафа, вы убираете со стола ту, что сейчас не читаете, и кладёте нужную. Стол маленький и быстрый, шкаф большой и медленный. Вся хитрость в том, кого убрать со стола, чтобы пореже ходить к шкафу.

                Иллюзия для программы          Реальность
              ┌───────────────────────┐   ┌──────────────────────┐
   виртуальное│  страница 0           │   │   RAM (быстро, мало)  │
   адресное   │  страница 1           │──▶│  ┌────┐ ┌────┐ ┌────┐ │
   пространство  страница 2           │   │  │стр1│ │стр4│ │стр0│ │
              │  страница 3           │   │  └────┘ └────┘ └────┘ │
              │  страница 4           │   └──────────────────────┘
              │  ...                  │   ┌──────────────────────┐
              │  страница N           │──▶│  SWAP на диске        │
              └───────────────────────┘   │  (медленно, много)    │
                                          │  стр2  стр3  ...  стрN│
                                          └──────────────────────┘

Что нарисовано: программа видит сплошное пространство страниц 0..N. На самом деле часть страниц лежит в RAM, а часть выселена в swap на диске. Программа об этом не знает — для неё всё прозрачно.

Present-bit: флаг «я в памяти?»

Как ОС понимает, где сейчас страница — в RAM или на диске? Вспомним устройство PTE (page table entry, запись таблицы страниц) из главы Страничная организация. Там кроме номера физического кадра есть служебные биты. Один из них — present bit (бит присутствия):

• present = 1 — страница в RAM, в PTE лежит действующий номер кадра.
• present = 0 — страницы в RAM нет. Либо она в swap, либо в файле на диске, либо к ней ещё ни разу не обращались (тогда ядро выдаст новый кадр, заполненный нулями), либо адрес вообще нелегален. Различает эти случаи ядро ОС по своим записям, а не железо (см. разницу valid и present в главе страничная организация).

   PTE (упрощённо)
   ┌───────┬─────┬─────┬─────┬───────────────────────┐
   │ PRES  │ R/W │  U  │  A  │   physical frame #     │
   │  1бит │     │     │     │   (или адрес в swap)   │
   └───┬───┴─────┴─────┴─────┴───────────────────────┘
       │
       ├─ PRES=1 → в поле кадра лежит номер кадра в RAM
       └─ PRES=0 → страницы в RAM нет; ОС хранит, где она
                   (в каком месте swap), отдельно

Что нарисовано: один бит PRES решает судьбу обращения. Если он 0, аппаратура не знает физического адреса и обязана позвать ОС.

Анатомия page fault

Page fault (страничный отказ, «промах страницы») — это ситуация, когда программа обращается к виртуальному адресу, страница которого сейчас не в RAM (present = 0). Слово «fault» пугает, но это не ошибка программы — это штатный механизм. Программа продолжит работать как ни в чём не бывало.

Разберём пошагово. Процессор сам ходит по таблице страниц (или это делает обработчик после промаха TLB — см. TLB). Он находит PTE и смотрит на present bit.

   CPU обращается к виртуальному адресу
                 │
                 ▼
        ┌─────────────────┐
        │ есть в TLB?      │──да──▶ берём кадр, готово (быстро)
        └────────┬────────┘
                 │ нет
                 ▼
        ┌─────────────────┐
        │ идём в таблицу   │
        │ страниц, читаем  │
        │ present bit      │
        └────────┬────────┘
                 │
        ┌────────┴─────────┐
        │ PRES=1           │ PRES=0
        ▼                  ▼
   кадр в RAM,        ╔══════════════════╗
   заполняем TLB,     ║   PAGE FAULT     ║
   повторяем доступ   ║  ловушка в ОС    ║
                      ╚════════╤═════════╝
                               ▼
                  1. ОС находит страницу в swap
                  2. выбирает свободный кадр в RAM
                     (если нет — кого-то вытесняет!)
                  3. читает страницу с диска в кадр ← МЕДЛЕННО
                  4. обновляет PTE: кадр + PRES=1
                  5. возвращается и ПОВТОРЯЕТ ту же
                     инструкцию — теперь PRES=1

Главное: после обработки page fault ОС перезапускает ту же самую инструкцию. Программа даже не замечает, что её на время «заморозили». Она видит лишь, что одно обращение к памяти заняло не сотню наносекунд, а десятки или сотни микросекунд на SSD и миллисекунды на HDD: в тысячи и десятки тысяч раз дольше. Пока идёт чтение с диска, процесс находится в состоянии BLOCKED (глава процесс), и процессор отдаётся другим.

Важно: page fault обрабатывает именно ОС (через ловушку/trap, как в главе Прямое исполнение с ограничениями). Аппаратура только ловит факт PRES=0 и зовёт ОС — а уже ОС решает, что с этим делать.

Minor и major page fault

Не каждый page fault идёт на диск. Linux различает два вида:

• Minor fault (лёгкий): данные уже в RAM, нужно только завести PTE. Например, первое обращение к свежевыделенной памяти (ядро даёт обнулённый кадр), страница файла, которая уже лежит в page cache, или copy-on-write после fork. Стоит порядка микросекунды.
• Major fault (тяжёлый): данных в RAM нет, нужно читать с диска, из свопа или файла. Стоит от десятков микросекунд на быстром SSD до миллисекунд на HDD.

Счётчики есть у каждого процесса: ps -o min_flt,maj_flt -p <PID>, или /usr/bin/time -v ./app после завершения программы. Тысячи minor faults при старте сервиса — норма: так выделяется память. Растущее число major faults под нагрузкой — тревожный признак: сервис ждёт диск на обращениях к памяти.

Когда RAM забита: нужно вытеснять

В шаге 2 выше есть коварная фраза: «если свободного кадра нет — кого-то вытесняем». Память конечна. Чтобы загрузить новую страницу, иногда нужно сначала выселить (evict) какую-то старую: записать её в swap (если её меняли) и освободить кадр.

Кого выселять — решает политика замещения страниц (page replacement policy). От выбора жертвы зависит, сколько будет page fault'ов в будущем, а значит — насколько быстро работает система. Идеал — выселить ту страницу, которая дольше всего не понадобится. Разберём политики.

Оптимум (Belady) — недостижимый идеал

Самая лучшая политика теоретически: выселяй ту страницу, к которой обращение будет дальше всего в будущем (или вовсе не будет). Её называют оптимальной, или политикой Belady (по имени исследователя Ласло Белади).

Проблема очевидна: чтобы знать будущее, нужна машина времени. На практике будущие обращения неизвестны. Поэтому оптимум используют только как эталон для сравнения: «наш реальный алгоритм даёт 80% попаданий, а оптимум дал бы 90% — есть куда расти».

FIFO и аномалия Belady

FIFO (first-in, first-out) — выселяем ту страницу, которая попала в память раньше всех, независимо от того, нужна она или нет. Просто как очередь. Проблема: «старая» не значит «ненужная». Можно выселить страницу, которой пользуются постоянно, просто потому что она зашла давно.

У FIFO есть знаменитая странность — аномалия Belady: иногда, если дать больше памяти, page fault'ов становится больше, а не меньше. Это противоречит здравому смыслу (больше стол — реже ходишь к шкафу), но для FIFO такое бывает. У LRU и оптимальной политики этой аномалии нет. Ниже посчитаем её на конкретной строке обращений.

LRU — выселяй давно не используемую

LRU (least recently used, «дольше всех не использовавшаяся») — главная рабочая идея. Выселяем ту страницу, к которой дольше всего не обращались. Логика опирается на принцип локальности: если к странице обращались только что, скорее всего обратятся снова в ближайшее время; а то, что не трогали давно, вряд ли понадобится скоро.

   История обращений:  7 0 1 2 0 3 0 4 ...
   В памяти 3 кадра.
 
   обращение 4, память [2,0,3], надо выселить одну:
       к 2 — обращались давно   ← кандидат (LRU)
       к 0 — обращались недавно
       к 3 — обращались только что
   ⇒ LRU выселяет страницу 2

Что нарисовано: LRU смотрит «когда последний раз трогали» и выгоняет самую залежавшуюся. На реальных нагрузках LRU работает заметно лучше FIFO.

Но есть беда: точный LRU дорого реализовать. Чтобы знать порядок последних обращений, надо при КАЖДОМ доступе к памяти что-то обновлять (например, ставить временну́ю метку или двигать страницу в начало списка). Обращений к памяти — миллиарды в секунду. Платить за каждое — непозволительно дорого. Поэтому в реальности используют приближение LRU.

Clock (second-chance) — дешёвое приближение LRU

Хитрость: аппаратура почти бесплатно умеет ставить один бит — reference bit (бит обращения, он же accessed bit, A-bit). При любом обращении к странице процессор сам выставляет этот бит в 1. ОС его периодически сбрасывает в 0. Получается грубый ответ на вопрос «трогали ли страницу недавно?» — без дорогих меток.

На этом построен алгоритм Clock (часы), он же second-chance (второй шанс). Все кадры выстроены в кольцо, по нему ходит «стрелка». Когда нужно выселить:

   Кольцо кадров. У каждого — reference bit (R).
   Стрелка ищет жертву по часовой стрелке.
 
              ┌──────┐
        ┌────▶│ R=1  │────┐
        │     └──────┘    ▼
    ┌──────┐          ┌──────┐
    │ R=0  │          │ R=1  │
    └──────┘          └──────┘
        ▲     ┌──────┐    │
        └─────│ R=0  │◀───┘
              └──────┘
                 ▲
              [стрелка]
 
   Правило на каждом шаге стрелки:
     R == 1 ?  → сбросить R в 0, дать «второй шанс», шаг дальше
     R == 0 ?  → ВЫСЕЛИТЬ эту страницу, стоп

Что нарисовано: стрелка идёт по кругу. Если у кадра R=1 (его недавно трогали) — стрелка не убивает его, а лишь обнуляет бит и идёт дальше («даём второй шанс»). Если R=0 (давно не трогали) — это жертва. Так часто используемые страницы постоянно «спасаются», а залежавшиеся вылетают. Получаем поведение, близкое к LRU, но почти даром.

Часто к этому добавляют dirty bit (бит модификации, M-bit): если страницу не меняли с момента загрузки, её копия в swap уже актуальна — выселить можно мгновенно, без записи на диск. А «грязную» (изменённую) сначала надо записать. Поэтому при прочих равных выгоднее выселять чистые страницы.

Все политики на одном примере

Возьмём строку обращений к страницам из симулятора ниже:

1 2 3 4 1 2 5 1 2 3 4 5

FIFO, 3 кадра. Выселяем самую старую по времени загрузки.

обращение:  1    2    3    4    1    2    5    1    2    3    4    5
результат:  M    M    M    M    M    M    M    h    h    M    M    h
кадры:     [1] [1,2][1,2,3][2,3,4][3,4,1][4,1,2][1,2,5][1,2,5][1,2,5][2,5,3][5,3,4][5,3,4]

M — промах (page fault), h — попадание. Итого 9 промахов.

FIFO, 4 кадра. Памяти больше, промахов должно стать меньше?

обращение:  1  2  3  4  1  2  5  1  2  3  4  5
результат:  M  M  M  M  h  h  M  M  M  M  M  M

10 промахов: на один больше, чем с тремя кадрами. Это и есть аномалия Belady. С четырьмя кадрами FIFO выселяет 1, 2, 3 и 4 ровно перед тем, как они снова понадобятся.

LRU, 3 кадра. Выселяем ту, к которой дольше всего не обращались.

обращение:  1  2  3  4  1  2  5  1  2  3  4  5
результат:  M  M  M  M  M  M  M  h  h  M  M  M

10 промахов, хуже FIFO на этой строке. LRU не обязан выигрывать на каждом примере: здесь он выселяет 3 и 4, которые как раз вернутся в конце. Но с 4 кадрами у LRU будет 8 промахов: добавили память — стало лучше, аномалии нет.

Оптимальная политика, 3 кадра. В момент обращения к 4 она смотрит в будущее: 1 и 2 скоро понадобятся, 3 — позже всех, выселяем 3.

обращение:  1  2  3  4  1  2  5  1  2  3  4  5
результат:  M  M  M  M  h  h  M  h  h  M  M  h

7 промахов, меньше быть не может. Первые три промаха неизбежны у любой политики: страниц ещё нет в памяти (их называют промахами холодного старта).

Проверьте эти числа в симуляторе в конце главы: переключите политику и число кадров.

Как это сделано в Linux

Linux не использует чистый Clock. Ядро держит страницы в двух списках: активном (недавно использованные) и неактивном (кандидаты на вытеснение) — и перемещает страницы между ними, проверяя тот же бит обращения. В новых ядрах есть вариант с несколькими поколениями (MGLRU), который многие дистрибутивы включают по умолчанию. Идея везде одна: дешёвое приближение LRU по аппаратному биту обращения.

Вытеснение начинается заранее, а не в момент, когда память кончилась совсем. Фоновый поток ядра kswapd просыпается, когда свободной памяти становится меньше порога, и освобождает страницы в фоне. Если процесс просит память быстрее, чем kswapd успевает, процесс сам занимается освобождением прямо в своём запросе (direct reclaim), и это видно как внезапные задержки.

Thrashing: когда система буксует

А что, если памяти настолько мало, что активных страниц всех процессов не влезает в RAM одновременно? Тогда наступает состояние под названием thrashing (трешинг, «пробуксовка»): ОС выселяет страницу, которая тут же снова нужна, грузит её, выселяя другую нужную, которая тут же снова нужна... Система почти всё время занята перекачкой страниц между RAM и диском, а полезной работы почти не делает.

   Производительность системы vs степень загрузки памяти
 
  пропуск-  │           ╭──────────╮
  ная       │         ╭─╯          ╰─╮      ← зона thrashing:
  способ-    │       ╭─╯              ╰────╮   всё время свопим,
  ность     │     ╭─╯                     ╰── полезной работы 0
            │   ╭─╯                          ╲___________
            │ ╭─╯                                        
            └─┴──────────────────┬──────────────────────▶
              мало процессов   оптимум    слишком много
                                          (память переполнена)

Что нарисовано: сначала чем больше загрузка, тем выше отдача. Но после некоторого порога RAM перестаёт вмещать «горячие» данные, начинается непрерывный свопинг, и производительность обрушивается почти до нуля. Классический «сервер завис, но CPU вроде свободен» — часто это именно thrashing: ядра простаивают в ожидании диска.

Working set: сколько памяти реально нужно

Чтобы не доводить до thrashing, вводят понятие working set (рабочее множество) — это набор страниц, которые процесс активно использует в текущий промежуток времени. Если рабочее множество помещается в выданную процессу RAM — page fault'ов мало, всё летает. Если не помещается — начинается пробуксовка.

Отсюда практический вывод для ОС: лучше не запускать процесс вовсе, чем запустить, когда суммарные рабочие множества не влезают в RAM. Это называют admission control (контроль допуска): иногда правильнее держать часть процессов «на паузе», чтобы оставшиеся работали быстро, а не тормозили все разом.

Своп в проде: его... выключают

Теперь мост к реальности и к главе Память в проде. Казалось бы, своп — спасение. Но на боевых серверах своп часто отключают (или сводят к минимуму). Почему?

• Своп прячет проблему, но делает её хуже. Вместо честного «памяти не хватило» система начинает тихо тормозить из-за свопинга. Latency (задержка ответа) запросов взлетает в сотни раз. Для сервиса с SLA по времени ответа «медленно» нередко хуже, чем «упал и перезапустился».
• Предсказуемость важнее живучести. Kubernetes долго требовал выключать своп на нодах: планировщик рассчитывает память по запросам и лимитам, а своп ломает эту арифметику. В новых версиях своп на нодах поддерживается, но включается явно и с ограничениями.
• Вместо свопа — OOM. Когда память реально кончается, ядро Linux зовёт OOM killer (Out Of Memory killer) — он выбирает процесс-жертву и убивает его, освобождая RAM. Грубо, но быстро и предсказуемо: один сервис умер и перезапустился, остальные живы и быстры. Подробно про OOM, лимиты cgroups и контейнеры — в главе Память в проде.

При этом сам механизм present-bit и page fault никуда не девается даже без свопа. Он работает постоянно: при первом обращении к свежевыделенной памяти (демандная подкачка — страница выдаётся «по требованию»), при работе с файлами через mmap (страницы файла подгружаются с диска по page fault'у), при разделяемых страницах. Так что page fault — это не «авария», а несущая конструкция всей виртуальной памяти.

Go-ракурс

Для Go-сервиса правило простое: рабочее множество должно помещаться в RAM. Если куча Go начинает уходить в своп, сборщик мусора, который обходит всю кучу, и обычные обращения к памяти превращаются в дисковые операции, и p99 задержки вырастает на порядки. На практике лучше настроить лимиты памяти (GOMEMLIMIT, лимиты контейнера) так, чтобы при нехватке процесс честно упал по OOM и перезапустился оркестратором, чем медленно умирал в свопе, утягивая за собой соседей. Подробнее про связку GC, GOMEMLIMIT и page cache — в главах Память в проде и API памяти.

Частые ошибки

• Считать page fault ошибкой программы. Это штатный механизм; ошибка — только обращение к нелегальному адресу, которое заканчивается SIGSEGV.
• Думать, что без свопа page fault'ов не бывает. Ленивое выделение памяти, mmap файлов и copy-on-write работают через page fault всегда.
• Путать промах TLB и page fault. Промах TLB разрешает железо за десятки наносекунд; page fault обрабатывает ядро ОС, и он может стоить миллисекунды.

Проверьте себя

1. FIFO, 3 кадра, обращения 1 2 3 1 4 1 2. Сколько промахов?
2. То же для LRU.
3. Сервис стартовал и сделал 200 000 minor faults за первую секунду. Это проблема?
4. Почему на сервере может «тормозить всё», хотя загрузка CPU низкая?

Что спрашивают на собесе

• Что такое page fault и что происходит по шагам? Обращение к странице с present=0 → ловушка в ОС → найти страницу в swap → выбрать кадр (возможно, вытеснив чужой) → прочитать с диска → обновить PTE и present bit → перезапустить ту же инструкцию. Прозрачно для программы.
• Зачем present bit и где он лежит? В PTE. Говорит, в RAM ли страница. Если 0 — аппаратура зовёт ОС.
• Почему не используют точный LRU, чем заменяют? Точный LRU требует обновлять данные при каждом обращении к памяти — слишком дорого. Заменяют приближением Clock/second-chance на основе reference bit.
• Что такое аномалия Belady? У FIFO добавление памяти иногда УВЕЛИЧИВАЕТ число page fault'ов. У стековых политик (LRU) такого не бывает.
• Что такое thrashing и working set? Thrashing — система почти всё время свопит, полезной работы нет. Working set — активные страницы процесса; если не влезают в RAM, начинается пробуксовка.
• Почему в проде/Kubernetes часто выключают своп? Своп даёт непредсказуемую latency и прячет нехватку памяти. Предпочитают честный OOM kill: быстрый перезапуск вместо медленной деградации всех сервисов.