Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
И тут неожиданно оказывается, что нужно выделять диапазоны из верхней половины адресного пространства 48 или 64 бит… А их выделять нужно. И каждая операция выделения памяти приводит к вставке/удалению элементов из середины таблицы.
Это же не std::vector, вставляйте на здоровье.
Возможно я не понял вопрос.
Возможно я не понял вопрос.
Многоуровневые таблицы позволяют эффективно их изменять, при этом каждый раз может изменяться только небольшая их часть. Одноуровневые требуют изменения всей таблицы. Это так, чтобы сходу.
1) На линейных таблицах не получится сделать эффективного кэширования. На двух-уровневых возможно раздельное кэширование каждого уровня, когда изменение одного из уровней не требует инвалидации всего кэша. Вплоть до того, что можно сделать инвалидацию только того фрагмента, который изменяется. У вас только полное перестроение всей таблицы.
2) Сравните сложность и количество операций pagewalk при промахе. Многоуровневая архитектура гарантирует максимальное время поиска элемента, а среднее время поиска изменяется не сильно. А у вас? Допустим, что у вас 128 Гб область со страницами 4 кб (муа-ха-ха) — вполне нормальный случай для всяких баз данных, файлов, отображаемых в память, кэшей и т.п. Посмотрите на сколько ваша линейная таблица будет медленнее при произвольном доступе.
3) У вас сложно организуются «пропуски» в памяти — требуется полноценный pagewalk. Для «классической» архитектуры всё обычно заканчивается на первом уровне. Страшно представить, на сколько ваша реализация медленней.
4) И самое главное. Вы как-то в процессе «усовершенствования» забыли зачем вообще нужна трансляция адресов. У вас получилась трансляция ради трансляции.
А на самом деле таблицы TLB не статичные. При переключении контекста, (может) переключаются TLB и у каждого процесса своя карта памяти. И логические адреса у всех процессов перекрываются. При этом значительные части карты памяти у всех процессов совпадают. В классической архитектуре это реализуется переключением таблиц второго уровня (изменение буквально нескольких записей в таблицах первого) и повторным использованием таблиц для разных процессов. При переключении процессов не обязателен сброс всех уровней всех таблиц (разделяемая память и память ОС остаются). А у вас… Вы будете для каждого процесса полную таблицу карты памяти строить и хранить, а на каждом переключении контекста полностью кэш TLB сбрасывать?
Сейчас если два процесса разделяют область памяти и у каждого по 32 ГБ виртуальной памяти, то это может одна и та же таблица (набор таблиц). Для чего под разделяемую память резервируется специальный диапазон адресного пространства. А у вас, что получится?
1) На линейных таблицах не получится сделать эффективного кэширования. На двух-уровневых возможно раздельное кэширование каждого уровня, когда изменение одного из уровней не требует инвалидации всего кэша. Вплоть до того, что можно сделать инвалидацию только того фрагмента, который изменяется. У вас только полное перестроение всей таблицы.
2) Сравните сложность и количество операций pagewalk при промахе. Многоуровневая архитектура гарантирует максимальное время поиска элемента, а среднее время поиска изменяется не сильно. А у вас? Допустим, что у вас 128 Гб область со страницами 4 кб (муа-ха-ха) — вполне нормальный случай для всяких баз данных, файлов, отображаемых в память, кэшей и т.п. Посмотрите на сколько ваша линейная таблица будет медленнее при произвольном доступе.
3) У вас сложно организуются «пропуски» в памяти — требуется полноценный pagewalk. Для «классической» архитектуры всё обычно заканчивается на первом уровне. Страшно представить, на сколько ваша реализация медленней.
4) И самое главное. Вы как-то в процессе «усовершенствования» забыли зачем вообще нужна трансляция адресов. У вас получилась трансляция ради трансляции.
А на самом деле таблицы TLB не статичные. При переключении контекста, (может) переключаются TLB и у каждого процесса своя карта памяти. И логические адреса у всех процессов перекрываются. При этом значительные части карты памяти у всех процессов совпадают. В классической архитектуре это реализуется переключением таблиц второго уровня (изменение буквально нескольких записей в таблицах первого) и повторным использованием таблиц для разных процессов. При переключении процессов не обязателен сброс всех уровней всех таблиц (разделяемая память и память ОС остаются). А у вас… Вы будете для каждого процесса полную таблицу карты памяти строить и хранить, а на каждом переключении контекста полностью кэш TLB сбрасывать?
Сейчас если два процесса разделяют область памяти и у каждого по 32 ГБ виртуальной памяти, то это может одна и та же таблица (набор таблиц). Для чего под разделяемую память резервируется специальный диапазон адресного пространства. А у вас, что получится?
А почему вы считаете, что массив с прямой индексацией медленней дерева?
Вот у вас 4-х уровневое дерево, допустим, три уровня закэшировались,
всё сводится к трём переходам и одному чтению с диска (PTE).
В случае прямого доступа вы всего-лишь пытаетесь прочитать значение по указателю и возможно (в худшем случае) придётся прочесть страницу.
Такая схема успешно работала на VAX-е и сейчас вполне успешно работает на Эльбрусах.
Для сохранения общей части TLB есть механизм глобальных страниц.
Вот у вас 4-х уровневое дерево, допустим, три уровня закэшировались,
всё сводится к трём переходам и одному чтению с диска (PTE).
В случае прямого доступа вы всего-лишь пытаетесь прочитать значение по указателю и возможно (в худшем случае) придётся прочесть страницу.
Такая схема успешно работала на VAX-е и сейчас вполне успешно работает на Эльбрусах.
Для сохранения общей части TLB есть механизм глобальных страниц.
Сколько записей вам придётся проанализировать для многоуровневого дерева и вашей таблицы?
На данный момент процессоры с самой сложной структурой TLB находят информацию о странице не более чем за шесть чтений памяти. При этом первые уровни очень эффективно кэшируются и практически никогда не сбрасываются. Это при адресации 128 Петабайт памяти с произвольной сложностью распределения.
На практике может использоваться от двух до трёх уровней, и, соответственно, не более трёх-четырёх обращений к памяти для поиска страницы для любого разумного объёма памяти. Среднее количество обращений при промахе — не более двух (за счёт кэширования).
А у вас сколько будет обращений при промахе максимальное и среднее после переключения контекста на другую задачу?
И, всё же, вы предлагаете для каждого процесса хранить полную таблицу и целиком переключать?
На данный момент процессоры с самой сложной структурой TLB находят информацию о странице не более чем за шесть чтений памяти. При этом первые уровни очень эффективно кэшируются и практически никогда не сбрасываются. Это при адресации 128 Петабайт памяти с произвольной сложностью распределения.
На практике может использоваться от двух до трёх уровней, и, соответственно, не более трёх-четырёх обращений к памяти для поиска страницы для любого разумного объёма памяти. Среднее количество обращений при промахе — не более двух (за счёт кэширования).
А у вас сколько будет обращений при промахе максимальное и среднее после переключения контекста на другую задачу?
И, всё же, вы предлагаете для каждого процесса хранить полную таблицу и целиком переключать?
Объясните пожалуйста об анализе каких записей (которые я по-вашему должен производить) вы говорите? Ощущение что мы про разное говорим.
Нижний уровень page-table, который в «моём» случае одномерный массив с прямой индексацией, всё равно нужен каждому процессу. И он составляет 0.1% от фактически используемого процессом виртуального пространства.
Нужно ли при переключении контекста на другой процесс как-то сериализовать содержимое TLB и возвращать потом обратно я не знаю.
Нижний уровень page-table, который в «моём» случае одномерный массив с прямой индексацией, всё равно нужен каждому процессу. И он составляет 0.1% от фактически используемого процессом виртуального пространства.
Нужно ли при переключении контекста на другой процесс как-то сериализовать содержимое TLB и возвращать потом обратно я не знаю.
Записи о страницах (регионах) памяти.
Я про количество чтений/анализирований записей в таблицах TLB. В классических таблицах всё выровнено, размер записи не превышает размера линии кэша и шины и одно чтение памяти даёт информацию, минимум, об одной записи в TLB. В результате общее количество обращений к памяти не превышает количества элементов TLB, которые должны быть просмотрены.
Другими словами: в худшем случае сколько записей в TLB процессору нужно проанализировать, чтобы найти информацию о физическом адресе по логическому. И сколько в среднем будет выполняться таких чтений/анализов для поиска физического адреса по логическому при промахе после переключении контекста и перестроения таблицы в области пользовательского процесса.
Я про количество чтений/анализирований записей в таблицах TLB. В классических таблицах всё выровнено, размер записи не превышает размера линии кэша и шины и одно чтение памяти даёт информацию, минимум, об одной записи в TLB. В результате общее количество обращений к памяти не превышает количества элементов TLB, которые должны быть просмотрены.
Другими словами: в худшем случае сколько записей в TLB процессору нужно проанализировать, чтобы найти информацию о физическом адресе по логическому. И сколько в среднем будет выполняться таких чтений/анализов для поиска физического адреса по логическому при промахе после переключении контекста и перестроения таблицы в области пользовательского процесса.
Но в отличие от THP, страницу не нужно резать сразу на 512 частей, можно и более аккуратно, например, отрезать половинки от большой страницы пока не останется сколько надо, после чего вытолкнуть на диск.Мне кажется, в этом случае сильно усложнится процесс определения page fault'ов, то есть если раньше достаточно было проверить, к какой странице относится адрес и есть ли она в памяти, то теперь еще надо будет проверять, а есть ли именно нужная часть страницы в памяти. Как результат — замедление всего доступа к памяти.
Допустим, в некоторой архитектуре, если страница есть в TLB, то она есть и в памяти.
И мы промахнулись, всё равно лезть в page table за нужным элементом, а там уже указано на диске она или нет.
Второй вариант, в элементе TLB указано, в памяти страница или нет (или частично, чем черт не шутит). Если частично, это ваш вариант, надо на всякий случай лезть в page table и проверять.
Проще вместо частичной выгрузки разбить страницу на фрагменты.
И мы промахнулись, всё равно лезть в page table за нужным элементом, а там уже указано на диске она или нет.
Второй вариант, в элементе TLB указано, в памяти страница или нет (или частично, чем черт не шутит). Если частично, это ваш вариант, надо на всякий случай лезть в page table и проверять.
Проще вместо частичной выгрузки разбить страницу на фрагменты.
Эдак можно докатиться до сегмент-дескрипторной адресации 286 protected mode. (Шутка.)
А вообще, я припоминаю, что её в те времена, на каких-то процессорах, возможно alpha, страницы были 8k, что приучало программистов держаться на чеку и помнить, что 4k не константа…
А вообще, я припоминаю, что её в те времена, на каких-то процессорах, возможно alpha, страницы были 8k, что приучало программистов держаться на чеку и помнить, что 4k не константа…
Да, у альфы было 8к,
на этот случай есть sysconf
на этот случай есть sysconf
В общем, перенос логики работы менеджера памяти второго уровня (аллокатора) на таблицы страниц. Так же, как там накладно при запрошенных 512 байтах выдавать 128 блоков по 4 байта, лучше иметь пул и на 4 и на 512. Так и здесь.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
4K страницы: навсегда, на веки вечные