Э. Таненбаум - Архитектура компьютера (1127755), страница 121
Текст из файла (страница 121)
В каждый момент времени г существует набор страниц, которые использовались при последних л обращениях. В [54~ этот набор страниц назван рабочим множеством. Поскольку рабочее множество обычно меняется очень медленно, можно, опираясь на последнее перед остановкой программы рабочее множество, предсказать, какие страницы понадобятся при новом запуске программы. Эти страницы можно загрузить заранее перед очередным запуском программы (предполагается, что предсказание будет точным).
Политика замещения страниц В идеале, чтобы сократить количество ошибок отсутствия страниц, можно хранить в памяти набор страниц, которые постоянно используются программой (так называемое рабочее множество). Однако программисты обычно не знают, 484 Глава б. Уровень операционной системы какие страницы находятся в рабочем множестве, поэтому операционная система периодически должна показывать это множество. Если программа обращается к странице, которая отсутствует в основной памяти, ее нужно вызвать с диска. Однако чтобы освободить для нее место, на диск нужно отправить какую-нибудь другую страницу.
Следовательно, нужен алгоритм, позволяющий определить, какую именно страницу необходимо удалить из памяти. Выбирать такую страницу просто наугад нельзя. Если, например, выбрать страницу, содержашую команду, выполнение которой вызвало ошибку, то при попытке вызвать следующую команду произойдет еще одна ошибка отсутствия страницы. Большинство операционных систем стараются предсказать, какие из страниц в памяти наименее полезны в том смысле, что их отсутствие значительно не повлияет на ход программы. Один из методов решения этой задачи таков: сначала прогнозируется время следующих обращений к каждой странице, а затем страница, обращение к которой, согласно прогнозу, должно произойти позже всех, удаляется.
Иными словами, вместо того чтобы удалять произвольную страницу, стараются выбрать такую страницу, которая не понадобится достаточно долго. По одному из алгоритмов удаляется та страница, которая дольше других не использовалась, поскольку вероятность того, что она окажется в текущем рабочем множестве, очень мала. Этот алгоритм называется 1ЛИ1 (1.еазг Кесеп11у 13зес1 — дольше всего не использовавшийся). Хотя этот алгоритм работает достаточно хорошо, иногда возникают патологические ситуации. Вот одна из них. Представьте себе программу, выполняющую огромный цикл, занимающий 9 виртуальных страниц, в то время как в физической памяти место есть только для 8 страниц.
Когда программа перейдет к странице 7, в основной памяти будут находиться страницы с О по 7. Затем совершается попытка вызвать команду с виртуальной страницы 8, что вызывает ошибку отсутствия страницы. В соответствии с алгоритмом 1.К(1 из памяти удаляется виртуальная страница О, поскольку она не использовалась дольше других. Виртуальная страница О удаляется, а на ее место помешается виртуальная страница 8 (в памяти оказываются страницы 1 — 8). После выполнения команд с виртуальной страницы 8 программа возвращается к началу цикла, то есть к виртуальной странице О.
Этот шаг вызывает еще одну ошибку отсутствия страницы, только что выброшенную виртуальную страницу О приходится вызывать обратно. В соответствии с алгоритмом БВП из памяти удаляется страница 1 (в памяти оказываются страница О плюс страницы 2 — 8). Через некоторое время программа пытается вызвать команду с виртуальной страницы 1, что опять вызывает ошибку.
Затем вызывается страница 1 и удаляется страница 2 и т. д. Очевидно, что в этой ситуации алгоритм 1.В(1 совершенно не работает (другие алгоритмы при сходных обстоятельствах тоже не работают). Однако если расширить размер рабочего множества, число ошибок отсутствия страниц станет минимальным. Можно применить другой алгоритм — ИГО (Е1гз1-1п Е(гзт-оц1 — первым пришел, первым ушел). В соответствии с алгоритмом Е1РО удаляется та страница, которая была загружена раньше всех, независимо от того, когда в последний раз Виртуальная память 488 производилось обращение к этой странице.
С каждым страничным кадром связан отдельный счетчик. Изначально все счетчики сброшены. После каждой ошибки отсутствия страницы счетчик каждой страницы, находящейся в памяти, увеличивается на 1, а счетчик только что вызванной страницы сбрасывается, Для удаления выбирается страница с самым большим значением счетчика.
Поскольку страница не загружалась в память очень давно, существует большая вероятность, что она больше не понадобится. Если размер рабочего множества больше, чем число доступных страничных кадров, ни один алгоритм не дает хороших результатов, и ошибки отсутствия страниц происходят часто. Если программа постоянно вызывает подобные ошибки, то говорят, что наблюдается пробуксовка (111газЫпй).
Вероятно, не нужно объяснять, почему пробуксовка нежелательна. Если программа использует большое виртуальное адресное пространство, но имеет компактное и медленно меняющееся рабочее множество, которое помещается в основную память, все отлично работает. Это утверждение имеет силу, даже если программа использует в сотни раз больше слов виртуальной памяти, чем их содержится в физической памяти. Если удаляемая страница не менялась с тех пор, как была считана (а это вполне вероятно, если страница содержит программу, а не данные), записывать ее обратно на диск не обязательно, поскольку точная копия там уже есть.
Однако если страница менялась, ее копия на диске ей уже не соответствует, и страницу нужно сбросить на диск. Если мы научимся определять, менялась страница или нет, то сможем избежать ненужных операций записи на диск и сэкономим много времени. На многих машинах в диспетчере памяти для каждой страницы выделяется 1 бит, который сбрасывается при загрузке страницы и устанавливается, когда эта страница меняется (микропрограммой или аппаратно). По этому биту операционная система определяет, менялась данная страница или нет, и нужно ее сбрасывать на диск или нет.
Размер страниц и фрагментация Если пользовательская программа и данные занимают ровно целое число страниц, то когда они время от времени загружаются в память, свободного места там не остается. В то же время, если они не занимают ровно целое число страниц, на последней странице останется неиспользованное пространство. Например, если программа и данные занимают 26 000 байт на машине со страницами по 4096 байт, то первые 6 страниц будут заполнены целиком, что в сумме даст 6 х 4096- 24 576 байт, а последняя страница будет содержать 26 000 — 24576 = 1424 байта.
Поскольку в каждой странице имеется пространство для 4096 байт, 2672 байта останутся свободными. Всякий раз, когда страница 7 будет оказываться в памяти, эти байты останутся неиспользуемыми, бесполезно занимая место в основной памяти. Эта проблема получила название внутренней фрагментации (поскольку неиспользуемое пространство является внутренним по отношению к странице). 486 Глава б. Уровень операционной системы Если размер страницы составляет п байт, то среднее неиспользуемое пространство последней страницы программы будет равно и/2 байт.
Таким образом, чтобы свести к минимуму объем бесполезного пространства, страницы должны быть небольшими. Однако при маленьких страницах потребуется много страниц и большая таблица страниц. Если таблица страниц сохраняется аппаратно, то для хранения большой таблицы страниц нужно много регистров, что повышает стоимость компьютера. Кроме того, при запуске и остановке программы на загрузку и сохранение этих регистров потребуется больше времени. Больше того, маленькие страницы снижают эффективность использования пропускной способности диска.
Поскольку перед началом передачи данных с диска приходится ждать примерно 10 миллисекунд (время поиска плюс задержка вращения), выгодно передать побольше данных. При скорости передачи данных 10 Мбайт/с, передача 8 Кбайт по сравнению с передачей 1 Кбайт добавляет всего 0,7 миллисекунд. Однако у маленьких страниц есть свои преимущества.
Если рабочее множество состоит из большого количества маленьких отделенных друг от друга областей виртуального адресного пространства, то при небольшом размере страницы реже будет возникать пробуксовка (режим интенсивной подкачки), чем при большом. Рассмотрим матрицу А размером 10 000 х 10 000, которая хранится в последовательных 8-байтных словах (А11,1], А12,11, А13,11 и т. д.). При такой записи элементы строки 1 (А11,11, А(1,21, А11,31 и т. д.) будут начинаться на расстоянии 80 000 байт друг от друга. Программе, обрабатывающей элементы этой строки, потребуется 10 000 областей, каждая из которых отделена от следующей величиной 79 992 байт.
Если бы размер страницы составлял 8 Кбайт, для хранения всех страниц понадобилось бы 80 Мбайт. При размере страницы в 1 Кбайт для хранения всех страниц потребуется всего 10 Мбайт ОЗУ. При размере памяти в 32 Мбайт и размере страницы в 8 Кбайт програьаиа войдет в режим интенсивной подкачки, а при размере страницы в 1 Кбайт этого не произойдет. Сегментация До сих пор мы говорили об одномерной виртуальной памяти, в которой виртуальные адреса следуют один за другим от 0 до какого-то максимального адреса. Однако по многим причинам гораздо удобнее использовать два или несколько отдельных виртуальных адресных пространств. Например, компилятор может иметь несколько структур, которые создаются в процессе компиляции; такими структурами могут быть; + символьная таблица с именами и атрибутами переменных; + исходный текст для распечатки; + таблица со всеми использующимися целочисленными константами и константами с плаваю|цей точкой; + дерево синтаксического разбора программы; + стек, используемый для вызова процедур в компиляторе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
