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

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

По одному из алгоритмов удаляется та страница, которая дольше других не использовалась, поскольку вероятность того, что она окажется в текущем рабочем множестве, очень мала. Этот алгоритм называется 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 совершенно не работает (другие алгоритмы при сходных обстоятельствах тоже не работают). Однако если расширить размер рабочего множества, число ошибок отсутствия страниц станет минимальным.

Можно применить другой алгоритм - FIFO (First-in First-out - первым пришел, первым ушел). В соответствии с алгоритмом FIFO удаляется та страница, которая была загружена раньше всех, независимо от того, когда в последний раз производилось обращение к этой странице. С каждым страничным кадром связан отдельный счетчик. Изначально все счетчики сброшены. После каждой ошибки отсутствия страницы счетчик каждой страницы, находящейся в памяти, увеличивается на 1, а счетчик только что вызванной страницы сбрасывается. Для удаления выбирается страница с самым большим значением счетчика. Поскольку страница не загружалась в память очень давно, существует большая вероятность, что она больше не понадобится.

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

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

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

Поиск по сайту: