Добавлен: 29.10.2018
Просмотров: 48064
Скачиваний: 190
3.2. Абстракция памяти: адресные пространства
221
перед обращением к памяти к каждому автоматически сгенерированному адресу добав-
ляется значение базового регистра. Многие реализации предусматривают такую защиту
базового и ограничительного регистров, при которой изменить их значения может только
операционная система. Именно так был устроен компьютер CDC 6600, в отличие от ком-
пьютеров на основе Intel 8088, у которых не было даже ограничительного регистра. Но
у последних было несколько базовых регистров, позволяющих, к примеру, реализовать
независимое перемещение текста и данных программы, но не предлагающих какой-либо
защиты от ссылок за пределы выделенной памяти.
Недостатком перемещений с использованием базовых и ограничительных регистров
является необходимость применения операций сложения и сравнения к каждой ссылке
на ячейку памяти. Сравнение может осуществляться довольно быстро, но сложение
является слишком медленной операцией из-за затрат времени на вспомогательный
сигнал переноса, если, конечно, не используются специальные сумматоры.
3.2.2. Свопинг
Если у компьютера объем памяти достаточен для размещения всех процессов, то все
рассмотренные до сих пор схемы будут в той или иной степени работоспособны. Но на
практике суммарный объем оперативной памяти, необходимый для размещения всех
процессов, зачастую значительно превышает имеющийся объем ОЗУ. На обычных
Windows-, OS X- или Linux-системах при запуске компьютера могут быть запущены
50–100 или более процессов. Например, при установке приложения Windows зачастую
выдаются команды, чтобы при последующих запусках системы запускался процесс,
единственной задачей которого была бы проверка наличия обновлений для этого при-
ложения. Такой процесс запросто может занять 5–10 Мбайт памяти. Остальные фоно-
вые процессы проверяют наличие входящей почты, входящих сетевых подключений
и многое другое. И все это еще до того, как будет запущена первая пользовательская
программа. Современные солидные пользовательские прикладные программы вроде
Photoshop могут запросто требовать просто для запуска 500 Мбайт памяти, а при на-
чале обработки данных занимать множество гигабайт. Следовательно, постоянное
содержание всех процессов в памяти требует огромных объемов и не может быть осу-
ществлено при дефиците памяти.
С годами для преодоления перегрузки памяти были выработаны два основных под-
хода. Самый простой из них, называемый свопингом, заключается в размещении
в памяти всего процесса целиком, его запуске на некоторое время, а затем сбросе на
диск. Бездействующие процессы большую часть времени хранятся на диске и в не-
рабочем состоянии не занимают пространство оперативной памяти (хотя некоторые
из них периодически активизируются, чтобы проделать свою работу, после чего опять
приостанавливаются). Второй подход называется виртуальной памятью, он позволяет
программам запускаться даже в том случае, если они находятся в оперативной памяти
лишь частично. Далее в этом разделе мы рассмотрим свопинг, а в последующих раз-
делах будет рассмотрена и виртуальная память.
Работа системы с использованием свопинга показана на рис. 3.4. Изначально в памя-
ти присутствует только процесс A. Затем создаются или появляются в памяти путем
свопинга с диска процессы B и C. На рис. 3.4, г процесс A за счет свопинга выгружается
на диск. Затем появляется процесс D и выгружается из памяти процесс B. И наконец,
снова появляется в памяти процесс A. Поскольку теперь процесс A находится в другом
222
Глава 3. Управление памятью
месте, содержащиеся в нем адреса должны быть перестроены либо программным путем,
при загрузке в процессе свопинга, либо (скорее всего) аппаратным путем в процессе
выполнения программы. К примеру, для этого случая хорошо подойдут механизмы
базового и ограничительного регистров.
Рис. 3.4. Изменения в выделении памяти по мере появления процессов в памяти
и выгрузки их из нее (неиспользованные области памяти заштрихованы)
Когда в результате свопинга в памяти создаются несколько свободных областей, их
можно объединить в одну большую за счет перемещения при первой же возможности
всех процессов в нижние адреса. Эта технология известна как уплотнение памяти. Но
зачастую она не выполняется, поскольку отнимает довольно много процессорного
времени. К примеру, на машине, оснащенной 16 Гбайт памяти, способной скопировать
8 байт за 8 нс, на уплотнение всего объема памяти может уйти около 16 с.
Стоит побеспокоиться о том, какой объем памяти нужно выделить процессу при его
создании или загрузке в процессе свопинга. Если создаваемый процесс имеет вполне
3.2. Абстракция памяти: адресные пространства
223
определенный неизменный объем, то выделение упрощается: операционная система
предоставляет процессу строго необходимый объем памяти, ни больше ни меньше.
Но если сегмент данных процесса может разрастаться, к примеру, за счет динамиче-
ского распределения памяти, как во многих языках программирования, то каждая
попытка разрастания процесса вызывает проблему. Если к выделенному пространству
памяти примыкает свободное место, то оно может быть распределено процессу и он
сможет расширяться в пределах этого свободного пространства. В то же время, если
память, выделенная процессу, примыкает к памяти другого процесса, то либо раз-
растающийся процесс должен быть перемещен на свободное пространство памяти,
достаточное для его размещения, либо один или более процессов сброшены на диск
путем свопинга, чтобы образовалось достаточно свободного пространства. Если про-
цесс не может разрастаться в памяти и область свопинга на диске уже заполнена, то
процессу придется приостановить свою работу до тех пор, пока не освободится не-
которое пространство памяти (или же этот процесс может быть уничтожен).
Если предполагается, что большинство процессов по мере выполнения будут разрас-
таться, то, наверное, будет лучше распределять небольшой объем дополнительной
памяти при каждой загрузке из области свопинга на диске в память или перемещении
процесса, чтобы сократить потери, связанные со свопингом или перемещением про-
цессов, которые больше не помещаются в отведенной им памяти. Но свопингу на диск
должна подвергаться только реально задействованная память, копировать при этом
еще и дополнительно выделенную память будет слишком расточительно. На рис. 3.5, а
показана конфигурация памяти, в которой пространства для разрастания были вы-
делены двум процессам.
Рис. 3.5. Выделение памяти: а — под разрастающийся сегмент данных;
б — под разрастающийся стек и сегмент данных
Если процессы могут иметь два разрастающихся сегмента, к примеру сегмент данных,
используемый в качестве динамически выделяемой и освобождаемой памяти для пере-
224
Глава 3. Управление памятью
менных, и сегмент стека для обычных локальных переменных и адресов возврата, то
предлагается альтернативная структура распределения памяти (рис. 3.5, б). На этом
рисунке видно, что у каждого изображенного процесса в верхних адресах выделенной
ему памяти имеется стек, растущий вниз, и сразу над текстом программы — сегмент
данных, растущий вверх. Разделяющая их память может использоваться обоими сег-
ментами. Если она иссякнет, процесс должен быть перемещен в свободное пространство
достаточного размера (или же перемещен из памяти в область свопинга) до тех пор,
пока не будет создано достаточное по размеру свободное пространство, либо он должен
быть уничтожен.
3.2.3. Управление свободной памятью
Если память распределяется в динамическом режиме, то управлять этим должна опе-
рационная система. В общих чертах, существуют два способа отслеживания использо-
вания памяти: битовые матрицы и списки свободного пространства. Мы рассмотрим
эти два метода в этом и следующем разделах. В главе 10 распределители памяти buddy
и slab, используемые в Linux, будут рассмотрены более подробно.
Управление памятью с помощью битовых матриц
При использовании битовых матриц память делится на единичные блоки размером от
нескольких слов до нескольких килобайт. С каждым единичным блоком соотносится
один бит в битовой матрице, который содержит 0, если единичный блок свободен, и 1,
если он занят (или наоборот). На рис. 3.6 показаны часть памяти и соответствующая
ей битовая матрица.
Важным вопросом для разработчика является размер единичного блока памяти. Чем
меньше блок, тем больше битовая матрица. Но даже с таким небольшим единичным
блоком памяти, размер которого равен 4 байта, для 32 бит памяти понадобится 1 бит
матрицы. Память, состоящая из 32n бит, будет использовать n бит матрицы, таким
Рис. 3.6. Часть памяти с пятью процессами и тремя свободными пространствами, единичные
блоки памяти разделены вертикальными штрихами: а — заштрихованные области
(которым соответствует 0 в битовой матрице) являются свободными; б — соответствующая
битовая матрица; в — та же самая информация в виде списка
3.2. Абстракция памяти: адресные пространства
225
образом, битовая матрица займет лишь 1/32 памяти. Если выбран более объемный
единичный блок памяти, битовая матрица будет меньше, но тогда в последнем блоке
процесса, если он не будет в точности кратен размеру единичного блока, будет впустую
теряться довольно существенный объем памяти.
Битовая матрица предоставляет довольно простой способ отслеживания слов памяти
в фиксированном объеме памяти, поскольку ее размер зависит только от размера па-
мяти и размера единичного блока памяти. Основная проблема заключается в том, что
при решении поместить в память процесс, занимающий k единичных блоков, диспетчер
памяти должен искать в битовой матрице непрерывную последовательность нулевых
битов. Поиск в битовой матрице последовательности заданной длины — довольно мед-
ленная операция (поскольку последовательность может пересекать границы слов в ма-
трице), и это обстоятельство служит аргументом против применения битовых матриц.
Управление памятью с помощью связанных списков
Другим способом отслеживания памяти является ведение связанных списков рас-
пределенных и свободных сегментов памяти, где сегмент либо содержит процесс,
либо является пустым пространством между двумя процессами. Участок памяти, изо-
браженный на рис. 3.6, а, представлен на рис. 3.6, в, как связанный список сегментов.
Каждая запись в списке хранит обозначение, содержит сегмент «дыру» — hole (H) или
процесс — process (P), адрес, с которого сегмент начинается, его длину и указатель на
следующую запись.
В этом примере список сегментов составлен отсортированным по адресам. Преиму-
щество такой сортировки заключается в том, что при завершении процесса или его
свопинге на диск упрощается обновление списка. У завершившегося процесса есть,
как правило, два соседа (за исключением тех случаев, когда он находился в верхних
или нижних адресах памяти). Этими соседями могут быть либо процессы, либо пустые
пространства, из чего можно составить четыре комбинации, показанные на рис. 3.7.
На рис. 3.7, а обновление списка требует замены P на H. На рис. 3.7, б и в две записи
объединяются в одну, и список становится на одну запись короче. На рис. 3.7, г объ-
единяются три записи, и из списка удаляются уже две записи.
Поскольку запись в таблице процессов, относящаяся к завершающемуся процессу, бу-
дет, как правило, указывать на запись в списке именно для этого процесса, возможно,
удобнее будет вести не односвязный список, как показано на рис. 3.6, в, а двусвязный
список. Такая структура облегчит поиск предыдущей записи и определение возмож-
ности объединения.
Рис. 3.7. Четыре комбинации соседей для завершающегося процесса X