Механизм передачи страниц

Мы разобрали как страничная память скрывает маленький объём ОП.

Часто страницы находятся не в оперативной памяти, а на диске. Команда обращается к странице, которой нет в оперативной памяти, и получает ошибку отсутствия страницы. После ошибки, ОС загружает новую страницу в оперативку с диска и снова вызывает команду со страницы.

Если в оперативке не будет ни одной страницы программы, она все равно запустится, но уже на первой странице получит ошибку и начнёт вызывать её с диска. Такой метод работы с памятью называется вызов страниц по требованию или же demand paging.

При вызове страницы с диска, операционная система должна решить какую страницу перенести на диск. Для этого ОС использует один из двух алгоритмов: LRU или FIFO.

LRU

Least Recently Used или самая неиспользуемая. ОС прогнозирует время следующих обращений к каждой странице. На основе прогноза удаляется страница к которой дольше всего не будут обращаться.

Иногда алгоритм дает сбой: программе нужно пройти циклом через 9 страниц, но в память влезают 8. Когда программа дойдет до 7 страницы произойдет ошибка отсутствия страницы. LRU перекинет на диск страницу 0, потому что она дольше всего не использовалось, а на её место поставит страницу 8. Страница 8 попытается вызвать страницу 0 и LRU заменит страницу 1 на страницу 0. Дальше страница 0 попытается вызвать страницу 1 и так дальше.

При работе алгоритма с этой программой будут постоянно появляться ошибки отсутствия страниц. Такое состояние называется пробуксовкой или же thrashing.

FIFO

First-in First-out — первым пришёл, первым ушёл. Этот алгоритм удаляет страницу которая была загружена раньше всех.

ОС использует доработанную версию алгоритма. Для каждой страницы в оперативной памяти появляется счетчик использования. При каждой ошибке, счётчик каждой страницы в памяти увеличивается на 1. Для новых страниц счетчик сбрасывается. Алгоритм удаляет из памяти страницу с самым большим счётчиком.

Выделением и освобождением оперативной памяти занимается диспетчер памяти. Он выделяет для каждой страницы проверочный бит изменения страницы. ОС его считывает и определяет, изменялась страница или нет.
Если изменялась — записывает её на диск, если нет — удаляет.

Вызов страниц нужен на запуске программы пока многие страницы лежат на диске. Позже, почти все нужные страницы оказываются в оперативке и постепенно меняются местами.

Вызов страниц по требованию не работает для компьютеров с разделением по времени. В таких компьютерах программа работает 100 миллисекунд, потом передаёт управление другой программе. При каждом запуске программы для неё выделяется новая область памяти.

Компьютеры с разделением по времени используют принцип локальности памяти. Принцип заключается в том, что программы часто обращаются к небольшому числу страниц. Этот набор страниц называется рабочим множеством.

Рабочее множество меняется медленно, поэтому можно предсказать какие страницы понадобятся программе при новом запуске и заранее загрузить их в оперативку.

Следующая статья про сегментную память.