LRU (Least Recently Used)
Algorytm LRU to technika stronicowania, która polega na zastępowaniu w pamięci podręcznej stron używanych najdawniej. Aby skutecznie wdrożyć ten algorytm, konieczne jest śledzenie czasu ostatniego użycia poszczególnych stron, co może być czasochłonne.
Dwie implementacje algorytmu LRU
- Liczniki: Każdej stronie przypisywany jest rejestr czasu użycia, a dodatkowo stosowany jest zegar logiczny. Zegar ten jest inkrementowany przy każdym odwołaniu do pamięci. W momencie odwołania, wartość zegara jest kopiowana do rejestru czasu użycia strony.
- Stos: Przy każdym odwołaniu do strony, jej numer jest przenoszony na szczyt stosu. Efektywną implementacją tej metody jest dwukierunkowa lista, która minimalizuje potrzebne zmiany wskaźników, eliminując konieczność przeszukiwania listy.
Algorytm LRU jest istotny w kontekście budowy systemów operacyjnych, pozwalając na efektywne zarządzanie pamięcią podręczną.
