Оптимальный алгоритм замещения страниц

Одна из возможных стратегий замещения страниц следующая: Замещается та страница, которая не использовалась в течение наибольшего периода времени. Это вполне оправдано с точки зрения здравого смысла: чем раньше страница последний раз использовалась, тем, по-видимому, меньше она необходима в основной памяти.

Рассмотрим пример применения данного алгоритма с той же строкой запроса и с четырьмя максимально возможными фреймами у каждого процесса:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Нетрудно видеть, что будет иметь место всего 6 отказов страниц (в отличие от алгоритма FIFO с 10 отказами страниц).

Пример использования оптимального алгоритма замещения страниц с той же строкой запроса, которая применялась на рис. 18.9 для алгоритма FIFO, приведен на рис. 11.

Рис. 11.Пример использования оптимального алгоритма замещения страниц.

Алгоритм Least Recently Used (LRU)

Данный алгоритм замещения страниц основан на следующем принципе: Замещается та страница, которая раньше всего использовалась.

Для примера со строкой запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 число отказов страниц равно всего 4.

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

Если требуется изменение в конфигурации страниц, необходимо проанализировать поля счетчиков всехэлементов таблицы страниц, чтобы определить, какую именно страницу следует заместить. Для определения элемента таблицы страниц с минимальным счетчиком требуется применить алгоритм поиска минимального элемента в массиве, сложность которого O(n),где n– длина таблицы страниц.

Пример использования алгоритма замещения страниц LRU с той же строкой запроса, что и на рис. 9 и рис. 11 для других алгоритмов, приведен на рис. 12.

Рис. 12.Пример использования алгоритма замещения страниц LRU.

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

На рис. 13 приведен пример использования стека в алгоритме LRU для хранения самых недавних обращений к страницам.

Рис. 13.Использование стека в алгоритме LRU для хранения самых недавних обращений к страницам.