The design of the UNIX Operating System 58 страница
Аномалия Билэди (Belady)
На первый взгляд кажется очевидным , что чем больше в памяти страничных кадров, тем реже будут иметь место page faults. Удивительно, но это не всегда так. Как установил Билэди с коллегами, опреде-ленные последовательности обращений к страницам в действительности приводят к увеличению числа страничных нарушений при увеличении кадров, выделенных процессу. Это явление носит название "аномалии Билэди" или "аномалии FIFO".
|
|
|
Система с тремя кадрами (9 faults) оказывается более производительной, чем с четырьмя кадрами (10 faults), для строки обращений к памяти 012301401234 при выборе стратегии FIFO.
Рис. 10.1. Аномалия Билэди: (a) - FIFOс тремя страничными кадрами;
(b) - FIFO с четырьмя страничными кадрами
Аномалию Билэди следует считать скорее курьезом, чем фактором, требующим серьезного отношения, который иллюстрирует сложность ОС, где интуитивный подход не всегда приемлем.
|
|
|
Оптимальный алгоритм (OPT)
Одним из последствий открытия аномалии Билэди стал поиск оптимального алгоритма , который при за-данной строке обращений имел бы минимальную частоту page faults среди всех других алгоритмов. Та-кой алгоритм был найден. Он прост: замещай страницу, которая не будет использоваться в течение само-го длительного периода времени.
|
|
|
Каждая страница должна быть помечена числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка. Выталкиваться должна страница, для которой это число наи-большее.
Этот алгоритм легко описать, но реализовать невозможно. ОС не знает, к какой странице будет следую-щее обращение. (Ранее такие проблемы возникали при планировании процессов - алгоритм SJF).
|
|
|
| Основы операционных систем | 92 |
Зато мы можем сделать вывод, что для того, чтобы алгоритм замещения был максимально близок к иде-альному алгоритму, система должна как можно точнее предсказывать обращения процессов к памяти. Данный алгоритм применяется для оценки качества реализуемых алгоритмов.
Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU
Одним из приближений к алгоритму OPT является алгоритм, исходящий из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего.
Ключевое отличие между FIFO и оптимальным алгоритмом заключается в том, что один смотрит назад, а другой вперед . Если использовать прошлое для аппроксимации будущего, имеет смысл замещать стра-ницу, которая не использовалась в течение самого долгого времени. Такой подход называется least recently used алгоритм (LRU). Работа алгоритма проиллюстрирована на рис . рис. 10.2. Сравнивая рис. 10.1 b и 10.2, можно увидеть, что использование LRU алгоритма позволяет сократить количество стра-ничных нарушений.
Рис. 10.2. Пример работы алгоритмаLRU
LRU - хороший, но труднореализуемый алгоритм. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут хранится недавно использованные страницы. Причем этот список дол-жен обновляться при каждом обращении к памяти. Много времени нужно и на поиск страниц в таком списке.
В [Таненбаум, 2002] рассмотрен вариант реализации алгоритма LRU со специальным 64-битным указа-телем, который автоматически увеличивается на единицу после выполнения каждой инструкции, а в таб-лице страниц имеется соответствующее поле, в которое заносится значение указателя при каждой ссылке на страницу. При возникновении page fault выгружается страница с наименьшим значением этого поля.
Дата добавления: 2021-01-21; просмотров: 120; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!