tgoop.com/the_algorithms/4948
Last Update:
Алгоритм оптимальной замены страниц
Цель алгоритма: уменьшение количества ошибок страниц. В этом алгоритме заменяются страницы, которые не будут использоваться в течение длительного времени в будущем.
Идея проста: для каждой ссылки мы делаем:
⁃ Если указанная страница уже существует, увеличьте количество обращений.
⁃ Если нет, найдите страницу, на которую никогда не будут ссылаться в будущем. Если такая страница существует, замените ее новой страницей. Если такой страницы не существует, найдите страницу, на которую в будущем будут чаще всего ссылаться. Замените эту страницу новой страницей.
Оптимальная замена страниц идеальна, но на практике невозможна, поскольку операционная система не может знать будущие запросы. Использование замены оптимальной страницы предназначено для установки эталона, позволяющего анализировать другие алгоритмы замены.
Сложность: O(n × f), где n — количество страниц, а f — количество кадров.
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4948