Управление виртуальной памятью

Виртуальная память – это фундаментальный механизм современных операционных систем, позволяющий каждой программе видеть логически непрерывное адресное пространство, абстрагированное от реальной (физической) оперативной памяти и вторичных накопителей. Такое “расслоение” адресов обеспечивает изоляцию процессов, гибкое распределение ресурсов, защиту данных и эффективную работу с большими объёмами информации. Для подготовки к ЕГЭ по информатике тема важна тем, что объединяет несколько экзаменационных блоков: устройство ОС, представление данных и адресов, модели вычислений, алгоритмы и оценку эффективности.

Теоретические основы

Память как иерархия

Иерархия памяти включает регистры → кэш-память (L1/L2/L3) → оперативную память (RAM) → вторичное хранилище (SSD/HDD). Виртуальная память «склеивает» эту иерархию в удобную для приложения модель: виртуальные адреса отображаются в физические кадры (frames), а при нехватке RAM редко используемые страницы выгружаются во внешнее хранилище (swap/подкачка).

Адресные пространства и страничная организация

• Виртуальный адрес – адрес из пространства процесса (логический).

• Физический адрес – реальный адрес ячейки в RAM.

• Виртуальное адресное пространство разбивается на страницы одинакового размера (обычно степени двойки: 4 KiB, 2 MiB, 1 GiB и т. д.).

• Оперативная память разбита на кадры такого же размера.

• Отображение «виртуальная страница → физический кадр» хранится в таблицах страниц (Page Tables).

Декомпозиция виртуального адреса для страничной организации:

виртуальный адрес = <номер страницы> : <смещение внутри страницы>

Размер поля «смещение» равен log2(размер_страницы). Остальные старшие биты – номер страницы.

Таблицы страниц и их многоуровневая организация

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

TLB и эффективное время доступа

Поскольку поиск в таблицах страниц дорогой (несколько обращений к памяти), в процессоре есть TLB (Translation Lookaside Buffer) – небольшой кэш преобразований «виртуальная страница → физический кадр».

• Промах TLB (TLB miss) ведёт к чтению таблиц страниц (дороже).

• Попадание TLB (TLB hit) ускоряет обращение: адрес сразу переводится и доступ происходит почти как к физической памяти.
  Эффективное время доступа (EMAT) зависит от вероятности попадания в TLB и числа необходимых обращений к памяти при промахе (без учёта страничной ошибки).

Страничные ошибки и подкачка

Если виртуальная страница не находится в RAM (её нет в таблице или она помечена как «внешняя»), возникает страничная ошибка (page fault). ОС:

• выбирает жертву (кадр для освобождения) по алгоритму замещения;

• при необходимости сбрасывает изменённую страницу на диск;

• загружает требуемую страницу с диска;

• обновляет таблицу страниц;

• возобновляет выполнение процесса.

Частые страничные ошибки приводят к трэшингу (thrashing) – система больше занимается подкачкой, чем полезной работой.

Алгоритмы замещения страниц

• FIFO: вытесняется страница, которая дольше всех находится в памяти. Просто, но подвержено аномалии Белади.

• LRU (Least Recently Used): вытесняется давно не использованная страница. Хорошее приближение к оптимальному, но требует поддержки статистики.

• Clock/Second Chance: аппроксимация LRU с «часовой» стрелкой и битом использования.

• NRU, LFU и др.: компромиссы между точностью и накладными расходами.

Рабочее множество и управление локальностью

Рабочее множество (working set) – множество страниц, реально используемых процессом за последний интервал (окно) обращений. Поддерживая в памяти хотя бы размер рабочего множества, ОС снижает вероятность трэшинга. При нехватке RAM система регулирует «резидентный набор» страниц, интервал окна и политику замещения.

Защита и расширенные механизмы

• Биты доступа в PTE: чтение/запись/исполнение, «грязная»/«использованная», «присутствует/не присутствует».

• Изоляция: разные процессы – разные таблицы страниц; ядро – свой защищённый диапазон.

• Копирование при записи (Copy-on-Write): страницы делятся между процессами как «только чтение», а при попытке записи – дублируются.

• Память, отображённая на файл (memory-mapped files): страница ↔ участок файла, удобны для загрузки данных «по требованию».

• Большие страницы (Huge Pages): снижение давления на TLB за счёт увеличения размера страницы (меньше записей, но грубее гранулярность).

Правила корректного использования виртуальной памяти (практическая памятка)

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

2. Оптимизируйте структуру данных под размер страницы: уменьшайте «скачки» по памяти, избегайте случайного доступа (особенно в больших массивах и хэш-таблицах).

3. Снижайте давление на TLB: по возможности используйте последовательный доступ; при интенсивных потоках обращений рассмотрите большие страницы.

4. Минимизируйте объём модифицируемых страниц: копирование при записи выгодно, если записи редки.

5. Следите за рабочим множеством: чрезмерная конкуренция за кадры ведёт к трэшингу – иногда выгоднее ограничить параллелизм или разбить задачу на батчи.

6. Понимайте стоимость промаха: случайный доступ к большой структуре на диске (через подкачку) дороже на порядки; кеширование и предварительная выборка (prefetch) спасают.

7. Разделяйте ответственность: алгоритмы и структуры – на совести программиста; выделение кадров, замещение и защита – на стороне ОС и MMU.

Связь с подготовкой к ЕГЭ

• Адреса и данные: двоичная арифметика, степени двойки, разбиение адресов на поля (страница/смещение).

• Алгоритмика: моделирование замещения страниц (FIFO/LRU/Clock), счёт событий (промахов), оценка эффективности.

• ОС: понятия процесса, памяти, подкачки, таблиц страниц, защиты.

• Оценка производительности: вычисление эффективного времени доступа, доли промахов TLB, анализа локальности.

Пять упражнений (с подробным разбором)

Упражнение 1. Разбор виртуального адреса на номер страницы и смещение
Условие. Страничная организация: размер страницы 4 KiB. Дан 32-битный виртуальный адрес 0x00AF3C2D.

1. Сколько бит отводится под смещение?
2. Определите номер виртуальной страницы и смещение (в шестнадцатеричном виде).

1. 4 KiB = 4096 = 2^12, значит 12 бит – смещение; оставшиеся 20 бит – номер страницы.
2. Смещение – младшие 12 бит адреса: 0xC2D. Номер страницы – старшие 20 бит: 0x00AF3.

Упражнение 2. Подсчёт размеров таблицы страниц и числа кадров
Условие. Виртуальное адресное пространство – 32 бита, размер страницы – 4 KiB, размер записи таблицы страниц (PTE) – 4 байта. Физическая память – 512 MiB.

1. Сколько записей в одноуровневой таблице страниц процесса?
2. Каков её размер в памяти?
3. Сколько кадров в физической памяти?

1. Число виртуальных страниц: 2^(32−12) = 2^20 = 1 048 576.
2. Размер PTE 4 байта: 1 048 576 × 4 = 4 MiB.
3. Число кадров: 512 MiB / 4 KiB = (512×1024 KiB)/4 KiB = 131 072 кадра.

Упражнение 3. Моделирование замещения страниц: FIFO vs LRU
Условие. Даны обращения к страницам:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3
Размер рамок (кадров) памяти процесса – 3. Определите число страничных ошибок для FIFO и LRU.

Решение (краткий пошаговый анализ).

• FIFO (первыми вытесняем самые старые): при последовательной симуляции получаем 10 промахов.
• LRU (вытесняем давно не использованные): при той же симуляции – 9 промахов.
  Вывод. LRU эффективнее FIFO на данной последовательности (снижает число промахов).
  Ответ. FIFO – 10, LRU – 9. 

Упражнение 4. Эффективное время доступа с учётом TLB
Условие. Время обращения к памяти T_mem = 100 нс, время поиска в TLB T_tlb = 10 нс. Используется одноуровневая таблица страниц без страничных ошибок. При попадании в TLB требуется 1 обращение к памяти (данные), при промахе – 2 (PTE + данные). Доля попаданий TLB – 95%. Найдите EMAT (Effective Memory Access Time).

Решение.

• Hit: T_hit = T_tlb + T_mem = 10 + 100 = 110 нс.
• Miss: T_miss = T_tlb + 2*T_mem = 10 + 200 = 210 нс.
• EMAT = 0.95*110 + 0.05*210 = 104.5 + 10.5 = 115 нс.
  Ответ. Эффективное время доступа ≈ 115 нс.

Упражнение 5. Рабочее множество и риск трэшинга
Условие. Для процесса за окно из 12 последних обращений последовательность страниц:
A, B, C, D, E, C, B, A, F, G, C, B

1. Определите размер рабочего множества на этом окне (количество уникальных страниц).

2. Если процессу выделено 5 кадров, оцените вероятность трэшинга.

3. Предложите способ уменьшить число страничных ошибок.

Решение.

1. Уникальные страницы во всём окне: {A, B, C, D, E, F, G} → 7.

2. Кадров 5, а рабочее множество 7 ⇒ высок риск трэшинга (страницы будут постоянно вытеснять друг друга).

3. Способы:
   

• увеличить кадры до ≥7;

• сократить активный набор (перестроить алгоритм, обрабатывать данные батчами);

• улучшить локальность (перегруппировать структуру данных, последовательный доступ);

• применить предварительную выборку и кэширование горячих данных.
  Ответ. |WS| = 7; при 5 кадрах велик риск трэшинга; уменьшать промахи за счёт расширения кадров и/или улучшения локальности/батчинга.

Ответ. |WS| = 7; при 5 кадрах велик риск трэшинга; уменьшать промахи за счёт расширения кадров и/или улучшения локальности/батчинга. 

Практические замечания для разработчика и аналитика ЕГЭ

• При вычислениях используйте степени двойки: размер страницы, смещение, число страниц – всё удобно считать в двоичном/шестнадцатеричном виде.

• Разбор адресов логичнее вести в hex: границы страниц кратны 2^k, младшие k бит – смещение.

• В задачах на замещение страниц строго фиксируйте правило (FIFO/LRU/Clock), аккуратно ведите состояние кадров и счётчик промахов.

• Для оценок времени доступа всегда выписывайте вклад каждого события (hit/miss) и его вероятность.

• Трэшинг распознаётся по резкому росту промахов и падению производительности; в ответах формулируйте конкретные меры (увеличить кадры/снизить активный набор/улучшить локальность).

Заключение

Виртуальная память – не просто «удобство» ОС, а строгая система отображений и политик, обеспечивающая изоляцию, защиту и эффективность. Понимание разбиения адреса, организации многоуровневых таблиц страниц, роли TLB, природы страничных ошибок и алгоритмов замещения позволяет осмысленно решать как учебные, так и практические задачи. Для ЕГЭ это означает уверенное владение вычислительной частью (битовые разложения, оценки времени), корректное моделирование алгоритмов и аргументированные выводы о производительности систем.