Страничные отказы, замещение страниц, биты A и D

Подкачка по требованию

Страница загружается в память только тогда, когда к ней обратились (demand paging). Если физическая память кончилась, ядро освобождает кадр — вытесняет какую-то страницу на диск: в файл подкачки (swap) для анонимной памяти или обратно в файл для отображённых файлов.

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

OPT (оптимальный, алгоритм Белади)

Вытеснить страницу, которая понадобится позже всех. Минимум отказов, но требует знать будущее — используется как эталон.

FIFO

Вытеснить страницу, загруженную раньше всех. Просто, но может выбросить активно используемую страницу. Подвержен аномалии Белади: больше кадров — иногда больше отказов.

LRU (Least Recently Used)

Вытеснить страницу, к которой дольше всего не обращались. Хорошо приближает OPT. Но точный LRU требует отмечать время каждого обращения — аппаратура этого не делает. Зато она умеет ставить бит A — и на нём строятся приближения LRU.

«Часы» (второй шанс)

Кадры по кругу, стрелка указывает на кандидата:

• если у страницы A = 1 — сбросить A в 0 («второй шанс») и сдвинуть стрелку;
• если A = 0 — вытеснить.

Буква w — запись: у страницы ставится бит D. Обратите внимание, когда вытеснение требует записи на диск.

NRU (Not Recently Used)

Периодически (по таймеру) ядро сбрасывает биты A. При вытеснении страницы делятся на 4 класса по (A, D):

Вытесняется случайная страница из наименьшего непустого класса.

Рабочее множество

Множество страниц, к которым процесс обращался за последние Δ единиц времени. Если сумма рабочих множеств больше памяти — пробуксовка (thrashing): система занята подкачкой, а не работой.

Страничный демон

Ждать, пока память кончится совсем, и только тогда искать жертву — медленно: процесс, вызвавший отказ, будет ждать записи на диск. Поэтому ядро держит запас свободных кадров. Этим занимается страничный демон — поток ядра (в Linux kswapd, по одному на узел памяти; в BSD — pagedaemon):

• просыпается, когда свободных кадров меньше нижнего порога (low watermark);
• просматривает страницы, используя бит A (в Linux — списки активных и неактивных страниц), выбирает давно не использовавшиеся;
• грязные (D = 1) отправляет на запись, чистые сразу освобождает;
• работает, пока не наберётся верхний порог (high watermark).

Если демон не справляется, процессы сами занимаются освобождением (direct reclaim), а в крайнем случае ядро запускает OOM killer.

Биты A и D: кто и как

Это ответ на задачу 5 экзамена.

Бит доступа (A, accessed / referenced):

1. Страничный демон периодически проходит по страницам: смотрит A и сбрасывает его.
2. Если к следующему проходу A снова 1 — страница используется (активная); если 0 — давно не использовалась, кандидат на вытеснение.
3. Так ядро приближает LRU (алгоритмы «часы», NRU, активный и неактивный списки Linux).
4. Сбросив A, ядро должно сбросить запись TLB для этой страницы: пока трансляция в TLB, процессор не обновляет бит в памяти.

Бит грязности (D, dirty / modified):

1. При вытеснении: если D = 0, на диске (в файле или swap) уже есть точная копия — кадр можно освободить без записи. Если D = 1 — страницу сначала нужно записать.
2. Для отображённых файлов и кеша страниц: потоки записи (writeback; в старых ядрах pdflush/bdflush) периодически записывают грязные страницы в файл; msync, fsync, sync — по запросу.
3. После записи ядро сбрасывает D (и запись TLB).
4. Алгоритм замещения предпочитает чистые страницы: их вытеснение дешевле.

Итог

• Подкачка по требованию: страничный отказ → найти кадр → при нехватке вытеснить жертву → загрузить страницу.
• Алгоритмы: OPT (эталон), FIFO (аномалия Белади), LRU, «часы», NRU по классам (A, D).
• Страничный демон держит запас свободных кадров между порогами.
• A и D ставит аппаратура; ядро сбрасывает A, чтобы находить неиспользуемые страницы, и смотрит D, чтобы решить, писать ли страницу на диск.