Таблица страниц: отображение виртуальных адресов в физические

Введение

Структура данных, которая сопоставляет виртуальные адреса с физическими адресами.

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

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

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

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

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

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

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

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

Страничная таблица является массивом элементов таблицы страниц.

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

Каждая запись в таблице страниц (PTE) содержит соответствие между виртуальным адресом страницы и адресом физической рамки. Также существует дополнительная информация о странице, такая как бит присутствия, бит изменения (грязный бит), информация об адресном пространстве или идентификаторе процесса и другие данные. Вторичное хранилище, например жесткий диск, может использоваться для расширения физической памяти. Страницы могут быть подкачиваться в физическую память и на диск. Бит присутствия указывает, какие страницы в данный момент находятся в физической памяти, а какие – на диске, и определяет, как обрабатывать эти разные страницы, то есть, следует ли загружать страницу с диска и выгружать другую страницу из физической памяти. Бит изменения позволяет оптимизировать производительность. Страница на диске, которая подкачивается в физическую память, затем считывается и впоследствии снова выгружается на диск, не требует повторной записи на диск, поскольку страница не была изменена. Однако, если после подкачки страницы в память в нее были внесены изменения, ее бит изменения устанавливается, указывая, что страницу необходимо записать обратно в резервное хранилище. Эта стратегия требует, чтобы резервное хранилище сохраняло копию страницы после ее подкачки в память. Если бит изменения не используется, размер резервного хранилища должен быть равен мгновенному общему размеру всех выгруженных страниц в любой момент времени. При использовании бита изменения в любой момент времени некоторые страницы будут существовать как в физической памяти, так и в резервном хранилище. В операционных системах, не являющихся операционными системами с единым адресным пространством, необходима информация об адресном пространстве или идентификаторе процесса, чтобы система управления виртуальной памятью знала, какие страницы связаны с каким процессом. Два процесса могут использовать два одинаковых виртуальных адреса для разных целей. Таблица страниц должна обеспечивать различные отображения виртуальной памяти для этих двух процессов. Это можно сделать, присвоив двум процессам различные идентификаторы адресного пространства или используя идентификаторы процессов. Связывание идентификаторов процессов с виртуальными страницами памяти также может помочь в выборе страниц для выгрузки, поскольку страницы, связанные с неактивными процессами, особенно с процессами, чьи страницы кода были выгружены, менее вероятно потребуются немедленно, чем страницы, принадлежащие активным процессам. В качестве альтернативы присвоению записям таблицы страниц уникальных идентификаторов процесса, сама таблица страниц может занимать отдельную страницу виртуальной памяти для каждого процесса, так что таблица страниц становится частью контекста процесса. В такой реализации таблицу страниц процесса можно выгрузить, когда процесс больше не находится в памяти.

Each page table entry (PTE) holds the mapping between a virtual address of a page and the address of a physical frame. There is also auxiliary information about the page such as a present bit, a dirty or modified bit, address space or process ID information, amongst others. Secondary storage, such as a hard disk drive, can be used to augment physical memory. Pages can be paged in and out of physical memory and the disk. The present bit can indicate what pages are currently present in physical memory or are on disk, and can indicate how to treat these different pages, i. e. whether to load a page from disk and page another page in physical memory out. The dirty bit allows for a performance optimization. A page on disk that is paged in to physical memory, then read from, and subsequently paged out again does not need to be written back to disk, since the page has not changed. However, if the page was written to after it is paged in, its dirty bit will be set, indicating that the page must be written back to the backing store. This strategy requires that the backing store retain a copy of the page after it is paged in to memory. When a dirty bit is not used, the backing store need only be as large as the instantaneous total size of all paged out pages at any moment. When a dirty bit is used, at all times some pages will exist in both physical memory and the backing store. In operating systems that are not single address space operating systems, address space or process ID information is necessary so the virtual memory management system knows what pages to associate to what process. Two processes may use two identical virtual addresses for different purposes. The page table must supply different virtual memory mappings for the two processes. This can be done by assigning the two processes distinct address map identifiers, or by using process IDs. Associating process IDs with virtual memory pages can also aid in selection of pages to page out, as pages associated with inactive processes, particularly processes whose code pages have been paged out, are less likely to be needed immediately than pages belonging to active processes. As an alternative to tagging page table entries with process unique identifiers, the page table itself may occupy a different virtual memory page for each process so that the page table becomes a part of the process context. In such an implementation, the process's page table can be paged out whenever the process is no longer resident in memory.

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

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

Перевернутые таблицы страниц

Инвертированная таблица страниц (IPT) лучше всего рассматривать как расширение TLB, использующее обычную системную оперативную память. В отличие от настоящей таблицы страниц, она не обязательно может содержать все текущие отображения. Операционная система должна быть готова к обработке промахов, как и в случае с TLB, заполняемой программным обеспечением в стиле MIPS. IPT объединяет таблицу страниц и таблицу фреймов в одну структуру данных. В её основе лежит таблица фиксированного размера, количество строк которой равно количеству фреймов в памяти. Если имеется 4000 фреймов, инвертированная таблица страниц будет содержать 4000 строк. Для каждой строки предусмотрена запись, содержащая номер виртуальной страницы (VPN), номер физической страницы (а не физический адрес), некоторые другие данные и механизм для создания цепочки разрешения коллизий, о котором мы поговорим позже. Поиск по всем записям основной структуры IPT неэффективен, поэтому для сопоставления виртуальных адресов (и информации о пространстве адресов/PID, при необходимости) с индексом в IPT может использоваться хеш-таблица – именно там и применяется цепочка разрешения коллизий. Эта хеш-таблица известна как хеш-анкерная таблица. Хеш-функция обычно не оптимизирована для полноты покрытия, приоритетнее более высокая скорость работы. Разумеется, в хеш-таблицах возникают коллизии. Из-за выбранной хеш-функции в процессе эксплуатации может возникать большое количество коллизий, поэтому для каждой записи в таблице указывается VPN, чтобы проверить, является ли это искомая запись или коллизия. При поиске отображения используется хеш-анкерная таблица. Если запись отсутствует, возникает ошибка страницы. В противном случае запись находится. В зависимости от архитектуры, запись может быть помещена обратно в TLB, и обращение к памяти перезапускается, либо выполняется обход цепочки разрешения коллизий до её исчерпания, после чего возникает ошибка страницы. Виртуальный адрес в данной схеме можно разделить на две части: первая половина – номер виртуальной страницы, вторая половина – смещение внутри этой страницы. Основная проблема данной конструкции – плохая локальность кэша, вызванная хеш-функцией. Конструкции на основе деревьев избегают этой проблемы, размещая записи таблицы страниц для соседних страниц в соседних областях памяти, но инвертированная таблица страниц разрушает пространственную локальность, разбрасывая записи по всей памяти. Операционная система может уменьшить размер хеш-таблицы, чтобы снизить эту проблему, но это приведет к увеличению частоты промахов. Обычно существует одна хеш-таблица, непрерывная в физической памяти и совместно используемая всеми процессами. Идентификатор процесса используется для различения страниц разных процессов. Удаление записей таблицы страниц для данного процесса происходит относительно медленно, поэтому ОС может избегать повторного использования значений идентификаторов процессов, чтобы отложить эту операцию. В качестве альтернативы можно использовать хеш-таблицы для каждого процесса, но они непрактичны из-за фрагментации памяти, требующей предварительного выделения таблиц. Инвертированные таблицы страниц используются, например, в архитектурах PowerPC, UltraSPARC и IA-64.

An inverted page table (IPT) is best thought of as an off chip extension of the TLB which uses normal system RAM. Unlike a true page table, it is not necessarily able to hold all current mappings. The operating system must be prepared to handle misses, just as it would with a MIPS style software filled TLB. The IPT combines a page table and a frame table into one data structure. At its core is a fixed size table with the number of rows equal to the number of frames in memory. If there are 4,000 frames, the inverted page table has 4,000 rows. For each row there is an entry for the virtual page number (VPN), the physical page number (not the physical address), some other data and a means for creating a collision chain, as we will see later. Searching through all entries of the core IPT structure is inefficient, and a hash table may be used to map virtual addresses (and address space/PID information if need be) to an index in the IPT this is where the collision chain is used. This hash table is known as a hash anchor table. The hashing function is not generally optimized for coverage raw speed is more desirable. Of course, hash tables experience collisions. Due to this chosen hashing function, we may experience a lot of collisions in usage, so for each entry in the table the VPN is provided to check if it is the searched entry or a collision. In searching for a mapping, the hash anchor table is used. If no entry exists, a page fault occurs. Otherwise, the entry is found. Depending on the architecture, the entry may be placed in the TLB again and the memory reference is restarted, or the collision chain may be followed until it has been exhausted and a page fault occurs. A virtual address in this schema could be split into two, the first half being a virtual page number and the second half being the offset in that page. A major problem with this design is poor cache locality caused by the hash function. Tree based designs avoid this by placing the page table entries for adjacent pages in adjacent locations, but an inverted page table destroys spatial locality of reference by scattering entries all over. An operating system may minimize the size of the hash table to reduce this problem, with the trade off being an increased miss rate. There is normally one hash table, contiguous in physical memory, shared by all processes. A per process identifier is used to disambiguate the pages of different processes from each other. It is somewhat slow to remove the page table entries of a given process; the OS may avoid reusing per process identifier values to delay facing this. Alternatively, per process hash tables may be used, but they are impractical because of memory fragmentation, which requires the tables to be pre allocated. Inverted page tables are used for example on the PowerPC, the UltraSPARC and the IA 64 architecture.

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

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

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

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

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

Вложенные таблицы страниц могут быть реализованы для повышения производительности аппаратной виртуализации. Обеспечивая аппаратную поддержку виртуализации таблиц страниц, потребность в эмуляции значительно снижается. Для виртуализации x86 текущими решениями являются функция Extended Page Table от Intel и функция Rapid Virtualization Indexing от AMD.