Таблица страниц - Page table

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

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

Роль таблицы страниц

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

Когда процесс запрашивает доступ к данным в своей памяти, операционная система несет ответственность за отображение виртуального адреса, предоставленного процессом, на физический адрес фактической памяти, в которой хранятся эти данные. Таблица страниц - это место, где операционная система хранит свои сопоставления виртуальных адресов с физическими адресами, причем каждое сопоставление также известно как запись в таблице страниц (PTE).[1][2]

Процесс перевода

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

ЦП блок управления памятью (MMU) хранит кэш недавно использованных сопоставлений из таблицы страниц операционной системы. Это называется резервный буфер перевода (TLB), который является ассоциативным кешем.[3]

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

Ошибки перевода

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

  • Поиск может завершиться неудачно, если для виртуального адреса недоступна трансляция, что означает, что виртуальный адрес недействителен. Обычно это происходит из-за ошибки программирования, и операционная система должна предпринять некоторые действия для решения этой проблемы. В современных операционных системах это вызовет ошибка сегментации сигнал отправляется программе-нарушителю.
  • Поиск также может завершиться ошибкой, если страница в настоящее время не находится в физической памяти. Это произойдет, если запрошенная страница была Съехал физической памяти, чтобы освободить место для другой страницы. В этом случае страница выгружается во вторичное хранилище, расположенное на носителе, таком как жесткий диск (это вторичное хранилище, или «резервное хранилище», часто называют «разделом подкачки», если это раздел диска, или файл подкачки, «файл подкачки» или «файл подкачки», если это файл). Когда это происходит, страницу необходимо взять с диска и вернуть в физическую память. Аналогичный механизм используется для файлы с отображением памяти, которые отображаются в виртуальную память и загружаются в физическую память по запросу.

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

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

  • Попытка записи, когда для таблицы страниц установлен бит только для чтения, вызывает сбой страницы. Это обычная часть реализации многих операционных систем. копирование при записи; это также может произойти, когда запись выполняется в место, из которого процессу разрешено читать, но в которое не разрешено писать, и в этом случае сигнал доставляется процессу.
  • Попытка выполнить код, когда таблица страниц имеет Бит NX (бит отсутствия выполнения), установленный в таблице страниц, вызывает сбой страницы. Это может использоваться операционной системой в сочетании с битом только для чтения, чтобы обеспечить Записать XOR Execute функция, которая останавливает некоторые виды эксплойтов.[4]

Данные таблицы кадров

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

Данные таблицы страниц

Таблица страниц - это массив записей таблицы страниц.

Запись в таблице страниц

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

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

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

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

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

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

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

Таблицы перевернутых страниц

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

IPT объединяет таблицу страниц и каркасный стол в одну структуру данных. По своей сути это таблица фиксированного размера с количеством строк, равным количеству кадров в памяти. Если имеется 4 000 фреймов, в перевернутой таблице страниц будет 4 000 строк. Для каждой строки есть запись для номера виртуальной страницы (VPN), номера физической страницы (не физического адреса), некоторых других данных и средств для создания столкновение цепь, как мы увидим позже.

Перебирать все записи основной структуры IPT неэффективно, и хеш-таблица может использоваться для отображения виртуальных адресов (и информации адресного пространства / PID, если необходимо) в индекс в IPT - здесь используется цепочка конфликтов. Эта хеш-таблица известна как хеш-таблица привязок. Функция хеширования обычно не оптимизирована для покрытия - более желательна чистая скорость. Конечно, в хеш-таблицах возникают коллизии. Из-за этой выбранной функции хеширования мы можем столкнуться с множеством конфликтов при использовании, поэтому для каждой записи в таблице предоставляется VPN, чтобы проверить, является ли это поисковой записью или коллизией.

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

Виртуальный адрес в этой схеме можно разделить на два, первая половина - это номер виртуальной страницы, а вторая половина - смещение на этой странице.

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

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

Таблицы перевернутых страниц используются, например, на PowerPC, то UltraSPARC и IA-64 архитектура.[5]

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

Двухуровневая структура таблицы страниц в x86 архитектура (без PAE или PSE ).
Трехуровневая структура таблицы страниц в архитектуре x86 (с PAE, без PSE ).

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

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

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

Многоуровневые таблицы страниц также называются «иерархическими таблицами страниц».

Виртуализированные таблицы страниц

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

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

Вложенные таблицы страниц

Смотрите также: Трансляция адресов второго уровня

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

Смотрите также

использованная литература

  1. ^ "Виртуальная память". umd.edu. Получено 28 сентября 2015.
  2. ^ «Управление таблицей страниц». kernel.org. Получено 28 сентября 2015.
  3. ^ "Обзор методов проектирования TLB ", Параллелизм и вычисления: практика и опыт, 2016.
  4. ^ "W ^ X - Механизм".
  5. ^ Уильям Столлингс, Внутреннее устройство операционных систем и принципы проектирования, п. 353.

дальнейшее чтение

внешние ссылки