Таблица страниц — это структура данных, используемая системой виртуальной памяти в компьютере для хранения сопоставлений между виртуальными адресами и физическими адресами . Виртуальные адреса используются программой, выполняемой процессом доступа , в то время как физические адреса используются оборудованием или, более конкретно, подсистемой оперативной памяти (ОЗУ). Таблица страниц — это ключевой компонент трансляции виртуальных адресов , необходимый для доступа к данным в памяти. Таблица страниц настраивается операционной системой компьютера и может быть прочитана и записана во время процесса трансляции виртуальных адресов блоком управления памятью или низкоуровневым системным программным обеспечением или прошивкой.
В операционных системах, использующих виртуальную память, создается впечатление, что каждый процесс работает с большими, непрерывными разделами памяти. Физически память каждого процесса может быть распределена по разным областям физической памяти или может быть перемещена ( выгружена ) во вторичное хранилище, обычно на жесткий диск (HDD) или твердотельный накопитель (SSD).
Когда процесс запрашивает доступ к данным в своей памяти, операционная система обязана сопоставить виртуальный адрес, предоставленный процессом, с физическим адресом фактической памяти, где хранятся эти данные. Таблица страниц — это место, где хранятся сопоставления виртуальных адресов с физическими адресами, причем каждое сопоставление также известно как запись таблицы страниц (PTE). [1] [2]
Блок управления памятью (MMU) внутри ЦП хранит кэш недавно использованных отображений из таблицы страниц операционной системы. Это называется буфером трансляции (TLB), который является ассоциативным кэшем.
Когда виртуальный адрес необходимо преобразовать в физический адрес, сначала выполняется поиск в TLB. Если совпадение найдено, что называется попаданием в TLB , возвращается физический адрес, и доступ к памяти может быть продолжен. Однако, если совпадения нет, что называется промахом TLB , MMU, системная прошивка или обработчик промахов TLB операционной системы обычно ищут сопоставление адресов в таблице страниц, чтобы узнать, существует ли сопоставление, что называется проходом страницы . Если оно существует, оно записывается обратно в TLB, что необходимо сделать, поскольку оборудование обращается к памяти через TLB в системе виртуальной памяти, а инструкция, вызвавшая ошибку, перезапускается, что также может происходить параллельно. Последующее преобразование приведет к попаданию в TLB, и доступ к памяти будет продолжен.
Поиск в таблице страниц может завершиться неудачей, вызвав ошибку страницы , по двум причинам:
Когда физическая память не заполнена, это простая операция: страница записывается обратно в физическую память, таблица страниц и TLB обновляются, и инструкция перезапускается. Однако, когда физическая память заполнена, одну или несколько страниц в физической памяти необходимо выгрузить, чтобы освободить место для запрошенной страницы. Таблицу страниц необходимо обновить, чтобы отметить, что страницы, которые ранее находились в физической памяти, больше не находятся там, и отметить, что страница, которая была на диске, теперь находится в физической памяти. TLB также необходимо обновить, включая удаление из нее выгруженной страницы, и перезапустить инструкцию. Какую страницу выгружать, является предметом алгоритмов замены страниц .
Некоторые блоки MMU вызывают ошибку страницы по другим причинам, независимо от того, находится ли страница в данный момент в физической памяти и отображена ли она в виртуальное адресное пространство процесса:
Простейшие системы таблиц страниц часто поддерживают таблицу фреймов и таблицу страниц. Таблица фреймов содержит информацию о том, какие фреймы отображаются. В более сложных системах таблица фреймов также может содержать информацию о том, к какому адресному пространству принадлежит страница, статистическую информацию или другую фоновую информацию.
Таблица страниц представляет собой массив записей таблицы страниц.
Каждая запись таблицы страниц (PTE) содержит сопоставление между виртуальным адресом страницы и адресом физического фрейма. Также есть вспомогательная информация о странице, такая как текущий бит, грязный или измененный бит, адресное пространство или информация об идентификаторе процесса, среди прочего.
Вторичное хранилище, такое как жесткий диск, может использоваться для увеличения физической памяти. Страницы могут быть загружены и выгружены из физической памяти и диска. Текущий бит может указывать, какие страницы в данный момент присутствуют в физической памяти или находятся на диске, и может указывать, как обрабатывать эти различные страницы, т. е. загружать ли страницу с диска и выгружать другую страницу из физической памяти.
Грязный бит позволяет оптимизировать производительность. Страница на диске, которая выгружается в физическую память, затем считывается и затем снова выгружается, не нуждается в обратной записи на диск, поскольку страница не изменилась. Однако, если страница была записана после того, как она выгружается, ее грязный бит будет установлен, указывая, что страница должна быть записана обратно в резервное хранилище. Эта стратегия требует, чтобы резервное хранилище сохраняло копию страницы после того, как она выгружается в память. Когда грязный бит не используется, резервное хранилище должно быть таким же большим, как мгновенный общий размер всех выгружаемых страниц в любой момент. Когда грязный бит используется, в любое время некоторые страницы будут существовать как в физической памяти, так и в резервном хранилище.
В операционных системах, которые не являются операционными системами с единым адресным пространством , необходима информация об адресном пространстве или идентификаторе процесса, чтобы система управления виртуальной памятью знала, какие страницы с каким процессом связать. Два процесса могут использовать два одинаковых виртуальных адреса для разных целей. Таблица страниц должна предоставлять разные сопоставления виртуальной памяти для двух процессов. Это можно сделать, назначив двум процессам различные идентификаторы адресной карты или используя идентификаторы процессов. Связывание идентификаторов процессов со страницами виртуальной памяти также может помочь в выборе страниц для выгрузки, поскольку страницы, связанные с неактивными процессами, особенно процессами, чьи кодовые страницы были выгружены, с меньшей вероятностью понадобятся немедленно, чем страницы, принадлежащие активным процессам.
В качестве альтернативы маркировке записей таблицы страниц уникальными для процесса идентификаторами, сама таблица страниц может занимать отдельную страницу виртуальной памяти для каждого процесса, так что таблица страниц становится частью контекста процесса. В такой реализации таблица страниц процесса может быть выгружена, когда процесс больше не находится в памяти.
Существует несколько типов таблиц страниц, оптимизированных для различных требований. По сути, простая таблица страниц должна хранить виртуальный адрес, физический адрес, который находится «под» этим виртуальным адресом, и, возможно, некоторую информацию об адресном пространстве.
Инвертированную таблицу страниц (IPT) лучше всего рассматривать как расширение TLB вне чипа , которое использует обычную системную оперативную память. В отличие от настоящей таблицы страниц, она не обязательно способна удерживать все текущие отображения. Операционная система должна быть готова обрабатывать промахи, как это было бы с заполненным программным обеспечением TLB в стиле MIPS.
IPT объединяет таблицу страниц и таблицу кадров в одну структуру данных. В ее основе лежит таблица фиксированного размера с числом строк, равным числу кадров в памяти. Если кадров 4000, то инвертированная таблица страниц имеет 4000 строк. Для каждой строки есть запись для номера виртуальной страницы (VPN), номера физической страницы (не физического адреса), некоторых других данных и средства для создания цепочки коллизий , как мы увидим позже.
Поиск по всем записям основной структуры IPT неэффективен, и для сопоставления виртуальных адресов (и информации об адресном пространстве/PID, если необходимо) с индексом в IPT может использоваться хэш-таблица — именно здесь используется цепочка коллизий. Эта хэш-таблица известна как таблица привязки хэша . Функция хэширования, как правило, не оптимизирована для покрытия — более желательна чистая скорость. Конечно, хэш-таблицы сталкиваются с коллизиями. Из-за этой выбранной функции хэширования мы можем столкнуться с большим количеством коллизий при использовании, поэтому для каждой записи в таблице предоставляется VPN для проверки, является ли она искомой записью или коллизией.
При поиске сопоставления используется таблица хэш-якорей. Если запись не существует, происходит ошибка страницы. В противном случае запись находится. В зависимости от архитектуры запись может быть снова помещена в TLB и обращение к памяти перезапускается, или цепочка коллизий может отслеживаться до тех пор, пока она не будет исчерпана и не произойдет ошибка страницы.
Виртуальный адрес в этой схеме можно разделить на две части: первая половина — это номер виртуальной страницы, а вторая половина — смещение на этой странице.
Основная проблема этой конструкции — плохая локальность кэша , вызванная хэш-функцией . Древовидные конструкции избегают этого, размещая записи таблицы страниц для соседних страниц в соседних местах, но инвертированная таблица страниц разрушает пространственную локальность ссылок , разбрасывая записи повсюду. Операционная система может минимизировать размер хэш-таблицы, чтобы уменьшить эту проблему, при этом компромиссом является увеличение частоты промахов.
Обычно существует одна хэш-таблица, непрерывная в физической памяти, общая для всех процессов. Идентификатор для каждого процесса используется для устранения неоднозначности страниц различных процессов друг от друга. Удаление записей таблицы страниц определенного процесса занимает довольно много времени; ОС может избегать повторного использования значений идентификатора для каждого процесса, чтобы отсрочить решение этой проблемы. В качестве альтернативы можно использовать хэш-таблицы для каждого процесса, но они непрактичны из-за фрагментации памяти , которая требует предварительного выделения таблиц.
Инвертированные таблицы страниц используются, например, в архитектуре PowerPC , UltraSPARC и IA-64 . [4]
Инвертированная таблица страниц хранит список отображений, установленных для всех фреймов в физической памяти. Однако это может быть довольно расточительно. Вместо этого мы могли бы создать структуру таблицы страниц, содержащую отображения для виртуальных страниц. Это делается путем хранения нескольких таблиц страниц, которые охватывают определенный блок виртуальной памяти. Например, мы можем создать меньшие страницы по 1024 записи по 4 КБ, которые охватывают 4 МБ виртуальной памяти.
Это полезно, поскольку часто самые верхние и самые нижние части виртуальной памяти используются при запуске процесса — верхние часто используются для сегментов текста и данных, а нижние — для стека, со свободной памятью между ними. Многоуровневая таблица страниц может хранить несколько меньших таблиц страниц, чтобы покрывать только верхние и нижние части памяти, и создавать новые только при крайней необходимости.
Теперь каждая из этих меньших таблиц страниц связана вместе с главной таблицей страниц, фактически создавая древовидную структуру данных. Не обязательно должно быть только два уровня, возможно, их может быть несколько. Например, виртуальный адрес в этой схеме может быть разделен на три части: индекс в корневой таблице страниц, индекс в таблице подстраниц и смещение на этой странице.
Многоуровневые таблицы страниц также называются «иерархическими таблицами страниц».
Было упомянуто, что создание структуры таблицы страниц, содержащей сопоставления для каждой виртуальной страницы в виртуальном адресном пространстве, может оказаться расточительным. Но мы можем обойти проблемы избыточного пространства, поместив таблицу страниц в виртуальную память и позволив системе виртуальной памяти управлять памятью для таблицы страниц.
Однако часть этой линейной структуры таблицы страниц должна всегда оставаться резидентной в физической памяти, чтобы предотвратить циклические ошибки страниц и искать ключевую часть таблицы страниц, которая отсутствует в таблице страниц.
Вложенные таблицы страниц могут быть реализованы для повышения производительности аппаратной виртуализации . Обеспечивая аппаратную поддержку виртуализации таблиц страниц, потребность в эмуляции значительно снижается. Для виртуализации x86 текущими вариантами являются функция Intel Extended Page Table и функция AMD Rapid Virtualization Indexing .