Размер страниц и фрагментация

Если пользовательская программа и данные занимают ровно целое число стра­ниц, то когда они время от времени загружаются в память, свободного места там не остается. В то же время, если они не занимают ровно целое число страниц, на последней странице останется неиспользованное пространство. Например, если программа и данные занимают 26 ООО байт на машине со страницами по 4096 байт, то первые 6 страниц будут заполнены целиком, что в сумме даст 6 х 4096 = 24 576 байт, а последняя страница будет содержать 26 ООО - 24576 = 1424 байта. Поскольку в каждой странице имеется пространство для 4096 байт, 2672 байта останутся свободными. Всякий раз, когда страница 7 будет оказываться в памя­ти, эти байты останутся неиспользуемыми, бесполезно занимая место в основ­ной памяти. Эта проблема получила название внутренней фрагментации (по­скольку неиспользуемое пространство является внутренним по отношению к стра­нице).

Если размер страницы составляет п байт, то среднее неиспользуемое про­странство последней страницы программы будет равно п/2 байт. Таким образом, чтобы свести к минимуму объем бесполезного пространства, страницы должны быть небольшими. Однако при маленьких страницах потребуется много страниц и большая таблица страниц. Если таблица страниц сохраняется аппаратно, то для хранения большой таблицы страниц нужно много регистров, что повышает стоимость компьютера. Кроме того, при запуске и остановке программы на за­грузку и сохранение этих регистров потребуется больше времени.

Больше того, маленькие страницы снижают эффективность использования пропускной способности диска. Поскольку перед началом передачи данных с диска приходится ждать примерно 10 миллисекунд (время поиска плюс задерж­ка вращения), выгодно передать побольше данных. При скорости передачи дан­ных 10 Мбайт/с, передача 8 Кбайт по сравнению с передачей 1 Кбайт добавляет всего 0,7 миллисекунд.

Однако у маленьких страниц есть свои преимущества. Если рабочее множест­во состоит из большого количества маленьких отделенных друг от друга облас­тей виртуального адресного пространства, то при небольшом размере страницы реже будет возникать пробуксовка (режим интенсивной подкачки), чем при большом. Рассмотрим матрицу А размером 10 ООО х 10 000, которая хранится в последовательных 8-байтных словах (Л[1,1], А[2,1], Л[3,1] и т. д.). При такой записи элементы строки 1 (Л[1,1], Л[1,2], Л[1,3] и т. д.) будут начинаться на рас­стоянии 80 000 байт друг от друга. Программе, обрабатывающей элементы этой строки, потребуется 10 000 областей, каждая из которых отделена от следующей величиной 79 992 байт. Если бы размер

страницы составлял 8 Кбайт, для хране­ния всех страниц понадобилось бы 80 Мбайт.

При размере страницы в 1 Кбайт для хранения всех страниц потребуется всего 10 Мбайт ОЗУ. При размере памяти в 32 Мбайт и размере страницы в 8 Кбайт программа войдет в режим интенсивной подкачки, а при размере страницы в 1 Кбайт этого не произойдет.

Сегментация

До сих пор мы говорили об одномерной виртуальной памяти, в которой вирту­альные адреса следуют один за другим от 0 до какого-то максимального адреса. Однако по многим причинам гораздо удобнее использовать два или несколько отдельных виртуальных адресных пространств. Например, компилятор может иметь несколько структур, которые создаются в процессе компиляции; такими структурами могут быть:

• символьная таблица с именами и атрибутами переменных;

• исходный текст для распечатки;

• таблица со всеми использующимися целочисленными константами и кон­стантами с плавающей точкой;

• дерево синтаксического разбора программы;

• стек, используемый для вызова процедур в компиляторе.Каждая из первых четырех структур постоянно растет в процессе компиля­ции. Размер последней структуры меняется совершенно непредсказуемо. В од­номерной памяти эти пять структур пришлось бы разместить в виртуальном ад­ресном пространстве в виде смежных областей, как показано на рис. 6.6.

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

Компилятор может забирать свободное пространство у одних структур и пе­редавать другим, но это будет напоминать управление оверлеями вручную — не­которое неудобство в лучшем случае и долгая нудная работа в худшем.

На самом деле нужно просто освободить программиста от необходимости ду­мать о расширении и сокращении структур, подобно тому, как виртуальная па­мять позволяет забыть о разбиении программы на оверлеи.

Для этого нужно создать множество абсолютно независимых адресных про­странств, которые называются сегментами. Каждый сегмент состоит из линей­ной последовательности адресов от 0 до какого-либо допустимого максимума. Разные сегменты могут иметь разную длину (обычно так и бывает). Более того, длина сегмента может меняться во время выполнения программы. Длина стеко­вого сегмента может увеличиваться всякий раз, когда что-либо помещается в стек, и уменьшаться, когда что-либо выталкивается из стека.

Так как каждый сегмент образует отдельное адресное пространство, разные сегменты могут увеличиваться или уменьшаться независимо друг от друга и не влияя друг на друга. Если стеку в определенном сегменте потребуется больше адресного пространства (чтобы стек мог расти), он может получить его, поскольку его адресному пространству больше не во что «врезаться». Естественно, сегмент может переполниться, но это происходит редко, поскольку сегменты очень боль­шие. Чтобы задать адрес в двухмерной памяти, программа должна указать номер сегмента и адрес внутри сегмента. Сегментированная память изображена на рис. 6.7.

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

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

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

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

Поскольку каждый сегмент являет собой логический объект (например, про­цедуру, массив или стек), о существовании которого знает программист, разные сегменты можно защищать по-разному. Например, сегменту с процедурой мож­но назначить атрибут «только для выполнения», запретив тем самым считыва­ние из него и запись в него. Для массива с плавающей точкой можно разрешить только чтение и запись, но не выполнение и т. д. Такая защита часто помогает выявлять программные ошибки.

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

Таблица 6-1- Сравнение страничной организации памяти и сегментации

Свойство	Страничная организация памяти	Сегментация
Необходимость учета программистом	Нет	Да
Количество линейных адресных пространств	1	Много
Возможность увеличения памяти для виртуального адресного пространств	Да	Да
Простота управления структурами переменного размера	Нет	Да
Назначение технологии	Имитация памяти большого размера	Предоставление нескольких адресных пространств

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