Least Recently Used

LRU (ang. Least Recently Used) - algorytm stronicowania polegający na zastępowaniu w cache'u w pierwszej kolejności strony używanej najdawniej. Wymaga on informacji o tym, kiedy poszczególne strony były używane, co jest procesem kosztownym czasowo, jeśli chce się uzyskać pewność, że wyrzuca się rzeczywiście stronę używaną najdawniej. Do przechowywania czasu użycia stron stosuje się różne metody, z których dwa zostały pokrótce opisane poniżej.

Dwie implementacje

Liczniki

Do każdej pozycji w tablicy stron dołączany jest rejestr czasu użycia, do procesora zaś dodaje się zegar logiczny lub licznik. Wskazania tego zegara są inkrementowane wraz z każdym odwołaniem do pamięci. Ilekroć występuje odwołanie do pamięci, tylekroć zawartość rejestru zegara jest kopiowana do rejestru czasu użycia należącego do danej strony w tablicy stron.

Stos

Przy każdym odwołaniu do strony jej numer zdejmuje się ze stosu i umieszcza na jego szczycie. Najlepszą implementacja tej metody jest dwukierunkowa lista ze wskaźnikami do czoła i do jej końca. W tym przypadku wykonując operację na stosie wystarczy wykonać najwyżej 6 zmian wskaźników, a przeszukiwanie listy jest zbędne.