Стратегии решения задачи замещения страниц при управлении виртуальной памятью

1. Принцип оптимальности.

Надо выталкивать ту страницу, к которой дольше всего не будет обращений. Как это можно определить? Никак!

Стратегия не реализуется.

2. Выталкивание случайной страницы.

Достоинство: быстрое решение с маленькими накладными расходами.

Недостатки: может возрасти частота прерываний (выталкиваем нужную страницу).

Используется крайне редко.

3. Принцип FIFO. (первая партия на приход — первая в расход first in, first out)

Красивое решение, обоснования нет.

Достоинство: достаточно быстрое решение.

Недостатки: возможна т.н. аномалия FIFO.

Используется достаточно часто.

4. Выталкивание дольше всего не использовавшейся страницы.

LRU (Least Recently Used)

Достоинство: временной анализ.

Недостатки: - накладные расходы на поддержку временных меток

- смотрит назад, а не вперед.

Используется достаточно редко.

5. Выталкивание реже всего использовавшейся страницы.

LFU (Least Frequently Used)

Будем считать число обращений к странице на заданном интервале.

Достоинство: временной анализ.

Недостатки: - накладные расходы на поддержку временных меток;

- можно вытолкнуть «свежую» страницу;

- трудно вытолкнуть «заслуженного ветерана», страницу которая сразу набрала много обращений

Используется достаточно редко.

6. Выталкивание не использовавшейся в последнее время страницы.

NUR (Not Used Recently)

Будем периодически обновлять счетчик обращений.

Достоинство: устраняем недостаток LFU.

Недостатки:- можно вытолкнуть «свежую» страницу;

- Используется достаточно редко.