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

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

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

Современные процессоры используют концепции физической памяти и виртуальной памяти: запущенные процессы используют виртуальные адреса и когда команда запрашивает доступ к памяти, процессор переводит виртуальный адрес на физический адрес, используя буфер ассоциативной трансляции (далее — TLB) и/или таблицу страниц.

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

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

Когда виртуальный адрес необходимо преобразовать в физический адрес, то вначале просматривается TLB. Если совпадение найдено (называется «TLB hit») то возвращается физический адрес и доступ к памяти может продолжаться. Однако, если нет совпадения (называемого «TLB miss»), то либо модуль управления памятью, либо обработчик пропусков TLB операционной системы ищет сопоставление адресов в таблице страниц, чтобы узнать, существует ли сопоставление (называется «page walk»). Если сопоставление существует — то оно записывается обратно в TLB (это необходимо сделать, поскольку аппаратное обеспечение обращается к памяти через TLB в системе виртуальной памяти), и текущая команда перезапускается (что также может происходить параллельно).

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

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

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

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

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

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

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

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

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

Адрес, используемый в машинном коде, то есть значение указателя, называется «виртуальный адрес».

Адрес, выставляемый процессором на шину, называется «линейный адрес» (который позже преобразуется в физический).

Запись таблицы страниц обычно содержит в себе следующую информацию:

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

Число записей в одной таблице ограничено и зависит от размера записи и размера страницы. Используется многоуровневая организация таблиц, часто 2 или 3 уровня, иногда - 4 уровня (для 64-разрядных архитектур).

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

При использовании 3-уровневой организации добавляется надкаталог, хранящий записи, указывающие на несколько каталогов.

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

Формат записей таблиц, их размер, размер страницы и организация таблиц зависит от типа процессора, а иногда и от режима его работы.

Исторически x86 использует 32-битные PTE, 32-битные виртуальные адреса, 4-КБ страницы, 1024 записи в таблице, двухуровневые таблицы. Старшие 10 битов виртуального адреса — номер записи в каталоге, следующие 10 — номер записи в таблице, младшие 12 — адрес внутри страницы.

Начиная с Pentium Pro, процессор поддерживает страницы размером 4 МБ. Однако, чтобы система и программы, запущенные в ней, могли использовать страницы такого размера, технология 4-МБ страниц (hugepages) должна быть соответствующим образом активирована, а приложение - настроено на использование страниц такого размера.

Процессор x86 в режиме PAE (Physical Address Extension) и в режиме x86_64 (long mode) использует 64-битные PTE (из них реально задействованы не все биты физического адреса, от 36 в PAE до 48 в некоторых x86_64), 32-битные виртуальные адреса, 4-КБ страницы, 512 записей в таблице, трёхуровневые таблицы с четырьмя каталогами и четырьмя записями в надкаталоге. Старшие 2 бита виртуального адреса — номер записи в надкаталоге, следующие 9 — в каталоге, следующие 9 — в таблице. Физический адрес каталога или же надкаталога загружен в один из управляющих регистров процессора.

При использовании PAE вместо 4-МБ больших страниц используются двухмегабайтные. См. также PSE.

В архитектуре x86_64 возможно использовать страницы размером 4 килобайта (4096 байтов), 2 мегабайта, и (в некоторых AMD64) 1 гигабайт.

Если обращение к памяти не может быть оттранслировано через TLB, то микрокод процессора обращается к таблицам страниц и пытается загрузить PTE оттуда в TLB. Если и после такой попытки сохранились проблемы, то процессор исполняет специальное прерывание, называемое «отказ страницы» (page fault). Обработчик этого прерывания находится в подсистеме виртуальной памяти ядра ОС.

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

Причины отказа страницы (page fault):

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

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

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

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

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

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

• Буфер ассоциативной трансляции
• Страничная память
• Защищённый режим
• Блок управления памятью
• Отображение файла в память
• Отказ страницы