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

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

Рис. 9.4. Оптимальний алгоритм заміщення сторінок

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

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

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