Least Recently Used
Z Wikipedii
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
LRU (ang. Least Recently Used) - algorytm stronicowania.
Zastępujemy najdawniej używaną stronę
Dwie implementacje
Liczniki - do każdej pozycji w tablicy stron dołączamy rejestr czasu użycia, do procesora zaś dodajemy zegar logiczny lub licznik. Wskazania zegara są zwiększane wraz z każdym odniesieniem do pamięci. Ilekroć występuje odniesienie 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 wyjmuje się ze stosu i umieszcza na szczycie - najlepsza implementacja to dwukierunkowa lista ze wskaźnikami do czoła i do końca najwyżej 6 zmian wskaźników nie jest potrzebne przeszukiwanie listy