Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU
Ключевое отличие между FIFO и оптимальным алгоритмом заключается в том, что один смотрит назад, а другой вперед.
Если использовать прошлое для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение самого долгого времени. Такой подход называется least recently used алгоритм (LRU). Работа алгоритма проиллюстрирована на рис. 10.2. Сравнивая рис. 10.1 b и 10.2, можно увидеть, что использование LRU алгоритма позволяет сократить количество страничных нарушений. Рис. 10.2. Пример работы алгоритма LRU |
LRU — хороший, но труднореализуемый алгоритм. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут хранится недавно использованные страницы. Причем этот список должен обновляться при каждом обращении к памяти. Много времени нужно и на поиск страниц в таком списке.
В [Таненбаум, 2002] рассмотрен вариант реализации алгоритма LRU со специальным 64-битным указателем, который автоматически увеличивается на единицу после выполнения каждой инструкции, а в таблице страниц имеется соответствующее поле, в которое заносится значение указателя при каждой ссылке на страницу. При возникновении page fault выгружается страница с наименьшим значением этого поля.
Как оптимальный алгоритм, так и LRU не страдают от аномалии Би- лэди. Существует класс алгоритмов, для которых при одной и той же строке обращений множество страниц в памяти для п кадров всегда является подмножеством страниц для п+1 кадра. Эти алгоритмы не проявляют аномалии Билэди и называются стековыми (stack) алгоритмами.
Еще по теме Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU:
- КАК ЛУЧШЕ ВСЕГО ИСПОЛЬЗОВАТЬ ЭТУ КНИГУ
- Первая страница
- И дольше века длится сон...
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- Алгоритм обработки результатов.
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Люди важнее всего
- Прогресс важнее всего
- Когда он больше всего нуждается в ее одобрении