7.Характеристика основних алгоритмів заміщення сторінок.

Оптимальний алгоритмзамінює ту сторінку звернення до якої відбувалось раніше іншої, які є в даний момент в пам’яті. Але, не існує способу вираження того, яка сторінка буде останньою, тому даний алгоритм не може бути використаний на практиці. Його використовують в якості тестової задачі, відносно якої можна оцінити інші алгоритми.

Алгоритм NRUділить сторінку 4 класи в залежності від стану бітів (R-звернення, N- змінна). Вибирається будь-яка сторінка з класу з найменшим номером.

Алгоритм «другої спроби» - це модифікація алгоритму FIFO. Він перед видаленням сторінки з пам’яті перевіряє, чи використовується вона в даний момент, якщо так, то така сторінка пропускається. Це значно підвищує продуктивність.

Алгоритм «годинник» -представляє собою всього лише друге здійснення алгоритму «другої спроби». Він має ті ж самі характеристики продуктивності, але вимагає менше часу на виконання алгоритму.

Алгоритм NFU - представляє собою спробу апроксимації (наближення) алгоритму LRU. Він не дуже добрий, але є алгоритмом старіння, який набагато краще апроксимує алгоритм LRU і може бути ефективно реалізований.

В результаті аналізу двома найкращими алгоритмами є алгоритм старіння та WSClock, які базуються на алгоритмі LRU і понятті робочого набору відповідно.