Добавлен: 29.10.2018
Просмотров: 48079
Скачиваний: 190
3.5. Разработка систем страничной организации памяти
261
Неплохим способом сокращения количества соревнующихся за обладание памятью
процессов является сброс некоторых из них на диск и освобождение всех удержи-
вавшихся ими страниц. Например, один процесс может быть сброшен на диск, а его
страничные блоки — поделены между другими пробуксовывающими процессами.
Если пробуксовка прекратится, то система некоторое время может проработать в таком
состоянии. Если она не прекратится, потребуется сбросить на диск другой процесс
и продолжать в том же духе, пока пробуксовка не прекратится. Таким образом, даже
при страничной организации памяти свопинг может не утратить своей актуальности,
только теперь он используется для сокращения потенциальной потребности в памяти,
а не для повторного востребования страниц.
Свопинг процессов, призванный снизить нагрузку на память, напоминает двухуров-
невую диспетчеризацию, при которой часть процессов помещается на диск, а для рас-
пределения оставшихся процессов используется краткосрочный диспетчер. Понятно,
что эти две идеи можно сочетать, выгружая достаточное количество процессов, чтобы
достичь приемлемого уровня ошибок отсутствия страницы. Периодически какие-то
процессы загружаются с диска, а какие-то выгружаются на него.
Еще одним фактором, требующим рассмотрения, является степень многозадачности.
Когда в основной памяти находится слишком мало процессов, центральный процессор
может весьма существенные периоды времени быть недогружен. С учетом этого при
принятии решения о выгрузке процесса нужно принимать во внимание не только его
размер и уровень подкачки страниц, но и его характеристики, например ограничен ли
этот процесс скоростью вычислений или же он ограничен скоростью работы устройств
ввода-вывода, и принимать во внимание те характеристики, которыми обладают
остальные процессы.
3.5.3. Размер страницы
Размер страницы является тем параметром, который должен быть выбран операци-
онной системой. Даже если аппаратура была разработана, к примеру, под страницы
в 4096 байт, операционная система может запросто рассматривать пары страниц 0 и 1,
2 и 3, 4 и 5 и т. д. как страницы размером 8 Кбайт, всегда выделяя им два последова-
тельных страничных блока размером 8192 байт.
Определение наилучшего размера страницы требует сохранения баланса между не-
сколькими конкурирующими факторами. Таким образом, абсолютно оптимального
решения не существует. Для начала возьмем два фактора, являющихся аргументами
в пользу небольшого размера страницы. Произвольно взятые текст, данные или сег-
мент стека не заполнят целое число страниц. В среднем половина последней страницы
останется незаполненной. Оставшееся пространство на этой странице тратится впу-
стую. Эти потери называются внутренней фрагментацией. Если в памяти n сегментов,
а размер страницы составляет p байт, то на внутреннюю фрагментацию будет потра-
чено впустую np/2 байт. Эти соображения являются аргументом в пользу небольшого
размера страницы.
Другой аргумент в пользу небольшого размера страницы возникает при рассмотрении
программы, состоящей из восьми последовательных этапов, каждый размером 4 Кбайт.
При размере страницы 32 Кбайт программе всегда должно быть выделено 32 Кбайт.
При странице размером 16 Кбайт ей потребуется только 16 Кбайт. А при размере стра-
ницы 4 Кбайт или меньше ей в любой момент времени потребуется только 4 Кбайт.
262
Глава 3. Управление памятью
В общем, при большом размере страницы в памяти будет больше неиспользуемого
пространства, чем при малом.
В то же время при небольших по объему страницах подразумевается, что программы
будут нуждаться в большом количестве страниц, а это приведет к большому размеру
таблицы страниц. Программе размером 32 Кбайт требуется только 4 страницы по
8 Кбайт, но 64 страницы по 512 байт. Как правило, на диск и с диска переносится сра-
зу вся страница, при этом основная часть времени тратится на задержки, связанные
с поиском нужного сектора и раскруткой диска, поэтому перенос небольшой страницы
занимает практически столько же времени, что и перенос большой страницы. Для за-
грузки 64 страниц по 512 байт может потребоваться 64 · 10 мс, а для загрузки четырех
страниц по 8 Кбайт — всего 4 · 12 мс.
Кроме того, страницы небольшого размера расходуют много ценного пространства
в TLB. Предположим, что ваша программа использует 1 Мбайт памяти с рабочим на-
бором размером 64 Кбайт. При страницах размером 4 Кбайт программа будет занимать
как минимум 16 записей в TLB. При страницах размером 2 Мбайт было бы достаточно
одной записи в TLB (теоретически вам может потребоваться разделить данные и ин-
струкции). Из-за дефицита TLB-записей и их значимого влияния на производитель-
ность приходится везде, где только можно, расплачиваться использованием больших
страниц. Чтобы сбалансировать все эти компромиссы, операционные системы иногда
используют разные размеры страниц для разных частей системы. Например, большие
страницы для ядра и меньшие по размеру страницы для пользовательских процессов.
На некоторых машинах таблица страниц должна быть загружена (операционной си-
стемой) в аппаратные регистры при каждом переключении центрального процессора
с одного процесса на другой. Для этих машин наличие небольших страниц означает
увеличение времени, необходимого для загрузки регистров страниц при уменьшении
размера страницы. Более того, при уменьшении размера страницы увеличивается про-
странство, занимаемое таблицей страниц.
Последнее утверждение может быть проанализировано с математической точки зрения.
Пусть средний размер процесса будет составлять s байт, а размер страницы — p байт.
Кроме этого предположим, что на каждую страничную запись требуется e байт. Тогда
приблизительное количество страниц, необходимое каждому процессу, будет равно s/p,
что займет se/p байт пространства таблицы страниц. Из-за внутренней фрагментации
неиспользуемое пространство памяти в последней странице процесса будет равно p/2.
Таким образом, общие издержки на таблицу страниц и внутреннюю фрагментацию
будут получены за счет суммирования этих двух величин:
Издержки = se/p + p/2.
Первое слагаемое (размер таблицы страниц) будет иметь большее значение при не-
большом размере страницы. Второе слагаемое (внутренняя фрагментация) будет иметь
большее значение при большом размере страницы. Оптимальный вариант находится
где-то посередине. Если взять первую производную по переменной p и приравнять ее
к нулю, то мы получим уравнение
–se/p
2
+ 1/2 = 0.
Из этого уравнения можно вывести формулу, дающую оптимальный размер страни-
цы (с учетом только потерь памяти на фрагментацию и на размер таблицы страниц).
Результат будет следующим:
3.5. Разработка систем страничной организации памяти
263
Для s = 1 Мбайт и e = 8 байт на каждую запись в таблице страниц оптимальный раз-
мер страницы будет 4 Кбайт. Имеющиеся в продаже компьютеры используют размер
страницы от 512 байт до 64 Кбайт. Раньше чаще всего использовался размер 1 Кбайт,
но сейчас чаще всего встречается размер страницы 4 Кбайт.
3.5.4. Разделение пространства команд и данных
У многих компьютеров имеется единое адресное пространство, в котором, как показано
на рис. 3.22, а, содержатся и программы и данные. При довольно большом объеме это-
го пространства все работает нормально. Но зачастую объем адресного пространства
слишком мал, что заставляет программистов как-то выкручиваться, чтобы поместить
в него все необходимое.
Рис. 3.22. Адресное пространство: а — единое; б — отдельные адресные пространства
команд (I) и данных (D)
Одно из решений, впервые примененное на шестнадцатиразрядной машине PDP-11,
заключалось в использовании отдельных адресных пространств для команд (текста
программы) и данных, называемых I-пространством и D-пространством соответствен-
но (рис. 3.22, б). Каждое пространство простирается от 0 до некоторого максимума,
обычно 2
16
– 1 или 2
32
– 1. Компоновщик должен знать о том, что используются от-
дельные I- и D-пространства, поскольку при их использовании данные переносятся
на виртуальный адрес 0, а не начинаются сразу после программы.
На компьютерах такой конструкции страничную организацию памяти могут иметь
оба пространства независимо друг от друга. У каждого из них имеется собственная
таблица страниц с собственным отображением виртуальных страниц на физические
страничные блоки. Когда аппаратуре требуется извлечь команду, она знает, что для это-
го нужно использовать I-пространство и таблицу страниц этого I-пространства. Точно
так же обращение к данным должно вестись через таблицу страниц D-пространства.
Кроме этих тонкостей, наличие отдельных I- и D-пространств не приводит к каким-
то особым осложнениям для операционной системы и при этом удваивает доступное
адресное пространство.
Поскольку теперь адресные пространства стали большими, серьезные про-
блемы, связанные с их размерами, ушли в прошлое. Но даже сегодня разделение
264
Глава 3. Управление памятью
I- и D-пространств встречается довольно часто. Правда, вместо обычных адресных
пространств теперь это разделение используется в кэше L1, который до сих пор ис-
пытывает дефицит памяти.
3.5.5. Совместно используемые страницы
Еще одним вопросом разработки является совместное использование ресурсов. В боль-
ших многозадачных системах одновременное использование несколькими пользова-
телями одной и той же программы является обычным делом. Даже отдельный пользо-
ватель может запускать несколько программ, использующих одну и ту же библиотеку.
При этом вполне очевидна эффективность совместного использования страниц, чтобы
избежать одновременного присутствия в памяти двух копий одной и той же страницы.
Проблема в том, что не все страницы могут использоваться совместно. В частности,
страницы, предназначенные только для чтения, например содержащие текст програм-
мы, могут использоваться совместно, а совместное использование страниц с данными
связано с дополнительными сложностями.
Если поддерживаются отдельные I- и D-пространства, задача совместного использова-
ния программ становится относительно простой за счет наличия одного или несколь-
ких процессов, использующих одну и ту же таблицу страниц для своих I-пространств,
но разные таблицы страниц для своих D-пространств. Обычно в реализациях, поддер-
живающих совместное использование страниц таким образом, таблица страниц явля-
ется структурой данных, независимой от таблицы процессов. При этом, как показано
на рис. 3.23, каждый процесс в своей таблице процесса имеет два указателя: один на
таблицу страниц I-пространства, другой на таблицу страниц D-пространства. Когда
планировщик процессов выбирает запускаемый процесс, он использует эти указатели
для определения местонахождения таблиц страниц и настройки с их помощью дис-
петчера памяти (MMU). Процессы могут совместно использовать программы (или
иногда библиотеки) даже в отсутствие отдельных I- и D-пространств, но для этого
используется более сложный механизм.
Когда два и более процесса совместно используют один и тот же код, возникает про-
блема совместно используемых страниц. Предположим, что два процесса, A и B, за-
пускают редактор и совместно используют его страницы. Если планировщик примет
решение удалить процесс A из памяти, пожертвовав всеми его страницами и заполнив
опустевшие страничные блоки какой-нибудь другой программой, это приведет к тому,
что процесс B сгенерирует большое количество ошибок отсутствия страницы и вернет
эти страницы назад.
Также при остановке процесса A необходимо иметь возможность определить, какие
страницы все еще используются, чтобы их дисковое пространство случайно не оказа-
лось освобожденным. Просмотр всех таблиц страниц для того, чтобы определить со-
вместное использование страницы, — обычно очень затратная операция, поэтому для
отслеживания совместно используемых страниц понадобится специальная структура
данных, особенно если предметом совместного использования является отдельная
страница (или ряд страниц), а не вся таблица страниц.
Совместное использование данных является более сложной задачей, чем совместное
использование кода, но и она не является невыполнимой. В частности, в UNIX после
системного вызова fork родительский и дочерний процессы вынуждены совместно ис-
пользовать как текст программы, так и данные. В системах со страничной организацией
3.5. Разработка систем страничной организации памяти
265
Рис. 3.23. Два процесса, совместно использующие одну и ту же программу,
имеют общие таблицы страниц
памяти часто практикуется предоставление каждому из таких процессов собственной
таблицы страниц и наличие у них обоих указателя на один и тот же набор страниц.
Таким образом, при выполнении системного вызова fork копирования страниц не про-
исходит. Тем не менее все страницы с данными отображаются для каждого процесса
как страницы только для чтения — READ ONLY.
Пока оба процесса только читают свои данные, не внося в них изменений, эта ситуация
может продолжаться. Как только какой-нибудь из процессов обновит слово памяти,
нарушение защиты режима только для чтения приведет к системному прерыванию
операционной системы. После чего делается копия вызвавшей эту ситуацию страницы,
чтобы у каждого процесса имелся собственный экземпляр. Теперь для обеих копий
устанавливается режим чтения-записи — READ-WRITE, поэтому следующие записи
в каждую копию происходят без системного прерывания. Эта стратегия означает, что
те страницы, которые никогда не изменяются (включая все страницы программы), не
нуждаются в копировании. Копирование требуется только для тех страниц, которые
на самом деле подвергаются изменениям. Этот подход, названный копированием при
записи
(copy on write), повышает производительность за счет сокращения объема
копирования.
3.5.6. Совместно используемые библиотеки
Совместное использование может быть с другой степенью структурированности. Если
программа будет запущена дважды, то большинство операционных систем автомати-
чески организуют совместное использование текстовых страниц, чтобы в памяти была
только одна копия. Текстовые страницы всегда используются в режиме только для чте-
ния, поэтому проблем не возникает. В зависимости от операционной системы каждый