Intel x86 Assembly Language & Microarchitecture
Пейджинг - виртуальная адресация и память

Вступление

история

Первые компьютеры

Ранние компьютеры имели блок памяти, в который программист помещал код и данные, а ЦП выполнялся в этой среде. Учитывая, что компьютеры тогда были очень дорогими, было жаль, что он выполнит одно задание, остановится и дождитесь загрузки следующей работы в него, а затем обработает его.

Многопользовательская многопроцессорная обработка

Таким образом, компьютеры быстро стали более сложными и одновременно поддерживали несколько пользователей и / или программ, но при этом возникли проблемы с простой идеей «один блок памяти». Если компьютер одновременно запускал две программы или запускал одну и ту же программу для нескольких пользователей - конечно, для каждого пользователя требовались отдельные данные - тогда управление этой памятью стало критическим.

пример

Например: если программа была написана для работы с адресом памяти 1000, но там была загружена другая программа, тогда новая программа не может быть загружена. Одним из способов решения этой проблемы было бы заставить программы работать с «относительной адресацией» - неважно, где была загружена программа, она просто сделала все относительно адреса памяти, в который она была загружена. Но для этого требовалась аппаратная поддержка.

утонченность

По мере усложнения компьютерного оборудования он смог поддерживать более крупные блоки памяти, что позволяло использовать более одновременные программы, и стало сложнее писать программы, которые не мешали тому, что уже было загружено. Одна обратная ссылка на память может снизить не только текущую программу, но и любую другую программу в памяти, включая операционную систему!

Решения

Нужен был механизм, который позволял блокам памяти иметь динамические адреса. Таким образом, программа может быть написана для работы со своими блоками памяти на адресах, которые она распознала, и не сможет получить доступ к другим блокам для других программ (если только это не позволило кому-то сотрудничать).

сегментация

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

Проблемы

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

Paging

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

Виртуальная адресация

Разделив память на эти блоки, они могут быть отнесены к различным программам по мере необходимости с любым адресом, в котором она нуждалась. Это «сопоставление» между физическим адресом памяти и желаемым адресом программы является очень мощным и является основой для управления памятью каждого основного процессора (Intel, ARM, MIPS, Power et al.).

Поддержка оборудования и ОС

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

Функции пейджинга

Как только аппаратное обеспечение может сделать это переназначение, что это позволило? Основным драйвером была многопроцессорность - возможность запускать несколько программ, каждая со своей «собственной» памятью, защищенных друг от друга. Но два других варианта включали «разреженные данные» и «виртуальную память».

многопроцессорная обработка

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

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

Редкие данные

Разрешение огромного виртуального адресного пространства (4 ГБ типично, чтобы соответствовать 32-разрядным регистрам, которые обычно имели эти процессоры) само по себе не является ненужной памятью, если большие области этого адресного пространства остаются без изменений. Это позволяет создавать огромные структуры данных, где только определенные части отображаются в любой момент времени. Представьте себе 3-мерный массив из 1000 байт в каждом направлении: это обычно занимает миллиард байт! Но программа может зарезервировать блок своего виртуального адресного пространства для «удержания» этих данных, но только отображать небольшие разделы по мере их заполнения. Это позволяет эффективно программировать, не теряя память для данных, которые еще не нужны.

Виртуальная память

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

Он работает следующим образом:

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

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

• Если программа обращается к немаркированной ячейке памяти, аппаратное обеспечение уведомляет ОС по-прежнему. На этот раз ОС отмечает, что это была не Страница, которая была сохранена, поэтому распознает ее как ошибку в программе и завершает ее!

  На самом деле это происходит, когда ваше приложение загадочно исчезает на вас - возможно, с MessageBox от ОС. Это также то, что (часто) приводит к печально известному Blue Screen или Sad Mac - багги-программа была фактически драйвером ОС, который получал доступ к памяти, которой он не должен!

Пейджинговые решения

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

Насколько велика должна быть страница?

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

+-----------------+------------+
| Page index      | Byte index |
+-----------------+------------+

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

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

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+

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

Как оптимизировать использование таблиц страниц?

Каждый адресный доступ, который будет делать ЦП, должен быть сопоставлен - процесс виртуальный-физический должен быть настолько эффективным, насколько это возможно. Если трехуровневая система, описанная выше, должна быть реализована, это будет означать, что каждый доступ к памяти фактически будет иметь три доступа: один в каталог; один в таблицу страниц; а затем, наконец, желаемые данные. И если ЦП также должен был выполнять домашнее хозяйство, например, указав, что эта страница была обращена к ней или была записана, тогда для этого потребуется еще больше доступа для обновления полей.

Память может быть быстрой, но это приведет к тройному замедлению всех обращений к памяти во время пейджинга! К счастью, большинство программ имеют «локальность масштаба» - то есть, если они обращаются к одному месту в памяти, тогда будущие обращения, вероятно, будут рядом. И поскольку страницы не слишком малы, преобразование отображения необходимо будет выполнять только при обращении к новой странице: не для абсолютно каждого доступа.

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

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

80386 Пейджинг

Дизайн высокого уровня

80386 - это 32-разрядный процессор с 32-разрядным адресным пространством памяти. Дизайнеры подсистемы пейджинга отметили, что дизайн страницы 4 КБ сопоставлен с этими 32 битами довольно аккуратным способом - 10 бит, 10 бит и 12 бит:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+
 3         2 2          1 1          0  Bit
 1         2 1          2 1          0  number

Это означало, что индекс байта был 12 бит в ширину, который бы индексировался на страницу 4K. Индексы Directory и страницы составляли 10 бит, каждая из которых была бы отображена в таблицу с 1024 байтами, и если эти записи в таблице составляли 4 байта, это было бы 4 КБ за таблицу: также страница!

Вот что они сделали:

• Каждая программа будет иметь свой собственный каталог, страницу с 1024 страницами, каждая из которых определяет, где следующая таблица страниц уровня - если она есть.
• Если бы это было так, то на этой странице Таблица было бы 1024 Записи страниц, каждая из которых определяла бы, где была страница последнего уровня, - если таковая была.
• Если бы это было так, то эта страница могла бы непосредственно считывать свой байт.

Вступление страницы

Оба каталога верхнего уровня и таблица страниц следующего уровня содержат 1024 записи страниц. Наиболее важной частью этих записей является адрес того, что он индексирует: Таблица страниц или фактическая страница. Обратите внимание, что для этого адреса не нужны полные 32 бита - поскольку все является страницей, важны только 20 лучших битов. Таким образом, остальные 12 бит в записи страницы могут использоваться для других вещей: присутствует ли следующий уровень; ведение домашнего хозяйства в отношении того, была ли страница доступна или написана; и даже нужно ли писать даже!

+--------------+----+------+-----+---+---+
| Page Address | OS | Used | Sup | W | P |
+--------------+----+------+-----+---+---+
Page Address = Top 20 bits of Page Table or Page address
OS           = Available for OS use
Used         = Whether this page has been accessed or written to
Sup          = Whether this page is Supervisory - only accessible by the OS
W            = Whether this page is allowed to be Written
P            = Whether this page is even Present

Обратите внимание, что если бит P равен 0, остальная часть записи имеет право иметь все, что ОС хочет разместить там - например, где содержимое страницы должно находиться на жестком диске!

Базовый регистр PDBR ( PDBR )

Если каждая программа имеет свой собственный каталог, как аппаратное обеспечение знает, с чего начать картографирование? Поскольку процессор работает только по одной программе за раз, он имеет один регистр управления для хранения адреса каталога текущей программы. Это регистр базы данных страниц ( CR3 ). По мере PDBR ОС между различными программами он обновляет PDBR с помощью соответствующего каталога страниц для программы.

Ошибки страницы

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

1. Индексируйте верхние 10 бит адреса на страницу, указанную PDBR чтобы получить адрес соответствующей таблицы страниц;
2. Индексируйте следующие 10 бит адреса на страницу, указанную Каталогом, чтобы получить адрес соответствующей страницы;
3. Индекс последних 12 бит адреса, чтобы получить данные из этой страницы.

Поскольку в обоих шагах 1 и 2. выше используются записи страниц, каждая запись может указывать на проблему:

• Следующий уровень может быть отмечен «Not Present»;
• Следующий уровень может быть отмечен как «Только для чтения» - и операция - запись;
• Следующий уровень может быть отмечен как «Супервизор» - и это программа, обращающаяся к памяти, а не к ОС.

Когда такая проблема отмечена аппаратным обеспечением, вместо завершения доступа возникает ошибка Fault: Прерывание # 14, ошибка страницы. Он также заполняет некоторые конкретные контрольные регистры информацией о том, почему произошел сбой: адрес, на который делается ссылка; будь то доступ к супервизору; и была ли это попыткой записи.

Ожидается, что ОС поймает этот Fault, расшифрует контрольные регистры и решит, что делать. Если это недопустимый доступ, он может завершить программу сбоя. Если это доступ к виртуальной памяти, ОС должна выделить новую страницу (которой может понадобиться освободить страницу, которая уже используется!), Заполнить ее необходимым содержимым (либо все нули, либо предыдущее содержимое, загруженное с диска ), сопоставьте новую страницу в соответствующей Таблице страниц, пометьте ее как присутствующую, затем возобновите инструкцию по сбою. На этот раз доступ будет успешно развиваться, и программа не будет знать, что что-то особенное произошло (если только не взглянуть на часы!)

80486 Пейджинг

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

Во всех других отношениях применим пример «80386 Пейджинг».

Пейджинг Pentium

Когда разрабатывался Pentium, размеры памяти и программы, которые запускались в них, становились все больше. ОС должна была все больше и больше работать, чтобы поддерживать подсистему подкачки только в большом количестве индексов страниц, которые необходимо было обновить, когда использовались большие программы или наборы данных.

Поэтому дизайнеры Pentium добавили простой трюк: они добавили дополнительный бит в записи каталога страниц, указав, был ли следующий уровень таблицей страниц (как и раньше) - или перешел непосредственно на страницу 4 МБ! Имея концепцию 4 МБ страниц, ОС не нужно было бы создавать таблицу страниц и заполнять ее 1024 байта, которые в основном индексировали адреса на 4 К выше предыдущего.

Макет адреса

+-----------+----------------------+
| Dir Index | 4MB Byte Index       |
+-----------+----------------------+
 3         2 2                    0   Bit
 1         2 1                    0   number

Схема размещения каталога

+-----------+----+---+------+-----+---+---+
| Page Addr | OS | S | Used | Sup | W | P |
+-----------+----+---+------+-----+---+---+
Page Addr = Top 20 bits of Page Table or Page address
OS        = Available for OS use
S         = Size of Next Level: 0 = Page Table, 1 = 4 MB Page
Used      = Whether this page has been accessed or written to
Sup       = Whether this page is Supervisory - onlly accessible by the OS
W         = Whether this page is allowed to be Written
P         = Whether this page is even Present

Конечно, это имело некоторые последствия:

• Страница 4 МБ должна была начинаться с границы адреса 4 МБ, так же как 4K-страницы должны были начинаться с границы адреса 4K.
• Все 4 МБ должны принадлежать одной программе - или быть разделены несколькими.

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

Расширение физического адреса (PAE)

Вступление

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

Больше ОЗУ

Необходима была возможность доступа к большей физической памяти - но это была уже 32-разрядная адресная шина, поэтому для любого увеличения потребовались бы более крупные регистры адресов. Или это? При разработке Pentium Pro (и даже Pentium M) в качестве стоп-кадра до 64-битных процессоров можно было бы добавить больше физических битов адреса (позволяющих больше физической памяти) без изменения количества бит регистра. Это может быть достигнуто, так как виртуальные адреса были сопоставлены с физическими адресами в любом случае - все, что необходимо было изменить, было системой сопоставления.

дизайн

Существующая система может получить доступ к 32 битам физических адресов. Для этого потребовалось полное изменение структуры страницы, от 32 до 64 бит. Было решено сохранить минимальную детализацию на страницах 4K, поэтому в 64-битной записи будет 52 бита адреса и 12 бит элемента управления (например, предыдущая запись имела 20 бит адреса и 12 бит элемента управления).

Наличие 64-битной записи, но размер страницы (все еще) 4K означал, что вместо прежних 1024 будет только 512 записей на таблицу страниц или каталог. Это означало, что 32-битный виртуальный адрес будет разделен по-разному, чем раньше:

+-----+-----------+------------+------------+
| DPI | Dir Index | Page Index | Byte Index |
+-----+-----------+------------+------------+
 3   3 2         2 2          1 1          0   Bit
 1   0 9         1 0          2 1          0   number

 DPI        = 2-bit index into Directory Pointer Table
 Dir Index  = 9-bit index into Directory
 Page Index = 9-bit index into Page Table
 Byte Index = 12-bit index into Page (as before)

Измельчение одного бита из индекса каталога и индекса страницы дало два бита для третьего уровня сопоставления: они назвали эту таблицу указателей страниц (PDPT) таблицей ровно четырьмя 64-битными Записями, которые адресовали четыре Каталога, а не предыдущие один. PDBR ( CR3 ) теперь указал на PDPT вместо этого, который, поскольку CR3 был всего 32 бита, необходимо было сохранить в первых 4 ГБ ОЗУ для обеспечения доступности. Обратите внимание, что поскольку младшие бит CR3 используются для Control, PDPT должен начинаться с 32-байтной границы.

Расширение размера страницы (PSE)

И, поскольку предыдущие страницы 4 МБ были такой хорошей идеей, они хотели снова поддерживать крупные страницы. На этот раз, хотя удаление последнего слоя системы уровня не создало 10 + 12 бит 4 МБ страниц, но вместо 9 + 12 бит 2 МБ страниц.

PSE-32 (и PSE-40)

Поскольку режим Physical Address Extension (PAE), который был представлен в Pentium Pro (и Pentum M), был таким изменением в подсистеме управления памятью операционной системы, когда Intel разработала Pentium II, они решили повысить «нормальный» режим страницы до поддерживать новые бит физического адреса процессора в ранее определенных 32-битных Записях.

Они поняли, что, когда использовалась страница 4 МБ, запись в каталоге выглядела так:

+-----------+------------+---------+
| Dir Index |  Unused    | Control |
+-----------+------------+---------+

Индексы Dir Index и Control в Entry были одинаковыми, но блок неиспользуемых битов между ними, который будет использоваться индексом страницы, если он существовал, был потрачен впустую. Поэтому они решили использовать эту область для определения верхних битов физического адреса выше 31 !

+-----------+------+-----+---------+
| Dir Index |Unused|Upper| Control |
+-----------+------+-----+---------+

Это позволило RAM свыше 4 ГБ быть доступным для ОС, которые не применяли режим PAE - с небольшой дополнительной логикой они могли бы обеспечить большое количество дополнительной ОЗУ для системы, хотя и не превышало нормальную 4 ГБ для каждой программы. Сначала было добавлено только 4 бита, что обеспечило 36-битную физическую адресацию, поэтому этот режим назывался расширением размера страницы 36 (PSE-36). На самом деле это не изменило размер страницы, но только Адресация.

Ограничением этого было то, что только 4 МБ страниц выше 4 ГБ были определены - 4 тыс. Страниц не разрешалось. Принятие этого режима было невеликим - он, как сообщается, был медленнее, чем использование PAE, и Linux в конечном итоге не использовал его.

Тем не менее, в более поздних процессорах, у которых было еще больше бит физического адреса, как AMD, так и Intel расширили область PSE до 8 бит, что некоторые люди называли «PSE-40»,