Библиотека сайта rus-linux.net
Что каждый программист должен знать о памяти. Виртуальная память
Оригинал: What every programmer should know about memoryАвтор: Ulrich Drepper
Дата публикации: 09.10.2007
Перевод: Капустин С.В.
Дата перевода: 19.03.2009
4.3 Оптимизация доступа к таблицам страниц
Все структуры данных таблиц страниц хранятся в основной памяти, там операционная система создает и обновляет страницы. При создании процесса или изменении таблицы страниц оповещается процессор. Таблицы страниц, используемые для преобразования любого виртуального адреса в физический адрес методом прогулки по дереву таблиц страниц, описаны выше. Более того, показано, что в процессе нахождения адреса используется, по крайней мере, один каталог на каждом уровне преобразования адреса. Это требует до четырех обращений к памяти (за одно обращение к работающему процессу), что конечно медленно. Можно обращаться с записями каталогов таблиц как с обычными данными и кэшировать их в L1d, L2 и т. д., но все равно это будет медленно.
С ранних дней применения виртуальной памяти разработчики процессоров используют другую оптимизацию. Простое вычисление может показать, что только хранение записей каталогов таблиц в L1d и в более высоком кэше приведет к ужасным результатам. Вычисление каждого абсолютного адреса потребует многочисленного обращения к L1d в соответствии с глубиной таблицы страниц. Эти обращения не могут быть распараллелены, так как они зависят от результатов предыдущего поиска. Это одно потребует, по крайней мере, 12 циклов на машине с четырьмя уровнями таблиц страниц. Добавьте к этому вероятность непопадания в L1d, и никакой конвейер команд не сможет скрыть результат. Дополнительные обращения к L1d также расходуют драгоценную пропускную способность кэша.
Вместо кэширования записей таблицы каталогов кэшируется всё вычисление адреса физической страницы. Такое кэширование работает по той же причине, по какой работает кэширование данных и кода. Так как часть виртуального адреса "смещение" не участвует в вычислении адреса физической страницы, только оставшаяся часть виртуального адреса используется как тег кэша. В зависимости от размера страницы это означает, что сотни или даже тысячи инструкций или объектов данных разделяют один и тот же тег и, следовательно, префикс физического адреса.
Кэш, в котором хранятся вычисленные значения, называется "буфер ассоциативного преобразования адресов" (TLB - Translation Look-Aside Buffer). Обычно это маленький кэш, так как он должен быть очень быстрым. Современные процессоры имеют многоуровневые TLB кэши. Также как и для обычного кэша, чем больше номер кэша, тем он больше и медленнее. Часто маленький размер L1TLB задается преднамеренно, для того, чтобы сделать кэш полностью ассоциативным с политикой удаления страниц, которые дольше всего не использовались (LRU - least recently used). В настоящее время размеры таких кэшей увеличиваются, и они перестают быть ассоциативными. Как результат, может получиться, что при добавлении новой записи исключается не самая старая запись.
Как отмечалось ранее, тэг, используемый для доступа к TLB, - это часть виртуального адреса. Если тэг найден в кэше, окончательное значение физического адреса вычисляется добавлением смещения внутри страницы, взятым из виртуального адреса, к кэшированному значению. Это очень быстрый процесс. Он должен быть таким, так как физический адрес должен быть доступен любой инструкции, использующей абсолютные адреса, и в некоторых случаях запросам к L2, которые используют физический адрес как индекс. Если запрос к TLB заканчивается неудачей, процессор должен выполнить алгоритм прогулки по дереву таблиц страниц, что может быть довольно затратно.
Предварительная выборка кода или данных программно или аппаратно может повлечь предварительную выборку записей в TLB, если адрес находится на другой странице. Этого нельзя допускать для аппаратной предварительной выборки, так как это может инициировать ошибочные прогулки по таблицам страниц. Программисты, следовательно, не должны полагаться на аппаратную предварительную выборку для предварительной выборки записей в TLB. Это должно быть сделано явно, используя инструкции предварительной выборки. Кэши TLB, также как и кэши данных и кода, могут появляться на нескольких уровнях. Также как кэш данных, TLB обычно появляется в двух разновидностях: TLB для кода (ITLB - instruction TLB) и TLB для данных (DTLB - data TLB). TLB с более большими номерами, такие как L2TLB, обычно объединены, как и в случае с обычным кэшем.
4.3.1 Пояснения к использованию TLB
TLB - это глобальный ресурс ядра процессора. Все потоки и процессы, выполняемые в ядре, используют один TLB. Так как преобразование виртуального адреса в физический зависит от того, какое загружено дерево таблиц страниц, процессор не может слепо продолжать использовать кэшированные записи, если таблица страниц поменялась. Каждый процесс имеет своё дерево таблиц страниц (но не потоки одного процесса), также как и ядро ОС и монитор виртуальной машины (Virtual Machine Monitor, VMM), если таковой имеется. Также возможно изменение конфигурации адресного пространства процесса. Есть два подхода к решению этой проблемы:
- TLB очищается при каждом изменении дерева таблиц страниц.
- В тэги TLB добавляется информация так, чтобы можно было однозначно определить, на какое дерево таблиц страниц ссылается тэг.
В первом случае TLB очищается при каждом переключении контекста. Так как в большинстве ОС переключение с одного потока/процесса на другой требует выполнения некоторого кода ядра ОС, очищение TLB происходит при входе и выходе из адресного пространства ядра ОС. На виртуализованных системах это случается также, когда ядро ОС вызывает VMM, и по пути назад. Если ядро ОС и/или VMM не обязано использовать виртуальный адрес, или может использовать тот же виртуальный адрес, что и процесс или ядро, которое сделало вызов системы/VMM, TLB очищается только если покидая ядро ОС или VMM процессор начинает выполнение другого процесса или ядра.
Очищение TLB эффективно, но затратно. Например, когда ядро ОС выполняет системный вызов, его код может быть ограничен несколькими тысячами инструкций, которые затрагивают небольшое количество новых страниц (или одну огромную страницу, в случае использования Linux на некоторых архитектурах). Это заставит поменять ровно столько записей TLB, сколько новых страниц использовано. Для архитектуры Intel Core2, которая имеет 128 записей ITLB и 256 ITLB, полное очищение означает, что более 100 и 200 записей соответственно будут удалены без необходимости делать это. Когда система вернется к этому процессу снова, эти записи могут понадобиться, но их уже не будет. То же самое верно для часто используемого кода ядра ОС или VMM. При каждом входе в ядро ОС TLB придется заполнять заново, хотя таблицы страниц для ядра ОС или VMM обычно не изменяются и, следовательно, в теории, могут храниться очень долгое время. Это также объясняет, почему кэши TLB в современных процессорах не такие большие: программы, скорее всего, не будут работать настолько долго, чтобы заполнить все эти записи.
Этот факт, конечно, не ускользнул от разработчиков процессоров. Одно из возможных решений - использовать выборочное удаление записей для оптимизации очищения кэша. Например, если код и данные ядра ОС попадают в некоторый диапазон адресов, то из TLB удаляются только страницы из этого диапазона. Это требует только сравнения тэгов и, следовательно, не очень затратно. Этот метод также полезен в случае, когда изменяется только часть адресного пространства, например через вызов munmap.
Намного лучшим решением будет расширить тэг, используемый для доступа к TLB. Если к части виртуального адреса будет добавлен уникальный идентификатор дерева таблиц страниц (например адресного пространства процесса), то TLB можно будет полностью не очищать. Ядро ОС, VMM, и процессы могут иметь уникальные идентификаторы. Единственная трудность здесь это то, что количество бит, доступных для тэга TLB жестко ограничено, тогда как число адресных пространств нет. Это значит, что некоторые идентификаторы придется переназначать. Когда такое происходит, TLB должен быть частично очищен (если это возможно). Все записи с переназначенным идентификатором должны быть удалены, но их, скорее всего, будет очень мало.
Это расширение тэгов TLB имеет общее преимущество когда в системе запущено много процессов. Если объем памяти (и, следовательно, количество записей TLB) для каждого процесса ограничен, то велика вероятность того, что последние по времени использования записи TLB для процесса будут все ещё в TLB, когда они понадобятся. И ещё два дополнительных преимущества:
- Специальные адресные пространства, такие как у ядра ОС и VMM, часто
используются только на короткое время, после чего управление обычно передается адресному пространству, которое инициировало вызов. Без тэгов было бы выполнено два очищения TLB. С тэгами преобразование адресов вызывающего адресного пространства сохраняется и, так как адресные пространства ядра ОС и VMM не часто изменяют записи TLB, преобразования адресов предыдущих системных вызовов и т.д. могут быть снова использованы.
- При переключении между потоками одного процесса очищение TLB не нужно вообще. Без расширенных тэгов TLB, вход в ядро ОС уничтожит записи в TLB первого потока.
На некоторых процессорах такие расширенные тэги уже стали появляться. AMD представило 1-битное расширение тэга на платформе аппаратной виртуализации Pacifica. Этот 1-битный идентификатор адресного пространства (ASID - Address Space ID) используется в контексте виртуализации, чтобы отличать адресное пространство VMM от адресных пространств гостевых операционных систем. Это позволяет ОС избежать удаления из TLB записей гостевой операционной системы каждый раз, когда управление передается VMM (например, при ошибке страницы) или записей VMM, когда управление возвращается гостевой операционной системе. Эта архитектура позволит использовать больше бит в будущем. Другие наиболее распространенные процессоры, скорее всего, также будут поддерживать это свойство.
4.3.1 Влияние на производительность TLB
Есть пара факторов, которые влияют на производительность TLB. Первый - это размер страниц. Очевидно, что чем больше страница, тем больше попадает в неё инструкций или объектов данных. Таким образом, больший размер страницы сокращает общее число необходимых преобразований адресов, что означает, что можно обойтись меньшим числом записей в кэше TLB. Большинство архитектур позволяют использовать разные размеры страниц. Некоторые размеры могут быть использованы одновременно. Например, процессоры 86/x86-64 имеют нормальный размер страницы 4Кб, но могут также использовать страницы размером 4Мб и 2Мб соответственно. IA-64 и PowerPC позволяют использовать в качестве базового размера страницы значение 64Кб.
Однако использование страниц большого размера несет в себе и некоторые проблемы. Область памяти, используемая для большой страницы, должна располагаться в памяти одним непрерывным куском. Если увеличить размер блока при администрировании физической памяти до размера страницы виртуальной памяти, то потери памяти будут расти. Все виды операций с памятью (например загрузка исполняемого кода) требуют выравнивания границ страниц. Это означает, что в среднем при каждом выделении памяти будет теряться половина размера страницы физической памяти. Эти потери легко могут накапливаться, что задает ограничение сверху на размер блока физической памяти.
Определенно можно сказать, что будет непрактично увеличивать размер блока до 2Мб на x86-64, чтобы получить большие страницы. Это слишком большой размер. Но это в свою очередь означает, что каждая большая страница должна состоять их множества маленьких страниц. Все эти страницы должны располагаться рядом в физической памяти. Выделение 2Мб непрерывной физической памяти может быть сложной задачей при размере блока 4Кб. Для этого требуется найти свободное пространство из 512 страниц, расположенных рядом. Это может быть очень сложно (или даже невозможно) после того как система работает некоторое время и физическая память фрагментирована.
На Linux, следовательно, нужно выделить эти большие страницы во время старта системы, используя специальную файловую систему hugetlbfs. Фиксированное количество физических страниц будут зарезервированы исключительно для использования в качестве больших виртуальных страниц. Это связывает ресурсы, которые могут вообще остаться неиспользованными. Их к тому же ограниченное количество - чтобы его увеличить потребуется перезагрузка. Но все равно это выход в ситуации, когда производительность на первом месте, ресурсов хватает, а долгая загрузка не страшна. Примером могут служить серверы баз данных.
Увеличение минимального размера виртуальной страницы (как альтернатива опциональному использованию больших страниц) тоже имеет свои проблемы. Операции, связанные с распределением памяти (например загрузка приложения), должны быть согласованы с этим размером страниц. Выделение памяти меньшего размера невозможно. Расположение различных частей исполняемого файла для большинства архитектур фиксировано. Если размер страницы увеличен больше того предела, на который ориентировались при компиляции исполняемого файла или библиотеки, загрузка будет невозможна. Важно держать это ограничение в голове. Рисунок 4.3 показывает, как можно определить требования к выравниванию по виду файла формата ELF. Это закодировано в его заголовке.
$ eu-readelf -l /bin/ls Program Headers: Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align ... LOAD 0x000000 0x0000000000400000 0x0000000000400000 0x0132ac 0x0132ac R E 0x200000 LOAD 0x0132b0 0x00000000006132b0 0x00000000006132b0 0x001a71 0x001a71 RW 0x200000 ...
Рисунок 4.3: Заголовок ELF, указывающий на требования к выравниванию
В этом примере бинарника на x86-64 значение выравнивания 0x200000 = 2,097,152 = 2Мб соответствует максимальному размеру страницы, поддерживаемому процессором.
Есть второй эффект от использования страниц большего размера - число уровней дерева таблиц страниц сокращается. Так как часть виртуального адреса, соответствующая смещению внутри страницы возрастает, остается не так много бит, которые требуется распределить по каталогам страниц. Это означает, что в случае отсутствия нужной записи в TLB, количество необходимой работы сократится.
Кроме использования большого размера страниц, возможно сократить необходимое количество записей TLB, перемещая данные, которые используются одновременно, на меньшее количество страниц. Это похоже на некоторые оптимизации кэша, о которых упоминалось ранее. Только теперь выравнивание большего размера. Учитывая, что количество записей TLB довольно мало, это может быть очень важной оптимизацией.
| Назад | Оглавление | Вперед |