Виштовхування сторінки, що найдовше не використовувалась. Алгоритм LRU.

Одним з наближень до алгоритму OPT є алгоритм, витікаючий з евристичного правила, що недавнє минуле - хороший орієнтир для прогнозування найближчого майбутнього.

Ключова відмінність між FIFO і оптимальним алгоритмом полягає в тому, що один дивиться назад, а інший вперед. Якщо використовувати минуле для апроксимації майбутнього, має сенс заміщати сторінку, яка не використовувалася протягом найдовшого часу. Такий підхід називається least recently used алгоритм (LRU). Робота алгоритму проілюстрована на мал. мал. 10.2. Порівнюючи мал. 10.1 b і 10.2, можна побачити, що використання LRU алгоритму дозволяє скоротити кількість сторінкових порушень.

Рис. 12.2. Приклад роботи алгоритму LRU

LRU - хороший, але важкореалізований алгоритм. Необхідно мати зв'язаний список всіх сторінок в пам'яті, на початку якого будуть зберігається недавно використані сторінки. Причому цей список повинен оновлюватися при кожному зверненні до пам'яті. Багато часу потрібно і на пошук сторінок в такому списку.

У [Таненбаум, 2002] розглянутий варіант реалізації алгоритму LRU із спеціальним 64-бітовим покажчиком, який автоматично збільшується на одиницю після виконання кожної інструкції, а в таблиці сторінок є відповідне поле, в яке заноситься значення покажчика при кожному посиланні на сторінку. При виникненні page fault вивантажується сторінка з найменшим значенням цього поля.

Як оптимальний алгоритм, так і LRU не страждають від аномалії Біледі. Існує клас алгоритмів, для яких при одному і тому ж рядку звернень безліч сторінок в пам'яті для n кадрів завжди є підмножиною сторінок для n+1 кадру. Ці алгоритми не проявляють аномалії Біледі і називаються стековими (stack) алгоритмами.