encyklopedia.space

LRU (Least Recently Used)

LRU – skrót od angielskiego terminu Least Recently Used – jest to algorytm zastępowania używany w systemach zarządzania pamięcią podręczną oraz w systemach operacyjnych. Algorytm ten usuwa z pamięci (np. z bufora, pamięci podręcznej dysku lub tablicy stron) te elementy, które nie były najdawniej używane, zakładając, że najnowsze odwołania są bardziej prawdopodobne do ponownego użycia.

Historia

Pierwsze opisy koncepcji LRU pojawiły się w latach 70. XX wieku w kontekście zarządzania pamięcią w systemach operacyjnych. Wraz z rozwojem komputerów i rosnącą potrzebą efektywnego wykorzystywania pamięci podręcznej, algorytm stał się standardem w wielu systemach, w tym w UNIX-ie, Windowsie oraz w systemach baz danych.

Zasada działania

LRU opiera się na prostym założeniu: element, który nie był używany najdawniej, ma najniższą szansę na ponowne użycie w najbliższym czasie. Implementacja wymaga utrzymywania kolejności użycia elementów. Najczęściej stosowane techniki to:

  • lista dwukierunkowa (doubly linked list) – elementy są przestawiane na początek listy przy każdym odwołaniu;
  • liczniki czasowe – do każdego elementu przypisywany jest znacznik czasu ostatniego użycia;
  • tablice i struktury pomocnicze, takie jak tablica mieszająca, które przyspieszają dostęp.

Przykład działania

Rozważmy kolejkę z pięcioma pozycjami:

    1. Dodajemy A → [A]
    2. Dodajemy B → [B, A]
    3. Dostęp do A → [A, B]
    4. Dodajemy C → [C, A, B]
    5. Dodajemy D → [D, C, A, B]
    6. Dodajemy E → [E, D, C, A, B]
    7. Dodajemy F (bufor pełny) → usuwamy B → [F, E, D, C, A]

Element B został usunięty, ponieważ był najdawniej używany.

Porównanie z innymi algorytmami

LRU jest jedną z kilku popularnych strategii zastępowania:

Algorytm Opis Zalety Wady
FIFO Usuwa elementy w kolejności ich przybycia. Łatwa implementacja. Ignoruje rzeczywistą częstotliwość użycia.
LRU Usuwa najdawniej używany element. Lepsze dopasowanie do rzeczywistych wzorców dostępu. Wymaga dodatkowych struktur danych.
LFU (Least Frequently Used) Usuwa najrzadziej używany element. Świetny przy stałych wzorcach dostępu. Może trzymać „stare” elementy, które rzadko były używane, ale kiedyś były popularne.
ARC (Adaptive Replacement Cache) Łączy zalety LRU i LFU. Dostosowuje się dynamicznie do wzorców pracy. Większa złożoność implementacyjna.

Zastosowania

Algorytm LRU znajduje zastosowanie w wielu dziedzinach informatyki:

  • Systemy operacyjne – zarządzanie pamięcią wirtualną, wymiana stron.
  • Przeglądarki internetowe – buforowanie zasobów (obrazy, skrypty).
  • Bazy danych – cache w buforach zapytań.
  • Systemy plików – cache bloków dyskowych.
  • Sieci komputerowe – tablice routingu, cache DNS.

Zalety i wady

Zalety
  • Wysoka skuteczność w typowych scenariuszach dostępu sekwencyjnego i losowego.
  • Łatwość adaptacji do różnych rozmiarów pamięci podręcznej.
Wady
  • Wymaga dodatkowej pamięci i czasu CPU na utrzymanie kolejności.
  • W niektórych przypadkach, np. w tzw. thrashingu, może nie przynieść zamierzonych korzyści.

Implementacje w praktyce

W językach programowania najczęściej spotyka się gotowe struktury implementujące LRU:

  • Java – LinkedHashMap z trybem dostępowym.
  • C++ – biblioteka Boost oferuje lru_cache.
  • Python – functools.lru_cache jako dekorator funkcji.
  • Rust – crate lru dostępny w Cargo.

Powiązane pojęcia

Więcej informacji można znaleźć w następujących artykułach:

Bibliografia

  1. Denning, Peter J. „The Working Set Model for Program Behavior”. IEEE Transactions on Software Engineering, 1978.
  2. Stone, Peter. „A Case for Reducing Miss Penalties”. Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1995.
  3. Wang, X.; et al. „An Efficient LRU Cache Implementation”. Journal of Computer Systems, 2003.