Файл: Tannenbaum.pdf

4 4 8 Глава 6. Уровень операционной системы

Если мы научимся определять, изменялась ли страница или не изменялась, то

сможем избежать ненужных переписываний на диск и сэкономим много времени.

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

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

Если пользовательская программа и данные время от времени заполняют ровно

целое число страниц, то когда они находятся в памяти, свободного места там не будет.

С другой стороны, если они не заполняют ровно целое число страниц, на последней

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

Если размер страницы составляет п байтов, то среднее неиспользованное про-

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

Более того, маленькие страницы снижают эффективность пропускной способ-

ности диска. Поскольку перед началом передачи данных с диска приходится ждать
примерно 10 млс (поиск + время вращения), выгоднее совершать большие пере-
дачи. При скорости передачи данных 10 Мбайт в секунду передача 8 Кбайт добав-

ляет всего 0,7 млс (по сравнению с передачей 1 Кбайт).

Однако у маленьких страниц есть свои преимущества. Если рабочее множество

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

Если бы размер страницы составлял 8 Кбайт, то для хранения всех страниц пона-

добилось бы 80 Мбайт.

Виртуальная память

449

При размере страницы в 1 Кбайт для хранения всех страниц потребуется всего

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

Сегментация

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

1. Таблица символов, которая содержит имена и атрибуты переменных.

2. Исходный текст, сохраняемый для распечатки.
3. Таблица, содержащая все использующиеся целочисленные константы и кон-

станты с плавающей точкой.

4. Дерево, содержащее синтаксический анализ программы.

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

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

Виртуальное

адресное пространство

Свободное •[

Используемое Г

в данный момент

Стек

вызовов

Дерево

Таблица

констант

Исходный

текст

Таблица

символов

t

т

Т

Адресное пространство,

i

 предназначенное

для стека вызовов

Рис. 6.6. В одномерном адресном пространстве, в котором содержатся постоянно

увеличивающиеся таблицы, одна из таблиц может «врезаться» в другую

Посмотрим, что произойдет, если программа содержит очень большое число

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

4 5 0 Глава 6. Уровень операционной системы

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

Компилятор может забирать свободное пространство у одних таблиц и переда-

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

На самом деле нужно просто освободить программиста от расширения и сокра-

щения таблиц, подобно тому как виртальная память исключает необходимость
следить за разбиением программы на оверлеи.

Для этого нужно создать много абсолютно независимых адресных пространств,

которые называются

 сегментами.

 Каждый сегмент состоит из линейной последо-

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

Так как каждый сегмент основывает отдельное адресное пространство, разные

сегменты могут увеличиваться или уменьшаться независимо друг от друга и не
влияя друг на друга. Если стеку в определенном сегменте понадобилось больше
адресного пространства (чтобы стек мог увеличиться), он может получить его, по-
скольку в его адресном пространстве больше не во что «врезаться». Естественно,

сегмент может переполниться, но это происходит редко, поскольку сегменты очень
большие. Чтобы определить адрес в двухмерной памяти, программа должна вы-
давать номер сегмента и адрес внутри сегмента. На рис. 6.7 изображена сегмен-
тированная память.

Мы подчеркиваем, что сегмент является логическим элементом, о котором про-

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

20К

16К

12К

8К

4К

О

Таблица

символов

Исходный

текст

Таблица

констант

Дерево

Стек

Сегмент 0 Сегмент 1 Сегмент 2 Сегмент 3 Сегмент 4

Рис. 6.7. Сегментированная память позволяет увеличивать

и уменьшать каждую таблицу независимо от других таблиц

Сегментированная память имеет и другие преимущества помимо упрощения

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

Виртуальная память

  4 5 1

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

Если процедура в сегменте п впоследствии изменяется и перекомпилируется,

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

Сегментация облегчает разделение общих процедур или данных между несколь-

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

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

Разные сегменты могут иметь разные виды защиты. Например, сегмент с про-

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

Вы должны понимать, почему защита имеет смысл только в сегментирован-

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

Таблица 6.4.

 Сравнение страничной организации памяти и сегментации

Свойства Страничная Сегментация

организация памяти

Должен ли программист знать об этом? Нет Да
Сколько линейных адресных 1 Много

пространств имеется?
Может ли виртуальное адресное пространство Да Да
увеличивать размер памяти?
Легко ли управлять таблицами Нет Да
с изменяющимися размерами?
Зачем была придумана такая технология? Чтобы смоделировать Чтобы обеспечить

память большого несколько адресных
размера пространств

4 5 2 Глава 6. Уровень операционной системы

Содержимое страницы в каком-то смысле случайно. Программист может ниче-

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

Как реализуется сегментация

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

места в памяти, один или несколько сегментов нужно сначала записать на диск

(если копия уже не находится там; в этом случае соответствующая копия просто

удаляется из памяти). В каком-то смысле подкачка сегментов очень похожа на

вызов страниц по требованию: сегменты загружаются и удаляются только в случае
необходимости.

Однако сегментация существенно отличается от разбиения на страницы в сле-

дующем: размер страниц фиксирован, а размер сегментов — нет. На рис. 6.8,

 а

показан пример физической памяти, в которой изначально содержится 5 сегмен-
тов. Посмотрим, что происходит, если сегмент 1 удаляется, а сегмент 7, который
меньше по размеру, помещается на его место. В результате получится конфигу-
рация, изображенная на рис. 6.8,

 б.

 Между сегментом 7 и сегментом 2 находит-

ся неиспользованная область («дырка»). Затем сегмент 4 меняется на сегмент 5
(рис. 6.8, в), а сегмент 3 замещается сегментом 6 (рис. 6.8,

 г).

 Через некоторое вре-

мя память разделится на ряд областей, одни из которых будут содержать сегменты,
а другие — неиспользованные области. Это называется

 внешней фрагментацией

(поскольку неиспользованное пространство попадает не в сегменты, а в «дырки»
между ними, то есть процесс происходит вне сегментов). Иногда внешнюю фраг-
ментацию называют

 поклеточной разбивкой.

Посмотрите, что произойдет, если программа обратится к сегменту 3 в тот

момент, когда память подвергается внешней фрагментации (рис. 6.8, г). Общее
пространство «дырок» составляет 10 Кбайт, а это больше, чем нужно для сегмента 3,
но так как это пространство разбито на маленькие кусочки, сегмент 3 туда загру-
зить нельзя. Вместо этого приходится сначала удалять другой сегмент.

Чтобы избежать такой ситуации, нужно сделать следующее. Каждый раз, когда

появляется «дырка», нужно перемещать сегменты, следующие за «дыркой», бли-
же к адресу 0, устраняя таким образом эту «дырку» и оставляя большую «дырку»
в конце. Есть и другой способ. Можно подождать, пока внешняя фрагментация
не примет серьезный оборот (когда на долю «дырок» приходится больше опре-
деленного процента от всего объема памяти), и только после этого совершить
уплотнение. На рис. 6.8,

 д

 показано, как память будет выглядеть после уплотнения.

Цель уплотнения памяти — собрать все маленькие «дырки» в одну большую «дыр-
ку», в которую можно поместить один или несколько сегментов. Недостаток