45. Поняття сторінкового переривання

Коли процес робить спробу доступу до сторінки, для якої біт Р дорівнює нулю, то, відбувається апаратне переривання. Його називають сторінковим перериванням або сторінко­вою відмовою. ОС має обробити це переривання.

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

• Якщо сторінка недоступна, процес переривають, якщо доступна, знаходять вільний фрейм фізичної пам'яті та ставлять у чергу дискову операцію читан­ня потрібної сторінки в цей фрейм.

• Після читання модифікують відповідний запис таблиці сторінок (біт присут­ності покладають рівним одиниці).

• Перезапускають інструкцію, що викликала апаратне переривання.

46. Алгоритм fifo

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

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

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

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

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

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

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

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

48. Алгоритм lru

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

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

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

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

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