Как видно из рассмотренного выше, поиск оптимального алгоритма замещения страниц должен быть основан на следующем критерии: необходимо добиваться уменьшения коэффициента отказов страниц p.
Оценка алгоритма может быть выполнена путем опробования его на конкретной строке обращений к памяти (строке запросов)и определения числа отказов страниц при данной строке запросов.
Во всех приводимых ниже в данном разделе примерах из области страничной организации строка запросов имеет вид:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
График зависимости числа отказов страниц от числа фреймов в основной памяти изображен на рис. 18.8.
Рис. 18.8. Зависимость числа отказов страниц от числа фреймов.
В целом, как и подсказывает здравый смысл, зависимость обратно пропорциональная: чем больше имеется фреймов, тем меньше отказов страниц. Однако случаются и аномалии в этом законе, рассмотренные далее.
Алгоритм FIFO (First-In-First-Out).Наиболее простой алгоритм замещения страниц – в качестве жертвы всегда выбирается фрейм, первым из имеющихся считанный в основную память.
Рассмотрим пример использования данного алгоритма.
Случай 1: 3 фрейма (3 страницы могут быть одновременно в памяти для одного процесса). Пусть имеются три процесса. Их таблицы страниц примут вид:
(1, 2, 3) (4, 1, 2) (5, 3, 4).
В данном случае имеет место 9 отказов страниц (проверьте в качестве упражнения).
Случай2: 4 фрейма. Пусть имеются по-прежнему три процесса. Таблицы страниц в данном случае будут иметь вид:
(1, 2, 3, 4) (5, 1, 2, 3) (4, 5)
Нетрудно проверить, что в данном случае имеет место 10 (!) отказов страниц, несмотря на то, что процесс может иметь больше свободных фреймов, чем в предыдущем случае.
Данная аномалия называется аномалией Belady.
В целом же, как уже говорилось, зависимость такова, что чем больше фреймов может иметь процесс (при достаточно большом числе фреймов), тем меньше отказов страниц.
Пример работы алгоритма FIFO для замещения страниц, при максимальном числе фреймов для процесса, равном 3, приведен на рис. 18.9.
Рис. 18.9. Пример работы алгоритма FIFO.
На рис. 18.10 изображен график зависимости числа отказов страниц от числа фреймов при алгоритме FIFO, отображающий аномалию Belady.
Рис. 18.10. Аномалия Belady при использовании алгоритма FIFO замещения страниц.
Одна из возможных стратегий замещения страниц следующая: Замещается та страница, которая не использовалась в течение наибольшего периода времени. Это вполне оправдано с точки зрения здравого смысла: чем раньше страница последний раз использовалась, тем, по-видимому, меньше она необходима в основной памяти.
Рассмотрим пример применения данного алгоритма с той же строкой запроса и с четырьмя максимально возможными фреймами у каждого процесса:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Нетрудно видеть, что будет иметь место всего 6 отказов страниц (в отличие от алгоритма FIFO с 10 отказами страниц).
Пример использования оптимального алгоритма замещения страниц с той же строкой запроса, которая применялась на рис. 18.9 для алгоритма FIFO, приведен на рис. 18.11.
Рис. 18.11. Пример использования оптимального алгоритма замещения страниц.
Алгоритм Least Recently Used (LRU)
Данный алгоритм замещения страниц основан на следющем принципе: Замещается та страница, которая раньше всего использовалась.
Для примера со сторокой запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 число отказов страниц равно всего 4.
Однако следует иметь в виду, что использование системой информации о времени последнего обращения к странице требует хранения в каждом элементе таблицы страниц значения времени последнего обращения (time stamp). Каждый элемент таблицы страниц содержит счетчик. Rаждый раз при обращении к странице через некоторый элемент таблицы страниц содержимое системных часов (clock) копируется в его поле счетчика.
Если требуется изменение в конфигурации страниц, необходимо проанализировать поля счетчиков всехэлементов таблицы страниц, чтобы определить, какую именно страницу следует заместить. Для определения элемента таблицы страниц с минимальным счетчиком требуется применить алгоритм поиска минимального элемента в массиве, сложность которого O(n),где n– длина таблицы страниц.
Пример использования алгоритма замещения страниц LRU с той же строкой запроса, что и на рис. 18.9 и рис. 18.11 для других алгоритмов, приведен на рис. 18.12.
Рис. 18.12. Пример использования алгоритма замещения страниц LRU.
Для оптимизации данного алгоритма, чтобы избежать поиска минимального элемента таблицы страниц при каждом замещении страниц, используется стековая реализация– стек номеров страниц хранится в форме двухсвязного списка. При обращении к странице она перемещается в начало списка (для этого требуется изменить 6 указателей). Преимущества данной модификации алгоритма в том, что при замещении страниц не требуется поиска.
На рис. 18.13 приведен пример использования стека в алгоритме LRU для хранения самых недавних обращений к страницам.
Рис. 18.13. Использование стека в алгоритме LRU для хранения самых недавних обращений к страницам.
