Вызов страниц по требованию и рабочее множество

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

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

Такой метод работы с виртуальной памятью называется вызовом страниц по требованию (demand paging). Такой вызов страниц напоминает кормление мла­денца по требованию (в противоположность кормлению по расписанию): когда младенец кричит, вы его кормите. При вызове страниц по требованию страницы переносятся в основную память только в случае необходимости, но не ранее.

Вопрос о том, стоит вызывать страницы по требованию или нет, имеет смысл только при запуске программы. Когда программа проработает некоторое время, нужные страницы уже окажутся в основной памяти. Однако если это компьютер с разделением времени и процессы выгружаются, проработав примерно 100 миллисе­кунд, то каждая программа будет запускаться многократно. Для каждой программы распределение памяти уникально и при переключении с одной программы на дру­гую меняется, поэтому в системах с разделением времени такой подход не годится.

Альтернативный подход основан на наблюдении, что многие программы об­ращаются к адресному пространству неравномерно. Обычно большинство обра­щений относятся к небольшому числу страниц. Это называется принципом ло­кальности. При обращении к памяти можно вызвать команду, вызвать данные или сохранить данные. В каждый момент времени t существует набор страниц, которые использовались при последних k обращениях. В [54] этот набор страниц назван рабочим множеством.

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