Алгоритм LRU
Хотя алгоритм LRU теоретически реализуем, он не дешев. Для полной реализации алгоритма LRU необходимо поддерживать список всех содержащихся в памяти страниц, такой, где последняя использовавшаяся страница находится в начале списка, а та, к которой дольше всего не было обращений, — в конце. Сложность заключается в том, что список должен обновляться при каждом обращении к памяти.
Поиск страницы, ее удаление, а затем вставка в начало списка — это операции, поглощающие очень много времени, даже если они выполняются аппаратно (предположим, что необходимое оборудование можно сконструировать).Существуют и другие способы реализации алгоритма LRU с помощью специального оборудования. Для первого метода требуется оснащение компьютера 64-разрядным аппаратным счетчиком С, который автоматически инкрементируется
после каждой команды. Кроме того, каждая запись в таблице страниц должна иметь поле, достаточно большое для хранения значения счетчика. После каждого обращения к памяти текущая величина счетчика С запоминается в записи таблицы, соответствующей той странице, к которой произошла ссылка. А если возникает ошибка отсутствия страницы, операционная система проверяет все значения счетчиков в таблице страниц и ищет наименьшее. Эта страница и является дольше всего не использовавшейся.
Рассмотрим второй вариант аппаратной реализации алгоритма LRU. На машине с п страничными блоками оборудование LRU может поддерживать матрицу размером п х п бит, изначально равных нулю. Всякий раз при доступе к страничному блоку k аппаратура сначала присваивает всем битам строки k единицу, а затем приравнивает нулю все биты столбца k. В любой момент времени строка, двоичное значение которой наименьшее, является дольше всего не использовавшейся. Работа этого алгоритма продемонстрирована на рис. 4.15, где рассматриваются четыре страничных блока и следующий порядок обращения к страницам:
0123210323
После ссылки на страницу 0 мы получаем ситуацию, показанную на рис. 4.15, а; после обращения к странице 1 — на рис. 4.15, б и т. д.
Рис. 4.15. Алгоритм LRU с привлечением матрицы. Обращения к страницам происходят в последовательности: 0, 1, 2, 3, 2, 1, 0, 3, 2, 3 |
1.4.1.
Еще по теме Алгоритм LRU:
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.