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