<<
>>

Программное моделирование алгоритма LRU

Хотя оба описанных алгоритма LRU в принципе реализуемы, очень мало (если вообще такие есть) машин оснащено подобным оборудованием, поэтому разработчики операционных систем для компьютеров, не имеющих такой аппаратуры,

редко используют эти алгоритмы.

Вместо них применяется решение, программно реализуемое. Одна из разновидностей алгоритма LRU называется NFU (Not Frequently Used — редко использовавшаяся страница). Для него необходим программный счетчик, связанный с каждой страницей в памяти, изначально равный нулю. Во время каждого прерывания от таймера операционная система исследует все страницы в памяти. Бит R каждой страницы (он равен 0 или 1) прибавляется к счетчику. В сущности, счетчики пытаются отследить, как часто происходят обращения к каждой странице. При ошибке отсутствия страницы для замещения выбирается страница с наименьшим значением счетчика.

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

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

К счастью, небольшая доработка алгоритма NFU наделяет его способностью моделировать алгоритм LRU достаточно хорошо. Изменение сводится к двум модификациям. Во-первых, каждый счетчик перед прибавлением бита R сдвигается вправо на один разряд. Во-вторых, бит R вдвигается в крайний слева, а не в крайний справа разряд счетчика.

На рис.

4.16 продемонстрировано, как работает видоизмененный алгоритм, известный под названием алгоритма старения (aging). Предположим, после первого такта часов биты R для страниц от 0 до 5 имеют значения 1, 0, 1,0, 1, 1 соответственно (у страницы 0 бит R равен 1, у страницы 1 — 0, у страницы 2 — 1 и т. д.). Другими словами, между тактом 0 и тактом 1 произошло обращение к страницам 0, 2, 4 и 5, их биты R приняли значение 1, остальные сохранили значение 0. После того как шесть соответствующих счетчиков сдвинулись на разряд и бит R занял крайнюю слева позицию, счетчики получили значения, показанные на рис. 4.16, а. Остальные четыре колонки рисунка изображают шесть счетчиков после следующих четырех тактов часов.

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

Эта схема отличается от алгоритма LRU в двух отношениях. Рассмотрим страницы 3 и 5 на рис. 4.16, д. Ни к одной из них не было обращений за последние два такта, к обеим было обращение за предшествующий такт. Следуя алгоритму LRU, при удалении страницы из памяти мы должны выбрать одну из двух. Проблема в том, что мы не знаем, к какой из них позже имелось обращение в интервале между тактами 1 и 2. Записывая только один бит за промежуток времени, мы теряем возможность отличить более ранние от более поздних обращений в этом

интервале времени. Все, что мы можем сделать, — это выгрузить страницу 3, так как к странице 5 также обращались двумя тактами раньше, а к странице 3 — нет.

Рис. 4.16. Алгоритм старения программно моделирует алгоритм LRU. Показаны шесть

страниц после пяти тактов часов

Второе отличие между алгоритмом LRU и алгоритмом старения заключается в том, что в последнем счетчик имеет конечное число разрядов, например 8. Предположим, что каждая из двух страниц получила нулевое значение счетчика. В данной ситуации мы лишь случайным образом можем выбрать одну из них. На самом деле не исключено, что к одной странице в последний раз обращались 9 тактов назад, а к другой — 1000 тактов назад. И мы не имеем возможности увидеть это. На практике, однако, обычно достаточно 8 бит при такте системных часов около 20 мс. Если к странице не обращались в течение 160 мс, очень вероятно, что она не нужна.

1.5.

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

Еще по теме Программное моделирование алгоритма LRU:

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