Как работает пейджинг на x86?

Question

Этот вопрос призван заполнить вакуум хорошей бесплатной информацией по этому вопросу.

Я считаю, что хороший ответ будет соответствовать одному большому SO-ответу или, по крайней мере, нескольким ответам.

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

Предлагаемые рекомендации:

• ответы должны быть новичками:
  • конкретные, но, возможно, упрощенные примеры очень важны
  • приложения представленных концепций приветствуются
• цитирование полезных ресурсов - это хорошо
• небольшие отступления в том, как ОС используют функции подкачки
• PAE и PSE объяснения приветствуются
• небольшие отступления в x86_64 приветствуются

Связанные вопросы и почему я думаю, что они не обманщики:

• Как работают таблицы страниц x86?: название почти такое же, как этот вопрос, но основная часть задает конкретные вопросы, связанные с cr3 и TLB. Этот вопрос является подмножеством этого.

• Как работает виртуализация x86: тело запрашивает только источники.

Answer 1

Версия этого ответа с хорошим содержанием и большим содержанием.

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

Образец кода

Минимальный пример: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Как и все остальное в программировании, единственный способ действительно понять это - играть с минимальным количеством примеров.

То, что делает это "трудным" предметом, состоит в том, что минимальный пример велик, потому что вам нужно сделать свою собственную маленькую ОС.

Руководство Intel

Хотя понять это невозможно без примеров, постарайтесь как можно скорее ознакомиться с руководствами.

Intel описывает пейджинг в Руководстве по системному программированию Intel Том 3 - 325384-056RU Сентябрь 2015 Глава 4 "Пейджинг".

Особенно интересным является рисунок 4-4 "Форматы записей CR3 и записей пейджинговой структуры с 32-битным пейджингом", на котором представлены ключевые структуры данных.

MMU

Пейджинг осуществляется частью блока управления памятью (MMU) ЦПУ. Как и многие другие (например, сопроцессор x87, APIC), раньше он был отдельным чипом, который впоследствии был интегрирован в процессор. Но термин все еще используется.

Главные факты

Логические адреса - это адреса памяти, используемые в "обычном" коде земли пользователя (например, содержимое rsi в mov eax, [rsi]).

Сначала сегментация переводит их в линейные адреса, а затем пейджинг затем переводит линейные адреса в физические адреса.

(logical) ------------------> (linear) ------------> (physical)
             segmentation                 paging

Большую часть времени мы можем думать о физических адресах как об индексе фактических аппаратных ячеек оперативной памяти, но это не на 100% верно из-за:

• области ввода-вывода с отображением в память
• многоканальная память

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

Пейджинг против сегментации

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

• подкачка разделяет оперативную память на куски одинакового размера, называемые страницами
• Сегментация разбивает память на куски произвольных размеров

Это главное преимущество подкачки, поскольку куски одинакового размера делают вещи более управляемыми.

Пейджинг стал настолько популярным, что поддержка сегментации была прекращена в x86-64 в 64-битном режиме, основном режиме работы для нового программного обеспечения, где он существует только в режиме совместимости, который эмулирует IA32.

заявка

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

• обе программы не должны ничего знать о других
• память обеих программ может увеличиваться и уменьшаться по мере необходимости
• переключение между программами происходит очень быстро
• одна программа никогда не сможет получить доступ к памяти другого процесса

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

Аппаратная реализация

Подобно сегментации в защищенном режиме (когда изменение регистра сегмента запускает загрузку из GDT или LDT), аппаратные средства разбиения на страницы используют структуры данных в памяти для выполнения своей работы (таблицы страниц, каталоги страниц и т. Д.).

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

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

Пример: упрощенная одноуровневая схема подкачки

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

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

ОС может дать им следующие таблицы страниц:

Таблица страниц, предоставленная процессу 1 ОС:

RAM location        physical address   present
-----------------   -----------------  --------
PT1 + 0       * L   0x00001            1
PT1 + 1       * L   0x00000            1
PT1 + 2       * L   0x00003            1
PT1 + 3       * L                      0
...                                    ...
PT1 + 0xFFFFF * L   0x00005            1

Таблица страниц, предоставленная процессу 2 ОС:

RAM location       physical address   present
-----------------  -----------------  --------
PT2 + 0       * L  0x0000A            1
PT2 + 1       * L  0x0000B            1
PT2 + 2       * L                     0
PT2 + 3       * L  0x00003            1
...                ...                ...
PT2 + 0xFFFFF * L  0x00004            1

Куда:

• PT1 а также PT2: начальная позиция таблиц 1 и 2 в оперативной памяти.

  Примерные значения: 0x00000000, 0x12345678, так далее.

  Именно ОС определяет эти значения.

• L: длина записи таблицы страниц.

• present: указывает, что страница присутствует в памяти.

Таблицы страниц расположены в оперативной памяти. Например, они могут быть расположены как:

--------------> 0xFFFFFFFF


--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1


--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2

--------------> 0x0

Начальные расположения в ОЗУ для обеих таблиц страниц являются произвольными и контролируются ОС. Это зависит от ОС, чтобы они не перекрывались!

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

Страница представляет собой фрагмент размером 4 КБ (12 бит), и поскольку адреса имеют 32 бита, для идентификации каждой страницы требуется только 20 бит (20 + 12 = 32, то есть 5 символов в шестнадцатеричном формате). Это значение фиксируется оборудованием.

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

Таблица страниц - это... таблица записей таблицы страниц!

Точный формат записей таблицы устанавливается аппаратно.

В этом упрощенном примере записи таблицы страниц содержат только два поля:

bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag

поэтому в этом примере конструкторы оборудования могли выбрать L = 21,

Большинство реальных записей таблицы страниц имеют другие поля.

Было бы нецелесообразно выравнивать объекты на 21 байте, поскольку память адресуется байтами, а не битами. Следовательно, даже в этом случае требуется всего 21 бит, разработчики оборудования, вероятно, выберут L = 32 чтобы сделать доступ быстрее, и просто зарезервировать биты оставшиеся биты для последующего использования. Фактическое значение для L на x86 стоит 32 бита.

Трансляция адресов в одноуровневой схеме

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

Когда ОС хочет активировать процесс 1, она устанавливает cr3 в PT1Начало таблицы для процесса один.

Если процесс 1 хочет получить доступ к линейному адресу 0x00000001аппаратная схема пейджинга автоматически выполняет следующие действия для ОС:

• разделить линейный адрес на две части:

  | page (20 bits) | offset (12 bits) |
  

  Так что в этом случае мы бы имели:

  • страница = 0x00000
  • смещение = 0x001

• загляните в таблицу страниц 1, потому что cr3 указывает на это.

• смотреть запись 0x00000 потому что это часть страницы.

  Аппаратное обеспечение знает, что эта запись находится по адресу RAM PT1 + 0 * L = PT1,

• поскольку он присутствует, доступ действителен

• по таблице страниц, расположение номера страницы 0x00000 я сидела 0x00001 * 4K = 0x00001000,

• чтобы найти конечный физический адрес, нам просто нужно добавить смещение:

    00001 000
  + 00000 001
    -----------
    00001 001
  

  так как 00001 это физический адрес страницы, которая была найдена на столе и 001 это смещение.

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

• аппаратное обеспечение затем получает память в этом физическом месте.

Таким же образом, следующие процессы будут происходить для процесса 1:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00002 000  00002 000
FFFFF 000  00005 000

Например, при доступе к адресу 00001000часть страницы 00001 оборудование знает, что его запись в таблице страниц находится по адресу RAM: PT1 + 1 * L (1 из-за части страницы), и именно там он будет искать его.

Когда ОС хочет переключиться на процесс 2, все, что ей нужно сделать, это сделать cr3 укажите на страницу 2. Это так просто!

Теперь для процесса 2 произойдут следующие переводы:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00003 000  00003 000
FFFFF 000  00004 000

Один и тот же линейный адрес преобразуется в разные физические адреса для разных процессов, в зависимости только от значения внутри cr3,

Таким образом, каждая программа может ожидать, что ее данные начнутся с 0 и заканчивается в FFFFFFFF, не беспокоясь о точных физических адресах.

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

Что если процесс 1 попытается получить доступ к адресу на странице, которого нет?

Аппаратное обеспечение уведомляет программное обеспечение через исключение ошибки страницы.

Затем обычно ОС должна зарегистрировать обработчик исключений, чтобы решить, что должно быть сделано.

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

int is[1];
is[2] = 1;

но могут быть случаи, когда это приемлемо, например в Linux, когда:

• программа хочет увеличить свой стек.

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

• страница была перенесена на диск.

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

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

  В Linux, например, когда присутствует = 0:

  • если все поля записи таблицы страниц равны 0, неверный адрес.

  • иначе, страница была перенесена на диск, и фактические значения этих полей кодируют положение страницы на диске.

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

Упрощения

Упрощения к реальности, которые облегчают понимание этого примера:

• все реальные пейджинговые схемы используют многоуровневый пейджинг для экономии места, но это показало простую одноуровневую схему.

• Таблицы страниц содержали только два поля: 20-битный адрес и 1-битный флаг присутствия.

  Реальные таблицы страниц содержат в общей сложности 12 полей и, следовательно, другие функции, которые были опущены.

Пример: многоуровневая пейджинговая схема

Проблема с одноуровневой схемой подкачки состоит в том, что она будет занимать слишком много оперативной памяти: 4G / 4K = 1M записей на процесс. Если каждая запись имеет длину 4 байта, это составит 4 МБ на процесс, что слишком много даже для настольного компьютера: ps -A | wc -l говорит, что я сейчас запускаю 244 процесса, так что это займет около 1 ГБ моей оперативной памяти!

По этой причине разработчики x86 решили использовать многоуровневую схему, которая уменьшает использование оперативной памяти.

Недостатком этой системы является то, что она имеет немного большее время доступа.

В простой трехуровневой схеме подкачки, используемой для 32-разрядных процессоров без PAE, 32 адресных бита разделены следующим образом:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Каждый процесс должен иметь один и только один каталог страниц, связанный с ним, поэтому он будет содержать как минимум 2^10 = 1K записи каталога страниц, намного лучше, чем минимум 1M, требуемый для одноуровневой схемы.

Таблицы страниц распределяются только по мере необходимости ОС. Каждая таблица страниц имеет 2^10 = 1K записи каталога страниц

Каталоги страниц содержат... записи каталога страниц! Записи каталога страниц такие же, как записи таблицы страниц, за исключением того, что они указывают на адреса ОЗУ таблиц страниц, а не на физические адреса таблиц. Поскольку эти адреса имеют ширину всего 20 бит, таблицы страниц должны быть в начале страниц размером 4 КБ.

cr3 теперь указывает на расположение в оперативной памяти каталога страниц текущего процесса вместо таблиц страниц.

Записи в таблицах страниц вообще не меняются по одноуровневой схеме.

Таблицы страниц изменяются от одноуровневой схемы, потому что:

• каждый процесс может иметь до 1 КБ таблиц страниц, по одной на каждую запись каталога страниц.
• Каждая таблица страниц содержит ровно 1 КБ записей вместо 1 МБ.

Причина использования 10 битов на первых двух уровнях (а не, скажем, 12 | 8 | 12) состоит в том, что каждая запись таблицы страниц имеет длину 4 байта. Тогда 2^10 записей каталогов страниц и таблиц страниц будут хорошо вписываться в страницы размером 4 КБ. Это означает, что для этой цели быстрее и проще выделять и освобождать страницы.

Трансляция адресов в многоуровневой схеме

Каталог страницы, данный процессу 1 ОС:

RAM location     physical address   present
---------------  -----------------  --------
PD1 + 0     * L  0x10000            1
PD1 + 1     * L                     0
PD1 + 2     * L  0x80000            1
PD1 + 3     * L                     0
...                                 ...
PD1 + 0x3FF * L                     0

Таблицы страниц, переданные процессу 1 ОС по адресу PT1 = 0x10000000 (0x10000 * 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT1 + 0     * L   0x00001            1
PT1 + 1     * L                      0
PT1 + 2     * L   0x0000D            1
...                                  ...
PT1 + 0x3FF * L   0x00005            1

Таблицы страниц, переданные процессу 1 ОС по адресу PT2 = 0x80000000 (0x80000 * 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT2 + 0     * L   0x0000A            1
PT2 + 1     * L   0x0000C            1
PT2 + 2     * L                      0
...                                  ...
PT2 + 0x3FF * L   0x00003            1

где:

• PD1: начальная позиция каталога страниц процесса 1 в оперативной памяти.
• PT1 а также PT2: начальная позиция таблицы страниц 1 и таблицы страниц 2 для процесса 1 в оперативной памяти.

Таким образом, в этом примере каталог страницы и таблица страниц могут храниться в ОЗУ примерно так:

----------------> 0xFFFFFFFF


----------------> PT2 + 0x3FF * L
Page Table 1
----------------> PT2

----------------> PD1 + 0x3FF * L
Page Directory 1
----------------> PD1


----------------> PT1 + 0x3FF * L
Page Table 2
----------------> PT1

----------------> 0x0

Переведем линейный адрес 0x00801004 шаг за шагом.

Мы предполагаем, что cr3 = PD1то есть он указывает на каталог страниц, только что описанный.

В двоичном коде линейный адрес:

0    0    8    0    1    0    0    4
0000 0000 1000 0000 0001 0000 0000 0100

Группировка как 10 | 10 | 12 дает:

0000000010 0000000001 000000000100
0x2        0x1        0x4

который дает:

• запись каталога страницы = 0x2
• запись таблицы страниц = 0x1
• смещение = 0x4

Таким образом, аппаратное обеспечение ищет запись 2 каталога страницы.

Таблица каталога страниц говорит, что таблица страниц расположена в 0x80000 * 4K = 0x80000000, Это первый доступ к ОЗУ процесса.

Поскольку запись таблицы страниц 0x1аппаратное обеспечение смотрит на запись 1 таблицы страниц в 0x80000000, что говорит о том, что физическая страница находится по адресу 0x0000C * 4K = 0x0000C000, Это второй доступ к ОЗУ процесса.

Наконец, пейджинговое оборудование добавляет смещение, и конечный адрес 0x0000C004,

Другие примеры переведенных адресов:

linear    10 10 12 split   physical
--------  ---------------  ----------
00000001  000 000 001      00001001
00001001  000 001 001      page fault
003FF001  000 3FF 001      00005001
00400000  001 000 000      page fault
00800001  002 000 001      0000A001
00801008  002 001 008      0000C008
00802008  002 002 008      page fault
00B00001  003 000 000      page fault

Сбои страниц возникают, если отсутствует запись каталога страниц или запись таблицы страниц.

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

64-битные архитектуры

64-битный - это все еще слишком большой адрес для текущих размеров оперативной памяти, поэтому большинство архитектур будет использовать меньше битов.

x86_64 использует 48 бит (256 TiB), а PAE в старом режиме уже позволяет 52-битные адреса (4 PiB).

12 из этих 48 битов уже зарезервированы для смещения, которое оставляет 36 битов.

Если используется двухуровневый подход, лучшим разделением будут два 18-битных уровня.

Но это будет означать, что каталог страницы будет иметь 2^18 = 256K записей, которые занимали бы слишком много ОЗУ: близко к одноуровневой подкачке для 32-битных архитектур!

Следовательно, 64-битные архитектуры создают еще больше уровней страниц, обычно 3 или 4.

x86_64 использует 4 уровня в 9 | 9 | 9 | 12 схема, так что верхний уровень занимает только 2^9 записи более высокого уровня.

PAE

Расширение физического адреса.

С 32 битами можно адресовать только 4 ГБ ОЗУ.

Это стало ограничением для больших серверов, поэтому Intel представила механизм PAE для Pentium Pro.

Чтобы решить эту проблему, Intel добавила 4 новые адресные строки, чтобы можно было адресовать 64 ГБ.

Структура таблицы страниц также изменяется, если включен PAE. Точный способ его изменения зависит от того, включен или выключен PSE.

PAE включается и выключается через PAE немного cr4,

Даже если общая адресуемая память составляет 64 ГБ, отдельные процессы могут использовать только до 4 ГБ. Однако ОС может размещать разные процессы на разных блоках по 4 ГБ.

PSE

Расширение размера страницы.

Позволяет страницам иметь длину 4M (или 2M, если включена PAE) вместо 4K.

PSE включается и выключается через PAE немного cr4,

PAE и PSE схемы таблиц страниц

Если активны либо PAE, либо PSE, используются разные схемы уровня пейджинга:

• нет PAE и нет PSE: 10 | 10 | 12

• нет PAE и PSE: 10 | 22,

  22 - это смещение на странице 4Mb, так как 22-битный адрес 4Mb.

• PAE и нет PSE: 2 | 9 | 9 | 12

  Причина дизайна, почему 9 используется дважды вместо 10, состоит в том, что теперь записи больше не могут помещаться в 32 бита, которые были заполнены 20 адресными битами и 12 значащими или зарезервированными битами флага.

  Причина в том, что 20 бит больше не достаточно для представления адреса таблиц страниц: теперь необходимо 24 бита из-за 4 дополнительных проводов, добавленных к процессору.

  Поэтому дизайнеры решили увеличить размер записи до 64 бит, и, чтобы они поместились в одну таблицу страниц, необходимо уменьшить количество записей до 2^9 вместо 2^10.

  Начало 2 - это новый уровень страницы, называемый таблицей указателей страниц (PDPT), поскольку он указывает на каталоги страниц и заполняет 32-битный линейный адрес. PDPT также имеют ширину 64 бита.

  cr3 Теперь указывает на PDPT, которые должны быть на первых четырех 4 ГБ памяти и выровнены по 32-битным кратным для эффективности адресации. Это означает, что сейчас cr3 имеет 27 значащих бит вместо 20: 2^5 для 32 кратных * 2^27 для завершения 2^32 из первых 4 ГБ.

• PAE и PSE: 2 | 9 | 21

  Дизайнеры решили оставить поле шириной 9 бит, чтобы оно поместилось на одной странице.

  Это оставляет 23 бита. Оставляя 2 для PDPT, чтобы сохранить единообразие в случае PAE без PSE, оставляется 21 для смещения, что означает, что страницы имеют ширину 2M ​​вместо 4M.

TLB

Буфер преобразования перевода (TLB) - это кэш для адресов подкачки.

Поскольку это кеш, он разделяет многие проблемы проектирования кеша процессора, такие как уровень ассоциативности.

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

Основная операция

После преобразования между линейным и физическим адресом он сохраняется в TLB. Например, TLB с 4 записями начинается в следующем состоянии:

  valid   linear   physical
  ------  -------  ---------
> 0       00000    00000
  0       00000    00000
  0       00000    00000
  0       00000    00000

> указывает текущую запись, подлежащую замене.

и после страницы линейный адрес 00003 переводится на физический адрес 00005TLB становится:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
> 0       00000    00000
  0       00000    00000
  0       00000    00000

и после второго перевода 00007 в 00009 это становится:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
  1       00007    00009
> 0       00000    00000
  0       00000    00000

Сейчас если 00003 необходимо снова перевести, аппаратное обеспечение сначала ищет TLB и выясняет его адрес с одним доступом к ОЗУ 00003 --> 00005,

Конечно, 00000 не находится в TLB, так как ни одна действительная запись не содержит 00000 в качестве ключа.

Политика замены

Когда TLB заполнен, старые адреса перезаписываются. Как и в случае с кэшем ЦП, политика замены является потенциально сложной операцией, но простой и разумной эвристикой является удаление наименее использованной записи (LRU).

С LRU, начиная с состояния:

  valid   linear   physical
  ------  -------  ---------
> 1       00003    00005
  1       00007    00009
  1       00009    00001
  1       0000B    00003

добавление 0000D -> 0000A даст:

  valid   linear   physical
  ------  -------  ---------
  1       0000D    0000A
> 1       00007    00009
  1       00009    00001
  1       0000B    00003

CAM

Использование TLB ускоряет преобразование, поскольку для первоначального преобразования требуется один доступ на уровень TLB, что означает 2 в простой 32-разрядной схеме, но 3 или 4 в 64-разрядных архитектурах.

TLB обычно реализуется как дорогой тип оперативной памяти, называемый контентно-адресуемой памятью (CAM). CAM реализует ассоциативную карту на аппаратном уровне, то есть структуру, которая дает ключ (линейный адрес), получает значение.

Сопоставления также могут быть реализованы для адресов ОЗУ, но для сопоставлений САМ может потребоваться гораздо меньше записей, чем для сопоставления ОЗУ.

Например, карта, на которой:

• и ключи, и значения имеют 20 бит (в случае простых схем пейджинга)
• максимум 4 значения должны быть сохранены каждый раз

может храниться в TLB с 4 записями:

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
FFFFF    00000

Однако для реализации этого с ОЗУ необходимо иметь 2^20 адресов:

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
... (from 00011 to FFFFE)
FFFFF    00000

что было бы даже дороже, чем использование TLB.

Недействительные записи

когда cr3 Изменения, все записи TLB становятся недействительными, потому что будет использоваться новая таблица страниц для нового процесса, поэтому маловероятно, чтобы какая-либо из старых записей имела какое-либо значение.

X86 также предлагает invlpg инструкция, которая явно делает недействительной одну запись TLB. Другие архитектуры предлагают еще больше инструкций для недействительных записей TLB, например, делают недействительными все записи в данном диапазоне.

Некоторые процессоры x86 выходят за рамки требований спецификации x86 и обеспечивают большую согласованность, чем она гарантирует, между изменением записи таблицы страниц и ее использованием, когда она еще не была кэширована в TLB. Очевидно, Windows 9x полагался на это для правильности, но современные процессоры AMD не обеспечивают последовательного просмотра страниц. Процессоры Intel делают, даже если они должны обнаружить неправильные предположения, чтобы сделать это. Воспользоваться этим преимуществом, вероятно, плохая идея, поскольку, вероятно, выиграть нечего, и существует большой риск возникновения тонких, чувствительных ко времени проблем, которые трудно будет отладить.

Использование ядра Linux

Ядро Linux широко использует функции подкачки x86, чтобы обеспечить быстрое переключение процессов с небольшой фрагментацией данных.

В v4.2заглянуть под arch/x86/:

• include/asm/pgtable*
• include/asm/page*
• mm/pgtable*
• mm/page*

Кажется, не существует структур, определенных для представления страниц, только макросы: include/asm/page_types.h особенно интересно. Выдержка:

#define _PAGE_BIT_PRESENT   0   /* is present */
#define _PAGE_BIT_RW        1   /* writeable */
#define _PAGE_BIT_USER      2   /* userspace addressable */
#define _PAGE_BIT_PWT       3   /* page write through */

arch/x86/include/uapi/asm/processor-flags.h определяет CR0и, в частности, PG положение бита:

#define X86_CR0_PG_BIT      31 /* Paging */

Список используемой литературы

Свободно:

• rutgers-pxk-416 глава "Управление памятью: конспект лекции"

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

Несвободное:

• bovet05 глава "Адресация памяти"

  Разумное введение в адресацию памяти x86. Не хватает хороших и простых примеров.

Answer 2

Вот очень короткий ответ высокого уровня:

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

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

Теперь режим адресации памяти придает смысл операндам памяти машинных инструкций (таких как mov DWORD PTR [eax], 25, который хранит 32-битный (ака dword) целое число со значением 25 в память, адрес которой хранится в eax 32-битный регистр). При плоско-линейной адресации это число в eax разрешено работать в одном непрерывном диапазоне от нуля до максимального значения (в нашем случае это 2³² - 1).

Однако плоско-линейная адресация может быть страничной или не страничной. Без подкачки адрес напрямую относится к физической памяти. При использовании подкачки блок управления памятью (или MMU) процессора прозрачно подает требуемый адрес (теперь называемый виртуальным адресом) в механизм поиска, так называемые таблицы страниц, и получает новое значение, которое интерпретируется как физический адрес. Исходная операция теперь работает с этим новым переведенным адресом в физической памяти, даже если пользователь только когда-либо видит виртуальный адрес.

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

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

И в случае, если вы беспокоитесь о том, что процесс может просто отключить разбиение на страницы или попытаться изменить таблицы страниц: это недопустимо, поскольку x86 реализует уровни привилегий (называемые "кольцами"), а код пользователя выполняется с уровнем привилегий, слишком низким, чтобы это изменить таблицы страниц процессора.