На початку цього списку повинна бути тільки що затребувана сторінка, а в кінці - найменш затребувана. Складність у тому, що цей список має оновлюватися при кожному зверненні до пам'яті. Для пошуку сторінки в списку, її видалення з нього і подальшого переміщення цієї сторінки вперед потрібно досить багато часу, навіть якщо це буде покладено на апаратне забезпечення (якщо припустити, що таке обладнання можна створити).
Проте існують інші способи реалізації LRU з використанням спеціального обладнання. Спочатку розглянемо найпростіший з цих способів. Для його реалізації апаратне забезпечення необхідно оснастити 64-розрядним лічильником С, значення якого автоматично збільшується після кожної команди. Крім цього, кожен запис в таблиці сторінок повинна мати достатньо велике поле, щоб утримувати значення цього лічильника. Після кожного звернення до пам'яті поточне значення лічильника С зберігається в записі таблиці сторінок, що відноситься до тієї сторінці, до якої було це звернення. При виникненні помилки відсутності сторінки операційна система перевіряє всі значення лічильника в таблиці сторінок, щоб знайти найменше з них. Та сторінка, до чиєї записи відноситься це значення, і буде найменш затребуваною.
Тепер розглянемо другий алгоритм роботи апаратного забезпечення LRU. У машині, що має п сторінкових блоків, апаратне забезпечення LRU може підтримувати спочатку нульову матрицю п на п бітів. Як тільки буде звернення до сторінкового блоку k, апаратура спочатку встановлює всі біти рядка k в 1, а потім обнуляє всі біти стовпця k. У будь-який момент часу рядок з найменшим двійковим значенням належить до найменш затребуваною сторінці, рядок з наступним найменшим значенням відноситься до наступної найменш затребуваною сторінці, і т. д. На рис. 3.16 показана робота цього алгоритму для чотирьох сторінкових блоків, до яких звернення відбувається в наступному порядку: 0123210323.
Після звернення до сторінці 0 виникає ситуація, показана на рис. 1, а. Після звернення до сторінці 1 виникає ситуація, показана на рис. 1, б, і т. д.
Рис. 1. Використання алгоритмом LRU матриці при зверненні до сторінок в наступному порядку: 0, 1, 2, 3, 2, 1, 0, 3, 2, 3.
При всій принципової можливості реалізації попереднього алгоритму LRU навряд чи знайдеться машина, що володіє потрібним обладнанням. Швидше за все, нам знадобиться рішення, яке може бути реалізоване в програмному забезпеченні. Одне з можливих рішень називається алгоритмом нечастого запитання - NFU (Not Frequently Used). Для його реалізації буде потрібно програмний лічильник з початковим нульовим значенням, пов'язаний з кожною сторінкою. При кожному перериванні від таймера операційна система сканує всі знаходяться в пам'яті сторінки. Для кожної сторінки до лічильника додається значення біта R, рівне 0 або 1. Лічильники дозволяють приблизно відстежити частоту звернень до кожної сторінки. При виникненні помилки відсутності сторінки для заміщення вибирається та сторінка, чий лічильник має найменше значення.
Основна проблема при використанні алгоритму NFU полягає в тому, що він ніколи нічого не забуває. Наприклад, при багатопрохідної компіляції ті сторінки, які інтенсивно використовувалися при першому проході, можуть по колишньому зберігати високі значення лічильників і при подальших проходах. Фактично якщо на перш...
