Моделирование LRU в программном обеспечении

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

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

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

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

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

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

Рис. 3.16. Алгоритм старения является программной моделью алгоритма ИЗЫ. Здесь показаны шесть страниц в моменты пяти таймерных прерываний, обозначенных буквами от а до д


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

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

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

3.4.6.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Моделирование LRU в программном обеспечении:

  1. Программное обеспечение
  2. Богомазова Г.Н.. Установка и обслуживание программного обеспечения персональных компьютеров, серверов, периферийных устройств и оборудования, 2015
  3. Эд САЛЛИВАН. ВРЕМЯ — ДЕНЬГИ Создание команды разработчиков, программного обеспечения, 2001
  4. Том ДеМарко. Вальсируя с Медведями Управление рисками в проектах по разработке программного обеспечения, 2005
  5. Алистэр Коуберн. Люди как нелинейные и наиболее важные компоненты в создании программного обеспечения, 1999
  6. 2.4.1. Программный анализатор
  7. КОНЦЕПЦИЯ ПРОГРАММНО - РОЛЕВАЯ
  8. 2.4.1. Программный анализатор
  9. Перевод программных вопросов в анкетные
  10. Глава 39 О ПРОГРАММНЫХ СВОЙСТВАХ ХУДОЖЕСТВЕННОЙ ЛИТЕРАТУРЫ
  11. Моделирование
  12. МОДЕЛИРОВАНИЕ
  13. Глава 4. Роль моделирования в социологии
  14. МОДЕЛИРОВАНИЕ ИЛИ ПОДРАЖАНИЕ?
  15. Тема 12. Иконологическое моделирование социальных процессов
  16. Уровни моделирования
  17. 12.1. Иконологическое моделирование
  18. СОЦИАЛЬНОЕ МОДЕЛИРОВАНИЕ
  19. Тема 4. Роль моделирования в социологии