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

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

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

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

Рекомендуемые рекомендации:

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

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

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

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

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

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

    Образец кода

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

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

    Что делает этот объект «трудным», так это то, что минимальный пример большой, потому что вам нужно создать свою собственную небольшую ОС.

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

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

    Intel описывает пейджинг в Руководстве по системному программированию Intel Manual Volume 3 – 325384-056US Сентябрь 2015 г. Глава 4 «Пейджинг».

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

    MMU

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

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

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

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

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

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

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

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

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

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

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

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

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

    заявка

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

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

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

    Реализация оборудования

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

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

    Некоторые другие архитектуры оставляют пейджинг почти полностью в armх программного обеспечения, поэтому пропуски 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 

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

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

    Страница представляет собой fragment 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 , начало таблицы для первого процесса.

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

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

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

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

      • page = 0x00000
      • offset = 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 , не беспокоясь о точном физическом FFFFFFFF .

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

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

    Аппаратное обеспечение уведомляет программное обеспечение через исключение Page Fault Exception.

    Тогда обычно до ОС регистрируется обработчик исключений, чтобы решить, что нужно сделать.

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

     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 ps -A | wc -l говорит, что я запускаю 244 процесса прямо сейчас, так что это займет около 1 ГБ моей памяти!

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

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

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

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

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

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

    Каталоги страниц содержат … записи в каталоге страниц! Записи каталога страниц такие же, как и записи в таблице страниц, за исключением того, что они указывают на адреса ОЗУ таблиц страниц вместо физических адресов таблиц . Поскольку эти адреса имеют ширину всего 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 ( 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 10 | 10 | 12 10 | 10 | 12 дает:

     0000000010 0000000001 000000000100 0x2 0x1 0x4 

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

    • запись в каталоге страницы = 0x2
    • запись в таблице страниц = 0x1
    • offset = 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 бит.

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

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

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

    x86_64 использует 4 уровня в 9 | 9 | 9 | 12 9 | 9 | 9 | 12 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 10 | 10 | 12

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

      22 – смещение на странице 4 Мб, так как 22 бита адресуют 4 Мб.

    • PAE и нет PSE: 2 | 9 | 9 | 12 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 2 | 9 | 21

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

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

    TLB

    Буфер Translation Lookahead (TLB) – это кеш для адресов подкачки.

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

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

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

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

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

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

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

      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 выходят за frameworks требований спецификации x86 и обеспечивают большую согласованность, чем это гарантирует, между изменением записи в таблице страниц и ее использованием, когда она еще не была кэширована в TLB . Видимо, Windows 9x полагалась на это для правильности, но современные процессоры AMD не обеспечивают согласованных переходов по страницам. Процессоры Intel делают, хотя им приходится обнаруживать ошибочные предположения. Пользуясь этим, возможно, это плохая идея, так как, вероятно, не так много, и большой риск вызвать тонкие чувствительные к времени проблемы, которые трудно отлаживать.

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

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

    В v4.2 смотрите под arch/x86/ :

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

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

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

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

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

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

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

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

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

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

    Давайте будем гением компьютера.