Виртуальная память представляет собой двухуровневую память, состоящую из оперативной (верхний уровень) и внешней (нижний уровень) памятей. Все страницы программы хранятся во внешней памяти, а копии некоторых из них – еще и в ОП.
Если в ходе выполнения программы выясняется, что нужная страница отсутствует в памяти верхнего уровня, она пересылается туда из памяти нижнего уровня и щанимает свободное место (если оно есть). Если же его нет, то какая-либо страница должна покинуть ОП. Если эта страница (выбранная по определенному алгоритму) во время ее нахождения в ОП никак не изменялась, то ее просто можно стереть в ОП (поскольку в ВЗУ есть ее копия). Если же страница изменилась, ее нужно переписать в ВЗУ.
Ситуация, когда в ОП нет требуемой страницы, называется страничным сбоем, процедура замены этой страницей в ОП на другую – процессом замещения страниц.
Поскольку операции обмена между уровнями памяти вызывают непроизводительные затраты времени процессора, следует уменьшать их количество. Процесс замещения страниц можно выполнить оптимальным образом, если известно, в каком порядке будут происходить обращения к отдельным страницам памяти. Однако такая информация при выполнении программ отсутствует, поэтому на практике используют эвристические алгоритмы замещения.
1. Алгоритм случайного замещения. Из памяти верхнего уровня отсылается с равной вероятностью любая страница. Это самый простой алгоритм; он используется редко.
2. Алгоритм FIFO («первый пришел – первый ушел»). Когда страница загружается в ОП, ей присваивается временная метка. Отсылается страница, дольше всех находившаяся в ОП. Реализация этой стратегии может привести даже к замене активной страницы
3. Алгоритм LIFO («последний пришел – первый ушел»). Отсылается страница, позже других поступившая в ОП (определяется по временной метке).
4. Замещение страницы, которая дольше всех не использовалась. Она определяется по временной метке, которая обновляется при каждом обращении к странице. Если этот алгоритм дополнить механизмом, который упорядочивает страницы по времени обращения к ним, то замене всегда подлежит последняя страница в ОП.
5. Стратегия «рабочего комплекта». Для каждой страницы в таблице страниц вводятся два бита признаков: признак обращения и признак изменения. Вначале они установлены в «0». Изменение состояния (установка в «1») происходит при обращении к данной странице или при ее изменении соответственно. Периодически признаки обращения сбрасываются в «0». В случае возникновения страничного сбоя вначале производится поиск страницы, к которой в последнее время не производились обращения. Если найдены такие страницы, среди них производится поиск страницы, в которой не было модификации. Это означает, что копия страницы в ОП идентична виртуальной странице в ВЗУ. Выделенные таким образом физические страницы могут быть объявлены свободными. Среди физических страниц, к которым были произведены обращения, выделяются страницы, в которых отсутствовали изменения. После такого просмотра образуются четыре группы физических страниц: 1) обращений не было, модификация отсутствует; 2) обращений не было, модификация производилась; 3) обращения были, модификация отсутствует; 4) обращения были, модификация производилась.
Страницы четвертой группы образуют «рабочий комплект»; они не подлежат замещению. В первую очередь кандидатами на замещение являются страницы первой группы, затем – второй или третьей.
Не менее важна процедуа «подкачки» страниц, т.е. выборки их из внешней памяти и перемещения в ОП. Выбор страниц для «подкачки» может осуществляться по запросу или с упреждением.
Подкачка страниц по запросу
Подкачка производится каждый раз, когда копия необходимой виртуальной страницы в ОП отсутствует. Эта стратегия гарантирует, что в ОП будут загружены только те страницы, которые фактически необходимы для выполнения процесса. Непроизводительные затраты времени на реализацию этой стратегии минимальны. Однако при появлении запроса на каждую новую страницу происходит прерывание по страничному сбою, и программа переходит в состояние ожидания до тех пор, пока копия этой страницы не будет загружена в ОП. Суммарные затраты времени на ожидание могут оказаться значительными. К тому же следует иметь в виду, что обмен по одной странице менее производителен, чем групповой обмен несколькими страницами.
Подкачка страниц с упреждением
При реализации этой стратегии ОС пытается заблаговременно предугадать, какие страницы потребуются программе. Как только в ОП появляются свободные физические страницы, в них загружаются копии этих страниц. Когда программа обратится к ним, они будут уже готовы к использованию.
Подкачка страниц с упреждением особенно широко используется в системах коллективного пользования. Преимущества такой стратегии очевидны: при смене программы необходимые для начала ее работы страницы уже будут находиться в ОП.
В некоторых системах используется сочетание этих стратегий (операционные системы VAX/VMS, UNIX и др).