Что такое страничная модель памяти

Что такое страничная модель памяти

Режимы работы микропроцессора.

1. Режимы работы микропроцессора

2. Организация памяти

· Модели использования оперативной памяти (сегментированная, страничная)

· Понятие о сегментированной модели памяти

· Понятие о страничной модели памяти

· Сегментно-страничный способ распределения памяти

3. Плоская модель памяти

Режимы работы микропроцессора

Защищенный режим ( protected mode)

Означает, что параллельные вычисления могут быть защищены программно-аппаратным путем.

Позволяет полностью использовать все возможности, предоставляемые микропроцессором. Все современные многозадачные ОС работают в этом режиме.

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

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

Режим виртуального 8086

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

ОП организована как последовательность байтов.

Каждому байту соответствует уникальный адрес (его номер), который называется физическим адресом.

Диапазон значений адресов зависит от разрядности шины адреса микропроцессора.

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

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

Понятие о сегментированной модели памяти

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

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

Сегмент представляет собой независимый, поддерживаемый на аппаратном уровне блок памяти.

Замечание. Программист может либо самостоятельно разбивать программу на фрагменты (сегменты), либо автоматизировать этот процесс и возложить его на систему программирования.

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

Операционная система (! а не сама программа) размещает сегменты программы в ОП по определенным физическим адресам, а значения этих адресов записывает в определенные места, в зависимости от режима работы микропроцессора:

· в реальном режиме адреса помещаются непосредственно в сегментные регистры ( cs, ds, ss, es, gs, fs) ;

Таким образом, для обращения к конкретному физическому адресу ОП необходимо определить адрес начала сегмента и смещение внутри сегмента.

Физический адрес принято записывать парой этих значений, разделенных двоеточием

Каждый сегмент описывается дескриптором сегмента.

ОС строит для каждого исполняемого процесса соответствующую таблицу дескрипторов сегментов и при размещении каждого из сегментов в ОП или внешней памяти в дескрипторе отмечает его текущее местоположение (бит присутствия).

Дескриптор содержит поле адреса, с которого сегмент начинается и поле длины сегмента. Благодаря этому можно осуществлять контроль

1) размещения сегментов без наложения друг на друга

2) обращается ли код исполняющейся задачи за пределы текущего сегмента.

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

1) общий объем виртуальной памяти превосходит объем физической памяти

2) возможность размещать в памяти как можно больше задач (до определенного предела) Þ увеличивает загрузку системы и более эффективно используются ресурсы системы

3) потери памяти на размещение дескрипторных таблиц

4) потери процессорного времени на обработку дескрипторных таблиц.

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

Понятие о страничной модели памяти

Это надстройка над сегментной моделью.

ОП делится на блоки фиксированного размера 4 Кб (должно быть число, кратное степени двойки, чтобы операции сложения можно было бы заменить на операции конкатенации).

Каждый такой блок называется страницей.

Их число 1.048.576 Þ 4 Гб адресуемой памяти.

Основное применение этой модели связано с организацией виртуальной памяти.

Для того, чтобы использовать для работы программ пространство памяти большее, чем объем физической памяти используется механизм виртуальной памяти.

В настоящее время файл подкачки может динамически изменять свой размер в зависимости от потребностей системы.

Для i486 и Pentium размер возможной виртуальной памяти может достигать 4 Тб (терабайт).

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

Для каждой текущей задачи создается таблица страниц.

Диспетчер памяти для каждой страницы формирует соответствующий дескриптор. Дескриптор содержит так называемый бит присутствия.

Если он = 1, это означает, что данная страница сейчас размещена в ОП.

Если он = 0, то страница расположена во внешней памяти.

Защита страничной памяти основана на контроле уровня доступа к каждой странице.

Каждая страница снабжается кодом уровня доступа (только чтение; чтение и запись; только выполнение). При работе со страницей сравнивается значение кода разрешенного уровня доступа с фактически требуемым. При несовпадении работа программы прерывается.

Страничная модель памяти поддерживается только в защищенном режиме работы микропроцессора.

минимально возможная фрагментация (эффективное распределение памяти).

1) потери памяти на размещение таблиц страниц

2) потери процессорного времени на обработку таблиц страниц (диспетчер памяти).

3) Программы разбиваются на страницы случайно, без учета логических взаимосвязей, имеющихся в коде Þ межстраничные переходы осуществляются чаще, чем межсегментные + трудности в организации разделения программных модулей между выполняющими процессами

Чтобы избежать недостатка №3 был предложен сегментно-страничный способ распределения памяти.

Сегментно-страничный способ распределения памяти

Программа разбивается на сегменты.

Но смещение относительно начала сегмента может состоять из двух полей: виртуальной страницы и индекса.

Для доступа к памяти необходимо:

1) вычислить адрес дескриптора сегмента и причитать его;

2) вычислить адрес элемента таблицы страниц этого сегмента и извлечь из памяти необходимый элемент;

3) к номеру (адресу) физической страницы приписать номер (адрес) ячейки в странице.

Þ Задержка в доступе к памяти (в три раза больше, чем при прямой адресации).

Чтобы избежать этого вводится кэширование (кэш строится по ассоциативному принципу). Мы будем это изучать позже.

Плоская модель памяти

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

Это подход называется плоской памятью.

· При использовании плоской модели памяти упрощается создание и ОС, и систем программирования.

· уменьшаются расходы памяти на поддержку системных информационных структур

В абсолютном большинстве современных 32-разрядных ОС (для микропроцессоров Intel ) используется плоская модель памяти.

Источник

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

Страничная память (Операционные Системы)

Страничная память — способ организации виртуальной памяти, при котором единицей отображения виртуальных адресов на физические является регион постоянного размера (т. н. страница). [1] Типичный размер страницы — 4096 байт, для некоторых архитектур — до 128 КБ.

Поддержка такого режима присутствует в большинстве 32-битных и 64-битных процессоров. Такой режим является классическим для почти всех современных ОС, в том числе Windows и семейства UNIX. Широкое использование такого режима началось с процессора VAX и ОС VMS с конца 70-х годов (по некоторым сведениям, первая реализация). В семействе x86 поддержка появилась с поколения 386, оно же первое 32-битное поколение.

Содержание

Решаемые задачи

Механизм работы

В самом простом и наиболее распространенном случае страничной организации памяти (или 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-х битный физический адрес.

Страничная память 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.

Работа менеджера памяти Windows

Для управления виртуальной памятью в операционной системе Windows предусмотрен специальный менеджер Virtual Memory Manager (VMM). Он является составной частью ядра операционной системы и представляет собой отдельный процесс, постоянно находящийся в оперативной памяти. Основная задача VMM заключается в управлении страницами виртуальной памяти. [4]

Каждому процессу VMM выделяет часть физической памяти, которая называется рабочим набором (Working Set). Кроме того, VMM создает базу состояния страниц (page-frame database), которая организована как шесть списков страниц одного типа. Выделяют следующие типы страниц:

Свободные страницы могут применяться, однако прежде они подлежат процедуре обнуления (заполнения нулями). Процедурой обнуления страниц занимается специальная подпрограмма менеджера памяти Zero Page Thread;

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

В идеале замещению должна подлежать та страница, к которой в будущем не будет обращений, или страница, которая не будет использоваться дольше других. Однако достоверного способа определить, какая именно страница отвечает перечисленным критериям, нет. Поэтому менеджер памяти применяет следующий алгоритм. Он периодически просматривает список рабочих страниц (Valid) и помечает их как отсутствующие (P = 0). Однако данные страницы не удаляются из рабочего процесса — они остаются на месте и просто переводятся из категории Valid в категорию модифицированных (Modified) или резервных (Standby) страниц ( никаких изменений в содержимом этих страниц не производится). Если измененная таким образом страница требуется какому-нибудь процессу, то происходит обращение к ней и возникает ошибка обращения к странице. Но поскольку в действительности страница находится в физической памяти и ее содержимое не подвергалось изменению, то менеджеру памяти достаточно перевести данную страницу обратно в категорию Valid, сделав ее доступной для процесса. Если же страница не используется в течение длительного времени процессами и обращений к ней не происходит, она со временем переводится в категорию свободных (Free) страниц, а затем обнуляется и переводится в категорию пустых (Zeroed) страниц.

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

Отображаемые в память файлы

Обработчик отказа страницы в ядре способен прочитать данную страницу из файла.

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

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

Третьим преимуществом является возможность «забывания» (discard) некоторых отображенных страниц без выгрузки их в область подкачки, обязательной для выделенной памяти. В случае повторной потребности в странице она может быть быстро загружена из файла снова.

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

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

Сегментно-страничная виртуальная память

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

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

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

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

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

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

Огромным достоинством страничной виртуальной памяти по сравнению с сегментной является отсутствие «ближних» и «дальних» указателей. Наличие таких концепций в программировании уменьшает применимость арифметики указателей, и приводит к огромным проблемам с переносимостью кода с/на такие архитектуры. Так, например, значительная часть ПО с открытым кодом изначально разрабатывалась для бессегментных 32-битных платформ со страничной памятью и не может быть перенесена на сегментные архитектуры без серьёзной переработки.

Источник

Пишем операционную систему на Rust. Страничная организация памяти

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

Этот блог выложен на GitHub. Если у вас какие-то вопросы или проблемы, открывайте там соответствующий запрос.

Защита памяти

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

Например, в некоторых процессорах ARM Cortex-M (во встраиваемых системах) есть блок защиты памяти (MPU), который определяет небольшое количество (например, 8) областей памяти с различными разрешениями доступа (например, нет доступа, только для чтения, для чтения и записи). При каждом доступе к памяти MPU гарантирует, что адрес находится в области с правильными разрешениями, в противном случае выдаёт исключение. Изменяя области и разрешения доступа, ОС гарантирует, что у каждого процесса есть доступ только к своей памяти, чтобы изолировать процессы друг от друга.

На x86 поддерживается два различных подхода к защите памяти: сегментация и страничная организация.

Сегментация

Сегментацию реализовали ещё в 1978 году, первоначально для увеличения объёма адресуемой памяти. В то время CPU поддерживали только 16-разрядные адреса, что ограничивало объём адресуемой памяти 64 КБ. Чтобы увеличить этот объём, ввели дополнительные сегментные регистры, каждый из которых содержит адрес смещения. CPU автоматически добавляет это смещение при каждом доступе к памяти, адресуя таким образом до 1 МБ памяти.

В первой версии сегментации регистры непосредственно содержали смещение и управление доступом не выполнялось. С появлением защищенного режима механизм изменился. Когда CPU работает в таком режиме, дескрипторы сегментов хранят индекс в локальной или глобальной таблице дескрипторов, которая в дополнение к адресу смещения содержит размер сегмента и разрешения доступа. Загружая отдельные глобальные/локальные таблицы дескрипторов для каждого процесса, ОС может изолировать процессы друг от друга.

Изменяя адреса памяти перед фактическим доступом, сегментация реализовала метод, который теперь используется почти везде: это виртуальная память.

Виртуальная память

Чтобы различать два типа адресов, адреса до преобразования называются виртуальными, а адреса после преобразования — физическими. Между ними одно важное различие: физические адреса уникальны и всегда ссылаются на одно и то же уникальное расположение в памяти. С другой стороны, виртуальные адреса зависят от функции преобразования. Два разных виртуальных адреса вполне могут ссылаться на один физический адрес. Кроме того, идентичные виртуальные адреса могут ссылаться на разные физические адреса после преобразования.

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

Здесь одна и та же программа запускается дважды, но с разными функциями преобразования. У первого экземпляра смещение сегмента 100, так что его виртуальные адреса 0-150 преобразуются в физические адреса 100-250. У второго экземпляра смещение 300, которое преобразует виртуальные адреса 0-150 в физические адреса 300-450. Это позволяет обеим программам выполнять один и тот же код и использовать одни и те же виртуальные адреса, не мешая друг другу.

Ещё одно преимущество в том, что теперь программы можно размещать в произвольных местах физической памяти. Таким образом, ОС использует весь объём доступной памяти без необходимости перекомпиляции программ.

Фрагментация

Различие виртуальных и физических адресов — реальное достижение сегментации. Но есть и проблема. Представьте, что мы хотим запустить третью копию программы, которую видели выше:

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

Один из способов борьбы с фрагментацией — приостановить выполнение программ, переместить используемые части памяти ближе друг к другу, обновить преобразование, а затем возобновить выполнение:

Теперь для запуска третьего экземпляра достаточно места.

Недостаток такой дефрагментации — необходимость копирования больших объёмов памяти, что снижает производительность. Данную процедуру приходится выполнять регулярно, пока память не стала слишком фрагментированной. Производительность становится непредсказуемой, программы останавливаются в произвольное время и могут перестать отвечать на запросы.

Фрагментация — одна из причин, почему в большинстве систем не используется сегментация. На самом деле она больше не поддерживается даже в 64-разрядном режиме на x86. Вместо сегментации используются страницы, которые полностью исключают проблему фрагментации.

Страничная организация памяти

Идея состоит в том, чтобы разделить пространство виртуальной и физической памяти на небольшие блоки фиксированного размера. Блоки виртуальной памяти называются страницами, а блоки физического адресного пространства — фреймами. Каждая страница индивидуально сопоставляется с фреймом, что позволяет разделить большие области памяти между несмежными физическими фреймами.

Преимущество становится очевидным, если повторить пример с фрагментированным пространством памяти, но на этот раз с использованием страниц вместо сегментации:

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

Скрытая фрагментация

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

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

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

Таблицы страниц

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

Для вышеприведённого примера таблицы будут выглядеть следующим образом:

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

В зависимости от архитектуры, в поле флагов таблицы страниц могут храниться и атрибуты, такие как права доступа. В приведенном выше примере флаг r/w делает страницу доступной для чтения и записи.

Многоуровневые таблицы страниц

Требуется всего четыре физических фрейма, но в таблице страниц более миллиона записей. Мы не можем пропустить пустые записи, потому что тогда CPU в процессе преобразования не сможет перейти напрямую к правильной записи (например, больше не гарантируется, что четвёртая страница использует четвёртую запись).

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

Страница 0 попадает в первую область 10_000 байт, поэтому использует первую запись таблицы страниц второго уровня. Эта запись указывает на таблицу страниц T1 первого уровня, которая определяет, что страница 0 ссылается на фрейм 0.

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

Зная о страничной организации и многоуровневых таблицах, можно посмотреть, как реализована страничная организация в архитектуре x86_64 (предполагаем, что процессор работает в 64-разрядном режиме).

Страничная организация на x86_64

Архитектура x86_64 использует четырёхуровневую таблицу с размером страницы 4 КБ. Независимо от уровня, в каждой таблице страниц 512 элементов. Каждая запись имеет размер 8 байт, поэтому размеры таблиц 512 × 8 байт = 4 КБ.

Как видим, каждый табличный индекс содержит 9 бит, что имеет смысл, потому что в таблицах 2^9 = 512 записей. Нижние 12 бит — это смещение в 4-килобайтную страницу (2^12 байт = 4 КБ). Биты от 48 до 64 отбрасываются, так что x86_64 на самом деле не 64-разрядная система, а поддерживает только 48-разрядные адреса. Есть планы расширить размер адреса до 57 бит через 5-уровневую таблицу страниц, но ещё не создан такой процессор.

Хотя биты от 48 до 64 отбрасываются, им нельзя задать произвольные значения. Все биты в этом диапазоне должны быть копиями бита 47, чтобы сохранить уникальные адреса и разрешить будущее расширение, например, до 5-уровневой таблицы страниц. Это называется расширением знака (sign-extension), потому что очень похоже на расширение знака в дополнительном коде. Если неправильно расширить адрес, CPU выдаёт исключение.

Пример преобразования

Рассмотрим на примере, как работает преобразование адреса:

С помощью этих индексов мы теперь можем пойти по иерархии таблиц страниц и найти соответствующий фрейм:

Хотя в этом примере используется только один экземпляр каждой таблицы, обычно в каждом адресном пространстве присутствует несколько экземпляров каждого уровня. Максимум:

Формат таблицы страниц

В архитектуре x86_64 таблицы страниц по сути представляют собой массивы из 512 записей. В синтаксисе Rust:

Размер каждой записи 8 байт (64 бита) и следующий формат:

Мы видим, что для хранения физического адреса фрейма используются только биты 12-51, а остальные работают как флаги или могут свободно использоваться операционной системой. Такое возможно, потому что мы всегда указываем или на выровненный по 4096 байтам адрес, или на выровненную страницу таблиц, или на начало соответствующего фрейма. Это означает, что биты 0-11 всегда равны нулю, так что их можно не хранить, они просто обнуляются на аппаратном уровне перед использованием адреса. То же самое относится и к битам 52-63, поскольку архитектура x86_64 поддерживает только 52-разрядные физические адреса (и только 48-разрядные виртуальные адреса).

Подробнее рассмотрим доступные флаги:

Буфер ассоциативной трансляции (TLB)

Из-за четырёх уровней для каждого преобразование адреса требуется четыре доступа к памяти. Ради повышения производительности x86_64 кэширует последние несколько переводов в так называемом буфере ассоциативной трансляции (TLB). Это позволяет пропустить преобразование, если оно ещё в кэше.

Важно не забывать чистить TLB после каждого изменения таблицы страниц, иначе CPU продолжит использовать старую трансляцию, что приведёт к непредсказуемым ошибкам, которые очень трудно отладить.

Реализация

Мы не упомянули одну вещь: наше ядро уже поддерживает страничную организацию. Загрузчик из статьи «Минимальное ядро на Rust» уже установил четырёхуровневую иерархию, которая сопоставляет каждую страницу нашего ядра с физическим фреймом, потому что страничная организация обязательна в 64-разрядном режиме на x86_64.

Благодаря страничной организации ядро уже относительно безопасно: каждый доступ за пределы допустимой памяти вызывает ошибку страницы, а не допускает запись в физическую память. Загрузчик даже установил правильные разрешения доступа для каждой страницы: исполняемыми будут только страницы с кодом, а доступны для записи только страницы с данными

Ошибки страницы (PageFault)

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

Теперь получаем доступ к памяти вне ядра:

После запуска мы видим, что происходит вызов обработчика ошибок страницы:

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

Доступ к таблицам страниц

Теперь взглянем на таблицы страниц для ядра:

После запуска видим такой результат:

Level 4 page table at: PhysAddr(0x1000)

После запуска видим такой результат:

Вместо работы с небезопасными указателями напрямую можно использовать тип PageTable из x86_64 :

x86_64 также предоставляет некоторые абстракции для отдельных записей, чтобы сразу увидеть установленные флаги:

Следующий шаг — последовать по указателям в записи 0 или записи 1 к таблице страниц уровня 3. Но теперь у нас опять возникает проблема, что 0x2000 и 0x6e5000 представляют собой физические адреса, поэтому мы не можем получить к ним прямой доступ. Эта проблема будет решена в следующей статье.

Резюме

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

Страничная организация хранит информацию о трансляции страниц в таблицах одного или нескольких уровней. Архитектура x86_64 использует четырёхуровневые таблицы с размером страницы 4 КБ. Оборудование автоматически обходит таблицы страниц и кэширует результаты преобразования в буфере ассоциативной трансляции (TLB). При изменении таблиц страниц его следует принудительно очищать.

Мы узнали, что наше ядро уже поддерживает страничную организацию, а при несанкционированном доступе к памяти выпадает PageFault. Мы попытались получить доступ к текущим активным таблицам страниц, но удалось получить доступ только к таблице четвёртого уровня, так как в таблицах страниц хранятся физические адреса, а мы не можем получить к ним доступ напрямую из ядра.

Источник