Расширения: кэширование в реальных рабочих условиях

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

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

Если задуматься, речь идет о том же алгоритме Белади с измененным направ- лением времени, — только наибольший продолжительный промежуток времени относится к прошлому, а не к будущему. Он эффективно работает, потому что для приложений обычно характерна локальность обращений: выполняемая программа, как правило, продолжает обращаться к тем данным, к которым она уже обраща- лась ранее. (Легко придумать аномальные исключения из этого принципа, но они относительно редко встречаются на практике.) По этой причине в кэше обычно хранятся данные, которые использовались недавно.

Спустя долгое время после практического принятия алгоритма LRU Слитор и Тарьян показали, что для эффективности LRU можно предоставить теорети- ческий анализ, ограничивающий количество промахов относительно алгоритма отдаленного использования. Мы рассмотрим этот анализ, равно как и анализ рандомизированной разновидности LRU, при возвращении к задаче кэширования в главе 13.

4.4.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения: кэширование в реальных рабочих условиях:

  1. 1.2.1.1. Общая продолжительность рабочего времени. Неполный и сокращенный рабочий день.
  2. § 2 Условное обязательство. – Разные виды условий. – Наступление условия и его действие. – Соотношение условий. – Понятие о сроке. – Действие срока.
  3. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  4. 1.2.1.2. Режим рабочего времени. Особый режим рабочего времени.
  5. Метод расширения сознания
  6. Расширение графического метода
  7. Самовоспитание как "расширение" сознания
  8. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  9. 3.12.2. Техника расширенного восприятия
  10. Расширение внутреннего кругозора
  11. 7.2.2. Расширение полноты ответа
  12. 7.2.2. Расширение полноты ответа
  13. 2. Расширение круга наследников по закону в российском наследственном праве