До сих пор мы помещали все адресное пространство каждого процесса в память. С помощью регистров base-and-bounds ОС может легко перемещать процессы в различные части физической памяти. Однако вы, возможно, заметили кое-что интересное в этих наших адресных пространствах: есть большой кусок “свободного” пространства прямо посередине, между стеком и кучей.
Как вы можете себе представить из рис. 16.1, хотя пространство между стеком и кучей не используется процессом, оно все еще занимает физическую память, когда мы перемещаем все адресное пространство куда-то в физическую память; таким образом, простой подход использования пары регистров base-and-bounds для виртуализации памяти является расточительным. Это также делает довольно трудным запуск программы, когда все адресное пространство не помещается в память; таким образом, подход base-and-bounds не так гибок, как хотелось бы. И таким образом:
СУТЬ: КАК ПОДДЕРЖИВАТЬ БОЛЬШОЕ АДРЕСНОЕ ПРОСТРАНСТВО
Как мы поддерживаем большое адресное пространство с (потенциально) большим количеством свободного пространства между стеком и кучей? Обратите внимание, что в наших примерах с крошечными (притворными) адресными пространствами мусора в виде неиспользуемой памяти, кажется, не так много. Представьте себе, однако, 32-битное адресное пространство (4 ГБ); типичная программа будет использовать только мегабайты памяти, но все равно потребует, чтобы все адресное пространство было резидентным в памяти.
Segmentation: Generalized Base/Bounds
Чтобы решить эту проблему, родилась идея, и она называется сегментацией. Это довольно старая идея, восходящая, по крайней мере, к самому началу 1960-х годов. Идея проста: вместо того, чтобы иметь только одну пару base-and-bounds для всей памяти, почему бы не иметь пару base-and-bounds на логический сегмент адресного пространства? Сегмент-это просто непрерывная часть адресного пространства определенной длины, и в нашем каноническом адресном пространстве у нас есть три логически различных сегмента: код, стек и куча. Сегментация позволяет ОС размещать каждый из этих сегментов в разных частях физической памяти и, таким образом, избегать заполнения физической памяти неиспользуемым виртуальным адресным пространством.
Давайте рассмотрим пример. Предположим, мы хотим поместить адресное пространство из рисунка 16.1 в физическую память. Имея пару base-and-bounds для каждого сегмента, мы можем поместить каждый сегмент независимо в физическую память. Например, см. рис. 16.2; там вы видите физическую память объемом 64 КБ с этими тремя сегментами (и 16 КБ, зарезервированными для ОС).
Как вы можете видеть на диаграмме, в физической памяти выделяется только используемая память, и поэтому можно разместить большие адресные пространства с большим количеством неиспользуемого адресного пространства (которое мы иногда называем разреженными адресными пространствами).
Аппаратная структура в нашем MMU, необходимая для поддержки сегментации, именно такая, как вы ожидаете: в данном случае набор из трех пар регистров base-and-bounds. На рис. 16.3 ниже показаны значения регистров для приведенного выше примера; каждый регистр границ содержит размер сегмента.
Из рисунка видно, что сегмент кода помещен по физическому адресу 32 КБ и имеет размер 2 КБ, а сегмент кучи помещен по адресу 34 КБ и имеет размер 3 КБ. Сегмент размера здесь точно такой же, как регистр границ, введенный ранее; он точно сообщает аппаратному обеспечению, сколько байтов допустимо в этом сегменте (и, таким образом, позволяет аппаратному обеспечению определить, когда программа совершила незаконный доступ за пределы этих границ).
Давайте повторим процесс трансляции, используя адресное пространство на рис. 16.1. Предположим, что ссылка сделана на виртуальный адрес 100 (который находится в сегменте кода, как вы можете видеть визуально на рис. 16.1). Когда происходит ссылка (скажем, на выборку команд), аппаратное обеспечение добавляет базовое значение к смещению в этот сегмент (в данном случае 100), чтобы получить желаемый физический адрес: 100 + 32 КБ или 32868. Затем он проверит, что адрес находится в пределах границ (100 меньше 2 КБ), обнаружит, что это так, и выдаст ссылку на адрес физической памяти 32868.
ОШИБКА СЕГМЕНТАЦИИ (Segmentation Fault)
Термин ошибка сегментации (Segmentation Fault) или нарушение (violation) возникает из-за доступа к памяти на сегментированной машине к незаконному адресу. Забавно, но этот термин сохраняется даже на машинах, вообще не поддерживающих сегментацию. Это не так смешно, если вы не можете понять, почему ваш код продолжает давать сбои.
Теперь давайте посмотрим на адрес в куче, виртуальный адрес 4200 (снова обратитесь к рис. 16.1). Если мы просто добавим виртуальный адрес 4200 к основанию кучи (34 КБ), мы получим физический адрес 39016, который не является правильным физическим адресом. Сначала нам нужно извлечь смещение в кучу, то есть определить, к какому байту(байтам) в этом сегменте относится адрес. Поскольку куча начинается с виртуального адреса 4 КБ (4096), смещение 4200 на самом деле равно 4200 минус 4096, или 104. Затем мы берем это смещение (104) и добавляем его к физическому адресу базового регистра (34K), чтобы получить желаемый результат: 34920.
Что, если мы попытаемся сослаться на незаконный адрес (то есть виртуальный адрес размером 7 КБ или больше), который находится за пределами кучи? Вы можете себе представить, что произойдет: аппаратное обеспечение обнаружит, что адрес находится за пределами границ, отправит trap в ОС, что, вероятно, приведет к прекращению процесса-нарушителя. И теперь вы знаете происхождение знаменитого термина, которого все программисты на языке Си боятся: нарушение сегментации (segmentation violation) или ошибка сегментации (segmentation fault).
О Каком Сегменте Идет Речь?
Аппаратное обеспечение использует сегментные регистры во время трансляции. Как оно узнает смещение в сегмент и к какому сегменту относится адрес?
Один из распространенных подходов, иногда называемый явным подходом, заключается в разделении адресного пространства на сегменты на основе нескольких верхних битов виртуального адреса; этот метод был использован в системе VAX/VMS. В приведенном выше примере у нас есть три сегмента; таким образом, нам нужно два бита для выполнения нашей задачи. Если мы используем два верхних бита нашего 14-битного виртуального адреса для выбора сегмента, наш виртуальный адрес выглядит следующим образом:
В нашем примере, если два верхних бита равны 00, аппаратное обеспечение знает, что виртуальный адрес находится в сегменте кода, и поэтому использует пару base-and-bounds сегмента Code для перемещения адреса в правильное физическое местоположение. Если два верхних бита равны 01, аппаратное обеспечение знает, что адрес находится в куче, и поэтому использует base-and-bounds сегмента Heap. Давайте возьмем наш пример виртуального адреса кучи сверху (4200) и переведем его, просто чтобы убедиться, что не осталось вопросов. Виртуальный адрес 4200 в двоичном виде можно увидеть здесь:
Как видно из рисунка, два верхних бита (01) сообщают аппаратному обеспечению, о каком сегменте идет речь. Нижние 12 бит-это смещение в сегмент: 0000 0110 1000, или шестнадцатеричный 0x068, или 104 в десятичном виде. Таким образом, аппаратное обеспечение просто берет первые два бита, чтобы определить, какой сегментный регистр использовать, а затем берет следующие 12 битов в качестве смещения в сегмент. Добавляя базовый регистр к смещению, аппаратное обеспечение получает конечный физический адрес. Обратите внимание, что смещение также облегчает проверку границ: мы можем просто проверить, меньше ли смещение границ; если нет, то адрес является незаконным. Таким образом, если бы база и границы были массивами (с одной записью на сегмент), аппаратное обеспечение делало бы что-то подобное, чтобы получить желаемый физический адрес:
В нашем запущенном примере мы можем заполнить значения для приведенных выше констант. В частности, SEG_MASK будет иметь значение 0x3000, SEG_SHIFT - 12, и OFFSET_MASK - 0xFFF.
Возможно, вы также заметили, что когда мы используем два верхних бита, а у нас есть только три сегмента (код, куча, стек), один сегмент адресного пространства остается неиспользуемым. Чтобы полностью использовать виртуальное адресное пространство (и избежать неиспользуемого сегмента), некоторые системы помещают код в тот же сегмент, что и куча, и таким образом используют только один бит для выбора того, какой сегмент использовать.
Еще одна проблема, связанная с использованием верхнего количества битов для выбора сегмента, заключается в том, что это ограничивает использование виртуального адресного пространства. В частности, каждый сегмент ограничен максимальным размером, который в нашем примере составляет 4 КБ (использование двух верхних битов для выбора сегментов подразумевает, что адресное пространство 16 КБ будет разрезано на четыре части, или 4 КБ в этом примере). Если запущенная программа хочет увеличить сегмент (скажем, кучу или стек) сверх этого максимума, программе не повезло.
Существуют и другие способы для аппаратного обеспечения определить, в каком сегменте находится конкретный адрес. В неявном подходе аппаратное обеспечение определяет сегмент, замечая, как был сформирован адрес. Если, например, адрес был сгенерирован из счетчика программы (то есть это была выборка инструкций), то адрес находится в сегменте кода; если адрес основан на стеке или base pointer, он должен быть в сегменте стека; любой другой адрес должен быть в куче.
Что там со стэком?
До сих пор мы упустили один важный компонент адресного пространства-стек. Стек был перемещен на физический адрес 28 КБ на приведенной выше диаграмме, но с одним критическим отличием: он растет назад (то есть в сторону более низких адресов). В физической памяти он “начинается” с 28КБ1 и вырастает обратно до 26КБ, что соответствует виртуальным адресам от 16КБ до 14КБ; трансляция должна идти по-другому.
Первое, что нам нужно, - это немного дополнительной аппаратной поддержки. Вместо обычных значений base-and-bounds аппаратное обеспечение также должно знать, в какую сторону растет сегмент (бит, например, устанавливается равным 1, когда сегмент растет в положительном направлении, и 0 для отрицательного). Наше обновленное представление о том, что отслеживает аппаратное обеспечение, показано на рис. 16.4:
Поскольку аппаратное обеспечение понимает, что сегменты могут расти в отрицательном направлении, аппаратное обеспечение теперь должно переводить такие виртуальные адреса немного по-другому. Давайте возьмем пример виртуального адреса стека и переведем его, чтобы понять процесс.
В этом примере предположим, что мы хотим получить доступ к виртуальному адресу 15 КБ, который должен сопоставляться с физическим адресом 27 КБ. Таким образом, наш виртуальный адрес в двоичной форме выглядит следующим образом: 11 1100 0000 0000 (hex 0x3C00). Аппаратное обеспечение использует два верхних бита (11) для обозначения сегмента, но тогда мы остаемся со смещением 3 КБ. Чтобы получить правильное отрицательное смещение, мы должны вычесть максимальный размер сегмента из 3 КБ: в этом примере сегмент может быть 4 КБ, и, таким образом, правильное отрицательное смещение равно 3 КБ минус 4 КБ, что равно-1 КБ. Мы просто добавляем отрицательное смещение (-1 КБ) к базе (28 КБ), чтобы получить правильный физический адрес: 27 КБ. Проверка границ может быть рассчитана путем обеспечения того, чтобы абсолютное значение отрицательного смещения было меньше или равно текущему размеру сегмента (в данном случае 2 Кб).
- Хотя для простоты мы говорим, что стек “начинается” с 28 КБ, это значение на самом деле является байтом чуть ниже местоположения области обратного роста; первый допустимый байт на самом деле равен 28 КБ минус 1. В отличие от этого, растущие вперед области начинаются с адреса первого байта сегмента. Мы используем этот подход, потому что он делает математику для вычисления физического адреса простой: физический адрес-это просто база плюс отрицательное смещение.
Support for Sharing
По мере того как поддержка сегментации росла, разработчики систем вскоре поняли, что они могут реализовать новые типы эффективности с немного большей аппаратной поддержкой. В частности, для экономии памяти иногда полезно разделить определенные сегменты памяти между адресными пространствами. В частности, совместное использование кода широко распространено и все еще используется в системах сегодня.
Для поддержки совместного использования памяти нам нужна небольшая дополнительная поддержка со стороны аппаратного обеспечения в виде битов защиты. Базовая поддержка добавляет несколько битов на сегмент, указывая, может ли программа читать или записывать сегмент или, возможно, выполнять код, лежащий внутри сегмента. Установив сегмент кода только для чтения, один и тот же код может быть разделен между несколькими процессами, не беспокоясь о вреде изоляции; в то время как каждый процесс все еще думает, что он обращается к своей собственной частной памяти, ОС тайно делится памятью, которая не может быть изменена процессом, и таким образом иллюзия сохраняется.
Пример дополнительной информации, отслеживаемой аппаратным обеспечением (и ОС), показан на рис. 16.5. Как вы можете видеть, сегмент кода настроен на чтение и выполнение, и поэтому один и тот же физический сегмент в памяти может быть сопоставлен с несколькими виртуальными адресными пространствами.
С защитными битами аппаратный алгоритм, описанный ранее, также должен был бы измениться. В дополнение к проверке того, находится ли виртуальный адрес в пределах границ, аппаратное обеспечение также должно проверить, допустим ли конкретный доступ. Если пользовательский процесс пытается выполнить запись в сегмент, доступный только для чтения, или выполнить из неисполняемого сегмента, аппаратное обеспечение должно вызвать исключение и, таким образом, позволить ОС справиться с нарушающим процессом.
Fine-grained vs. Coarse-grained Segmentation
Большинство наших примеров до сих пор были сосредоточены на системах с несколькими сегментами (например, код, стек, куча); мы можем думать об этой сегментации как о coarse-grained, поскольку она разбивает адресное пространство на относительно большие, грубые куски. Однако некоторые ранние системы (например, Multics) были более гибкими и позволяли адресным пространствам состоять из большого числа более мелких сегментов, называемых fine-grained.
Поддержка многих сегментов требует еще большей аппаратной поддержки, с некоторой таблицей сегментов, хранящейся в памяти. Такие таблицы сегментов обычно поддерживают создание очень большого числа сегментов и, таким образом, позволяют системе использовать сегменты более гибкими способами, чем мы до сих пор обсуждали. Например, ранние машины, такие как Burroughs B5000, поддерживали тысячи сегментов и ожидали, что компилятор будет разделять код и данные на отдельные сегменты, которые затем будут поддерживать ОС и аппаратное обеспечение. В то время считалось, что, имея fine-grained сегменты, ОС может лучше узнать, какие сегменты используются, а какие нет, и таким образом более эффективно использовать основную память.
OS Support
Теперь вы должны иметь базовое представление о том, как работает сегментация. Фрагменты адресного пространства перемещаются в физическую память по мере работы системы, и таким образом достигается огромная экономия физической памяти по сравнению с нашим более простым подходом с использованием только одной пары base-and-bounds для всего адресного пространства. В частности, все неиспользуемое пространство между стеком и кучей не должно быть выделено в физической памяти, что позволяет нам помещать больше адресных пространств в физическую память и поддерживать большое и разреженное виртуальное адресное пространство для каждого процесса.
Однако сегментация порождает ряд новых проблем для операционной системы. Первый: что должна делать ОС при переключении контекста? Вы уже должны догадаться: регистры сегментов должны быть сохранены и восстановлены. Очевидно, что каждый процесс имеет свое собственное виртуальное адресное пространство, и ОС должна убедиться, что эти регистры правильно настроены, прежде чем позволить процессу работать снова.
Второе - это взаимодействие ОС, когда сегменты растут (или, возможно, уменьшаются). Например, программа может вызвать malloc() для выделения объекта. В некоторых случаях существующая куча сможет обслуживать запрос, и таким образом malloc() найдет свободное место для объекта и вернет указатель на него. В других, однако, сам сегмент кучи может нуждаться в увеличении размера. В этом случае библиотека выделения памяти выполнит системный вызов для увеличения кучи (например, традиционный системный вызов UNIX sbrk()). Затем ОС (обычно) предоставляет больше места, обновляя регистр размера сегмента до нового (большего) размера и информируя библиотеку об успехе; затем библиотека может выделить место для нового объекта и успешно вернуться к вызывающей программе. Обратите внимание, что ОС может отклонить запрос, если больше нет физической памяти или если она решит, что вызывающий процесс уже имеет слишком много.
Последний и, возможно, самый важный вопрос-это управление свободным пространством в физической памяти. Когда создается новое адресное пространство, ОС должна иметь возможность найти место в физической памяти для своих сегментов. Ранее мы предполагали, что каждое адресное пространство имеет одинаковый размер, и поэтому физическую память можно рассматривать как набор слотов, в которые помещаются процессы. Теперь у нас есть несколько сегментов для каждого процесса, и каждый сегмент может быть разного размера.
Общая проблема, которая возникает, заключается в том, что физическая память быстро заполняется маленькими дырочками свободного пространства, что затрудняет выделение новых сегментов или увеличение существующих. Мы называем эту проблему внешней фрагментацией [R69]; см. рис. 16.6 (слева)
В этом примере появляется процесс, который хочет выделить сегмент размером 20 КБ. В этом примере есть 24 КБ свободного места, но не в одном непрерывном сегменте (скорее, в трех несмежных кусках). Таким образом, ОС не может удовлетворить запрос на 20 КБ. Подобные проблемы могут возникнуть при поступлении запроса на увеличение сегмента; если следующее такое количество байтов физического пространства недоступно, ОС придется отклонить запрос, даже если в другом месте физической памяти могут быть свободные байты.
Одним из решений этой проблемы было бы сжатие физической памяти путем перестановки существующих сегментов. Например, ОС может остановить запущенные процессы, скопировать их данные в одну смежную область памяти, изменить значения сегментных регистров, чтобы указать на новые физические местоположения, и, таким образом, иметь большой свободный объем памяти для работы. Таким образом, ОС позволяет успешно выполнить новый запрос на выделение. Однако сжатие дорого обходится, так как копирование сегментов требует больших затрат памяти и, как правило, занимает значительное количество процессорного времени; см.
Рис. 16.6 (справа) для диаграммы уплотненной физической памяти. Уплотнение также (по иронии судьбы) затрудняет обслуживание запросов на увеличение существующих сегментов и, таким образом, может привести к дальнейшей перестройке для удовлетворения таких запросов.
Вместо этого более простой подход может заключаться в использовании алгоритма управления свободными списками, который пытается сохранить большие объемы памяти доступными для выделения. Существуют буквально сотни подходов, которые люди использовали, включая классические алгоритмы, такие как best-fit (который сохраняет список свободных пространств и возвращает наиболее близкий по размеру, который удовлетворяет желаемому распределению запрашивающему), worst-fit, first-fit и более сложные схемы, такие как buddy algorithm. Отличный обзор Уилсона и др. это хорошее место для начала, если вы хотите узнать больше о таких алгоритмах, или вы можете подождать, пока мы не рассмотрим некоторые основы в следующей главе. К сожалению, однако, каким бы умным ни был алгоритм, внешняя фрагментация все равно будет существовать; таким образом, хороший алгоритм просто пытается минимизировать ее.
Резюме
Сегментация решает ряд проблем и помогает нам построить более эффективную виртуализацию памяти. Помимо простого динамического перемещения, сегментация может лучше поддерживать разреженные адресные пространства, избегая огромной потенциальной потери памяти между логическими сегментами адресного пространства. Это также быстро, так как выполнение арифметической сегментации требует простоты и хорошо подходит для аппаратного обеспечения; накладные расходы на перевод минимальны. Возникает и дополнительная выгода: совместное использование кода. Если код помещен в отдельный сегмент, такой сегмент потенциально может быть общим для нескольких запущенных программ.
Однако, как мы узнали, выделение сегментов переменного размера в памяти приводит к некоторым проблемам, которые мы хотели бы преодолеть. Первая, как уже говорилось выше, - это внешняя фрагментация. Поскольку сегменты имеют переменный размер, свободная память дробится на части нечетного размера, и поэтому удовлетворение запроса на выделение памяти может быть затруднено. Можно попробовать использовать умные алгоритмы или периодически компактную память, но проблема фундаментальна и ее трудно избежать.
Вторая и, возможно, более важная проблема заключается в том, что сегментация все еще недостаточно гибка, чтобы поддерживать наше полностью обобщенное, разреженное адресное пространство. Например, если у нас есть большая, но редко используемая куча в одном логическом сегменте, вся куча все равно должна находиться в памяти, чтобы к ней можно было получить доступ. Другими словами, если наша модель того, как используется адресное пространство, не совсем соответствует тому, как базовая сегментация была разработана для его поддержки, сегментация работает не очень хорошо. Поэтому нам нужно найти какие-то новые решения. Готовы их найти?