Сегментация памяти

Размещено на http://www.allbest.ru/

1. Сегментация памяти. Реализация сегментации

Системы виртуальной памяти можно разделить на два класса:

системы с фиксированным размером блоков, называемых страницами, и системы с переменным размером блоков, называемых сегментами.

Основные понятия сегментации.

Рассмотрим пример, когда программа использует одно адресное пространство.

Недостатки такой системы:

Один участок может полностью заполниться, но при этом останутся свободные участки. Можно конечно перемещать участки, но это очень сложно.

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

Рассмотрим то же пример с использованием сегментов:

Каждый сегмент может расти или уменьшаться независимо от других.

Сегментированная память

Сегмент - это логический объект.

В этом случае адрес имеет две части:

o номер сегмента

o адрес в сегменте

Преимущества сегментации:

o Сегменты не мешают друг другу.

o Начальный адрес процедуры всегда начинается с (n,0). Это упрощает программирование.

o Облегчает совместное использование процедур и данных.

o Раздельная защита каждого сегмента (чтение, запись).

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

Если страницы имеют фиксированный размер, то сегменты нет.

У сегментов так же, как и у страниц, существует проблема фрагментации.

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

2. Сегментация с использованием страниц: MULTICS

В одной из первых, где была применена страничная сегментация, была система MULTICS.

Каждая программа обеспечивалась до 2^18 сегментов (более 250 000), каждый из которых мог быть до 65 536 (36-разрядных) слов длиной.

Таблица сегментов - хранит дескриптор для каждого сегмента. У каждой программы своя таблица.

Т.к. записей в таблице более 250 000, она сама разбита на страницы.

Сама таблица является отдельным сегментом.

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

Нормальный размер страницы равен 1024 словам. Если сегмент меньше 1024, то он либо не разбит на страницы, либо разбит на страницы по 64 слова.

Дескриптор сегмента

Когда происходит обращение к памяти, выполняется следующий алгоритм:

1. По номеру сегмента находится дескриптор сегмента.

2. Проверяется, находиться ли таблица страницы в памяти. Если в памяти, определяется ее расположение. Если нет, вызывается сегментное прерывание.

3. Проверяется, находиться ли страница в памяти. Если в памяти, определяется ее расположение в памяти. Если нет в памяти, вызывается страничное прерывание.

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

5. Происходит запись или чтение.

3. Преобразование адреса в системе MULTICS

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

Сегментация с использованием страниц: Intel Pentium

Каждая программа обеспечивается до 16К сегментов, каждый из которых может быть до 1 млдр 36-разрядных слов длиной.

Основа виртуальной памяти системы Pentium состоит из двух таблиц:

o Локальная таблица дескрипторов LDT (Local Descriptor Table) - есть у каждой программы, и описывает сегменты программы.

o Глобальная таблица дескрипторов GDT (Global Descriptor Table) - одна для всех программ, и описывает системные сегменты (включая саму ОС).

Каждый селектор (указывает на дескриптор) представляет собой 16-разрядный номер.

4. Селектор в системе Pentium

13 битов определяют номер записи в таблице дескрипторов, поэтому эти таблицы ограничены, каждая содержит 8К (2^13) сегментных дескрипторов.

1 бит указывает тип используемой таблицы дескрипторов LDT или GDT.

5. Уровни привилегированности в системе Pentium

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

С учетом максимального размера сегмента - 4 Гбайта - каждая задача, при чисто сегментной организации виртуальной памяти, работает в виртуальном адресном пространстве в 64 Тбайта (4 Гбайта * 16К, где 16К=8К*2 т.к. LDT и GDT).

Дескриптор программного (не данных) сегмента в системе Pentium (всего 8 байт (64 бита)).

База (Base) - базовый адрес сегмента (32-бита), разделен на три части из-за совместимости с i286, в котором это поле имеет только 24 бита.

Размер (Limit) - размер сегмента (20 бит), разнесен на две части.

Если размер сегмента указан в страницах, он может достигать 2^32 байтов (2^20 * 4Кбайт (2^12) (размер страницы в Pentium)).

Алгоритм получение физического адреса:

1. Селектор загружается в регистр (для сегмента команд в CS, для сегмента данных в DS).

2. Определяется глобальный или локальный сегмент (LDT или GDT).

3. Дескриптор извлекается из LDT или GDT, и сохраняется в микропрограммных регистрах.

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

5. Система Pentium прибавляет базовый адрес к смещению, и получает линейный адрес,

6. - если страничная организация памяти не используется, то он является физическим адресом (адрес получен),

7. - если страничная организация памяти используется, то он является виртуальным адресом.

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

5. Преобразование пары (селектора, смещение) в физический адрес

При 32-разрядном (2^32=4Гбайт) адресе и 4Кбатной странице, сегмент может содержать 1 млн страниц (4Гбайт/4Кбайта).

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

В этом случае сегмент в 4 Мбайта (1024 записи по 4 Кбайта страницы), будет иметь страничный каталог только с одной записью (и 1024 в таблице страниц), вместо 1 млн в одной таблице.

6. Отображение линейного адреса на физический адрес

В системе Pentium также есть буфер быстрого преобразования адреса (TLB), в котором хранятся наиболее часто используемые комбинации Каталог-Страница на физический адрес страничного блока. Только если комбинация в TLB отсутствует, выполняется это алгоритм.

7. Особенности реализации в UNIX

В LUNIX системе на 32-разрядной машине каждый процесс получает 3Гбайта виртуального пространства для себя, и 1Гбайт для страничных таблиц и других данных ядра.

На компьютерах Pentium, используется двухуровневые таблицы страниц, и размер страниц фиксирован 4Кбайта

На компьютерах Alpha, используется трехуровневые таблицы страниц, и размер страниц фиксирован 8Кбайт

Для каждой программы выделяется 3 сегмента:

1. Код программы (только для чтения)

2. Данные

3. Стек

8. Реализация сегментации

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

Однако сегментация существенно отличается от разбиения на страницы в следующем: размер страниц фиксирован, а размер сегментов - нет. На рис. 6.8, а показан пример физической памяти, в которой изначально содержится 5 сегментов.

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

Затем сегмент 4 заменяется сегментом 5 (рис. 6.8, в), а сегмент 3 - сегментом 6 (рис. 6.8, г).

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

Иногда внешнюю фрагментацию называют поклеточной разбивкой (checkerboarding).

Рис. 6.8. Динамика внешней фрагментации (а, б, в, г); дефрагментация путем уплотнения (д)

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

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

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

В другом популярном алгоритме список пустот просто просматривается по кругу и выбирается первый же свободный фрагмент, по размеру подходящий для данного сегмента. Удивительно, но последний алгоритм с точки зрения общей производительности работает гораздо лучше, чем алгоритм оптимальной подгонки, поскольку последний порождает очень много маленьких пустот [114].

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

Опишем один из таких процессов. Всякий раз, когда сегмент удаляется из памяти, а одна или обе соседние области этого сегмента - не сегменты, а пустоты, смежные пустоты можно объединить. Если на рис. 6.8, г удалить сегмент 5, то две соседние пустоты, объединившись с фрагментом размером 4 Кбайт, который занимал удаленный сегмент, дадут в результате свободный фрагмент размером уже 11 Кбайт.

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

MULTICS (Multiplexed Information and Computing Service - служба общей информации и вычислений) - это древняя операционная система, совмещающая сегментацию с разбиением на страницы. Она была разработана Массачусетсом технологическим институтом совместно с компаниями Bell Labs и General Electric [49, 155]. Адреса в MULTICS состоят из двух частей: номера сегмента и адреса внутри сегмента. Для каждого процесса существовал дескрипторный сегмент, содержащий дескрипторы каждого сегмента. При аппаратном получении виртуального адреса для нахождения дескриптора нужного сегмента номер сегмента использовался в качестве индекса в дескрипторном сегменте (рис. 6.9). Дескриптор указывал на таблицу страниц, что позволяло разбивать на страницы каждый сегмент обычным способом. Для повышения производительности недавно использованные сочетания сегментов и страниц помещались в ассоциативную память из 16 элементов. Операционная система MULTICS уже давно не применяется, но виртуальная память всех процессоров Intel, начиная с 386, очень похожа на эту систему.

Рис. 6.9. Преобразование составного MULTICS-адреса в адрес основной памяти

9. Сегментная и сегментно-страничная организация памяти

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

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

Каждый сегмент - линейная последовательность адресов, начинающаяся с 0. Максимальный размер сегмента определяется разрядностью процессора (при 32-разрядной адресации это 2³² байт или 4 Гбайт). Размер сегмента может меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента обычно содержится и длинасегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает исключительная ситуация.

Логический адрес - упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента. сегментация виртуальная память селектор

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

Рис. 8.8. Преобразование логического адреса при сегментной организации памяти

Аппаратная поддержка сегментов распространена мало (главным образом на процессорах Intel). В большинстве ОС сегментацияреализуется на уровне, не зависящем от аппаратуры.

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

Рис. 8.9. Упрощенная схема формирования физического адреса при сегментно-страничной организации памяти

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

Заключение

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

Размещено на Allbest.ru