Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.339

Политика замещения страниц

В идеале, чтобы сократить количество ошибок отсутствия страниц, можно хранить в памяти набор страниц, которые постоянно используются программой (так называемое рабочее множество). Однако программисты обычно не знают,

какие страницы находятся в рабочем множестве, поэтому операционная система периодически должна показывать это множество. Если программа обращается к странице, которая отсутствует в основной памяти, ее нужно вызвать с диска. Однако чтобы освободить для нее место, на диск нужно отправить какую-нибудь другую страницу. Следовательно, нужен алгоритм, позволяющий определить, какую именно страницу необходимо удалить из памяти.

Выбирать такую страницу просто наугад нельзя. Если, например, выбрать страницу, содержащую команду, выполнение которой вызвало ошибку, то при попытке вызвать следующую команду произойдет еще одна ошибка отсутствия страницы. Большинство операционных систем стараются предсказать, какие из страниц в памяти наименее полезны в том смысле, что их отсутствие значительно не повлияет на ход программы. Один из методов решения этой задачи таков: сначала прогнозируется время следующих обращений к каждой странице, а затем страница, обращение к которой, согласно прогнозу, должно произойти позже всех, удаляется. Иными словами, вместо того чтобы удалять произвольную страницу, стараются выбрать такую страницу, которая не понадобится достаточно долго.

По одному из алгоритмов удаляется та страница, которая дольше других не использовалась, поскольку вероятность того, что она окажется в текущем рабочем множестве, очень мала. Этот алгоритм называется LRU (Least Recently Used — дольше всего не использовавшийся). Хотя этот алгоритм работает достаточно хорошо, иногда возникают патологические ситуации. Вот одна из них.

Представьте себе программу, выполняющую огромный цикл, занимающий 9 виртуальных страниц, в то время как в физической памяти место есть только для 8 страниц. Когда программа перейдет к странице 7, в основной памяти будут находиться страницы с 0 по 7. Затем совершается попытка вызвать команду с виртуальной страницы 8, что вызывает ошибку отсутствия страницы. В соответствии с алгоритмом LRU из памяти удаляется виртуальная страница 0, поскольку она не использовалась дольше других. Виртуальная страница 0 удаляется, а на ее место помещается виртуальная страница 8 (в памяти оказываются страницы 1-8).

После выполнения команд с виртуальной страницы 8 программа возвращается к началу цикла, то есть к виртуальной странице 0. Этот шаг вызывает еще одну ошибку отсутствия страницы, только что выброшенную виртуальную страницу 0 приходится вызывать обратно. В соответствии с алгоритмом LRU из памяти удаляется страница 1 (в памяти оказываются страница 0 плюс страницы 2-8). Через некоторое время программа пытается вызвать команду с виртуальной страницы 1, что опять вызывает ошибку. Затем вызывается страница 1 и удаляется страница 2 и т. д.

Очевидно, что в этой ситуации алгоритм LRU совершенно не работает (другие алгоритмы при сходных обстоятельствах тоже не работают). Однако если расширить размер рабочего множества, число ошибок отсутствия страниц станет минимальным.