Добавлен: 29.10.2018
Просмотров: 48077
Скачиваний: 190
3.4. Алгоритмы замещения страниц
251
не перейдет к другой фазе выполнения (например, к следующему проходу компилято-
ра). Если объем доступной памяти слишком мал для размещения всего рабочего набора,
процесс вызовет множество ошибок отсутствия страниц и будет работать медленно,
поскольку выполнение команды занимает всего несколько наносекунд, а считывание
страницы с диска — обычно 10 мс. Если он будет выполнять одну или две команды за
10 мс, то завершение его работы займет целую вечность. О программе, вызывающей
ошибку отсутствия страницы через каждые несколько команд, говорят, что она про-
буксовывает
(Denning, 1968б).
В многозадачных системах процессы довольно часто сбрасываются на диск (то есть все
их страницы удаляются из памяти), чтобы дать возможность другим процессам вос-
пользоваться своей очередью доступа к центральному процессору. Возникает вопрос: что
делать, когда процесс возобновляет свою работу? С технической точки зрения ничего
делать не нужно. Процесс просто будет вызывать ошибки отсутствия страниц до тех пор,
пока не будет загружен его рабочий набор. Проблема в том, что наличие многочисленных
ошибок отсутствия страниц при каждой загрузке процесса замедляет работу, а также
вызывает пустую трату значительной части рабочего времени центрального процессора,
поскольку на обработку операционной системой одной ошибки отсутствия страницы
затрачивается несколько миллисекунд процессорного времени.
Поэтому многие системы замещения страниц пытаются отслеживать рабочий набор
каждого процесса и обеспечивать его присутствие в памяти, перед тем как позволить
процессу возобновить работу. Такой подход называется моделью рабочего набора
(Denning, 1970). Он был разработан для существенного сокращения количества ошибок
отсутствия страниц. Загрузка страниц до того, как процессу будет позволено возобно-
вить работу, называется также опережающей подкачкой страниц (prepaging). Следует
заметить, что со временем рабочий набор изменяется.
Давно подмечено, что большинство программ неравномерно обращается к своему адрес-
ному пространству: их обращения склонны группироваться на небольшом количестве
страниц. Обращение к памяти может быть извлечением команды или данных или со-
хранением данных. В любой момент времени t существует некий набор, состоящий из
всех страниц, используемый в k самых последних обращений к памяти. Этот набор,
w(k, t), и является рабочим набором. Так как все недавние обращения к памяти для
k > 1 обязательно должны были обращаться ко всем страницам, использовавшимся для
(k = 1)-го обращения к памяти, то есть к последней и, возможно, еще к некоторым стра-
ницам, w(k, t) является монотонно неубывающей функцией от k. По мере роста значения
k значение функции w(k, t) достигает своего предела, поскольку программа не может
обращаться к количеству страниц, превышающему по объему имеющееся адресное про-
странство, а каждая отдельно взятая страница будет использоваться лишь немногими
программами. На рис. 3.17 показано, что размер рабочего набора является функцией от k.
Тот факт, что большинство программ произвольно обращается к небольшому количе-
ству страниц, но со временем этот набор медленно изменяется, объясняет начальный
быстрый взлет кривой графика, а затем, при больших значениях k, существенное за-
медление этого взлета. К примеру, программа, выполняющая цикл, при этом занима-
ющая две страницы и использующая данные, расположенные на четырех страницах,
может обращаться ко всем шести страницам каждые 1000 команд, но самые последние
обращения к некоторым другим страницам могут состояться за 1 млн команд до этого,
в процессе фазы инициализации. Благодаря такому асимптотическому поведению со-
держимое рабочего набора нечувствительно к выбранному значению k.
252
Глава 3. Управление памятью
Рис. 3.17. Рабочий набор — это набор страниц, используемых при k самых последних
обращений. Значение функции w(k, t) является размером рабочего набора в момент времени t
Иначе говоря, существует широкий диапазон значений k, для которого рабочий набор
остается неизменным. Поскольку со временем рабочий набор изменяется медленно,
появляется возможность выстроить разумные предположения о том, какие страницы
понадобятся при возобновлении работы программы, основываясь на том, каков был ее
рабочий набор при последней приостановке ее работы. Опережающая подкачка страниц
как раз и заключается в загрузке этих страниц перед возобновлением процесса.
Для реализации модели рабочего набора необходимо, чтобы операционная система
отслеживала, какие именно страницы входят в рабочий набор. При наличии такой
информации тут же напрашивается возможный алгоритм замещения страниц: при
возникновении ошибки отсутствия страницы нужно выселить ту страницу, которая не
относится к рабочему набору. Для реализации подобного алгоритма нам необходим чет-
кий способ определения того, какие именно страницы относятся к рабочему набору. По
определению рабочий набор — это набор страниц, используемых в k самых последних
обращений (некоторые авторы используют термин «k самых последних страничных
обращений», но это дело вкуса). Для реализации любого алгоритма рабочего набора
некоторые значения k должны быть выбраны заранее. Затем после каждого обращения
к памяти однозначно определяется и набор страниц, используемый при самых послед-
них k обращениях к памяти.
Разумеется, это определение рабочего набора не означает наличия эффективного
способа его вычисления в процессе выполнения программы. Можно представить себе
регистр со сдвигом, имеющий длину k, в котором при каждом обращении к памяти его
содержимое сдвигается влево на одну позицию и справа вставляется номер страницы,
к которой было самое последнее обращение. Набор из всех k номеров страниц в реги-
стре со сдвигом и будет представлять собой рабочий набор. Теоретически при возник-
новении ошибки отсутствия страницы содержимое регистра со сдвигом может быть
считано и отсортировано. Затем могут быть удалены продублированные страницы.
В результате должен получиться рабочий набор. Но обслуживание регистра со сдвигом
и обработка его содержимого при возникновении ошибки отсутствия страницы ока-
жется недопустимо затратным делом, поэтому эта технология никогда не используется.
Вместо нее используются различные приближения. Одно из часто используемых при-
ближений сводится к отказу от идеи вычисления k обращений к памяти и использованию
вместо этого времени выполнения. Например, вместо определения рабочего набора
в качестве страниц, использовавшихся в течение предыдущих 10 млн обращений к па-
3.4. Алгоритмы замещения страниц
253
мяти, мы можем определить его как набор страниц, используемых в течение последних
100 мс времени выполнения. На практике с таким определением работать гораздо лучше
и проще. Следует заметить, что для каждого процесса вычисляется только его собствен-
ное время выполнения. Таким образом, если процесс запускается во время T и получает
40 мс времени центрального процессора за время T + 100 мс, то для определения рабо-
чего набора берется время 40 мс. Интервал времени центрального процессора, реально
занимаемый процессом с момента его запуска, часто называют текущим виртуальным
временем
. При этом приближении рабочим набором процесса является набор страниц,
к которым он обращался в течение последних t секунд виртуального времени.
Теперь взглянем на алгоритм замещения страниц, основанный на рабочем наборе.
Основной замысел состоит в том, чтобы найти страницу, не принадлежащую рабочему
набору, и удалить ее из памяти. На рис. 3.18 показана часть таблицы страниц, исполь-
зуемой в некой машине. Поскольку в качестве кандидатов на выселение рассматрива-
ются только страницы, находящиеся в памяти, страницы, в ней отсутствующие, этим
алгоритмом игнорируются. Каждая запись состоит (как минимум) из двух ключевых
элементов информации: времени (приблизительного) последнего использования стра-
ницы и бита R (Referenced — бита обращения). Пустыми белыми прямоугольниками
обозначены другие поля, не нужные для этого алгоритма, например номер страничного
блока, биты защиты и бит изменения — M (Modified).
Рис. 3.18. Алгоритм рабочего набора
Рассмотрим работу алгоритма. Предполагается, что аппаратура, как было рассмотрено
ранее, устанавливает биты R и M. Также предполагается, что периодические преры-
вания от таймера запускают программу, очищающую бит обращения R. При каждой
ошибке отсутствия страницы происходит сканирование таблицы страниц с целью
найти страницу, пригодную для удаления.
При каждой обработке записи проверяется состояние бита R. Если его значение
равно 1, текущее виртуальное время записывается в поле времени последнего исполь-
254
Глава 3. Управление памятью
зования таблицы страниц, показывая, что страница была использована при возникно-
вении ошибки отсутствия страницы. Если обращение к странице происходит в течение
текущего такта времени, становится понятно, что она принадлежит рабочему набору
и не является кандидатом на удаление (предполагается, что t охватывает несколько
системных тактов).
Если значение R равно 0, значит, за текущий такт времени обращений к странице не
было и она может быть кандидатом на удаление. Чтобы понять, должна ли она быть
удалена или нет, вычисляется ее возраст (текущее виртуальное время за вычетом вре-
мени последнего использования), который сравнивается со значением t. Если возраст
превышает значение t, то страница уже не относится к рабочему набору и заменяется
новой страницей. Сканирование продолжается, и происходит обновление всех осталь-
ных записей.
Но если значение R равно 0, но возраст меньше или равен t, то страница все еще от-
носится к рабочему набору. Страница временно избегает удаления, но страница с наи-
большим возрастом (наименьшим значением времени последнего использования)
берется на заметку. Если будет просканирована вся таблица страниц и не будет найдена
страница — кандидат на удаление, значит, к рабочему набору относятся все страницы.
В таком случае, если найдена одна и более страниц с R = 0, удаляется одна из них, име-
ющая наибольший возраст. В худшем случае в течение текущего такта было обращение
ко всем страницам (и поэтому у всех страниц R = 1), поэтому для удаления одна из
них выбирается случайным образом, при этом предпочтение отдается неизмененной
странице, если таковая имеется.
3.4.9. Алгоритм WSClock
Базовый алгоритм рабочего набора слишком трудоемок, поскольку при возникнове-
нии ошибки отсутствия страницы для определения местонахождения подходящего
кандидата на удаление необходимо просканировать всю таблицу страниц. Усовер-
шенствованный алгоритм, основанный на алгоритме «часы», но также использующий
информацию о рабочем наборе, называется WSClock (Carr and Hennessey, 1981).
Благодаря простоте реализации и хорошей производительности он довольно широко
используется на практике.
Необходимая структура данных сводится к циклическому списку страничных блоков,
как в алгоритме «часы» и как показано на рис. 3.19, а. Изначально этот список пуст.
При загрузке первой страницы она добавляется к списку. По мере загрузки следующих
страниц они попадают в список, формируя замкнутое кольцо. В каждой записи содер-
жится поле времени последнего использования из базового алгоритма рабочего набора,
а также бит R (показанный на рисунке) и бит M (не показанный на рисунке).
Как и в алгоритме «часы», при каждой ошибке отсутствия страницы сначала проверя-
ется страница, на которую указывает стрелка. Если бит R установлен в 1, значит, стра-
ница была использована в течение текущего такта, поэтому она не является идеальным
кандидатом на удаление. Затем бит R устанавливается в 0, стрелка перемещается на
следующую страницу, и алгоритм повторяется уже для нее. Состояние, получившееся
после этой последовательности событий, показано на рис. 3.19, б.
Теперь посмотрим, что получится, если у страницы, на которую указывает стрелка,
бит R = 0 (рис. 3.19, в). Если ее возраст превышает значение t и страница не изме-
3.4. Алгоритмы замещения страниц
255
Рис. 3.19. Работа алгоритма WSClock: а и б — пример того, что происходит, когда R = 1;
в и г — пример того, что происходит, когда R = 0
нена, она не относится к рабочему набору и ее точная копия присутствует на дис-
ке. Тогда страничный блок просто истребуется и в него помещается новая страница
(рис. 3.19, г). Но если страница изменена, ее блок не может быть тотчас же истребован,
поскольку на диске нет ее точной копии. Чтобы избежать переключения процесса,
запись на диск планируется, а стрелка перемещается дальше и алгоритм продолжает
свою работу на следующей странице. В конце концов должна попасться старая, неиз-
мененная страница, которой можно будет тут же и воспользоваться.
В принципе, за один оборот часовой стрелки может быть запланирована операция
дискового ввода-вывода для всех страниц. Для уменьшения потока обмена данными