Зачем выходить за пределы 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, либо вообще ещё не выделена.

   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 ОС перезапускает ту же самую инструкцию. Программа даже не замечает, что её на время «заморозили». Она видит лишь, что обращение к памяти заняло не наносекунды, а миллисекунды (диск в десятки тысяч раз медленнее RAM). Эта прозрачность — главное достоинство механизма.

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

Когда 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 уже актуальна — выселить можно мгновенно, без записи на диск. А «грязную» (изменённую) сначала надо записать. Поэтому при прочих равных выгоднее выселять чистые страницы.

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 начинает свопиться, паузы сборщика мусора (GC) и обычные обращения к памяти превращаются в дисковые операции — p99 latency улетает в космос. На практике лучше настроить лимиты памяти (GOMEMLIMIT, лимиты контейнера) так, чтобы при нехватке процесс честно упал по OOM и перезапустился оркестратором, чем медленно умирал в свопе, утягивая за собой соседей. Подробнее про связку GC, GOMEMLIMIT и page cache — в главах Память в проде и API памяти.

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

• Что такое 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: быстрый перезапуск вместо медленной деградации всех сервисов.