Что включает в себя промежуточный виртуальный адрес при сегментно страничной организации памяти
Модуль 5. Управление основной памятью
Динамическая страничная организация памяти - это страничная организация РОП с динамическим размещением страниц процессов по их запросам (Intel 386 – размер страницы 4 Кбайт)
- Допустимость максимального объема выполняющихся программ, простота их программирования.
- Значительное уменьшение временной фрагментации, максимальное использование РОП и максимальный уровень мультипрограммирования.
- Произвольное разбиение процесса на страницы плохо учитывает свойство локальности программ и не устраняет полностью временную фрагментацию, а также создает трудности совместного использования и защиты общих программ и данных.
- Сложность управления памятью, накладные расходы на хранение таблиц отображения страниц. При неоптимальных рабочих множествах страниц и размерах страниц возможна пробуксовка процессов ("сплошной обмен").
Для решения проблемы пробуксовки страниц важную роль играет не только стратегия выталкивания, но и размер страницы.
На выбор оптимального размера страницы влияют следующие факторы:
1.Малый размер приводит к увеличению таблицы отображения страниц, называемый табличной фрагментацией.
2.Большой размер страницы приводит к тому, что в ОП здесь помещены команды и данные, к которым не было обращений.
3.Ввод-вывод будет эффективен при больших размерах страниц.
4.Свойство локальности распространяется, как правило, на малые участки программ.
5.При малых размерах страниц потери на внутреннюю фрагментацию уменьшаются.
Вывод: необходимость небольших размеров страницы.
Экспериментальные результаты поведения программы в ВС со страничной организацией ВП показывают:
1.Когда процесс начинается выполняться, он обращается к большему проценту своих страниц.
2.При постоянном объеме выделенной ОП с увеличением размера страницы растет число прерываний по отсутствию нужной страницы.
3.С увеличением количества выделенных процессу блоков (страничных кадров) уменьшается число страничных прерываний, однако, когда процессу выделено достаточное число блоков, уменьшение прерываний стабилизируется (эффект насыщения).
4.Число команд, выполненных на странице до передачи управления другой странице, как правило, невелико.
В системе с сегментной организацией памяти снимается ограничение на фиксированный размер блока и выполняется соответствующее произвольное разбиение АП процесса на сегменты.
Сегмент - это единица логического разбиения программ (процедура, модуль, область данных), имеющая переменный размер и имя. Напомним, что страница - это физическая единица памяти.
Сегментная организация обеспечивает простое и естественное разделение общих сегментов между несколькими пользователями и защиту сегментов посредством связывания с ним прав доступа, подразделяющихся на:
и их различных комбинаций.
Для сегментной организации в таблице отображения сегментов с каждым сегментом связан дескриптор, который содержит адрес размещения сегмента в ОП, его длину и права доступа (ERWA), признак обращения к сегменту за последний интервал времени, а также признак присутствия в РОП. Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единственном экземпляре.
В сегментной организации все сегменты различного размера и могут размещаться в несмежных участках РОП.
1.Уменьшение временной фрагментации, так как естественно учитывается свойство локальности программ.
2.Легко совмещается с использованием общих процессов, поскольку данные и программа целиком находятся в одном блоке.
3.Возможность обеспечить четкое управление доступом к сегменту со стороны общих процессов и их полную защиту.
1.Более сложное управление и защита ОП. Здесь уже не достаточно пары граничных регистров, а необходимы ключи защиты индивидуальных сегментов памяти.
2.Может возникнуть временная фрагментация для больших размеров процедур и данных.
Как видно из названия, данный метод представляет собой комбинацию страничного и сегментного распределения памяти и, вследствие этого, сочетает в себе достоинства обоих подходов. Виртуальное пространство процесса делится на сегменты, а каждый сегмент в свою очередь делится на виртуальные страницы, которые нумеруются в пределах сегмента. Оперативная память делится на физические страницы. Загрузка процесса выполняется операционной системой постранично, при этом часть страниц размещается в оперативной памяти, а часть на диске. Для каждого сегмента создается своя таблица страниц, структура которой полностью совпадает со структурой таблицы страниц, используемой при страничном распределении. Для каждого процесса создается таблица сегментов, в которой указываются адреса таблиц страниц для всех сегментов данного процесса. Адрес таблицы сегментов загружается в специальный регистр процессора, когда активизируется соответствующий процесс.
Рисунок.6.3 Преобразование адреса страницы при чисто ассоциативном отображении.
Трехуровневая адресация использует две таблицы отображения (таблица сегментов + таблица страниц сегментов).
S - номер сегмента; P- номер страницы; d - смещение.
Динамическое управление адресами здесь выполняется более сложно в два этапа, и поэтому в таких системах применяется высокоскоростная ассоциативная память, по типу кэш-памяти.
Обычная адресуемая память - это память, к которой обращаются по адресу и выбирают значение.
Ассоциативная память - это параллельная память, к которой осуществляется одновременный доступ по всем ячейкам памяти по значению и выбирается в результате либо адрес соответствующей ячейки, либо связанные с этой ячейкой другие значения.
Достоинства странично-сегментной организации:
- Комбинированная организация эффективна для больших программ (процедур), имеющих свою локальность.
- Делает более эффективным коллективное использование общих (разделяемых) сегментов, так как строки различных таблиц сегментов будут указывать на одну таблицу страниц коллективно используемого сегмента.
Двухуровневая страничная организация образуется из гиперстраниц, традиционно называющихся сегментами, которые в свою очередь подразделяются на страницы.
Виртуальный адрес состоит также из трех компонентов (гиперстраница, страница, смещение).
- Сокращение объема памяти под таблицы страниц путем размещения в ОП только активных частей таблиц страниц.
- Появляется возможность моделировать сегментную организацию, то есть обеспечить эффективное разделение общих процедур и защиту процессов посредством более простой схемы адресации.
Пример: ЕС ЭВМ ряд 2 и IBM PC
В общем случае информация постоянно находится на более низком уровне иерархической структуры памяти, а механизм управления иерархией обеспечивает передачу на верхний уровень наиболее вероятную для обработки информацию. В этом случае верхний уровень работает как КЭШ по отношению к нижнему уровню. Вначале идея рассматривалась только к памяти между ЦП и ОП, затем распространилась в общем смысле к иерархии памяти.
Какие утверждения относительно многопоточных приложений являются правильными?
+ 1. многопоточные приложения создают иллюзию одновременного выполнения приложением нескольких задач
2. многопоточные приложения позволяют рационально загружать ресурсы системы
+ 3. многопоточные приложения требут очень тщательной отладки
4. многопоточными являются все современные приложения
Какая структура данных используется при планировании потоков?
1. набор очередей, упорядоченный по значению приоритета
+ 2. список потоков, упорядоченных по их идентификаторам
3. набор стеков, упорядоченный по значению приоритета
4. неупорядоченный список потоков
Какую информацию обычно содержит дескриптор потока
1. состояние потока
+ 2. указатель на контекст потока
3. идентификатор потока
4. приоритет потока
+ 5. имя файла с кодом потока
Какие утверждения относительно понятия семафора являются правильными
1. семафоры применяются для отслеживания использования набора однотипных разделяемых ресурсов
+ 2. семафоры используют внутренние системные переменные с множеством возможных состояний
Что такое критическая секция
1. фрагмент кода потока, непосредственно использующий общую с другим потоком структуру данных
2. фрагмент кода потока, в котором возможно появление ошибок во время выполнения потока
3. струкутра данных, совместно используемая несколькими потоками
+ 4. фрагмент кода потока, наиболее критичный по времени выполнения
Как группируются потоки в зависимости от их приоритетов
1. потоки реального времени > системные потоки > прикладные потоки
2. системные потоки > потоки реального времени > прикладные потоки
+ 3. системные потоки > прикладные потоки > потоки реального времени
4. потоки реального времени > прикладные потоки > системные потоки
Какие состояния потоков являются основными
+ 1. состояние выполнения кода потока процессором
+ 2. состояние ожидания наступления некоторого события
+ 3. состояние готовности к выполнению
4. состояние изменения кода потока
Что содержит раздел жесткого диска
+ 1. основные параметры файловой системы
+ 2. информацию об используемых блоках и их распределении между файлами
3. главный каталог раздела
4. файлы и каталоги, входящие в раздел
Какие вопросы являются основными при реализации файловых систем
+ 1. физическая организация хранения данных на дисках
+ 2. способы определения местонахождения запрошенных данных на дисках
+ 3. алгоритмы выполнения операций с файлами
4. организация основной памяти
Какие действия выполняются при удалении файла
+ 1. извлечение из записи в каталоге адреса первого блока файла или номера индексного узла
+ 2. просмотр цепочки выделенных файлу блоков и освобождение их
3. удаление записи о файле из каталога
4. очистка всех выделенных файлу блоков от хранящейся там информации
Какие основные подходы можно использовать для распределения дискового пространства между файлами
+ 1. каждый файл занимает непрерывный набор блоков
+ 2. файл распределяется между любыми свободными блоками с созданием единой общей таблицы распределения файлов
3. файл распределяется между любыми свободными блоками с созданием для каждого файла своей структуры, хранящей номера выделенных блоков
4. в зависимости от размера файла система создает дисковый блок необходимого размера и назначает его файлу
Какие утверждения относительно индексно-узловог о способа распределения файлов являются правильными
+ 1. для каждого файла создается и поддерживается свой индексный узел
+ 2. очень легко и быстро реализуется прямой доступ к нужному фрагменту файла
3. немного замедляется обработка очень больших файлов
4. требуются большие затраты памяти для хранения индексных узлов файлов
Какие утверждения относительно разделов жесткого диска являются правильными
+ 1. раздел – это непрерывная область жесткого диска
+ 2. каждый раздел может иметь свою файловую систему
+ 3. разделы могут иметь разные размеры
4. разделы содержат только служебную информацию о файловых системах, а сами файлы разных файловых систем хранятся в общей части диска
Какие особенности характерны для дисковых блоков небольшого размера
+ 1. эффективное использование дискового пространства за счет малой фрагментации
2. большие накладные расходы на поддержку большого числа блоков
3. замедление операций чтения/записи для файлов, занимающих несмежные блоки
+ 4. более высокая скорость операций чтения/записи по сравнению с блоками большого размера
Какие утверждения относительно таблицы распределения файлов (File Allocation Table) являются правильными
+ 1. таблица используется в файловых системах FAT16/FAT32
+ 2. число j в ячейке i таблицы говорит, что за блоком i файлу выделен блок j
+ 3. после загрузки системы таблица постоянно находится в основной памяти
4. для размещения таблицы требуется очень мало памяти
Какие операции должно выполнить устройство управления диском для установки на начало заданного сектора
+ 1. выбрать необходимую головку чтения/записи (поверхность одного из дисков)
Сегментация - это деление памяти на сегменты. Это механизм адресации, обеспечивающий существование нескольких независимых адресных пространств как в пределах одной задачи, так и в системе в целом для защиты задач от взаимного влияния. С точки зрения разработчиков программного обеспечения, сегментация дает удобный способ совместного использования информации несколькими процессами. Конкретный сегмент может использоваться совместно с другими без нарушения требований его защиты. Сегментация также предполагает естественное разделение программных строк и данных и отделение модуля от модуля. [1]
Содержание
Аппаратная реализация
В системе, использующей сегментацию, адреса памяти компьютера состоят из идентификатора сегмента и смещения в сегменте. Аппаратный блок управления памятью (MMU) ответственен за перевод сегмента и смещения в адрес физической памяти, и за выполнение проверок, чтобы удостовериться, что перевод может быть произведен и что ссылка на сегмент и смещение разрешены.
У каждого сегмента есть длина и связанный с ним набор полномочий (например, чтение, запись, выполнение). Процессу позволяют сделать ссылку в сегмент в том случае, если тип ссылки разрешен полномочиями, и если смещение в сегменте находится в диапазоне, определенном длиной сегмента. Иначе возникает ошибка сегментации.
Сегменты могут также использоваться, чтобы реализовать виртуальную память. В этом случае у каждого сегмента есть связанный флаг, указывающий, присутствует ли сегмент в оперативной памяти или нет. Если сегмент, к которому получают доступ, не присутствует в оперативной памяти, выбрасывается исключение, и операционная система считает сегмент в память из внешнего хранилища.
Сегментация - это один метод реализации защиты памяти. Разбивка на страницы - другой, и они могут быть объединены. Размер сегмента памяти обычно не фиксирован и может иметь размер в 1 байт.
Сегментация была реализована несколькими различными способами на различных аппаратных средствах, с или без разбивки на страницы. Сегментация памяти Intel x86 не соответствует ни одной модели и обсуждена отдельно ниже.
Сегментация без разбиения на страницы
Реализация виртуальной памяти в системе, используя сегментацию без разбивки на страницы требует, чтобы все сегменты перемещались между оперативной памятью и внешней памятью. Когда сегмент загружен, операционная система должна выделить достаточное количество непрерывной свободной памяти, чтобы содержать весь сегмент. Часто результатом фрагментации является невозможность выделить именно непрерывный участок заданной памяти.
Сегментация с разбиением на страницы
Вместо фактической ячейки памяти информация о сегменте включает адрес таблицы страниц для сегмента. Когда программа ссылается на ячейку памяти, смещение переводится в адрес памяти, используя таблицу страниц. Сегмент может быть расширен, просто выделением другой страницы памяти и добавлением ее к таблице страниц сегмента.
Совместное использование сегментов
Сегментирование физической памяти не только не позволяет виртуальной памяти отъедать физическую, но также даёт возможность совместного использования физических сегментов с помощью виртуальных адресных пространств разных процессов.
Если дважды запустить задачу А, то кодовый сегмент у них будет один и тот же: в обеих задачах выполняются одинаковые машинные инструкции. В то же время у каждой задачи будут свои стек и куча, поскольку они оперируют разными наборами данных.
При этом оба процесса не подозревают, что делят с кем-то свою память. Такой подход стал возможен благодаря внедрению битов защиты сегмента (segment protection bits).
Для каждого создаваемого физического сегмента ОС регистрирует значение bounds, которое используется MMU для последующей переадресации. Но в то же время регистрируется и так называемый флаг разрешения (permission flag). Поскольку сам код нельзя модифицировать, то все кодовые сегменты создаются с флагами RX. Это значит, что процесс может загружать эту область памяти для последующего выполнения, но в неё никто не может записывать. Другие два сегмента — куча и стек — имеют флаги RW, то есть процесс может считывать и записывать в эти свои два сегмента, однако код из них выполнять нельзя. Это сделано для обеспечения безопасности, чтобы злоумышленник не мог повредить кучу или стек, внедрив в них свой код для получения root-прав. Так было не всегда, и для высокой эффективности этого решения требуется аппаратная поддержка. В процессорах Intel это называется “NX bit”.
Флаги могут быть изменены в процессе выполнения программы, для этого используется mprotect().
Под Linux все эти сегменты памяти можно посмотреть с помощью утилит /proc//maps или /usr/bin/pmap.
Вот пример на PHP:
Здесь есть все необходимые подробности относительно распределения памяти. Адреса виртуальные, отображаются разрешения для каждой области памяти. Каждый совместно используемый объект (.so) размещён в адресном пространстве в виде нескольких частей (обычно код и данные). Кодовые сегменты являются исполняемыми и совместно используются в физической памяти всеми процессами, которые разместили подобный совместно используемый объект в своём адресном пространстве.
Shared Objects — это одно из крупнейших преимуществ Unix- и Linux-систем, обеспечивающее экономию памяти.
Также с помощью системного вызова mmap() можно создавать совместно используемую область, которая преобразуется в совместно используемый физический сегмент. Тогда у каждой области появится индекс s, означающий shared.
Ограничения сегментации
Итак, сегментация позволила решить проблему неиспользуемой виртуальной памяти. Если она не используется, то и не размещается в физической памяти благодаря использованию сегментов, соответствующих именно объёму используемой памяти.
Но это не совсем верно.
Допустим, процесс запросил у кучи 16 Кб. Скорее всего, ОС создаст в физической памяти сегмент соответствующего размера. Если пользователь потом освободит из них 2 Кб, тогда ОС придётся уменьшить размер сегмента до 14 Кб. Но вдруг потом программист запросит у кучи ещё 30 Кб? Тогда предыдущий сегмент нужно увеличить более чем в два раза, а возможно ли это будет сделать? Может быть, его уже окружают другие сегменты, не позволяющие ему увеличиться. Тогда ОС придётся искать свободное место на 30 Кб и перераспределять сегмент.
Главный недостаток сегментов заключается в том, что из-за них физическая память сильно фрагментируется, поскольку сегменты увеличиваются и уменьшаются по мере того, как пользовательские процессы запрашивают и освобождают память. А ОС приходится поддерживать список свободных участков и управлять ими.
Фрагментация может привести к тому, что какой-нибудь процесс запросит такой объём памяти, который будет больше любого из свободных участков. И в этом случае ОС придётся отказать процессу в выделении памяти, даже если суммарный объём свободных областей будет существенно больше.
ОС может попытаться разместить данные компактнее, объединяя все свободные области в один большой чанк, который в дальнейшем можно использовать для нужд новых процессов и перераспределения.
Но подобные алгоритмы оптимизации сильно нагружают процессор, а ведь его мощности нужны для выполнения пользовательских процессов. Если ОС начинает реорганизовывать физическую память, то система становится недоступной.
Рассмотрим пример, когда программа использует одно адресное пространство.
программа использует одно адресное пространство
Недостатки такой системы:
Один участок может полностью заполниться, но при этом останутся свободные участки. Можно конечно перемещать участки, но это очень сложно.
Эти проблемы можно решить, если дать каждому участку независимое адресное пространство, называемое сегментом.
Рассмотрим то же пример с использованием сегментов:
Каждый сегмент может расти или уменьшаться независимо от других.
Сегмент - это логический объект.
В этом случае адрес имеет две части:
адрес в сегменте
Сегменты не мешают друг другу.
Начальный адрес процедуры всегда начинается с (n,0). Что упрощает программирование.
Облегчает совместное использование процедур и данных.
Раздельная защита каждого сегмента (чтение, запись).
8.2 Реализация сегментации
Если страницы имеют фиксированный размер, то сегменты нет.
У сегментов так же, как и у страниц, существует проблема фрагментации.
Т.к. памяти часто не хватает, стали использовать страничную организацию сегментов. При которой в памяти может находиться только часть сегмента.
8.2.1 Сегментация с использованием страниц: MULTICS
В одной из первых, где была применена страничная сегментация, была система MULTICS .
Каждая программа обеспечивалась до 2^18 сегментов (более 250 000), каждый из которых мог быть до 65 536 (36-разрядных) слов длиной.
Таблица сегментов - хранит дескриптор для каждого сегмента. У каждой программы своя таблица.
Т.к. записей в таблице более 250 000, она сама разбита на страницы.
Сама таблица является отдельным сегментом.
Сегмент с таблицей дескрипторов указывающих на таблицы страниц для каждого сегмента
Нормальный размер страницы равен 1024 словам. Если сегмент меньше 1024, то он либо не разбит на страницы, либо разбит на страницы по 64 слова.
Когда происходит обращение к памяти, выполняется следующий алгоритм:
По номеру сегмента находится дескриптор сегмента.
Проверяется, находиться ли таблица страницы в памяти. Если в памяти, определяется ее расположение. Если нет, вызывается сегментное прерывание.
Проверяется, находиться ли страница в памяти. Если в памяти, определяется ее расположение в памяти. Если нет в памяти, вызывается страничное прерывание.
К адресу начала страницы прибавляется смещение, в результате получаем адрес нужного слова в оперативной памяти.
Происходит запись или чтение.
Преобразование адреса в системе MULTICS
Так как такой алгоритм будет работать достаточно медленно. Аппаратура системы MULTICS содержит высокоскоростной буфер быстрого преобразования адреса (TLB) размером в 16 слов. Адреса 16 наиболее часто использующихся страниц хранятся в буфере.
8.2.2 Сегментация с использованием страниц: Intel Pentium
Каждая программа обеспечивается до 16К сегментов, каждый из которых может быть до 1 млдр 36-разрядных слов длиной.
Основа виртуальной памяти системы Pentium состоит из двух таблиц:
Локальная таблица дескрипторов LDT (Local Descriptor Table) - есть у каждой программы, и описывает сегменты программы.
Глобальная таблица дескрипторов GDT (Global Descriptor Table) - одна для всех программ, и описывает системные сегменты (включая саму ОС).
Каждый селектор (указывает на дескриптор) представляет собой 16-разрядный номер.
Селектор в системе Pentium
13 битов определяют номер записи в таблице дескрипторов, поэтому эти таблицы ограничены, каждая содержит 8К (2^13) сегментных дескрипторов.
1 бит указывает тип используемой таблицы дескрипторов LDT или GDT.
Уровни привилегированности в системе 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)).
Алгоритм получение физического адреса:
Селектор загружается в регистр (для сегмента команд в CS, для сегмента данных в DS).
Определяется глобальный или локальный сегмент (LDT или GDT).
Дескриптор извлекается из LDT или GDT, и сохраняется в микропрограммных регистрах.
Если дескриптор в памяти и смещение не выходит за пределы сегмента, программа может продолжить работу, если нет, происходит прерывание.
Система Pentium прибавляет базовый адрес к смещению, и получает линейный адрес,
- если страничная организация памяти не используется, то он является физическим адресом (адрес получен),
- если страничная организация памяти используется, то он является виртуальным адресом.
В случае, если используется страничная организация памяти, линейный адрес переводится в физический с помощью таблицы страниц.
Преобразование пары (селектора, смещение) в физический адрес
При 32-разрядном (2^32=4Гбайт) адресе и 4Кбатной странице, сегмент может содержать 1 млн страниц (4Гбайт/4Кбайта). Поэтому используется двухуровневое отображение (создана таблица (страничный каталог) содержащая список из 1024 таблиц страниц), благодаря чему можно снизить количество записей в таблице страниц до 1024.
В этом случае сегмент в 4 Мбайта (1024 записи по 4 Кбайта страницы), будет иметь страничный каталог только с одной записью (и 1024 в таблице страниц), вместо 1 млн в одной таблице.
Отображение линейного адреса на физический адрес
8.3 Особенности реализации в UNIX
В LUNIX системе на 32-разрядной машине каждый процесс получает 3Гбайта виртуального пространства для себя, и 1Гбайт для страничных таблиц и других данных ядра.
На компьютерах Pentium, используется двухуровневые таблицы страниц, и размер страниц фиксирован 4Кбайта
На компьютерах Alpha, используется трехуровневые таблицы страниц, и размер страниц фиксирован 8Кбайт
Читайте также: