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

Оптимальный (нереализуемый)

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

Исключение недавно использованных страниц

Бит R – бит обращения, бит M – бит модификации.

Суть:

1 при запуске процесса R=0, M=0 для всех страниц.

2 При каждом прерывании по таймеру бит R сбрасывается

3 При возникновении ошибки отсутствия страницы ОС просматривает все дескрипторы страниц и делит их на четыре категории:

Класс 0: ни обращений, ни модификации

Класс 1: нет обращений, есть модификация

Класс 2: есть обращения, нет модификации

Класс 3: есть обращения, есть модификация

Алгоритм удаляет произвольную страницу низшего класса.

Алгоритм «первый пришёл, первый ушёл» (FIFO)

Страницы хранятся в связанном списке, по порядку загрузки. Выгружается та страница, которая стоит в начале списка (загружена первой)

Достоинства:

· простой алгоритм.

Второй шанс»

Как в FIFO, но если у первой страницы бит R=0, то она удаляется, а если бит R=1, то он сбрасывается, а страница отправляется в конец списка. Если ко всем страницам есть обращение – вырождается в FIFO.

Часы»

Циклический список. Если R=0, страница выгружается, на её место загружается новая. Если R=1, то R сбрасывается, стрелка идёт дальше.