<<
>>

Алгоритм LRU

В основе этой неплохой аппроксимации оптимального алгоритма лежит наблюдение, что страницы, к которым наблюдалось многократное обращение в нескольких последних командах, вероятно, также будут часто востребованы в следующих.
И наоборот, можно полагать, что страницы, к которым ранее не было обращений, не потребуются в течение долгого времени. Эта идея привела к следующему реализуемому алгоритму: когда происходит ошибка отсутствия страницы, выгружается из памяти страница, которая не использовалась дольше всего. Такая стратегия замещения страниц называется LRU (Least Recently Used — дольше всего не использовавшаяся страница).

Хотя алгоритм 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.

<< | >>
Источник: Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание. 2007

Еще по теме Алгоритм LRU:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.