Таблица страниц
Таблица страниц — это структура данных используемая системой виртуальной памяти компьютера , для хранения сопоставлений между виртуальными и физическими адресами . Виртуальные адреса используются программой, выполняемой процессом доступа , тогда как физические адреса используются оборудованием или, точнее, подсистемой оперативной памяти (ОЗУ). Таблица страниц — это ключевой компонент трансляции виртуальных адресов , необходимый для доступа к данным в памяти. Таблица страниц настраивается операционной системой компьютера и может быть прочитана и записана во время процесса трансляции виртуальных адресов блоком управления памятью или низкоуровневым системным программным обеспечением или микропрограммой.
Роль таблицы страниц
[ редактировать ]В операционных системах, использующих виртуальную память, у каждого процесса создается впечатление, что он работает с большими смежными участками памяти. Физически память каждого процесса может быть рассредоточена по разным областям физической памяти или может быть перемещена ( выгружена ) во вторичное хранилище, обычно на жесткий диск (HDD) или твердотельный накопитель (SSD).
Когда процесс запрашивает доступ к данным в своей памяти, операционная система несет ответственность за сопоставление виртуального адреса, предоставленного процессом, с физическим адресом фактической памяти, где хранятся эти данные. В таблице страниц хранятся сопоставления виртуальных адресов с физическими адресами, причем каждое сопоставление также известно как запись таблицы страниц (PTE). [1] [2]
Процесс перевода
[ редактировать ]
Блок управления памятью (MMU) внутри ЦП хранит кэш недавно использованных сопоставлений из таблицы страниц операционной системы. Это называется резервным буфером трансляции (TLB), который представляет собой ассоциативный кеш.
Когда виртуальный адрес необходимо преобразовать в физический адрес, сначала выполняется поиск в TLB. Если совпадение найдено, что называется попаданием TLB , возвращается физический адрес и доступ к памяти может быть продолжен. Однако если совпадения нет, что называется промахом TLB , MMU, системная прошивка или обработчик промаха TLB операционной системы обычно просматривают сопоставление адресов в таблице страниц, чтобы узнать, существует ли сопоставление, что называется прогулка по странице . Если он существует, он записывается обратно в TLB, что необходимо сделать, поскольку оборудование обращается к памяти через TLB в системе виртуальной памяти, и команда, вызвавшая сбой, перезапускается, что также может происходить параллельно. Последующая трансляция приведет к попаданию в TLB, и доступ к памяти продолжится.
Ошибки перевода
[ редактировать ]Поиск в таблице страниц может завершиться неудачно, что приведет к ошибке страницы , по двум причинам:
- Поиск может завершиться неудачно, если для виртуального адреса нет трансляции, а это означает, что виртуальный адрес недействителен. Обычно это происходит из-за ошибки программирования, и операционная система должна предпринять некоторые действия для решения этой проблемы. В современных операционных системах это приведет к ошибки сегментации в программу-нарушитель. отправке сигнала
- Поиск также может завершиться неудачей, если страница в данный момент не находится в физической памяти. Это произойдет, если запрошенная страница была перемещена из физической памяти, чтобы освободить место для другой страницы. В этом случае страница выгружается во вторичное хранилище, расположенное на таком носителе, как жесткий диск (это вторичное хранилище, или «резервное хранилище», часто называется разделом подкачки, если это раздел диска, или файлом подкачки). , файл подкачки или файл подкачки, если это файл). В этом случае страницу необходимо взять с диска и поместить обратно в физическую память. Аналогичный механизм используется для файлов, отображаемых в памяти , которые отображаются в виртуальную память и загружаются в физическую память по требованию.
Когда физическая память не заполнена, это простая операция; страница записывается обратно в физическую память, таблица страниц и TLB обновляются, и инструкция перезапускается. Однако когда физическая память заполнена, одну или несколько страниц физической памяти необходимо выгрузить, чтобы освободить место для запрошенной страницы. Таблицу страниц необходимо обновить, чтобы отметить, что страниц, которые ранее находились в физической памяти, больше нет, и чтобы отметить, что страница, которая была на диске, теперь находится в физической памяти. TLB также необходимо обновить, в том числе удалить из него выгруженную страницу и перезапустить инструкцию. Выбор страницы для выгрузки является предметом алгоритмов замены страниц .
Некоторые MMU вызывают ошибку страницы по другим причинам, независимо от того, находится ли страница в данный момент в физической памяти и отображается в виртуальное адресное пространство процесса:
- Попытка записи, когда в таблице страниц установлен бит только для чтения, приводит к ошибке страницы. Это обычная часть реализации копирования при записи во многих операционных системах ; это также может произойти, когда запись выполняется в место, из которого процессу разрешено чтение, но в которое ему не разрешена запись, и в этом случае процессу доставляется сигнал.
- Попытка выполнить код, когда в таблице страниц установлен бит NX (бит запрета выполнения), вызывает ошибку страницы. Это может использоваться операционной системой в сочетании с битом «только для чтения» для обеспечения функции Write XOR Execute , которая останавливает некоторые виды эксплойтов. [3]
Данные таблицы фреймов
[ редактировать ]Простейшие системы таблиц страниц часто поддерживают таблицу фреймов и таблицу страниц. Таблица кадров содержит информацию о том, какие кадры отображаются. В более продвинутых системах таблица фреймов также может содержать информацию о том, к какому адресному пространству принадлежит страница, статистические данные или другую справочную информацию.
Данные таблицы страниц
[ редактировать ]Таблица страниц представляет собой массив записей таблицы страниц.
Запись таблицы страниц
[ редактировать ]Каждая запись таблицы страниц (PTE) содержит сопоставление между виртуальным адресом страницы и адресом физического кадра. Существует также вспомогательная информация о странице, такая как текущий бит, измененный или измененный бит, адресное пространство или информация идентификатора процесса, среди прочего.
Вторичное хранилище, например жесткий диск, можно использовать для увеличения физической памяти. Страницы можно перемещать по страницам в физическую память и на диск и из них. Бит присутствия может указывать, какие страницы в данный момент присутствуют в физической памяти или на диске, а также может указывать, как обращаться с этими разными страницами, т. е. загружать ли страницу с диска и выгружать другую страницу из физической памяти.
Грязный бит позволяет оптимизировать производительность. Страница на диске, которая выгружается в физическую память, затем считывается и затем снова выгружается, не требует обратной записи на диск, поскольку страница не изменилась. Однако если страница была записана после того, как она была выгружена, ее грязный бит будет установлен, указывая, что страница должна быть записана обратно в резервное хранилище. Эта стратегия требует, чтобы резервное хранилище сохраняло копию страницы после ее выгрузки в память. Когда «грязный бит» не используется, размер резервного хранилища должен соответствовать мгновенному общему размеру всех выгруженных страниц в любой момент. Когда используется «грязный бит», некоторые страницы всегда будут существовать как в физической памяти, так и в резервном хранилище.
В операционных системах, которые не имеют единого адресного пространства , необходима информация об адресном пространстве или идентификаторе процесса, чтобы система управления виртуальной памятью знала, какие страницы с каким процессом связывать. Два процесса могут использовать два одинаковых виртуальных адреса для разных целей. Таблица страниц должна предоставлять разные сопоставления виртуальной памяти для двух процессов. Это можно сделать, назначив двум процессам отдельные идентификаторы карты адресов или используя идентификаторы процессов. Связывание идентификаторов процессов со страницами виртуальной памяти также может помочь в выборе страниц для выгрузки, поскольку страницы, связанные с неактивными процессами, особенно процессы, кодовые страницы которых были выгружены, с меньшей вероятностью потребуются немедленно, чем страницы, принадлежащие активным процессам.
В качестве альтернативы пометке записей таблицы страниц уникальными для процесса идентификаторами сама таблица страниц может занимать разные страницы виртуальной памяти для каждого процесса, так что таблица страниц становится частью контекста процесса. В такой реализации таблица страниц процесса может быть выгружена всякий раз, когда процесс больше не находится в памяти.
Типы таблиц страниц
[ редактировать ]Существует несколько типов таблиц страниц, оптимизированных под разные требования. По сути, простая таблица страниц должна хранить виртуальный адрес, физический адрес, который находится «под» этим виртуальным адресом, и, возможно, некоторую информацию об адресном пространстве.
Инвертированные таблицы страниц
[ редактировать ]Инвертированную таблицу страниц (IPT) лучше всего рассматривать как внешнее расширение TLB , которое использует обычную системную оперативную память. В отличие от настоящей таблицы страниц, она не обязательно способна хранить все текущие сопоставления. Операционная система должна быть готова обрабатывать промахи, как и в случае с программным обеспечением TLB в стиле MIPS.
IPT объединяет таблицу страниц и таблицу кадров в одну структуру данных. По своей сути это таблица фиксированного размера с количеством строк, равным количеству кадров в памяти. Если имеется 4000 кадров, инвертированная таблица страниц будет содержать 4000 строк. Для каждой строки есть запись для номера виртуальной страницы (VPN), номера физической страницы (не физического адреса), некоторых других данных и средств для создания цепочки коллизий , как мы увидим позже.
Поиск по всем записям основной структуры IPT неэффективен, и хэш-таблица может использоваться для сопоставления виртуальных адресов (и адресного пространства/информации PID, если необходимо) с индексом в IPT - именно здесь используется цепочка коллизий. Эта хеш-таблица известна как хэш-таблица привязки . Функция хеширования обычно не оптимизирована для покрытия — более желательна чистая скорость. Конечно, хеш-таблицы сталкиваются с коллизиями. Из-за выбранной функции хеширования мы можем столкнуться с множеством коллизий при использовании, поэтому для каждой записи в таблице предоставляется VPN, чтобы проверить, является ли это искомой записью или коллизией.
При поиске сопоставления используется хэш-таблица привязки. Если запись не существует, возникает ошибка страницы. В противном случае запись будет найдена. В зависимости от архитектуры запись может быть снова помещена в TLB, и ссылка на память перезапускается, или цепочка коллизий может следовать до тех пор, пока она не будет исчерпана и не произойдет страничная ошибка.
Виртуальный адрес в этой схеме можно разделить на две части: первая половина — это номер виртуальной страницы, а вторая половина — смещение на этой странице.
Основная проблема этой конструкции — плохая локальность кэша , вызванная хеш-функцией . Древовидные конструкции позволяют избежать этого, размещая записи таблицы страниц для соседних страниц в соседних местах, но инвертированная таблица страниц разрушает пространственную локальность ссылки , разбрасывая записи повсюду. Чтобы уменьшить эту проблему, операционная система может минимизировать размер хеш-таблицы, но компромиссом будет увеличение частоты ошибок.
Обычно существует одна хеш-таблица, непрерывная в физической памяти, совместно используемая всеми процессами. Идентификатор каждого процесса используется для устранения неоднозначности страниц разных процессов друг от друга. Удаление записей таблицы страниц данного процесса происходит несколько медленно; ОС может избегать повторного использования значений идентификаторов каждого процесса, чтобы отложить решение этой проблемы. В качестве альтернативы можно использовать хеш-таблицы для каждого процесса, но они непрактичны из-за фрагментации памяти , которая требует предварительного выделения таблиц.
Инвертированные таблицы страниц используются, например, в PowerPC , UltraSPARC и архитектуре IA-64 . [4]
Многоуровневые таблицы страниц
[ редактировать ]
В инвертированной таблице страниц хранится список сопоставлений, установленных для всех кадров в физической памяти. Однако это может быть весьма расточительно. Вместо этого мы могли бы создать структуру таблицы страниц, содержащую сопоставления для виртуальных страниц. Это делается путем хранения нескольких таблиц страниц, которые покрывают определенный блок виртуальной памяти. Например, мы можем создать меньшие страницы размером 4 КБ с 1024 элементами, которые покрывают 4 МБ виртуальной памяти.
Это полезно, поскольку часто при запуске процесса используются самые верхние и самые нижние части виртуальной памяти: верхняя часть часто используется для сегментов текста и данных, а нижняя — для стека, со свободной памятью между ними. Многоуровневая таблица страниц может содержать несколько меньших таблиц страниц, чтобы покрывать только верхнюю и нижнюю части памяти, а новые создавать только в случае крайней необходимости.
Теперь каждая из этих меньших таблиц страниц связана вместе главной таблицей страниц, эффективно создавая древовидную структуру данных. Уровней должно быть не только два, но, возможно, и несколько. Например, виртуальный адрес в этой схеме можно разделить на три части: индекс в таблице корневых страниц, индекс в таблице подстраниц и смещение на этой странице.
Многоуровневые таблицы страниц также называются «иерархическими таблицами страниц».
Виртуализированные таблицы страниц
[ редактировать ]Было упомянуто, что создание структуры таблицы страниц, содержащей сопоставления для каждой виртуальной страницы в виртуальном адресном пространстве, может оказаться расточительным. Но мы можем обойти проблему чрезмерного пространства, поместив таблицу страниц в виртуальную память и позволив системе виртуальной памяти управлять памятью для таблицы страниц.
Однако часть этой линейной структуры таблицы страниц должна всегда оставаться в физической памяти, чтобы предотвратить циклические ошибки страниц и искать ключевую часть таблицы страниц, которой нет в таблице страниц.
Вложенные таблицы страниц
[ редактировать ]Вложенные таблицы страниц могут быть реализованы для повышения производительности аппаратной виртуализации . Благодаря аппаратной поддержке виртуализации таблиц страниц необходимость в эмуляции значительно снижается. Для виртуализации x86 в настоящее время используются Intel функция расширенной таблицы страниц и AMD виртуализации функция быстрого индексирования .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Виртуальная память» . umd.edu . Проверено 28 сентября 2015 г.
- ^ «Управление таблицей страниц» . ядро.орг . Проверено 28 сентября 2015 г.
- ^ "W^X - Механизм" .
- ^ Уильям Столлингс, Внутреннее устройство операционных систем и принципы проектирования , стр. 353.
Дальнейшее чтение
[ редактировать ]- Эндрю С. Таненбаум , Современные операционные системы , ISBN 0-13-031358-0
- А. Зильбершац , П. Б. Галвин, Г. Ганье, Концепции операционной системы , ISBN 0-471-69466-5
- Операционные системы: три простых части , Ремзи Х. Арпачи-Дюссо и Андреа К. Арпачи-Дюссо. Arpaci-Dusseau Books, 2014. Соответствующие главы: Адресные пространства. Трансляция адресов. Введение в пейджинговые TLB. Расширенные таблицы страниц.
- Учебное пособие по виртуальной памяти CNE, Центр новых инженеров Университета Джорджа Мейсона, Таблицы страниц
- «Искусство ассемблера, 6.6. Виртуальная память, защита и подкачка» . Архивировано из оригинала 18 февраля 2012 года.
- «Руководства для разработчиков программного обеспечения для архитектур Intel 64 и IA-32» . Интел. 18 января 2018 г.
- «Руководство разработчика программного обеспечения для архитектуры AMD64» . АМД. Архивировано из оригинала 13 марта 2010 г.
Внешние ссылки
[ редактировать ]
| Базы данных органов управления : Национальные |
|---|
