Что такое страничная память
Страничная организация памяти
Страничная организация
При страничной организации ОС хранит информацию обо всех свободных фреймах. Поскольку память выделяется с точностью до страницы, возможна внутренняя фрагментация (см. п. 16.5).
Цели страничной организации – обеспечить возможность не смежного распределения физической памяти для процессов, а также расширить пространство логической памяти.
Архитектура трансляции адресов при страничной организации изображена на рис. 16.3.
На рис. 16.5 приведен другой возможный пример страничной организации : логическая и физическая память разбита на блоки по 4 страницы подряд; в таблице страниц хранится не номер страницы, а номер блока страниц. Например, в элементе 0 таблицы страниц хранится номер блока 5, по которому адрес начала блока вычисляется домножением содержимого элемента таблицы страниц на размер блока, равный 4 (результат – 20).
Использования списка свободных фреймов иллюстрируется на рис. 16.6.
Страничная организация памяти
Презентацию к данной лекции Вы можете скачать здесь.
Введение
Откачка и подкачка
Наибольшие временные затраты на откачку – это затраты на передачу данных: полный образ процесса может занимать большую область памяти. Общее время откачки пропорционально размеру откачиваемых данных.
Схема откачки и подкачки изображена на рис. 16.1.
Смежное распределение памяти
Общая задача распределения памяти и стратегии ее решения
В общем случае, в операционных системах может использоваться смежное распределение памяти в нескольких смежных областях. Свободная область – это смежный блок свободной памяти. Свободные области могут быть произвольно разбросаны по памяти. При загрузке процесса ему предоставляется память из любой свободной смежной области, которая достаточно велика для его размещения. При этом операционная система хранит список свободных областей памяти и список занятых областей памяти. Все эти области могут быть произвольно расположены в памяти и иметь различную длину.
Возникает общая задача распределения памяти: Имеется список свободных областей памяти и список занятых областей разного размера. Разработать и реализовать оптимальный ( по некоторому критерию) алгоритм выделения свободного смежного участка памяти длины n (слов или байтов).
Для решения данной задачи применяются следующие стратегии: метод первого подходящего (first-fit), метод наиболее подходящего (best-fit) и метод наименее подходящего (worst-fit).Рассмотрим каждую из них подробнее.
Метод первого подходящего:Выбирается первый по списку свободный участок подходящего размера (не меньшего, чем n ). На первый взгляд, данная стратегия оптимальна, но далее мы увидим, что это не всегда так.
Метод наиболее подходящего:Выбирается из списка наиболее подходящий свободный участок (минимального размера, не меньшего, чем n ). В отличие от предыдущего метода, требует просмотра всего списка, если список не упорядочен по размеру областей. Применение метода приводит к образованию оставшейся части самого маленького размера.
Метод наименее подходящего: Выбирается из списка подходящая область наибольшего размера. Почему наибольшего? Чтобы избежать фрагментации (проблема фрагментации подробно рассмотрена далее в данной лекции).
Применение первой и второй стратегий лучше со следующих точек зрения: скорость выполнения и минимальность объема использованной памяти. Однако их применение может создать фрагментацию.
Фрагментация
Внешняя фрагментация может быть уменьшена или ликвидирована путем применения компактировки (compaction) – сдвига или перемешивания памяти с целью объединения всех не смежных свободных областей в один непрерывный блок. Компактировка может выполняться либо простым сдвигом всех свободных областей памяти, либо путем перестановки занятых областей, с выбором на каждом шаге подходящей свободной области методом наиболее подходящего. Компактировка возможна, только если связывание адресов и перемещение (см. лекцию 15) происходит динамически. Компактировка выполняется во время исполнения программы.
При компактировке памяти и анализе свободных областей может быть выявлена проблема зависшей задачи: какая-либо задача может «застрять» в памяти, так как выполняет ввод-вывод в свою область памяти ( по этой причине откачать ее невозможно). Решение данной проблемы: ввод-вывод должен выполняться только в специальные буфера, выделяемой для этой цели операционной системой.
Страничная организация памяти
Страничная организация памяти основана на том, что физическое и виртуальное адресные пространства разбиваются на фрагменты постоянной длины. Размер страницы выбирается кратным степени 2, т.к. это позволяет максимально просто выполнять преобразование ВА в ФА на аппаратном уровне. Наиболее распространенный размер страницы равен 212 = 4096 байт. Все страницы нумеруются от 0 до N. Тем самым ВАП состоит из 232 / 212 = 220 = 1 Мбайт страниц, а число реальных физических страниц зависит от размера установленной памяти.
Так, для объема основной памяти 128 Мб получим 32 Кбайт страниц. Можно сказать, что страница – это просто некоторый диапазон адресов: страница 0 определяет адреса от 0 до 4095 (или 0FFFh), страница 1 – от 4096 до 8191 (или от 1000h до 1FFFh), страница 2 – от 8192 до 12287 (от 2000h до 2FFFh) и т.д. Видно, что номер страницы однозначно определяет соответствующий этой странице диапазон адресов.
Если размер страницы равен 4096 байт, то смещение для любой страницы будет принимать значения от 0 до 4095. Тем самым полный 32-х разрядный виртуальный адрес разбивается на две составляющие: младшие 12 разрядов (т.е. 3 полубайта) определяют смещение на странице, а старшие 20 разрядов (5 полубайтов) определяют номер страницы. Например, виртуальный адрес 002A4C38 разбивается следующим образом
Поскольку ВАП и ФАП разбиты на страницы совершенно одинаково, замена ВА на ФА сводится только к замене номера страницы, смещение при этом остается неизменным! Это является важнейшим преимуществом страничной организации и одной из основных причин столь высокой популярности этого способа организации памяти в современных ОС. Замена номера страницы в виртуальном адресе сводится к действиям с отдельными битами и чрезвычайно эффективно выполняется на аппаратном уровне.
Такой подход позволяет отображать любую виртуальную страницу на любую физическую. Это приводит к исключительно эффективному использованию основной памяти и эффективной реализации механизма виртуальной памяти. Для того чтобы процессор мог выполнить преобразование адресов, ему необходима информация о соответствии виртуальных и физических страниц: в какую физическую страницу отображена данная виртуальная страница. Для этого система для каждого процесса строит специальную таблицу страниц. Каждая запись в этой таблице называется дескриптором страницы и обычно содержит следующие данные:
Поскольку для каждого процесса создается своя таблица страниц, появляется возможность организовать защиту адресных пространств процессов. Процесс может манипулировать только своими страницами. Если нескольким процессам надо использовать общие данные, то для этого система создает общие или разделяемые страницы. Начальный адрес размещения таблицы страниц активного процесса содержится в специальном системном регистре процессора, недоступном для прикладных программ. При переключении процессов система заменяет содержимое этого регистра, тем самым включая в работу новую таблицу страниц.
Если при запуске процесса в основной памяти нет достаточного количества свободных страниц, чтобы разместить весь код и данные, то загружается только часть страниц, остальные сохраняются на диске и в таблице страниц помечаются как отсутствующие. При необходимости любая отсутствующая страница может быть загружена в память с назначением ей свободной физической страницы. Наоборот, система может вытеснить на диск часть или даже все страницы процесса. Такой обмен страницами между основной и дисковой памятью называют страничным обменом, или своппингом (swap – обмен). Часто перемещаемые на диск страницы сохраняются в специальном файле, называемом страничным файлом, или файлом подкачки. Каждая такая операция сопровождается соответствующими изменениями в таблице страниц.
Алгоритм преобразования ВА в ФА можно представить следующим образом. Пусть при выполнении некоторой команды процессору необходимо обратиться к памяти по виртуальному адресу. Тогда система, используя реализованную в процессоре аппаратную поддержку, выполняет следующее:
статьи IT, лекции по программированию, операционные системы, память
Национальная библиотека им. Н. Э. Баумана
Bauman National Library
Персональные инструменты
Страничная память
Страничная память — способ организации виртуальной памяти, при котором единицей отображения виртуальных адресов на физические является регион постоянного размера (т. н. страница). [1] Типичный размер страницы — 4096 байт, для некоторых архитектур — до 128 КБ.
Поддержка такого режима присутствует в большинстве 32-битных и 64-битных процессоров. Такой режим является классическим для почти всех современных ОС, в том числе Windows и семейства UNIX. Широкое использование такого режима началось с процессора VAX и ОС VMS с конца 70-х годов (по некоторым сведениям, первая реализация). В семействе x86 поддержка появилась с поколения 386, оно же первое 32-битное поколение.
Содержание
Введение
Любая программная система имеет логическую модель памяти. Самая простая из них — совпадающая с физической, когда все программы имеют прямой доступ ко всему адресному пространству. При таком подходе программы имеют доступ ко всему адресному пространству, не только могут “мешать” друг другу, но и способны привести к сбою работы всей системы — для этого достаточно, например, затереть кусок памяти, в котором располагается код ОС. Кроме того, иногда физической памяти может просто не хватить для того, чтобы все нужные процессы могли работать одновременно. Виртуальная память — один из механизмов, позволяющих решить эти проблемы. В данной статье рассматривается работа с этим механизмом со стороны операционной системы на примере ОС Embox. Все функции и типы данных, упомянутые в статье, вы можете найти в исходном коде нашего проекта.
Будет приведён ряд листингов, и некоторые из них слишком громоздки для размещения в статье в оригинальном виде, поэтому по возможности они будут сокращены и адаптированы. Также в тексте будут возникать отсылки к функциям и структурам, не имеющим прямого отношения к тематике статьи. Для них будет дано краткое описание, а более полную информацию о реализации можно найти на вики проекта.
Общие идеи
Виртуальная память — это концепция, которая позволяет уйти от использования физических адресов, используя вместо них виртуальные, и это даёт ряд преимуществ: Расширение реального адресного пространства. Часть виртуальной памяти может быть вытеснена на жёсткий диск, и это позволяет программам использовать больше оперативной памяти, чем есть на самом деле. Создание изолированных адресных пространств для различных процессов, что повышает безопасность системы, а также решает проблему привязанности программы к определённым адресам памяти. Задание различных свойств для разных участков участков памяти. Например, может существовать неизменяемый участок памяти, видный нескольким процессам.
При этом вся виртуальная память делится на участки памяти постоянного размера, называемые страницами.
Механизм работы
В самом простом и наиболее распространенном случае страничной организации памяти (или paging) как логическое адресное пространство, так и физическое представляются состоящими из наборов блоков или страниц одинакового размера. При этом образуются логические страницы(page), а соответствующие единицы в физической памяти называют физическими страницами или страничными кадрами (page frames).Страницы (и страничные кадры) имеют фиксированную длину, обычно являющуюся степенью числа 2, и не могут перекрываться. Каждый кадр содержит одну страницу данных. При такой организации внешняя фрагментация отсутствует, а потери из-за внутренней фрагментации, поскольку процесс занимает целое число страниц, ограничены частью последней страницы процесса.
Описываемая схема позволяет загрузить процесс, даже если нет непрерывной области кадров, достаточной для размещения процесса целиком.
Число записей в одной таблице ограничено и зависит от размера записи и размера страницы. Используется многоуровневая организация таблиц, часто 2 или 3 уровня, иногда 4 уровня (для 64-разрядных архитектур).
Как и сегментация, страничная организация памяти связана с преобразованием виртуального адреса (в данном случае линейного) в физический. В страничном преобразовании базовым объектом памяти является блок фиксированного размера, называемый страницей (page).
Для уменьшения размера таблицы страниц в микропроцессорах x86 предусмотрена двухуровневая схема преобразования адреса. Основой страничного преобразования служит регистр управления CR3, содержащий 20-ти битный физический базовый адрес каталога страниц текущей задачи. Предполагается, что каталог выровнен по границе страничного кадра, постоянно находится в памяти и не участвует в свопинге. Корневая страница, называемая каталогом страниц, содержит 1024 32-х битных дескриптора, называемых элементами каталога страниц PDE (Page Directory Entry). Каждый из них адресует подчиненную таблицу страниц. Каждая из этих таблиц содержит 1024 32-х битных дескриптора, называемая элементами таблицы страниц. PTE (Page Table Entry). Каждый PTE содержит адрес страничного кадра в физической памяти. Собственно преобразование линейных адресов в физические состоит из следующих действий:
Этот базовый адрес из элемента PTE объединяется с младшими 12-ю битами линейного адреса, образуя 32-х битный физический адрес.
Программная поддержка
Для приложений работа с виртуальной памятью незаметна. Это прозрачность обеспечивается наличием в ядре ОС соответствующей подсистемы, осуществляющей следующие действия: Выделение физических страниц из некоторого зарезервированного участка памяти Внесение соответствующих изменений в таблицы виртуальной памяти Сопоставление участков виртуальной памяти с процессами, выделившими их Проецирование региона физической памяти на виртуальный адрес
Данные механизмы будут рассмотрены подробно ниже, после введения нескольких базовых определений.
Виртуальный адрес
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.
Страничная память x86
Исторически x86 использует 32-битные PTE, 32-битные виртуальные адреса, 4KB-страницы, 1024 записи в таблице, двухуровневые таблицы. Старшие 10 бит виртуального адреса — номер записи в директории, следующие 10 — номер записи в таблице, младшие 12 — адрес внутри страницы. [2]
Начиная с Pentium Pro, процессор поддерживает страницы размером 4Мб. Однако, чтобы система и программы, запущенные в ней, могли использовать страницы такого размера, технология 4-х Мб страниц (hugepages) должна быть соответствующим образом активирована, а приложение настроено на использование страниц такого размера. Процессор x86 в режиме PAE (Physical Address Extension) и в режиме x86_64 (long mode) использует 64-битные PTE (из них реально задействованы не все биты физического адреса, от 36 в PAE до 48 в некоторых x86_64), 32-битные виртуальные адреса, 4KB-страницы, 512 записей в таблице, трехуровневые таблицы с четыремя директориями и четыремя записями в супер-директории. Старшие 2 бита виртуального адреса — номер записи в супер-директории, следующие 9 — в директории, следующие 9 — в таблице. Физический адрес директории или же супер-директории загружен в один из управляющих регистров процессора.
При использовании PAE вместо 4МБ больших страниц используются двухмегзбайтные. В архитектуре x86_64 возможно использовать страницы размером 4 килобайта (4096 байт), 2 мегабайта, и (в некоторых AMD64) 1 гигабайт.
Страничное прерывание
Некоторые процессоры (MIPS) не имеют обращающегося к таблице микрокода, и генерируют отказ страницы сразу после неудачи поиска в TLB, обращение к таблице и её интерпретация возлагаются уже на обработчик отказа страницы. Это лишает таблицы страниц требования соответствовать жёстко заданному на уровне аппаратуры формату.
Причины отказа страницы (page fault):
Алгоритм работы страничного прерывания:
Обработчик отказов в ядре может загрузить нужную страницу из файла или же из области подкачки, может создать доступную на запись копию страницы «только для чтения», а может и возбудить исключительную ситуацию (в терминах UNIX — сигнал SIGSEGV) в данном процессе.
Таблицы страниц
Если страница не присутствует в памяти (бит P=0), то процессор не использует все остальные биты элемента PTE и программа может их использовать по своему усмотрению.
Таблицы страниц процессов
Каждый процесс имеет свой собственный набор таблиц страниц. Регистр «директория страниц» перегружается при каждом переключении контекста процесса. Также необходимо очистить ту часть TLB, которая относится к этому процессу.
В большинстве случаев ядро ОС помещается в то же адресное пространство, что и процессы, для него резервируется верхние 1-2 гигабайта 32-битного адресного пространства каждого процесса. Целью этих действий является предотвращение переключению таблиц страниц при входе в ядро на выходе из него. Страницы ядра помечаются как недоступные для кода режима пользователя.
Память региона ядра часто одинакова для всех процессов, но некоторые подрегионы ядра (например, регион, где находится подсистема графики и видео-драйвер) могут быть различным для разных групп процессов.
Потому что память ядра одинакова для всех процессов, соответствующие к ней записи в TLB не нужно перезагружать после переключения процесса. Для этой оптимизации архитектура x86 поддерживает флажок «глобальный» в PTE.
Страницы и работа с ними
В реальных (то есть не в учебных) системах используются страницы от 512 байт до 64 килобайт. Чаще всего размер страницы определяется архитектурой и является фиксированным для всей системы, например — 4 KiB.
С одной стороны, при меньшем размере страницы память меньше фрагментируется. Ведь наименьшая единица виртуальной памяти, которая может быть выделена процессу — это одна страница, а программам очень редко требуется целое число страниц. А значит, в последней странице, которую запросил процесс, скорее всего останется неиспользуемая память, которая, тем не менее, будет выделена, а значит — использована неэффективно.
С другой стороны, чем меньше размер страницы, тем больше размер страничных таблиц. Более того, при отгрузке на HDD и при чтении страниц с HDD быстрее получится записать несколько больших страниц, чем много маленьких такого же суммарного размера.
Отдельного внимания заслуживают так называемые большие страницы: huge pages и large pages[вики]. Платформа Размер обычной страницы Размер страницы максимально возможного размера
Действительно, при использовании таких страниц накладные расходы памяти повышаются. Тем не менее, прирост производительности программ в некоторых случаях может доходить до 10%[ссылка], что объясняется меньшим размером страничных директорий и более эффективной работой TLB.
Устройство 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 — Используется ли данная запись директории
Снимать и устанавливать эти флаги можно с помощью следующих функций: mmu_pte_set_writable(), mmu_pte_set_usermode(), mmu_pte_set_cacheable(), mmu_pte_set_executable()
Отображаемые в память файлы
Обработчик отказа страницы в ядре способен прочитать данную страницу из файла.
Это приводит к возможности легкой реализации отображенных в память файлов. Концептуально это то же, что выделение памяти и чтение в неё отрезка файла, с той разницей, что чтение осуществляется неявно «по требованию», выраженному отказом страницы при попытке обращения к ней.
Вторым преимуществом такого подхода является — в случае отображения «только для чтения» — разделение одной и той же физической памяти между всеми процессами, отображающими данный файл (выделенная же память своя у каждого процесса).
Третьим преимуществом является возможность «забывания» (discard) некоторых отображенных страниц без выгрузки их в область подкачки, обязательной для выделенной памяти. В случае повторной потребности в странице она может быть быстро загружена из файла снова.
Четвертым преимуществом является не-использование дискового кэша в этом режиме, что означает экономию на копировании данных из кэша в запрошенный регион. Преимущества дискового кэша, оптимизирующего операции небольшого размера, а также повторное чтение одних и тех же данных, полностью исчезают при чтениях целых страниц и тем более их групп, недостаток же в виде обязательного лишнего копирования — сохраняется.
Отображаемые в память файлы используется в ОС Windows, а также ОС семейства UNIX, для загрузки исполняемых модулей и динамических библиотек. Они же используются утилитой GNU grep для чтения входящего файла, а также для загрузки шрифтов в ряде графических подсистем.
Сегментно-страничная виртуальная память
Существуют две другие схемы организации управления памятью: сегментная и сегментно-страничная. [4] Сегменты, в отличие от страниц, могут иметь переменный размер. При сегментной организации виртуальный адрес является двумерным как для программиста, так и для операционной системы, и состоит из двух полей – номера сегмента и смещения внутри сегмента. Главное отличие сегментной организации от страничной в том, что в последней линейный адрес преобразован в двумерный операционной системой для удобства отображения, а сегментной двумерность адреса является следствием представления пользователя о процессе не в виде линейного массива байтов, а как набор сегментов переменного размера.
Логическое адресное пространство – набор сегментов. Каждый сегмент имеет имя, размер и другие параметры (уровень привилегий, разрешенные виды обращений, флаги присутствия). В отличие от страничной схемы, где пользователь задает только один адрес, в сегментной схеме пользователь специфицирует каждый адрес двумя величинами: именем сегмента и смещением.
Каждый сегмент – линейная последовательность адресов, начинающаяся с 0. Максимальный размер сегмента определяется разрядностью процессора (при 32-разрядной адресации это 232 байт или 4 Гбайт). Размер сегмента может меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента обычно содержится и длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает исключительная ситуация.
Логический адрес – упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.
В системах, где сегменты поддерживаются аппаратно, эти параметры обычно хранятся в таблице дескрипторов сегментов, а программа обращается к этим дескрипторам по номерам-селекторам. При этом в контекст каждого процесса входит набор сегментных регистров, содержащих селекторы текущих сегментов кода, стека, данных и т. д. и определяющих, какие сегменты будут использоваться при разных видах обращений к памяти. Это позволяет процессору уже на аппаратном уровне определять допустимость обращений к памяти, упрощая реализацию защиты информации от повреждения и несанкционированного доступа.
Хранить в памяти сегменты большого размера целиком так же неудобно, как и хранить процесс непрерывным блоком. Отсюда получается идея разбиения сегментов на страницы. При сегментно-страничной организации памяти происходит двухуровневая трансляция виртуального адреса в физический. В этом случае логический адрес состоит из трех полей: номера сегмента логической памяти, номера страницы внутри сегмента и смещения внутри страницы. Соответственно, используются две таблицы отображения – таблица сегментов, связывающая номер сегмента с таблицей страниц, и отдельная таблица страниц для каждого сегмента.
Огромным достоинством страничной виртуальной памяти по сравнению с сегментной является отсутствие «ближних» и «дальних» указателей. Наличие таких концепций в программировании уменьшает применимость арифметики указателей, и приводит к огромным проблемам с переносимостью кода с/на такие архитектуры. Так, например, значительная часть ПО с открытым кодом изначально разрабатывалась для бессегментных 32-битных платформ со страничной памятью и не может быть перенесена на сегментные архитектуры без серьёзной переработки.