Как работает принцип LRU в управлении кэшем на жестких дисках?

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

Принцип работы: garden.struchkov.dev

1. Отслеживание использования. garden.struchkov.dev Каждый элемент в кэше имеет метку времени или счётчик, который обновляется каждый раз, когда элемент используется. garden.struchkov.dev
2. Удаление устаревших элементов. garden.struchkov.dev Когда необходимо освободить место в кэше для нового элемента, удаляется элемент с наименьшим значением метки времени или счётчика, то есть наименее недавно использованный элемент. garden.struchkov.dev

Пример работы LRU с кэшем на 3 элемента: dzen.ru

1. Начальное состояние: кэш пустой. dzen.ru
2. Добавляем A: [A]. dzen.ru
3. Добавляем B: [A, B]. dzen.ru
4. Добавляем C: [A, B, C] (кэш заполнен). dzen.ru
5. Используем A: [B, C, A] (A становится недавно использованным). dzen.ru
6. Добавляем D: [C, A, D] — B вытеснен как наименее востребованный. dzen.ru