Читайте также:
|
|
Алгоритм FIFO
Найпростішим у реалізації (за винятком алгоритму випадкового заміщення) є алгоритм FIFO. Він дозволяє замінити сторінку, яка перебувала у пам'яті найдовше.
Для реалізації такого алгоритму досить підтримувати у пам'яті список усіх сторінок, організований за принципом FIFO-черги (звідси й назва алгоритму). Коли сторінку завантажують у пам'ять, її додають у хвіст черги, у разі заміщення її вилучають з голови черги.
Основними перевагами цього алгоритму є те, що він не потребує апаратної підтримки (тому для архітектур, які такої підтримки не надають, він може бути єдиним варіантом реалізації заміщення сторінок).
Головним недоліком алгоритму FIFO є те, що він не враховує інформації про використання сторінки. Такий алгоритм може вибрати для вилучення, наприклад, сторінку із важливою змінною, котра вперше отримала своє значення на початку роботи, і з того часу її постійно використовують та модифікують. Вилучення такої сторінки із пам'яті призводить до того, що система буде негайно змушена знову звернутися по неї на диск.
Оптимальний алгоритм
Є алгоритм заміщення сторінок, оптимальність якого теоретично доведена (тобто він буде гарантовано кращим за будь-який інший алгоритм). Він зводиться до таких дій: замінити сторінку, яку не використовуватимуть найдовше.
На жаль, у загальному випадку реалізувати оптимальний алгоритм заміщення сторінок неможливо, бо він вимагає знання того, як у майбутньому буде поводитися процес (цим він схожий на інший теоретично оптимальний алгоритм - алгоритм планування STCF, описаний у розділі 4).
З іншого боку, якщо є конкретний набір сторінок для процесу, можна його запустити і зібрати інформацію про поведінку кожної сторінки; під час наступних запусків можна заміщувати сторінки оптимально. Це може бути корисно для оцінки продуктивності алгоритмів заміщення (під час тестування алгоритму завжди корисно знати, наскільки він гірший від оптимального для конкретних умов).
Алгоритм LRU
Головною особливістю оптимального алгоритму (крім використання знання про майбутнє, що на практиці реалізувати не можна) є те, що він грунтується на збереженні для кожної сторінки інформації про те, коли до неї зверталися востаннє. Збереження цієї інформації за умови заміни майбутнього часу на минулий привело до найефективнішого алгоритму з тих, які можна реалізувати - алгоритму LRU (Least Recently Used — алгоритм заміщення сторінки, не використовуваної найдовше). Формулюють його так: замінити сторінку, що не була використана упродовж найбільшого проміжку часу.
Основні труднощі під час використання LRU-алгоритму полягають у тому, що його складно реалізувати, оскільки потрібно зберігати інформацію про кожне звертання до пам'яті так, щоб не страждала продуктивність. Потрібна набагато серйозніша апаратна підтримка, ніж наявність біта модифікації або асоціативна пам'ять. Таку підтримку можуть забезпечувати тільки деякі спеціалізовані архітектури. Розглянемо деякі можливі варіанти реалізації LRU-алгоритму.
• Можна організувати всі номери сторінок у вигляді двозв'язного списку. Під час кожного звертання до сторінки її вилучають зі списку (можливо, із середини) і поміщають у його початок. Тому сторінка, до якої зверталися найпізніше, буде завжди на початку списку, а та, до якої не зверталися найдовше (тобто жертва), — позаду.
• Можна організувати в процесорі глобальний лічильник (завдовжки, наприклад, 64 біти), збільшувати його на кожній інструкції та зберігати у відповідному елементі таблиці сторінок у разі звертання до кожної сторінки. Тоді потрібно замінювати сторінку із найменшим значенням лічильника.
Основний недолік цих підходів - низька продуктивність.
Дата добавления: 2015-04-12; просмотров: 109 | Поможем написать вашу работу | Нарушение авторских прав |