--- title: "За пределами физической памяти: page fault и вытеснение" description: "До этого момента мы делали вид, что вся память программы целиком лежит в физической RAM. Удобно для объяснения, но в жизни так не бывает. Представьте сервер с 16 ГБ оперативки, на…" canonical: https://graphlms.ru/os/book/swapping course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # За пределами физической памяти: page fault и вытеснение > Источник: https://graphlms.ru/os/book/swapping — курс «Операционные системы», GraphLMS. ## Зачем выходить за пределы RAM До этого момента мы делали вид, что вся память программы целиком лежит в физической RAM. Удобно для объяснения, но в жизни так не бывает. Представьте сервер с 16 ГБ оперативки, на котором крутятся десятки процессов, и каждый «думает», что у него есть огромное приватное адресное пространство (про эту иллюзию мы говорили в главе [Адресное пространство](/os/book/address-space)). Если сложить всё, что хотят процессы, выйдет сильно больше 16 ГБ. Куда девать лишнее? Ответ: **часть страниц держать не в RAM, а на диске**. Диск медленный, зато большой и дешёвый. ОС создаёт на диске специальную область — **swap** (своп, «область подкачки»). Туда складываются страницы, которые сейчас не нужны. Когда страница снова понадобится — её подгрузят обратно в RAM. Аналогия: рабочий стол — это RAM, на нём помещается несколько открытых книг. Шкаф за спиной — диск (swap), книг в нём гораздо больше. Когда нужна книга из шкафа, вы убираете со стола ту, что сейчас не читаете, и кладёте нужную. Стол маленький и быстрый, шкаф большой и медленный. Вся хитрость в том, **кого убрать со стола**, чтобы пореже ходить к шкафу. ```text Иллюзия для программы Реальность ┌───────────────────────┐ ┌──────────────────────┐ виртуальное│ страница 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, запись таблицы страниц) из главы [Страничная организация](/os/book/paging). Там кроме номера физического кадра есть служебные биты. Один из них — **present bit** (бит присутствия): - `present = 1` — страница в RAM, в PTE лежит действующий номер кадра. - `present = 0` — страницы в RAM нет. Либо она в swap, либо в файле на диске, либо к ней ещё ни разу не обращались (тогда ядро выдаст новый кадр, заполненный нулями), либо адрес вообще нелегален. Различает эти случаи ядро ОС по своим записям, а не железо (см. разницу valid и present в главе [страничная организация](/os/book/paging)). ```text 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](/os/book/tlb)). Он находит PTE и смотрит на present bit. ```text 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 (глава [процесс](/os/book/process)), и процессор отдаётся другим. Важно: page fault обрабатывает именно ОС (через ловушку/trap, как в главе [Прямое исполнение с ограничениями](/os/book/limited-direct-execution)). Аппаратура только ловит факт `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 `, или `/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, «дольше всех не использовавшаяся»)** — главная рабочая идея. Выселяем ту страницу, к которой **дольше всего не обращались**. Логика опирается на **принцип локальности**: если к странице обращались только что, скорее всего обратятся снова в ближайшее время; а то, что не трогали давно, вряд ли понадобится скоро. ```text История обращений: 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 (второй шанс)**. Все кадры выстроены в кольцо, по нему ходит «стрелка». Когда нужно выселить: ```text Кольцо кадров. У каждого — 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 уже актуальна — выселить можно мгновенно, без записи на диск. А «грязную» (изменённую) сначала надо записать. Поэтому при прочих равных выгоднее выселять чистые страницы. | Политика | Идея | Плюс | Минус | |----------|------|------|-------| | Optimal (Belady) | выселить нужную дальше всех | теоретический максимум | требует знать будущее | | FIFO | выселить старейшую по входу | проще некуда | аномалия Belady, выгоняет нужное | | LRU | выселить давно не используемую | близко к оптимуму | дорого: метка на каждый доступ | | Clock | приближение LRU через ref-bit | дёшево, почти как LRU | чуть хуже точного LRU | ## Все политики на одном примере Возьмём строку обращений к страницам из симулятора ниже: ```text 1 2 3 4 1 2 5 1 2 3 4 5 ``` **FIFO, 3 кадра.** Выселяем самую старую по времени загрузки. ```text обращение: 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 кадра.** Памяти больше, промахов должно стать меньше? ```text обращение: 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 кадра.** Выселяем ту, к которой дольше всего не обращались. ```text обращение: 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. ```text обращение: 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 промахов, меньше быть не может. Первые три промаха неизбежны у любой политики: страниц ещё нет в памяти (их называют промахами холодного старта). | Политика | 3 кадра | 4 кадра | |---|---|---| | FIFO | 9 | 10 | | LRU | 10 | 8 | | Оптимальная | 7 | 6 | Проверьте эти числа в симуляторе в конце главы: переключите политику и число кадров. ### Как это сделано в Linux Linux не использует чистый Clock. Ядро держит страницы в двух списках: активном (недавно использованные) и неактивном (кандидаты на вытеснение) — и перемещает страницы между ними, проверяя тот же бит обращения. В новых ядрах есть вариант с несколькими поколениями (MGLRU), который многие дистрибутивы включают по умолчанию. Идея везде одна: дешёвое приближение LRU по аппаратному биту обращения. Вытеснение начинается заранее, а не в момент, когда память кончилась совсем. Фоновый поток ядра `kswapd` просыпается, когда свободной памяти становится меньше порога, и освобождает страницы в фоне. Если процесс просит память быстрее, чем `kswapd` успевает, процесс сам занимается освобождением прямо в своём запросе (direct reclaim), и это видно как внезапные задержки. ## Thrashing: когда система буксует А что, если памяти настолько мало, что **активных страниц всех процессов не влезает в RAM одновременно**? Тогда наступает состояние под названием **thrashing (трешинг, «пробуксовка»)**: ОС выселяет страницу, которая тут же снова нужна, грузит её, выселяя другую нужную, которая тут же снова нужна... Система почти всё время занята перекачкой страниц между RAM и диском, а полезной работы почти не делает. ```text Производительность системы vs степень загрузки памяти пропуск- │ ╭──────────╮ ная │ ╭─╯ ╰─╮ ← зона thrashing: способ- │ ╭─╯ ╰────╮ всё время свопим, ность │ ╭─╯ ╰── полезной работы 0 │ ╭─╯ ╲___________ │ ╭─╯ └─┴──────────────────┬──────────────────────▶ мало процессов оптимум слишком много (память переполнена) ``` Что нарисовано: сначала чем больше загрузка, тем выше отдача. Но после некоторого порога RAM перестаёт вмещать «горячие» данные, начинается непрерывный свопинг, и производительность **обрушивается** почти до нуля. Классический «сервер завис, но CPU вроде свободен» — часто это именно thrashing: ядра простаивают в ожидании диска. ## Working set: сколько памяти реально нужно Чтобы не доводить до thrashing, вводят понятие **working set (рабочее множество)** — это набор страниц, которые процесс активно использует в текущий промежуток времени. Если рабочее множество **помещается** в выданную процессу RAM — page fault'ов мало, всё летает. Если не помещается — начинается пробуксовка. Отсюда практический вывод для ОС: лучше **не запускать процесс вовсе**, чем запустить, когда суммарные рабочие множества не влезают в RAM. Это называют **admission control (контроль допуска)**: иногда правильнее держать часть процессов «на паузе», чтобы оставшиеся работали быстро, а не тормозили все разом. ## Своп в проде: его... выключают Теперь мост к реальности и к главе [Память в проде](/os/book/memory-cloud). Казалось бы, своп — спасение. Но на боевых серверах своп часто **отключают** (или сводят к минимуму). Почему? - **Своп прячет проблему, но делает её хуже.** Вместо честного «памяти не хватило» система начинает тихо тормозить из-за свопинга. Latency (задержка ответа) запросов взлетает в сотни раз. Для сервиса с SLA по времени ответа «медленно» нередко хуже, чем «упал и перезапустился». - **Предсказуемость важнее живучести.** Kubernetes долго требовал выключать своп на нодах: планировщик рассчитывает память по запросам и лимитам, а своп ломает эту арифметику. В новых версиях своп на нодах поддерживается, но включается явно и с ограничениями. - **Вместо свопа — OOM.** Когда память реально кончается, ядро Linux зовёт **OOM killer (Out Of Memory killer)** — он выбирает процесс-жертву и убивает его, освобождая RAM. Грубо, но быстро и предсказуемо: один сервис умер и перезапустился, остальные живы и быстры. Подробно про OOM, лимиты cgroups и контейнеры — в главе [Память в проде](/os/book/memory-cloud). При этом сам механизм present-bit и page fault **никуда не девается даже без свопа**. Он работает постоянно: при первом обращении к свежевыделенной памяти (демандная подкачка — страница выдаётся «по требованию»), при работе с файлами через `mmap` (страницы файла подгружаются с диска по page fault'у), при разделяемых страницах. Так что page fault — это не «авария», а несущая конструкция всей виртуальной памяти. ### Go-ракурс Для Go-сервиса правило простое: **рабочее множество должно помещаться в RAM**. Если куча Go начинает уходить в своп, сборщик мусора, который обходит всю кучу, и обычные обращения к памяти превращаются в дисковые операции, и p99 задержки вырастает на порядки. На практике лучше настроить лимиты памяти (`GOMEMLIMIT`, лимиты контейнера) так, чтобы при нехватке процесс честно упал по OOM и перезапустился оркестратором, чем медленно умирал в свопе, утягивая за собой соседей. Подробнее про связку GC, `GOMEMLIMIT` и page cache — в главах [Память в проде](/os/book/memory-cloud) и [API памяти](/os/book/memory-api). > Интерактивный симулятор «Вытеснение страниц»: Поток обращений прогоняется через кадры памяти. Переключай политику (FIFO/LRU/Clock/OPT) и число кадров — смотри, как меняется число промахов. Запустить: https://graphlms.ru/os/book/swapping > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/swapping ## Частые ошибки - Считать 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 низкая? Ответы. (1) 1 2 3 — три промаха; 1 — попадание; 4 — промах, выселяем 1 → [2, 3, 4]; 1 — промах, выселяем 2 → [3, 4, 1]; 2 — промах, выселяем 3. Итого 6. (2) 1 2 3 — три промаха; 1 — попадание; 4 — промах, выселяем 2 (давно не трогали) → [3, 1, 4]; 1 — попадание; 2 — промах, выселяем 3. Итого 5. (3) Нет: так ядро лениво выдаёт память при первом обращении. (4) Thrashing: процессы ждут диск на page fault'ах, процессор простаивает. ## Что спрашивают на собесе - **Что такое 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: быстрый перезапуск вместо медленной деградации всех сервисов. ## Вопросы для самопроверки **Квиз «Page fault и вытеснение страниц»** 1. Что аппаратура делает, когда обращение идёт к странице с present bit = 0? - Пишет страницу в swap - Сразу убивает процесс - Возвращает нули и продолжает - Генерирует page fault и зовёт ОС (верно) - Пояснение: present = 0 значит, что страницы нет в RAM, и железо не знает физического адреса. Оно поднимает ловушку (page fault), а решает ОС: подгрузить страницу с диска, обновить PTE и повторить инструкцию. 2. Почему в реальных системах не используют ТОЧНЫЙ LRU? - Он требует обновлять метаданные при каждом обращении к памяти — слишком дорого (верно) - Он даёт больше page fault'ов, чем FIFO - Он подвержен аномалии Belady - Он работает только с маленькой памятью - Пояснение: Чтобы знать порядок последних обращений, точный LRU должен реагировать на каждый доступ к памяти (метка/перемещение в списке). Обращений миллиарды в секунду — это неподъёмно, поэтому берут приближение Clock на основе reference bit. 3. Что характерно для алгоритма Clock (second-chance)? (несколько вариантов) - Требует знать будущие обращения - Даёт странице с R=1 второй шанс, сбрасывая бит (верно) - Выселяет страницу, у которой R=0 (верно) - Использует reference bit, который ставит аппаратура (верно) - Пояснение: Clock — дешёвое приближение LRU: ходит по кольцу кадров, страницам с R=1 даёт второй шанс (сбрасывает бит), а выселяет первую встреченную с R=0. Знание будущего нужно только оптимуму (Belady), а не Clock. 4. Что такое thrashing? - Аппаратный сбой памяти - Состояние, когда система почти всё время перекачивает страницы между RAM и диском и не делает полезной работы (верно) - Способ ускорить доступ к диску - Алгоритм вытеснения страниц - Пояснение: Thrashing наступает, когда рабочие множества процессов не влезают в RAM: ОС выселяет нужную страницу, тут же грузит её обратно, выселяя другую нужную, и так по кругу. CPU простаивает в ожидании диска, производительность обрушивается. 5. Почему на боевых серверах (в т.ч. Kubernetes) своп часто отключают? - Своп даёт непредсказуемую latency и прячет нехватку памяти (верно) - Без свопа исчезает механизм page fault - Предпочитают честный OOM kill и быстрый перезапуск (верно) - Своп ломает арифметику лимитов памяти оркестратора (верно) - Пояснение: Своп маскирует нехватку памяти медленной деградацией (latency взлетает) и ломает расчёт лимитов. Предсказуемее дать процессу честно упасть по OOM и перезапуститься. А вот механизм page fault никуда не девается — он работает и без свопа (демандная подкачка, mmap). 6. FIFO, 3 кадра, поток обращений 1 2 3 4 1 2. Сколько page fault'ов произойдёт? - Ответ: 6 - Пояснение: 1,2,3 — 3 промаха (заполнили память [1,2,3]). 4 — промах, выселяем 1 → [2,3,4]. 1 — промах (1 уже выселили), выселяем 2 → [3,4,1]. 2 — промах, выселяем 3 → [4,1,2]. Итого 6 промахов: FIFO выгнал страницы 1 и 2 как раз перед тем, как они снова понадобились.