ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12150
Скачиваний: 10
Виртуальная память
443
всего 8 страничных кадров, не все виртуальные страницы могут находиться в па-
мяти одновременно. Контроллер управления памятью проверяет
бит
присутствия
в данном элементе таблицы страниц. В нашем примере этот бит равен 1. Это зна-
чит, что страница в данный момент находится в памяти.
-15-битный адрес памяти
Виртуальная
страница
Бит присутствия
Таблица
страниц
1
110 --
20-битная виртуальная страница — И - * - 12-битное смещение -
32-битный виртуальный адрес
Выходной
регистр
Входной
регистр
Рис. 6.4. Формирование адреса основной памяти из адреса виртуальной памяти
Далее из выбранного элемента таблицы нужно взять значение страничного кадра
(в нашем примере — 6) и скопировать его в старшие три бита 15-битного выходного
регистра. Нужно именно три бита, потому что в физической памяти находится
8 страничных кадров. Параллельно с этой операцией младшие 12 битов виртуально-
го адреса (поле смещения страницы) копируются в младшие 12 битов выходного
4 4 4 Глава 6. Уровень операционной системы
регистра. Затем полученный 15-битный адрес отправляется в кэш-память или ос-
новную память для поиска.
На рисунке 6.5 показано возможное отображение виртуальных страниц в физи-
ческие страничные кадры. Виртуальная страница 0 находится в страничном кадре 1.
Виртуальная страница 1 находится в страничном кадре 0. Виртуальной страницы 2
нет в основной памяти. Виртуальная страница 3 находится в страничном кадре 2.
Виртуальной страницы 4 нет в основной памяти. Виртуальная страница 5 нахо-
дится в страничном кадре 6 и т. д.
Таблица страниц
Виртуальная Страничный
страница кадр
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
;
'.
0
1
0
0
1
0
0
1
0
1
1
0
1
0
1
1
г s
0
4 \
0
0
5 N
0
0
3 -
0
7 -
6 -
0
2 -
0
0 -
1 -
Страничный
кадр
Основная память
Виртуальная страница 6
Виртуальная страница 5
Виртуальная страница 11
Виртуальная страница 14
Виртуальная страница 8
Виртуальная страница 3
Виртуальная страница 0
Виртуальная страница 1
7
6
5
4
3
2
1
0
\
1 = присутствует в основной памяти
0 = отсутствует в основной памяти
Рис. 6.5. Возможное отображение первых 16 виртуальных страниц
в основную память, содержащую 8 страничных кадров
Вызов страниц по требованию
и рабочее множество
Ранее предполагалось, что виртуальная страница, к которой происходит обраще-
ние, находится в основной памяти. Однако это предположение не всегда верно,
поскольку в основной памяти недостаточно места для всех виртуальных страниц.
Виртуальная память 445
При обращении к адресу страницы, которой нет в основной памяти, происходит
ошибка из-за отсутствия страницы.
В случае такой ошибки операционная систе-
ма должна считать нужную страницу с диска, ввести новый адрес физической па-
мяти в таблицу страниц, а затем повторить команду, которая вызвала ошибку.
На машине с виртуальной памятью можно запустить программу даже в том
случае, если ни одной части программы нет в основной памяти. Просто таблица
страниц должна указывать, что абсолютно все виртуальные страницы находятся
во вспомогательной памяти. Если центральный процессор пытается вызвать пер-
вую команду, он сразу получает ошибку из-за отсутствия страницы, в результате
чего страница, содержащая первую команду, загружается в память и вносится
в таблицу страниц. После этого начинается выполнение первой команды. Если пер-
вая команда содержит два адреса и оба эти адреса находятся на разных страницах,
причем обе страницы не являются страницей, в которой находится команда, то
произойдет еще две ошибки из-за отсуствия страницы и еще две страницы будут
перенесены в основную память до завершения команды. Следующая команда мо-
жет вызвать еще несколько ошибок и т. д.
Такой метод работы с виртуальной памятью называется
вызовом страниц по
требованию.
Он похож на один из способов кормления младенцев: когда младе-
нец кричит, вы его кормите (в противоположность кормлению по расписанию).
При вызове страниц по требованию страницы переносятся в основную память толь-
ко в случае необходимости, но не заранее.
Вопрос о том, стоит ли использовать вызов страниц по требованию или нет,
имеет смысл только в самом начале при запуске программы. Когда программа про-
работает некоторое время, нужные страницы уже будут собраны в основной памя-
ти. Если это компьютер с разделением времени и процессы откачиваются обратно,
проработав примерно 100 миллисекунд, то каждая программа будет запускаться
много раз. Для каждой программы распределение памяти уникально и при пере-
ключении с одной программы на другую меняется, поэтому в системах с разделе-
нием времени такой подход не годится.
Альтернативный подход основан на наблюдении, что большинство команд обра-
щаются к адресному пространству не равномерно. Обычно большинство обраще-
ний относятся к небольшому числу страниц. При обращении к памяти можно вы-
звать команду, вызвать данные или сохранить данные. В каждый момент времени
t существует набор страниц, которые использовались при последних
к
обращени-
ях. Деннинг [29] назвал этот набор страниц
рабочим множеством.
Поскольку рабочее множество обычно меняется очень медленно, можно, опи-
раясь на последнее перед остановкой программы рабочее множество, предсказать,
какие страницы понадобятся при новом запуске программы. Эти страницы можно
загрузить заранее перед очередным запуском программы (предполагается, что пред-
сказание будет точным).
Политика замещения страниц
В идеале набор страниц, которые постоянно используются программой (так назы-
ваемое
рабочее множество),
можно хранить в памяти, чтобы сократить количе-
ство ошибок из-за отсутствия страниц. Однако программисты обычно не знают,
какие страницы находятся в рабочем множестве, поэтому операционная система
периодически должна показывать это множество. Если программа обращается
4 4 6
Глава 6. Уровень операционной системы
к странице, которая отсутствует в основной памяти, ее нужно вызвать с диска. Од-
нако чтобы освободить для нее место, на диск нужно отправить какую-нибудь дру-
гую страницу. Следовательно, нужен алгоритм для определения, какую именно
страницу необходимо убрать из памяти.
Выбирать такую страницу просто наугад нельзя. Если, например, выбрать стра-
ницу, содержащую команду, выполнение которой вызвало ошибку, то при попытке
вызвать следующую команду произойдет еще одна ошибка из-за отсутствия страни-
цы. Большинство операционных систем стараются предсказать, какие из страниц
в памяти наименее полезны в том смысле, что их отсутствие не повлияет сильно на
ход программы. Иными словами, вместо того чтобы удалять страницу, которая
скоро понадобится, постарайтесь выбрать такую страницу, которая не будет нуж-
на долгое время.
По одному из алгоритмов удаляется та страница, которая использовалась наи-
более давно, поскольку вероятность того, что она будет в текущем рабочем множе-
стве, очень мала. Этот алгоритм называется
LRU (Least Recently Used — алго-
ритм удаления наиболее давно использовавшихся элементов).
Хотя этот алгоритм
работает достаточно хорошо, иногда возникают патологические ситуации. Ниже
описана одна из них.
Представьте себе программу, выполняющую огромный цикл, который прости-
рается на девять виртуальных страниц, а в физической памяти место есть только
для восьми страниц. Когда программа перейдет к странице 7, в основной памяти
будут находиться страницы с 0 по 7 (табл. 6.1). Затем совершается попытка вы-
звать команду из виртуальной страницы 8, что вызывает ошибку из-за отсутствия
страницы. Нужно принять решение, какую страницу убрать. По алгоритму LRU
будет выбрана виртуальная страница 0, поскольку она использовалась раньше всех.
Виртуальная страница 0 удаляется, а нужная виртуальная страница помещается
на ее место (табл. 6.2).
Таблица 6 . 1 .
Ситуация, в которой алгоритм LRU не действует (1)
Виртуальная страница 7
Виртуальная страница 6
Виртуальная страница 5
Виртуальная страница 4
Виртуальная страница 3
Виртуальная страница 2
Виртуальная страница 1
Виртуальная страница О
Таблица 6.2.
Ситуация, в которой алгоритм LRU не действует (2)
Виртуальная страница 7
Виртуальная страница 6
Виртуальная страница 5
Виртуальная страница 4
Виртуальная страница 3
Виртуальная страница 2
Виртуальная страница 1
Виртуальная страница 8
Виртуальная память
4 4 7
Таблица 6.3.
Ситуация, в которой алгоритм LRU не действует (3)
Виртуальная страница 7
Виртуальная страница 6
Виртуальная страница 5
Виртуальная страница 4
Виртуальная страница 3
Виртуальная страница 2
Виртуальная страница О
Виртуальная страница 8
После выполнения команд из виртуальной страницы 8 программа возвращает-
ся к началу цикла, то есть к виртуальной странице 0. Этот шаг вызывает еще одну
ошибку из-за отсутствия страницы. Только что выброшенную виртуальную стра-
ницу 0 приходится вызывать обратно. По алгоритму LRU удаляется страница 1
(табл. 6.3). Через некоторое время программа пытается вызвать команду из вир-
туальной страницы 1, что опять вызывает ошибку. Затем вызывается страница 1
и удаляется страница 2 и т. д.
Очевидно, что в этой ситуации алгоритм LRU совершенно не работает (другие
алгоритмы тоже не работают при сходных обстоятельствах). Однако если расши-
рить размер рабочего множества, число ошибок из-за отсутствия страниц станет
минимальным.
Можно применять и другой алгоритм —
FIFO (First-in First-out — первым
поступил, первым выводится).
FIFO удаляет ту страницу, которая раньше всех
загружалась, независимо от того, когда в последний раз производилось обращение
к этой странице. С каждым страничным кадром связан отдельный счетчик. Изна-
чально все счетчики установлены на 0.
После каждой ошибки из-за отсутствия страниц счетчик каждой страницы, на-
ходящейся в памяти, увеличивается на 1, а счетчик только что вызванной страни-
цы принимает значение 0. Когда нужно выбрать страницу для удаления, выбира-
ется страница с самым большим значением счетчика. Поскольку она не загружалась
в память очень давно, существует большая вероятность, что она больше не понадо-
бится.
Если размер рабочего множества больше, чем число доступных страничных
кадров, ни один алгоритм не дает хороших результатов, и ошибки из-за отсутствия
страниц будут происходить часто. Если программа постоянно вызывает подобные
ошибки, то говорят, что наблюдается
пробуксовка (thrashing).
Думаю, не нужно
объяснять, что пробуксовка очень нежелательна. Если программа использует боль-
шое виртуальное адресное пространство, но имеет небольшое медленно изменяю-
щееся рабочее множество, которое помещается в основную память, ничего страш-
ного не произойдет. Это утверждение имеет силу, даже если программа использует
в сто раз больше слов виртуальной памяти, чем их содержится в физической ос-
новной памяти.
Если страница, которую нужно удалить, не менялась с тех пор, как ее считали
(а это вполне вероятно, если страница содержит программу, а не данные), то не-
обязательно записывать ее обратно на диск, поскольку точная копия там уже
существует. Однако если эта страница изменилась, то копия на диске уже ей не
соответствует, и ее нужно туда переписать.