Почему концепция виртуальной памяти базируется на ее страничном разбиении
Очевидно, что невозможно создать полностью машинно-независимый компонент управления виртуальной памятью . С другой стороны, имеются существенные части программного обеспечения, связанного с управлением виртуальной памятью , для которых детали аппаратной реализации совершенно не важны. Одним из достижений современных ОС является грамотное и эффективное разделение средств управления виртуальной памятью на аппаратно-независимую и аппаратно-зависимую части. Коротко рассмотрим, что и каким образом входит в аппаратно-зависимую часть подсистемы управления виртуальной памятью . Компоненты аппаратно-независимой подсистемы будут рассмотрены в следующей лекции.
В самом распространенном случае необходимо отобразить большое виртуальное адресное пространство в физическое адресное пространство существенно меньшего размера. Пользовательский процесс или ОС должны иметь возможность осуществить запись по виртуальному адресу , а задача ОС – сделать так, чтобы записанная информация оказалась в физической памяти (впоследствии при нехватке оперативной памяти она может быть вытеснена во внешнюю память ). В случае виртуальной памяти система отображения адресных пространств помимо трансляции адресов должна предусматривать ведение таблиц, показывающих, какие области виртуальной памяти в данный момент находятся в физической памяти и где именно размещаются.
Страничная виртуальная память
Как и в случае простой страничной организации , страничная виртуальная память и физическая память представляются состоящими из наборов блоков или страниц одинакового размера. Виртуальные адреса делятся на страницы (page), соответствующие единицы в физической памяти образуют страничные кадры (page frames), а в целом система поддержки страничной виртуальной памяти называется пейджингом (paging). Передача информации между памятью и диском всегда осуществляется целыми страницами.
После разбиения менеджером памяти виртуального адресного пространства на страницы виртуальный адрес преобразуется в упорядоченную пару (p,d) , где p – номер страницы в виртуальной памяти , а d – смещение в рамках страницы p , внутри которой размещается адресуемый элемент. Процесс может выполняться, если его текущая страница находится в оперативной памяти. Если текущей страницы в главной памяти нет, она должна быть переписана (подкачана) из внешней памяти. Поступившую страницу можно поместить в любой свободный страничный кадр.
Поскольку число виртуальных страниц велико, таблица страниц принимает специфический вид (см. раздел "Структура таблицы страниц "), структура записей становится более сложной, среди атрибутов страницы появляются биты присутствия , модификации и другие управляющие биты.
При отсутствии страницы в памяти в процессе выполнения команды возникает исключительная ситуация, называемая страничное нарушение (page fault) или страничный отказ. Обработка страничного нарушения заключается в том, что выполнение команды прерывается, затребованная страница подкачивается из конкретного места вторичной памяти в свободный страничный кадр физической памяти и попытка выполнения команды повторяется. При отсутствии свободных страничных кадров на диск выгружается редко используемая страница. Проблемы замещения страниц и обработки страничных нарушений рассматриваются в следующей лекции.
Для управления физической памятью ОС поддерживает структуру таблицы кадров. Она имеет одну запись на каждый физический кадр, показывающую его состояние.
В большинстве современных компьютеров со страничной организацией в основной памяти хранится лишь часть таблицы страниц , а быстрота доступа к элементам таблицы текущей виртуальной памяти достигается, как будет показано ниже, за счет использования сверхбыстродействующей памяти, размещенной в кэше процессора.
Сегментно-страничная организации виртуальной памяти
Как и в случае простой сегментации, в схемах виртуальной памяти сегмент – это линейная последовательность адресов, начинающаяся с 0 . При организации виртуальной памяти размер сегмента может быть велик, например, может превышать размер оперативной памяти. Повторяя все ранее приведенные рассуждения о размещении в памяти больших программ, приходим к разбиению сегментов на страницы и необходимости поддержки своей таблицы страниц для каждого сегмента.
На практике, однако, появления в системе большого количества таблиц страниц стараются избежать, организуя неперекрывающиеся сегменты в одном виртуальном пространстве, для описания которого хватает одной таблицы страниц . Таким образом, одна таблица страниц отводится для всего процесса. Например, в популярных ОС Linux и Windows 2000 все сегменты процесса, а также область памяти ядра ограничены виртуальным адресным пространством объемом 4 Гбайт. При этом ядро ОС располагается по фиксированным виртуальным адресам вне зависимости от выполняемого процесса.
Структура таблицы страниц
Организация таблицы страниц – один из ключевых элементов отображения адресов в страничной и сегментно-страничной схемах. Рассмотрим структуру таблицы страниц для случая страничной организации более подробно.
Итак, виртуальный адрес состоит из виртуального номера страницы и смещения. Номер записи в таблице страниц соответствует номеру виртуальной страницы . Размер записи колеблется от системы к системе, но чаще всего он составляет 32 бита. Из этой записи в таблице страниц находится номер кадра для данной виртуальной страницы , затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы. Это биты присутствия и защиты (например, 0 – read/write, 1 – read only. ). Также могут быть указаны: бит модификации , который устанавливается, если содержимое страницы модифицировано, и позволяет контролировать необходимость перезаписи страницы на диск; бит ссылки , который помогает выделить малоиспользуемые страницы; бит, разрешающий кэширование, и другие управляющие биты. Заметим, что адреса страниц на диске не являются частью таблицы страниц .
Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодня являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства размером 4 Гбайт (для 64-разрядных компьютеров эта величина равна 2 64 байт). Кроме того, существует проблема скорости отображения, которая решается за счет использования так называемой ассоциативной памяти (см. следующий раздел).
Подсчитаем примерный размер таблицы страниц . В 32-битном адресном пространстве при размере страницы 4 Кбайт (Intel) получаем 2 32 /2 12 =2 20 , то есть приблизительно миллион страниц, а в 64-битном и того более. Таким образом, таблица должна иметь примерно миллион строк (entry), причем запись в строке состоит из нескольких байтов. Заметим, что каждый процесс нуждается в своей таблице страниц (а в случае сегментно-страничной схемы желательно иметь по одной таблице страниц на каждый сегмент).
Понятно, что количество памяти, отводимое таблицам страниц , не может быть так велико. Для того чтобы избежать размещения в памяти огромной таблицы, ее разбивают на ряд фрагментов. В оперативной памяти хранят лишь некоторые, необходимые для конкретного момента исполнения фрагменты таблицы страниц . В силу свойства локальности число таких фрагментов относительно невелико. Выполнить разбиение таблицы страниц на части можно по-разному. Наиболее распространенный способ разбиения – организация так называемой многоуровневой таблицы страниц . Для примера рассмотрим двухуровневую таблицу с размером страниц 4 Кбайт, реализованную в 32-разрядной архитектуре Intel.
Таблица , состоящая из 2 20 строк, разбивается на 2 10 таблиц второго уровня по 2 10 строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2 10 строк. 32-разрядный адрес делится на 10-разрядное поле p1 , 10-разрядное поле p2 и 12-разрядное смещение d . Поле p1 указывает на нужную строку в таблице первого уровня, поле p2 – второго, а поле d локализует нужный байт внутри указанного страничного кадра (см. рис. 9.1).
При помощи всего лишь одной таблицы второго уровня можно охватить 4 Мбайт (4 Кбайт x 1024) оперативной памяти. Таким образом, для размещения процесса с большим объемом занимаемой памяти достаточно иметь в оперативной памяти одну таблицу первого уровня и несколько таблиц второго уровня. Очевидно, что суммарное количество строк в этих таблицах много меньше 2 20 . Такой подход естественным образом обобщается на три и более уровней таблицы .
Наличие нескольких уровней, естественно, снижает производительность менеджера памяти. Несмотря на то что размеры таблиц на каждом уровне подобраны так, чтобы таблица помещалась целиком внутри одной страницы, обращение к каждому уровню – это отдельное обращение к памяти. Таким образом, трансляция адреса может потребовать нескольких обращений к памяти.
Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) пейджинга , а также пейджинга с заданным количеством уровней (Motorola). Функционирование RISC-процессора MIPS R2000 осуществляется вообще без таблицы страниц . Здесь поиск нужной страницы, если эта страница отсутствует в ассоциативной памяти , должна взять на себя ОС (так называемый zero level paging).
 (1) программа для своего исполнения требует блока памяти необходимой ей длины. Наличие таких блоков переменной длины обеспечивает более плотное заполнение памяти при работе ЭВМ в мультипрограммном режиме и повышает коэффициент ее использования 
 (2) при каждом конкретном исполнении в зависимости от исходных данных некоторые части программы вообще не используются 
Номер 3
Ответ:
 (1) память, объем которой равен сумме объемов ОЗУ и внешних запоминающих устройств данного компьютера 
 (2) память, организация которой позволяет статически выделять программам блоки памяти произвольной длины при параллельном развитии нескольких процессов в мультипрограммном режиме 
 (3) память, используемая программистом при написании программ, и имеющая объем, равный максимально возможному при заданной разрядности адресной шины 
Упражнение 3: Номер 1
Ответ:
 (2) смещение в физической странице есть сумма по модулю 2 смещения в виртуальной странице и величины n , где n – определяется размером страницы ( V=2 n ) 
Номер 2
Ответ:
 (1) фиксированная длина страницы обеспечивает эффективное заполнение оперативной памяти в процессе выполнения программ 
 (3) отсутствует фрагментация оперативной памяти при обменен информацией между внешней и оперативной памятью 
Номер 3
Ответ:
Упражнение 4: Номер 1
Ответ:
 (2) увеличение степени использования оперативной памяти при параллельном развитии нескольких процессов в мультипрограммном режиме 
Номер 2
Ответ:
Упражнение 5: Номер 1
Ответ:
 (1) страницы имеют меньший объем, по сравнению с программой, что позволяет проводить более плотную упаковку оперативной памяти 
 (2) страницы используются программистом при написании программы, поэтому могут быть легко интерпретированы средства управления памяти для организации виртуальной памяти 
 (3) при страничном разбиении памяти объемы физической и виртуальной страниц совпадают, что позволяет заменять страницу оперативной памяти новой страницей из внешней памяти без возникновения проблем фрагментации памяти 
Номер 2
Ответ:
 (1) номер виртуальной страницы заменяется номером физической. Смещение в странице не меняется 
 (2) смещение, составляющее часть виртуального адреса, заменяется смещением в физической странице 
 (3) виртуальный адрес преобразуется как единое целое с помощью таблицы преобразования, уникальной для каждой выполняемой программы 
Упражнение 6: Номер 1
Ответ:
 (3) сложность обмена между оперативной и внешней памятью при выделении оперативной памяти пользователю 
 (4) невозможность выделения оперативной памяти, объем которой в точности равен программе пользователя 
Привет, Хабрахабр!
В предыдущей статье я рассказал про vfork() и пообещал рассказать о реализации вызова fork() как с поддержкой MMU, так и без неё (последняя, само собой, со значительными ограничениями). Но прежде, чем перейти к подробностям, будет логичнее начать с устройства виртуальной памяти.
Конечно, многие слышали про MMU, страничные таблицы и TLB. К сожалению, материалы на эту тему обычно рассматривают аппаратную сторону этого механизма, упоминая механизмы ОС только в общих чертах. Я же хочу разобрать конкретную программную реализацию в проекте Embox. Это лишь один из возможных подходов, и он достаточно лёгок для понимания. Кроме того, это не музейный экспонат, и при желании можно залезть “под капот” ОС и попробовать что-нибудь поменять.
Любая программная система имеет логическую модель памяти. Самая простая из них — совпадающая с физической, когда все программы имеют прямой доступ ко всему адресному пространству.
При таком подходе программы имеют доступ ко всему адресному пространству, не только могут “мешать” друг другу, но и способны привести к сбою работы всей системы — для этого достаточно, например, затереть кусок памяти, в котором располагается код ОС. Кроме того, иногда физической памяти может просто не хватить для того, чтобы все нужные процессы могли работать одновременно. Виртуальная память — один из механизмов, позволяющих решить эти проблемы. В данной статье рассматривается работа с этим механизмом со стороны операционной системы на примере ОС Embox. Все функции и типы данных, упомянутые в статье, вы можете найти в исходном коде нашего проекта.
Будет приведён ряд листингов, и некоторые из них слишком громоздки для размещения в статье в оригинальном виде, поэтому по возможности они будут сокращены и адаптированы. Также в тексте будут возникать отсылки к функциям и структурам, не имеющим прямого отношения к тематике статьи. Для них будет дано краткое описание, а более полную информацию о реализации можно найти на вики проекта.
- Расширение реального адресного пространства. Часть виртуальной памяти может быть вытеснена на жёсткий диск, и это позволяет программам использовать больше оперативной памяти, чем есть на самом деле.
- Создание изолированных адресных пространств для различных процессов, что повышает безопасность системы, а также решает проблему привязанности программы к определённым адресам памяти.
- Задание различных свойств для разных участков участков памяти. Например, может существовать неизменяемый участок памяти, видный нескольким процессам.
Работа с Page Table Entry
Для работы с записей в таблице страниц, а так же с самими таблицами, есть ряд функций:
Эти функции возвращают 1, если у соответствующей структуры установлен бит MMU_PAGE_PRESENT
Аппаратная поддержка
Обращение к памяти хорошо описанно в этой хабростатье. Происходит оно следующим образом:
Процессор подаёт на вход MMU виртуальный адрес
Если MMU выключено или если виртуальный адрес попал в нетранслируемую область, то физический адрес просто приравнивается к виртуальному
Если MMU включено и виртуальный адрес попал в транслируемую область, производится трансляция адреса, то есть замена номера виртуальной страницы на номер соответствующей ей физической страницы (смещение внутри страницы одинаковое):
Если запись с нужным номером виртуальной страницы есть в TLB [Translation Lookaside Buffer], то номер физической страницы берётся из нее же
Если нужной записи в TLB нет, то приходится искать ее в таблицах страниц, которые операционная система размещает в нетранслируемой области ОЗУ (чтобы не было промаха TLB при обработке предыдущего промаха). Поиск может быть реализован как аппаратно, так и программно — через обработчик исключения, называемого страничной ошибкой (page fault). Найденная запись добавляется в TLB, после чего команда, вызвавшая промах TLB, выполняется снова.
Таким образом, при обращении программы к тому или иному участку памяти трансляция адресов производится аппаратно. Программная часть работы с MMU — формирование таблиц страниц и работа с ними, распределение участков памяти, установка тех или иных флагов для страниц, а также обработка page fault, ошибки, которая происходит при отсутствии страницы в отображении.
В тексте статьи в основном будет рассматриваться трёхуровневая модель памяти, но это не является принципиальным ограничением: для получения модели с бóльшим количеством уровней можно действовать аналогичным образом, а особенности работы с меньшим количеством уровней (как, например, в архитектуре x86 — там всего два уровня) будут рассмотрены отдельно.
Размер страницы
В реальных (то есть не в учебных) системах используются страницы от 512 байт до 64 килобайт. Чаще всего размер страницы определяется архитектурой и является фиксированным для всей системы, например — 4 KiB.
С одной стороны, при меньшем размере страницы память меньше фрагментируется. Ведь наименьшая единица виртуальной памяти, которая может быть выделена процессу — это одна страница, а программам очень редко требуется целое число страниц. А значит, в последней странице, которую запросил процесс, скорее всего останется неиспользуемая память, которая, тем не менее, будет выделена, а значит — использована неэффективно.
С другой стороны, чем меньше размер страницы, тем больше размер страничных таблиц. Более того, при отгрузке на HDD и при чтении страниц с HDD быстрее получится записать несколько больших страниц, чем много маленьких такого же суммарного размера.
Отдельного внимания заслуживают так называемые большие страницы: huge pages и large pages [вики] .
Платформа | Размер обычной страницы | Размер страницы максимально возможного размера |
x86 | 4KB | 4MB |
x86_64 | 4KB | 1GB |
IA-64 | 4KB | 256MB |
PPC | 4KB | 16GB |
SPARC | 8KB | 2GB |
ARMv7 | 4KB | 16MB |
Действительно, при использовании таких страниц накладные расходы памяти повышаются. Тем не менее, прирост производительности программ в некоторых случаях может доходить до 10% [ссылка] , что объясняется меньшим размером страничных директорий и более эффективной работой TLB.
В дальнейшем речь пойдёт о страницах обычного размера.
Page Fault
Page fault — это исключение, возникающее при обращении к странице, которая не загружена в физическую память — или потому, что она была вытеснена, или потому, что не была выделена.
В операционных системах общего назначения при обработке этого исключения происходит поиск нужной странице на внешнем носителе (жёстком диске, к примеру).
В нашей системе все страницы, к которым процесс имеет доступ, считаются присутствующими в оперативной памяти. Так, например, соответствующие сегменты .text, .data, .bss; куча; и так далее отображаются в таблицы при инициализации процесса. Данные, связанные с потоками (например, стэк), отображаются в таблицы процесса при создании потоков.
Выталкивание страниц во внешнюю память и их чтение в случае page fault не реализовано. С одной стороны, это лишает возможности использовать больше физической памяти, чем имеется на самом деле, а с другой — не является актуальной проблемой для встраиваемых систем. Нет никаких ограничений, делающих невозможной реализацию данного механизма, и при желании читатель может попробовать себя в этом деле :)
Для виртуальных страниц и для физических страниц, которые могут быть использованы при работе с виртуальной памятью, статически резервируется некоторое место в оперативной памяти. Тогда при выделении новых страниц и директорий они будут браться именно из этого места.
Исключением является набор указателей на PGD для каждого процесса (MMU-контексты процессов): этот массив хранится отдельно и используется при создании и разрушении процесса.
Выделение страниц
Итак, выделить физическую страницу можно с помощью vmem_alloc_page
Функция page_alloc() ищет участок памяти из N незанятых страниц и возвращает физический адрес начала этого участка, помечая его как занятый. В приведённом коде virt_page_allocator ссылается на участок памяти, резервированной для выделения физических страниц, а 1 — количество необходимых страниц.
Выделение таблиц
Тип таблицы (PGD, PMD, PTE) не имеет значения при аллокации. Более того, выделение таблиц производится также с помощью функции page_alloc(), только с другим аллокатором (virt_table_allocator).
После добавления страниц в соответствующие таблицы нужно уметь сопоставлять участки памяти с процессами, к которым они относятся. У нас в системе процесс представлен структурой task, содержащей всю необходимую информацию для работы ОС с процессом. Все физически доступные участки адресного пространства процесса записываются в специальный репозиторий: task_mmap. Он представляет из себя список дескрипторов этих участков (регионов), которые могут быть отображены на виртуальную память, если включена соответствующая поддержка.
brk — это самый большой из всех физических адресов репозитория, данное значение необходимо для ряда системных вызовов, которые не будут рассматриваться в данной статье.
ctx — это контекст задачи, использование которого обсуждалось в разделе “Виртуальный адрес”.
struct dlist_head — это указатель на начало двусвязного списка, организация которого аналогична организации Linux Linked List.
За каждый выделенный участок памяти отвечает структура marea
Поля данной структуры имеют говорящие имена: адреса начала и конца данного участка памяти, флаги региона памяти. Поле mmap_link нужно для поддержания двусвязного списка, о котором говорилось выше.
Ранее уже рассказывалось о том, как происходит выделение физических страниц, какие данные о виртуальной памяти относятся к задаче, и теперь всё готово для того, чтобы говорить о непосредственном отображении виртуальных участков памяти на физические.
Отображение виртуальных участков памяти на физическую память подразумевает внесение соответствующих изменений в иерархию страничных директорий.
Подразумевается, что некоторый участок физической памяти уже выделен. Для того, чтобы выделить соответствующие виртуальные страницы и привязать их к физическим, используется функция vmem_map_region()
В качестве параметров передаётся контекст задачи, адрес начала физического участка памяти, а также адрес начала виртуального участка. Переменная flags содержит флаги, которые будут установлены у соответствующих записей в PTE.
Основную работу на себя берёт do_map_region(). Она возвращает 0 при удачном выполнении и код ошибки — в ином случае. Если во время маппирования произошла ошибка, то часть страниц, которые успели выделиться, нужно откатить сделанные изменения с помощью функции vmem_unmap_region(), которая будет рассмотрена позднее.
Рассмотрим функцию do_map_region() подробнее.
Макросы GET_PTE и GET_PMD нужны для лучшей читаемости кода. Они делают следующее: если в таблице памяти нужный нам указатель не ссылается на существующую запись, нужно выделить её, если нет — то просто перейти по указателю к следующей записи.
В самом начале необходимо проверить, выровнены ли под размер страницы размер региона, физический и виртуальный адреса. После этого определяется PGD, соответствующая указанному контексту, и извлекаются сдвиги из виртуального адреса (более подробно это уже обсуждалось выше).
Затем последовательно перебираются виртуальные адреса, и в соответствующих записях PTE к ним привязывается нужный физический адрес. Если в таблицах отсутствуют какие-то записи, то они будут автоматически сгенерированы при вызове вышеупомянутых макросов GET_PTE и GET_PMD.
После того, как участок виртуальной памяти был отображён на физическую, рано или поздно её придётся освободить: либо в случае ошибки, либо в случае завершения работы процесса.
Изменения, которые при этом необходимо внести в структуру страничной иерархии памяти, производятся с помощью функции vmem_unmap_region().
Все параметры функции, кроме последнего, должны быть уже знакомы. free_pages отвечает за то, должны ли быть удалены страничные записи из таблиц.
try_free_pte, try_free_pmd, try_free_pgd — это вспомогательные функции. При удалении очередной страницы может выясниться, что директория, её содержащая, могла стать пустой, а значит, её нужно удалить из памяти.
нужны как раз для случая двухуровневой иерархии памяти.
Конечно, данной статьи не достаточно, чтобы с нуля организовать работу с MMU, но, я надеюсь, она хоть немного поможет погрузиться в OSDev тем, кому он кажется слишком сложным.
Аннотация: В лекции рассмотрены следующие вопросы: концепция виртуальной памяти; страничная организация виртуальной памяти; обработка отсутствия страницы в памяти (page fault); обработка страниц по требованию; совместное использование страниц процессами; файлы, отображаемые в память (memory-mapped files); стратегии замещения страниц; алгоритмы FIFO и LRU; алгоритм "второго шанса"; алгоритмы со счетчиком; выделение фреймов – фиксированное и с приоритетами; thrashing; страничная организация в Windows NT и Solaris.
Презентацию к данной лекции Вы можете скачать здесь.
Трансляция виртуального адреса в физический
Как уже писалось выше, при обращении к памяти трансляция адресов производится аппаратно, однако, явный доступ к физическим адресам может быть полезен в ряде случаев. Принцип поиска нужного участка памяти, конечно, такой же, как и в MMU.
Для того, чтобы получить из виртуального адреса физический, необходимо пройти по цепочке таблиц PGD, PMD и PTE. Функция vmem_translate() и производит эти шаги.
Сначала проверяется, есть ли в PGD указатель на директорию PMD. Если это так, то вычисляется адрес PMD, а затем аналогичным образом находится PTE. После выделения физического адреса страницы из PTE необходимо добавить смещение, и после этого будет получен искомый физический адрес.
Пояснения к коду функции.
mmu_paddr_t — это физический адрес страницы, назначение mmu_ctx_t уже обсуждалось выше в разделе “Виртуальный адрес”.
С помощью функции vmem_get_idx_from_vaddr() находятся сдвиги в таблицах PGD, PMD и PTE.
Виртуальный адрес
Page Global Directory (далее — PGD) — таблица (здесь и далее — то же самое, что директория) самого высокого уровня, каждая запись в ней — ссылка на Page Middle Directory (PMD), записи которой, в свою очередь, ссылаются на таблицу Page Table Entry (PTE). Записи в PTE ссылаются на реальные физические адреса, а также хранят флаги состояния страницы.
То есть, при трёхуровневой иерархии памяти виртуальный адрес будет выглядеть так:
Значения полей PGD, PMD и PTE — это индексы в соответствующих таблицах (то есть сдвиги от начала этих таблиц), а offset — это смещение адреса от начала страницы.
В зависимости от архитектуры и режима страничной адресации, количество битов, выделяемых для каждого из полей, может отличаться. Кроме того, сама страничная иерархия может иметь число уровней, отличное от трёх: например, на x86 нет PMD.
Для обеспечения переносимости мы задали границы этих полей с помощью констант: MMU_PGD_SHIFT, MMU_PMD_SHIFT, MMU_PTE_SHIFT, которые в приведённой выше схеме равны 24, 18 и 12 соответственно их определение дано в заголовочном файле src/include/hal/mmu.h. В дальнейшем будет рассматриваться именно этот пример.
На основании сдвигов PGD, PMD и PTE вычисляются соответствующие маски адресов.
Эти макросы даны в том же заголовочном файле.
Для работы с виртуальной таблицами виртуальной памяти в некоторой области памяти хранятся указатели на все PGD. При этом каждая задача хранит в себе контекст struct mmu_context, который, по сути, является индексом в этой таблице. Таким образом, к каждой задаче относится одна таблица PGD, которую можно определить с помощью mmu_get_root(ctx).
Устройство Page Table Entry
В реализации проекта Embox тип mmu_pte_t — это указатель.
Каждая запись PTE должна ссылаться на некоторую физическую страницу, а каждая физическая страница должна быть адресована какой-то записью PTE. Таким образом, в mmu_pte_t незанятыми остаются MMU_PTE_SHIFT бит, которые можно использовать для сохранения состояния страницы. Конкретный адрес бита, отвечающего за тот или иной флаг, как и набор флагов в целом, зависит от архитектуры.
- MMU_PAGE_WRITABLE — Можно ли менять страницу
- MMU_PAGE_SUPERVISOR — Пространство супер-пользователя/пользователя
- MMU_PAGE_CACHEABLE — Нужно ли кэшировать
- MMU_PAGE_PRESENT — Используется ли данная запись директории
Можно установить сразу несколько флагов:
Здесь vmem_page_flags_t — 32-битное значение, и соответствующие флаги берутся из первых MMU_PTE_SHIFT бит.
Введение
Виртуальная память – распространенная стратегия распределения памяти , используемая во всех современных операционных системах, основанная на идее расширения физической памяти путем размещения расширенной памяти на диске и использования таблиц страниц (или сегментов) для трансляции адресов . В лекции рассмотрены следующие вопросы:
- Мотивировка концепции виртуальной памяти;
- Потребность в страничной организации ;
- Создание процесса и его пространства виртуальной памяти;
- Замена страницы;
- Размещение фреймов;
- Thrashing ;
- Примеры организации виртуальной памяти в различных ОС.
Программная поддержка
- Выделение физических страниц из некоторого зарезервированного участка памяти
- Внесение соответствующих изменений в таблицы виртуальной памяти
- Сопоставление участков виртуальной памяти с процессами, выделившими их
- Проецирование региона физической памяти на виртуальный адрес
Мотивировка концепции виртуальной памяти
Концепция виртуальной памяти основана на идеях отделения логической памяти пользователя от физической памяти и расширения логической памяти путем хранения ее образа на диске.
При исполнении программы только часть ее кода и данных, к которым происходит обращение, в каждый момент требует размещения в физической памяти. Поэтому, естественно, возникает идея расширить пространство логической памяти, которое может быть реализовано намного большего размера, чем физическая память . Это и есть основной принцип организации виртуальной памяти.
Виртуальная память поддерживает совместное использование одного и того же адресного пространства более чем одним процессом, создание и исполнение облегченных процессов в общем пространстве виртуальной памяти.
Виртуальная память допускает более эффективное создание процесса , чем предшествующие схемы организации памяти и процессов.
Заметим, что концепция виртуальной памяти непосредственно не связана ни со страничной, ни с сегментной стратегиями распределения памяти . Виртуальная память может быть реализована различными способами, например, с помощью:
- страничной организации по требованию (paging on demand);
- сегментной организации по требованию (segmentation on demand).
В приведенных терминах подчеркивается динамический характер управления виртуальной памятью: термин по требованию означает, что страница или сегмент будут размещены в физической памяти только в случае, если к ним реально происходит обращение из программы пользователя. Причем если размер обрабатываемой области виртуальной памяти (например, массива) очень велик – например, 1000 страниц, то в физической памяти будет размещена только та его страница, к которой обращается пользовательская программа .
Принцип управления виртуальной памятью иллюстрируется рис. 18.1.
Из схемы видно, что виртуальная память , как предполагается, больше, чем физическая память . Взаимодействие между частями виртуальной памяти и физической памяти происходит через отображение памяти – системную таблицу (сегментов, страниц и т.п.). Образ виртуальной памяти процесса хранится на диске.
Страничная организация по требованию
Принцип реализации виртуальной памяти в виде страничной организации по требованию заключается в том, что каждая страница загружается в память , только если она реально требуется при выполнении программы – содержит код или данные, к которым произошло обращение.
Преимущества данного подхода:
- Меньший объем ввода-вывода: В память подкачивается только минимально необходимый объем данных (например, одна страница большого массива, а не весь многостраничный массив);
- Меньший объем памяти: При данном способе расходуется минимально необходимый объем физической памяти;
- Более быстрая реакция системы: Поскольку объем пересылаемых данных меньше, система в среднем быстрее реагирует на каждый запрос к памяти;
- Система может обслуживать большее число пользователей: Ввиду экономии физической памяти и времени обращения, система в состоянии при данном подходе обслуживать большее число пользовательских процессов .
Основные принципы страничной организации по требованию:
- Если страница требуется программе, на нее имеется ссылка из программы.
- Если ссылка на страницу неверна (например, страницы с данным номером не существует), происходит прерывание.
- Если требуемая страница отсутствует в памяти, то она подкачивается в память. Механизм подкачки реализуется через прерывание (page fault – отказ страницы).
рис. 18.2 иллюстрирует размещение виртуальной памяти на диске и ее откачку и подкачку.
Из схемы видно, что, с точки зрения каждой программы, пространство ее виртуальной памяти непрерывно. Оно преобразуется в непрерывную область дисковой памяти. С помощью механизма откачки – подкачки в нужный момент страница виртуальной памяти размещается в основной памяти.
С каждым элементом таблицы страниц связывается бит "valid/invalid",однако, в отличие от организации логической памяти, он играет несколько иную роль – он указывает на присутствие или отсутствие страницы в основной памяти. Значение бита равно 1, если страница в памяти, и 0, если страница отсутствует в памяти.
Первоначально для всех элементов таблицы страниц бит valid / invalid полагается равным 0.
Если в процессе трансляции адреса бит " valid / invalid " в таблице страниц оказыется равным 0, то происходит прерывание по отсутствию страницы в памяти (page fault).
На рис. 18.3 приведен пример таблицы страниц , в которой не все страницы присутствуют в основной памяти.
Большинство систем виртуальной памяти используют технику, называемую страничной организацией памяти [32, 37]. Любой процесс, реализуемый в компьютере, может обратиться к множеству адресов в памяти. Адреса могут формироваться с применением индексации, базовых регистров, сегментных регистров и другими путями. Эти программно формируемые адреса, называемые виртуальными адресами, формируют виртуальное адресное пространство . На компьютерах без виртуальной памяти виртуальные адреса подаются непосредственно на шину памяти и вызывают для чтения или записи слово в физической памяти с тем же самым адресом.
Когда используется виртуальная память , виртуальные адреса не передаются напрямую шиной памяти. Вместо этого они передаются диспетчеру памяти ( MMU – Memory Management Unit), который отображает виртуальные адреса на физические адреса памяти, как показано на рис. 6.9. Здесь диспетчер памяти показан как часть микросхемы процессора, как обычно и бывает чаще всего. Но логически он мог бы быть отдельной микросхемой, как было в недавнем прошлом.
Все имеющееся в настоящее время множество реализаций виртуальной памяти различается в основном способом структуризации виртуального адресного пространства.
В настоящее время выделяют три метода реализации виртуальной памяти.
- Страничная виртуальная память организует перемещение данных между основной памятью и диском страницами – частями виртуального адресного пространства фиксированного и сравнительно небольшого размера.
- Сегментная виртуальная память предусматривает перемещение данных сегментами – частями виртуального адресного пространства произвольного размера, полученного с учетом смыслового значения данных.
- Сегментно- страничная виртуальная память использует двухуровневое деление: виртуальное адресное пространство делится на сегменты, а затем сегменты делятся на страницы. Единицей перемещения данных является страница.
Для временного хранения сегментов и страниц на диске отводится специальная область либо специальный файл (страничный файл или файл подкачки – paging file ). Текущий размер страничного файла является важным параметром, оказывающим влияние на возможности операционной системы: чем больше страничный файл , тем больше приложений может одновременно выполнять ОС (при фиксированном размере оперативной памяти). Однако необходимо понимать, что увеличение числа одновременно работающих приложений за счет увеличения размера страничного файла замедляет их работу, так как значительная часть времени при этом тратится на перемещение данных на диск и обратно.
Размер страничного файла в современных ОС является настраиваемым параметром, который выбирается администратором системы для достижения компромисса между уровнем программирования и быстродействием системы.
При страничной организации виртуальное адресное пространство каждого процесса делится на части одинакового, фиксированного для данной системы размера, называемые виртуальными страницами ( Virtual pages). В общем случае размер виртуального адресного пространства не кратен размеру страницы, поэтому последняя страница дополняется фиксированной областью.
Вся оперативная память машины также делится на части такого же размера, называемые физическими страницами (или блоками, или кадрами). Размер страницы выбирается равным степени двойки: 1024, 2048, 4096 байт и т.д. Это позволяет упростить механизм преобразования адресов.
При создании процесса ОС загружает в операционную память несколько его виртуальных страниц (начальные страницы кодового сегмента и сегмента данных). Копия всего виртуального адресного пространства процесса находится на диске. Смежные виртуальные страницы не обязательно находятся в смежных физических страницах. Для каждого процесса ОС создает таблицу страниц – информационную структуру, содержащую записи обо всех виртуальных страницах процесса (рис. 6.10).
Запись таблицы ( дескриптор страницы) включает следующую информацию:
- номер физической страницы (N ф.с.), в которую загружена данная виртуальная страница ;
- признак присутствия Р, устанавливаемый в единицу, если данная страница находится в оперативной памяти;
- признак модификации страницы D, который устанавливается в единицу всякий раз, когда производится запись по адресу, относящемуся к данной странице;
- признак обращения А к странице, называемый также битом доступа, который устанавливается в единицу при каждом обращении по адресу, относящемуся к данной странице;
- другие управляющие биты, служащие, например, для целей защиты или совместного использования памяти на уровне страниц.
Перечисленные признаки в большинстве моделей процессов устанавливаются аппаратно схемами процессора при выполнении операций с памятью. Информация из таблицы страниц используется для решения вопроса о необходимости перемещения той или иной страницы между памятью и диском, а также для преобразования виртуального адреса в физический. Сами таблицы страниц, так же как и описываемые ими страницы, размещаются в оперативной памяти.
Поскольку процесс может задействовать большой объем виртуальной памяти (например, в Windows 2000 он равен 2 32 = 4 Гбайт), при использовании страницы объемом 4 Кбайт (2 12 ) потребуется 2 20 записей в таблице страниц для каждого процесса. Понятно, что выделять такое количество оперативной памяти под таблицы страниц нецелесообразно. Для преодоления этой проблемы большинство схем виртуальной памяти хранит таблицы страниц не в реальной, а в виртуальной памяти. Это означает, что сами таблицы страниц становятся объектами страничной организации. При работе процесса как минимум часть его таблицы страниц должна располагаться в основной памяти, в том числе запись о странице, выполняющейся в настоящий момент. Адрес таблицы страниц включается в контекст процесса . При активизации очередного процесса ОС загружает адрес его таблицы страниц в специальный регистр .
При каждом обращении к памяти выполняется поиск номера виртуальной страницы , содержащей требуемый адрес , затем по этому номеру определяется нужный элемент таблицы страниц и из него извлекается описывающая страницу информация . Далее анализируется признак присутствия, и если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический. Если же нужная виртуальная страница в данный момент выгружена на диск , то происходит страничное прерывание .
Выполняющий процесс переводится в состояние ожидания, активизируя процесс из очереди процессов, находящихся в состоянии готовности. Параллельно программа обработки страничного прерывания находит на диске требуемую виртуальную страницу и пытается ее загрузить в оперативную память . Если в памяти имеется свободная физическая страница , то загрузка выполняется немедленно. Если же свободных страниц нет, то на основании принятой в данной системе стратегии замещения страниц решается вопрос о том, какую страницу следует выгрузить из оперативной памяти.
После того как выбрана страница, которая должна покинуть оперативную память , обнуляется ее бит присутствия и анализируется ее признак модификации. Если удаляемая страница за время последнего требования в оперативной памяти была модифицирована, то ее новая версия должна быть переписана на диск . Если нет, то принимается во внимание, что на диске уже имеется предыдущая копия этой виртуальной страницы , и никакой записи на диск не производится. Физическая страница объявляется свободной. Из соображений безопасности в некоторых системах освобождаемая страница обнуляется, чтобы невозможно было использовать содержимое выгруженной страницы. Для хранения информации о положении вытесненной страницы в страничном файле ОС может задействовать специальные поля таблицы страниц.
Виртуальный адрес при страничном распределении может быть представлен в виде пары ( P, Sv ), где Р – номер виртуальной страницы процесса ( нумерация страниц начинается с 0), а Sv – смещение в пределах виртуальной страницы (рис. 6.11). Физический адрес также может быть представлен в виде пары ( N, Sf ), где N – номер физической страницы, а Sf – смещение а пределах физической страницы. Задача подсистемы виртуальной памяти состоит в отображении пары значений ( P, Sv ) в пару ( N, Sf ).
Чтобы понять механизм реализации этого отображения, следует остановиться на двух базисных свойствах страничной организации. Как уже отмечалось, объем страницы, как виртуальной, так и физической, выбирается равным степени двойки – 2 к ( k = 8 и более). Отсюда следует, что смещение Sv и Sf может быть получено отделением k младших разделов в двоичной записи виртуального и, соответственно, физического адреса страницы. При этом оставшиеся старшие разделы адреса представляют собой двоичную запись номера виртуальной и, соответственно, физической страницы. Дополнив эти номера к нулям, можно получить начальный адрес виртуальной и физической страниц.
Второе свойство – линейность адресного пространства виртуальной и физической страницы – приводит к тому, что Sf = Sv. Отсюда следует простая схема преобразования виртуального адреса в физический.
При обращении к памяти по некоторому виртуальному адресу ( P, Sv ) аппаратные схемы процессора выполняют следующие действия.
- Из специального регистра процессора извлекается начальный адрес АТ таблицы страниц активного процесса. С помощью сумматора по значениям АТ, Р, L (длина отдельной записи в таблице страниц) определяется адрес нужной записи в таблице страниц:
В итоге полученный физический адрес оперативной памяти представляется парой значений ( N, Sf ).
Рассмотрим пример, поясняющий основные характеристики организации страничной виртуальной памяти. Пусть компьютер имеет оперативную память объемом Еоп = 256 Мбайт , размер страницы выбран равным Естр= 4 Кбайт . В этом случае количество физических страниц равно
Для отображения физического адреса произвольного байта оперативной памяти потребуется K = log2 256*20 2 0 = 28 двоичных разрядов.
Число разрядов для отображения смещения в странице M = log2 4 Кбайт = log2 4096 = 12 .
Если процессор имеет 32-разрядную структуру, то на номер виртуальной страницы отводится 32-12=20 двоичных разрядов. Таким образом, число виртуальных страниц равно Nв = 220 (примерно 1 млн виртуальных страниц ).
Для каждой виртуальной страницы в таблице страниц должна быть запись , содержащая номер виртуальной страницы (20 двоичных разрядов), начальный адрес соответствующей ей физической страницы плюс дополнительные разряды, характеризующие свойства страницы (присутствие, модификация, обращение и т.п.), на которые потребуется 1 байт . Поскольку адрес начала физической страницы кратен 4096, то на него достаточно 28 – 12 = 16 двоичных разрядов (остальные 12 разрядов заполняются нулями). Таким образом, одна запись таблицы страниц займет 20 + 16 + 8 = 44 двоичных разрядов или 6 байт . Общий объем таблицы страниц составит 6 * Nв = 6 Мбайт .
Реально при выборе структуры записи таблицы страниц нужно учитывать следующие факторы. Современные компьютеры позволяют наращивать объем оперативной памяти (например, в ПК она может почти достигать объема виртуальной памяти и даже более). Поэтому на адрес физической страницы в нашем примере следует выделить 32-12 = 20 двоичных разрядов. С другой стороны, нет необходимости в записи (дескрипторе) виртуальной страницы иметь поле с номером виртуальной страницы (20 разрядов), так как адрес нужной записи можно вычислять, как это было рассмотрено выше. Следовательно, в нашем примере длина записи должна быть равной 32 - 12 + 8 = 28 двоичным разрядам, т.е. с округлением до целого числа байт – 4 байт . Таким образом, для каждого выполняющегося в компьютере процесса ОС должна создать страничную таблицу размером 4 * Nв байт = 5 * 2 20 = 4 Мбайт .
Процедура преобразования виртуального адреса в физический без принятия специальных мер ( кэширование активных страниц) занимает один цикл оперативной памяти, который затрачивается на считывание номера физической страницы из таблицы страниц. Поэтому любое обращение к ОП будет занимать 2 цикла вместо одного при работе без виртуальной памяти. Другим фактором, влияющим на производительность систем, являются затраты времени на обработку страничных прерываний. При неправильно выбранной стратегии замещения страниц может возникнуть ситуация, когда система тратит большую часть времени впустую на подкачку страниц из оперативной памяти на диск и обратно.
Читайте также: