Алгоритм LRU

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

Головною особливістю оптимального алгоритму (крім використання знання про майбутнє, що на практиці реалізувати не можна) є те, що він ґрунтується на збереженні для кожної сторінки інформації про те, коли до неї зверталися востаннє. Збереження цієї інформації за умови заміни майбутнього часу на минулий привело до найефективнішого алгоритму з тих, які можна реалізувати – алгоритму LRU (Least Recently Used - алгоритм заміщення сторінки, не використовува­ної найдовше). Формулюють його так: замінити сторінку, що не була використана упродовж найбільшого проміжку часу.

Рис. 9.5 ілюструє роботу цього алгоритму. По суті, LRU – це оптимальний алгоритм, розгорнутий за часом назад, а не вперед.

Рис. 9.5. LRU-алгоритм заміщення сторінок

Основні труднощі під час використання LRU-алгоритму полягають у тому, що його складно реалізувати, оскільки потрібно зберігати інформацію про кожне звертання до пам’яті так, щоб не страждала продуктивність. Потрібна набагато серйозніша апаратна підтримка, ніж наявність біта модифікації або асоціативна пам’ять. Таку підтримку можуть забезпечувати тільки деякі спеціалізовані архітектури. Розглянемо деякі можливі варіанти реалізації LRU-алгоритму.

Можна організувати всі номери сторінок у вигляді двозв’язного списку. Під час кожного звертання до сторінки її вилучають зі списку (можливо, із середини) і поміщають у його початок. Тому сторінка, до якої зверталися найпізніше, буде завжди на початку списку, а та, до якої не зверталися найдовше (тобто жертва), – позаду.

Можна організувати в процесорі глобальний лічильник (завдовжки, наприклад, 64 біти), збільшувати його на кожній інструкції та зберігати у відповідному елементі таблиці сторінок у разі звертання до кожної сторінки. Тоді потрібно замінювати сторінку із найменшим значенням лічильника.

Основний недолік цих підходів – низька продуктивність. Наприклад, якщо для поновлення лічильника або стека організовувати переривання, то оброблювач цього переривання буде виконуватися після кожної інструкції доступу до пам’яті, сповільнюючи доступ до пам’яті в кілька разів.

Дата добавления: 2014-01-05