Оцінка алгоритмів заміщення сторінок. Рядок посилань
Оскільки реалізація алгоритмів заміщення сторінок важлива з погляду продуктивності системи, вони ретельно досліджувалися, були виділені критерії їх порівняння і формат даних для тестування.
Критерієм для порівняння алгоритмів заміщення звичайно є рівень сторінкових переривань: що він нижчий, то кращим вважають алгоритм. Оцінку алгоритму здійснюють через підрахунок кількості сторінкових переривань, які виникли внаслідок його запуску для конкретного набору посилань на сторінки у пам’яті. Набір посилань на сторінки подають рядком посилань (reference string) із номерами сторінок. Такий рядок можливо згенерувати випадково, а можна отримати відстеженням посилань на пам’ять у реальній системі (у цьому разі даних бути зібрано дуже багато). Групу із кількох посилань, що йдуть підряд, на одну й ту саму сторінку в рядку відображають одним номером сторінки, оскільки такий набір посилань не може спричинити сторінкового переривання
У цьому розділі використовуватимемо такий рядок посилань:
1, 2, 3, 5, 2, 4, 2, 4, 3, 1, 4.
Щоб оцінити алгоритми заміщення, потрібно також зазначити кількість доступних фреймів. Чим вона більша, тим меншим буде рівень сторінкових переривань, тому алгоритми оцінюють для однакових її значень. Зазначимо, що, коли доступний один фрейм, кожен елемент рядка посилань викликатиме сторінкове переривання; з іншого боку, якщо кількість доступних фреймів дорівнює кількості різних сторінок у рядку посилань, сторінкових переривань не буде зовсім. Алгоритми оцінюватимемо для трьох доступних фреймів.
|
|
|
Алгоритм FIFO
Найпростішим у реалізації (за винятком алгоритму випадкового заміщення) є алгоритм FIFO. Він дозволяє замінити сторінку, яка перебувала у пам’яті найдовше.
На рис. 9.3 зображена робота цього алгоритму на рядку посилань (кольором тут і далі виділено сторінкові переривання).
Рис. 9.3. FIFO-алгоритм заміщення сторінок
Для реалізації такого алгоритму досить підтримувати у пам’яті список усіх сторінок, організований за принципом FIFO-черги (звідси й назва алгоритму). Коли сторінку завантажують у пам’ять, її додають у хвіст черги, у разі заміщення її вилучають з голови черги.
Основними перевагами цього алгоритму є те, що він не потребує апаратної підтримки (тому для архітектур, які такої підтримки не надають, він може бути єдиним варіантом реалізації заміщення сторінок).
Головним недоліком алгоритму FIFO є те, що він не враховує інформації про використання сторінки. Такий алгоритм може вибрати для вилучення, наприклад, сторінку із важливою змінною, котра вперше отримала своє значення на початку роботи, і з того часу її постійно використовують та модифікують. Вилучення такої сторінки із пам’яті призводить до того, що система буде негайно змушена знову звернутися по неї на диск.
|
|
|
Такий алгоритм недостатньо ефективний, і його варто використовувати тоді, коли кращого алгоритму реалізувати не вдається (або у поєднанні з іншими підходами, наприклад, з буферизацією сторінок, яку буде описано в розділі 9.5.6). Деякі інші, ефективніші алгоритми в найгіршому випадку можуть зводитися до алгоритму FIFO.
Наголосимо, однак, що жоден алгоритм заміщення не може призвести до некоректної роботи програми. Після того як сторінка буде завантажена у пам’ять із диска, робота з нею відбуватиметься так, ніби вона була в пам’яті від самого початку. Різниця полягатиме тільки у продуктивності (втім, ця різниця може виявитися дуже істотною).
Оптимальний алгоритм
Є алгоритм заміщення сторінок, оптимальність якого теоретично доведена (тобто він буде гарантовано кращим за будь-який інший алгоритм). Він зводиться до таких дій: замінити сторінку, яку не використовуватимуть найдовше. Приклад використання такого алгоритму зображено на рис. 9.4.
Рис. 9.4. Оптимальний алгоритм заміщення сторінок
На жаль, у загальному випадку реалізувати оптимальний алгоритм заміщення сторінок неможливо, бо він вимагає знання того, як у майбутньому буде поводитися процес (цим він схожий на інший теоретично оптимальний алгоритм – алгоритм планування STCF, описаний у розділі 4).
|
|
|
З іншого боку, якщо є конкретний набір сторінок для процесу, можна його запустити і зібрати інформацію про поведінку кожної сторінки; під час наступних запусків можна заміщувати сторінки оптимально. Це може бути корисно для оцінки продуктивності алгоритмів заміщення (під час тестування алгоритму завжди корисно знати, наскільки він гірший від оптимального для конкретних умов).
Алгоритм LRU
Оскільки оптимальний алгоритм заміщення сторінок прямо реалізувати неможливо, основним завданням розробників має бути максимальне наближення до оптимального алгоритму. Опишемо основні принципи такого наближення.
Головною особливістю оптимального алгоритму (крім використання знання про майбутнє, що на практиці реалізувати не можна) є те, що він ґрунтується на збереженні для кожної сторінки інформації про те, коли до неї зверталися востаннє. Збереження цієї інформації за умови заміни майбутнього часу на минулий привело до найефективнішого алгоритму з тих, які можна реалізувати – алгоритму LRU (Least Recently Used - алгоритм заміщення сторінки, не використовуваної найдовше). Формулюють його так: замінити сторінку, що не була використана упродовж найбільшого проміжку часу.
|
|
|
Рис. 9.5 ілюструє роботу цього алгоритму. По суті, LRU – це оптимальний алгоритм, розгорнутий за часом назад, а не вперед.
Рис. 9.5. LRU-алгоритм заміщення сторінок
Основні труднощі під час використання LRU-алгоритму полягають у тому, що його складно реалізувати, оскільки потрібно зберігати інформацію про кожне звертання до пам’яті так, щоб не страждала продуктивність. Потрібна набагато серйозніша апаратна підтримка, ніж наявність біта модифікації або асоціативна пам’ять. Таку підтримку можуть забезпечувати тільки деякі спеціалізовані архітектури. Розглянемо деякі можливі варіанти реалізації LRU-алгоритму.
Можна організувати всі номери сторінок у вигляді двозв’язного списку. Під час кожного звертання до сторінки її вилучають зі списку (можливо, із середини) і поміщають у його початок. Тому сторінка, до якої зверталися найпізніше, буде завжди на початку списку, а та, до якої не зверталися найдовше (тобто жертва), – позаду.
Можна організувати в процесорі глобальний лічильник (завдовжки, наприклад, 64 біти), збільшувати його на кожній інструкції та зберігати у відповідному елементі таблиці сторінок у разі звертання до кожної сторінки. Тоді потрібно замінювати сторінку із найменшим значенням лічильника.
Основний недолік цих підходів – низька продуктивність. Наприклад, якщо для поновлення лічильника або стека організовувати переривання, то оброблювач цього переривання буде виконуватися після кожної інструкції доступу до пам’яті, сповільнюючи доступ до пам’яті в кілька разів.
Годинниковий алгоритм
Дата добавления: 2018-04-05; просмотров: 464; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!