Кратко и по сути — принципы, ключевые понятия и влияние стратегий замещения.
Принципы виртуальной памяти и страничной подстановки
- Идея: каждое адресное пространство разделяется на страницы фиксированного размера; физическая память — на рамки (frames). Процессу дают вид большой непрерывной памяти, а ОС переводит виртуальные адреса в физические через таблицы страниц.
- При обращении к адресу происходит трансляция через таблицу страниц (и TLB — кеш трансляций). Если нужной страницы нет в ОЗУ, возникает page fault: ОС загружает страницу с диска (swap или файл), обновляет таблицу, возобновляет процесс.
- Производительность определяется частотой отказов страниц (page-fault rate) и временем обслуживания промаха: среднее время доступа (EAT)
$$EAT=(1-p)T_{mem}+p{T}_{pf},$$ где $p$ — вероятность промаха (page-fault rate), $T_{mem}$ — время нормального доступа, $T_{pf}$ — время обработки page fault (обычно миллисекунды).
- Локальность обращений (временная и пространственная) делает систему эффективной: рабочее множество (working set) — набор страниц, активно используемых в данный период. Если ОЗУ хватает на рабочее множество — промахи редки; иначе — трешинг (частые промахи).
Стратегии замещения страниц — что делают и как влияют
- FIFO (First-In—First-Out)
- Правило: вытесняется самая «древняя» загруженная страница.
- Плюсы: очень просто реализуется.
- Минусы: игнорирует актуальность; подвержен аномалии Белади (увеличение числа рамок может увеличить число промахов). В реальных приложениях часто хуже, чем LRU.
- LRU (Least Recently Used)
- Правило: вытесняется страница, на которую дольше всего не было обращений.
- Плюсы: хорошо использует временную локальность; в большинстве рабочих нагрузок даёт низкий уровень промахов.
- Минусы: точная реализация дорогая (поддержание упорядочивания); практическая реализация — аппаратные биты использованием/возраста (reference bits) и аппроксимации (Clock/Second-Chance).
- В реальных приложениях (циклические, повторяющиеся доступы, кэши, БД) LRU-стили хорошо работают.
- LFU (Least Frequently Used)
- Правило: вытесняется страница с наименьшей суммарной частотой обращений.
- Плюсы: учитывает долгосрочную «популярность».
- Минусы: плохо реагирует на изменяющиеся рабочие множества (старые сильно использованные страницы остаются даже если больше не нужны); требуется хранить счётчики; чувствителен к «временной» неактуальности.
- В реальности LFU редко хорош в чистом виде; полезны версии с ослаблением (decay).
- Оптимальная (Belady)
- Правило: вытесняется страница, обращение к которой случится позже всего в будущем.
- Плюсы: минимизирует количество промахов (теоретически лучшая).
- Минусы: требует знания будущих обращений — нереализуема в общем случае. Используется как эталон при анализе.
- Сравнение: многие алгоритмы (LRU-аппроксимации) стремятся к поведению, близкому к оптимальному при наличии локальности.
Практические последствия для реальных приложений
- Локализация доступа — ключ. Приложения с хорошей временной/пространственной локальностью (цикл по массиву с повторением блоков, OLTP БД с кэшированием индексных страниц) выигрывают от LRU-подобных алгоритмов и малого p.
- Последовательное одноразовое чтение больших файлов (стриминг) — большинство стратегий одинаковы, но LRU может бесполезно удерживать страницы, если нет повторного доступа; в таких случаях полезны подсказки (madvise, posix_fadvise) или алгоритмы с распознаванием стрима.
- Рабочие множества, превышающие ОЗУ → трешинг: независимо от алгоритма промахи будут частыми; решение — увеличить память, уменьшить конкуренцию, или ограничить параллелизм.
- FIFO может плохо вести себя в реальных нагрузках (особенно при смешанных паттернах) из-за Белади-аномаалии.
- LFU полезен там, где есть стабильный набор «горячих» страниц, но вреден при смене паттернов; обычно предпочитают LRU-аппроксимации.
- Аппаратные/основные реализации: современные ОС используют аппроксимации LRU (Clock, enhanced second-chance), дополнительные механизмы: dirty/clean различие (запись требует записи на диск), предварительный обмен (prefetch), HugePages для снижения накладных расходов на таблицы страниц.
- Влияние на производительность можно оценивать через EAT: даже небольшое увеличение $p$ (даже $p\sim 10^{-3}$) может увеличить время доступа на порядки, потому что $T_{pf}$ намного больше $T_{mem}$.
Практические рекомендации
- Для ОС и сервисов: использовать LRU-аппроксимации (Clock), поддерживать TLB, давать приложениям возможность подсказывать паттерны доступа (madvise), применять HugePages для больших рабочих множеств.
- Для приложений: проектировать с учётом локальности (блоковые проходы, буферизация), избегать случайного указательного доступа там, где возможен последовательный; при потоковом доступе использовать системные подсказки, чтобы не загрязнять кеш страниц.
Краткая сводка по влиянию:
- LRU (или его аппроксимации) — чаще всего лучший выбор для общих рабочих нагрузок с локальностью.
- FIFO — прост, но может сильно проигрывать (Belady).
- LFU — хорош для стабильных «популярных» страниц, плох при изменчивости.
- Оптимальная — теоретический эталон, недостижим в общем случае.
Если нужно, могу кратко описать реализацию LRU-аппроксимаций (Clock, aging) и привести формулу для расчёта EAT с примерными числовыми величинами.