Open Library - открытая библиотека учебной информации

Открытая библиотека для школьников и студентов. Лекции, конспекты и учебные материалы по всем научным направлениям.

Категории

Компьютеры Выталкивание дольше всего не использовавшейся страницы. LRU (The Least Recently Used) Algorithm .
просмотров - 245

Оптимальный алгоритм

Одно из последствий открытия аномалии Belady - поиск оптимального алгоритма. Этот алгоритм имеет минимальную частоту fault'ов среди всœех алгоритмов. Он прост:

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

Каждая страница помечается числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка.

Этот алгоритм нереализуем. ОС не знает, к какой странице будет следующее обращение. (Ранее такие проблемы были с планированием процессов - алгоритм SJF). Для второго обращения уже можно делать прогноз на основе информации собранной после первого обращения.

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

Исходим из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего.

Ключевое отличие между FIFO и оптимальным алгоритмом в том, что один смотрит назад, а другой вперед. В случае если использовать прошлое, для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение долгого времени. Такой подход принято называть least recently used (LRU) алгоритм.

LRU часто используется и считается хорошим. Основная проблема - реализация.

Необходимо иметь связанный список всœех страниц в памяти, в начале которого будут часто используемые страницы.

Причем он должен обновляться при каждой ссылке. Много времени нужно на поиск страниц в списке. Есть вариант реализации со специальным устройством. К примеру, - иметь 64-битный указатель, который автоматически увеличивается на 1 после каждой инструкции и в таблице страниц иметь соответствующее поле, в ĸᴏᴛᴏᴩᴏᴇ заносится значение указателя при каждой ссылке на страницу. При возникновении page fault'а выгружается страница с наименьшим указателœем.

Как оптимальный алгоритм, так и LRU не страдают от аномалии Белœейди. Существует класс алгоритмов, называемых стековыми (stack) алгоритмами, которые не проявляют аномалии Белœейди. Это алгоритмы, для которых множество страниц в памяти для n кадров всœегда подмножество страниц для n+1 кадра. LRU таковым является.

Заметим, что никакая реализация LRU неприемлема без специального оборудования помимо стандартных регистров. В случае если, к примеру, задействовать прерывание для модификации полей, то это будет замедлять ссылку к памяти в 10 раз.


Читайте также


  • - Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU

    Одним из приближений к алгоритму OPT является алгоритм, исходящий из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего. Ключевое отличие между FIFO и оптимальным алгоритмом заключается в том, что один смотрит назад, а... [читать подробенее]


  • - Выталкивание дольше всего не использовавшейся страницы. LRU (The Least Recently Used) Algorithm .

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