Как работает подкачка x86?

Question 1

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

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

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

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

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

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

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

Question 2

Версия этого ответа с хорошим оглавлением и другим контентом .

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

Образец кода

Минимальный пример: 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 ), раньше это был отдельный чип, который позже был интегрирован в ЦП. Но этот термин все еще используется.

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

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

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

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

В большинстве случаев мы можем думать о физических адресах как об индексировании фактических ячеек аппаратной памяти RAM, но это не на 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ускорить доступ и просто зарезервируют биты, оставшиеся биты для дальнейшего использования. Фактическое значение для Lx86 - 32 бита.

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

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

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

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

разделите линейный адрес на две части:
```
| page (20 bits) | offset (12 bits) |
```
Итак, в этом случае у нас будет:
- page = 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страниц имеет записи каталога страниц

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

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

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

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

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

Причина использования 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 ТиБ), а PAE устаревшего режима уже допускает 52-битные адреса (4 ПиБ).

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 - это смещение в пределах страницы 4 Мб, поскольку 22 бита адресуют 4 Мб.
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

и после второго перевода 00007to 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 реализует ассоциативную карту на оборудовании, то есть структуру, которая по ключу (линейный адрес) извлекает значение.

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

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

и ключи, и значения имеют 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. Отсутствует несколько хороших и простых примеров.

Question 3

Вот очень короткий общий ответ:

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

1

Это должно быть помечено как «faq» и «community-wiki».

Kerrek SB

Answer 3

@KerrekSB Я действительно не знаю, как решать подобные вопросы. Ответы должны быть вики сообщества, не так ли? Я не нашел faqметку.

Чиро Сантилли 郝海东冠状病六四事件法轮功

Answer 4

3

Я бы сказал, что краткий ответ: «прочтите Том 3, Главу 4: Пейджинг в Руководстве Intel». Это довольно ясно, лаконично и хорошо написано, и это не становится более авторитетным.

Kerrek SB

Answer 5

4

@KerrekSB Я согласен с тем, что руководство ясное и авторитетное, но оно было для меня слишком суровым при первом чтении, мне нужно было несколько простых и конкретных примеров + обоснование, чтобы лучше понять вещи.

Чиро Сантилли 郝海东冠状病六四事件法轮功

Answer 6

Версия этого ответа с хорошим оглавлением и другим контентом .

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

Образец кода

Минимальный пример: 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 ), раньше это был отдельный чип, который позже был интегрирован в ЦП. Но этот термин все еще используется.

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

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

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

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

В большинстве случаев мы можем думать о физических адресах как об индексировании фактических ячеек аппаратной памяти RAM, но это не на 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ускорить доступ и просто зарезервируют биты, оставшиеся биты для дальнейшего использования. Фактическое значение для Lx86 - 32 бита.

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

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

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

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

разделите линейный адрес на две части:
```
| page (20 bits) | offset (12 bits) |
```
Итак, в этом случае у нас будет:
- page = 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страниц имеет записи каталога страниц

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

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

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

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

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

Причина использования 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 ТиБ), а PAE устаревшего режима уже допускает 52-битные адреса (4 ПиБ).

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 - это смещение в пределах страницы 4 Мб, поскольку 22 бита адресуют 4 Мб.
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

и после второго перевода 00007to 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 реализует ассоциативную карту на оборудовании, то есть структуру, которая по ключу (линейный адрес) извлекает значение.

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

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

и ключи, и значения имеют 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 7

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

Кейнан

Answer 8

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

Чиро Сантилли 郝海东冠状病六四事件法轮功

Answer 9

1

real TLBs are not usually fully associative… The TLB is usually implemented as … CAMРазве эти два утверждения не противоречат друг другу?

a3f 09

Answer 10

>>> x86_64 использует 4 уровня в 9 | 9 | 9 | 12 схема должна быть 9 | 9 | 9 | 9 | 12

monklof

Answer 11

@monklof Я думаю, что это правильно: 9 9 9 12 уже позволяет 512 ГБ ОЗУ. Пятиуровневая схема - это более поздняя разработка, направленная только на серверы, это упоминается в ответе на моем веб-сайте, который является более современным.

Чиро Сантилли 郝海东冠状病六四事件法轮功

Answer 12

Вот очень короткий общий ответ:

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

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

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

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

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

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

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

Как работает подкачка x86?

Ответы:

Образец кода

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

MMU

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

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

заявка

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

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

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

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

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

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

Упрощения

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

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

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

PAE

PSE

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

TLB

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

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

CAM

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

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

Библиография