Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм LRU

Алгоритм FIFO

Найпростішим у реалізації (за винятком алгоритму випадкового заміщення) є алгоритм FIFO. Він дозволяє замінити сторінку, яка перебувала у пам'яті най­довше.

Для реалізації такого алгоритму досить підтримувати у пам'яті список усіх сторінок, організований за принципом FIFO-черги (звідси й назва алгоритму). Коли сторінку завантажують у пам'ять, її додають у хвіст черги, у разі заміщення її вилучають з голови черги.

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

Головним недоліком алгоритму FIFO є те, що він не враховує інформації про використання сторінки. Такий алгоритм може вибрати для вилучення, наприклад, сторінку із важливою змінною, котра вперше отримала своє значення на початку роботи, і з того часу її постійно використовують та модифікують. Вилучення та­кої сторінки із пам'яті призводить до того, що система буде негайно змушена зно­ву звернутися по неї на диск.

Оптимальний алгоритм

Є алгоритм заміщення сторінок, оптимальність якого теоретично доведена (тобто він буде гарантовано кращим за будь-який інший алгоритм). Він зводиться до та­ких дій: замінити сторінку, яку не використовуватимуть найдовше.

На жаль, у загальному випадку реалізувати оптимальний алгоритм заміщення сторінок неможливо, бо він вимагає знання того, як у майбутньому буде поводи­тися процес (цим він схожий на інший теоретично оптимальний алгоритм - ал­горитм планування STCF, описаний у розділі 4).

З іншого боку, якщо є конкретний набір сторінок для процесу, можна його за­пустити і зібрати інформацію про поведінку кожної сторінки; під час наступних запусків можна заміщувати сторінки оптимально. Це може бути корисно для оцін­ки продуктивності алгоритмів заміщення (під час тестування алгоритму завжди корисно знати, наскільки він гірший від оптимального для конкретних умов).

Алгоритм LRU

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

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

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

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

Основний недолік цих підходів - низька продуктивність.