Страничное замещение в BSD

Вся ОП делится на три части. Первые две фиксированы в ОП (не выгружаются) – ядро и карта памяти. Остальная часть поделена на страничные блоки, каждый из которых может быть занят текстом, данными, стеком или быть свободным. Информация о содержимом блоков содержится в карте памяти.

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

В системе поддерживается количество страниц не меньшее некоторого заданного параметра lotsfree(как правило ¼ памяти). Если становится меньше, начинается откачка страниц из памяти на диск. Если >=, то страничный демон ничего не делает – спит.

Страничный демон использует модификацию алгоритма часов.

Изначально использовался основной алгоритм с одной стрелкой.

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

При больших объемах ОП основной алгоритм работает медленно. Поэтому его заменили на алгоритм часов с двумя стрелками.

Первый проход делает первая стрелка и очищает биты использования блоков страниц. Вторая стрелка проверяет этот бит (как было при втором проходе). Если стрелки находятся очень близко, то только очень активно используемые страницы имеют шанс остаться в памяти. Если стрелки далеко (~ 359⁰), то получится основной алгоритм. Выбирается оптимальный вариант.

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