Как устроены многоуровневые таблицы виртуальной памяти?
Если каждая запись в каталоге является обычной ссылкой на каталог (чит. таблицу) уровня ниже, допустим Каталог уровня 4 с некоторой записью будет содержать ссылку на Каталог уровня 3 для некоторого процесса. Вопрос: зачем нам более одной записи в Каталоге уровня 4, учитывая, что все записи эквивалентны (ссылки на Каталог уровня 3)?
Ответы (1 шт):
Данная архитектура возникает для решения противоречия: (1) Обращение к памяти должно быть как можно более быстрым. Нужно гарантировать O(1) - в худшем случае, иначе невозможно построение систем реального времени. (2) Адресация памяти, сама по себе, не должна тратить много памяти. Количество физической памяти, может быть существенно меньше адресного пространства, а процессов с независимыми адресными пространствами - много. (3) желательно, без ветвлений и сложной логики (это все в железе "программировать").
Например, если у нас есть адресное пространство 2^64 байт, и страница памяти 64K = 2^16 байт, значит всего возможно 2^48 страниц. Если мы хотим обойтись одним каталогом, то как этот каталог должен быть устроен?
Самый быстрый способ - достать элемент из массива по номеру. Значит заводим массив размером 2^48 Но тогда для каждого процесса потребуется (2^48)*8 байт физической памяти, только под нужды менеджера памяти. Неприемлемо.
Можно хранить в каталоге только только записи о выделенных страницах памяти. На выбор: сортированный массив, хеш таблица, сбалансированное дерево - не гарантируют O(1)-в худшем (только амортизированное среднее O(1)). Неприемлемо.
Цифровой бор (trie), внезапно, обеспечивает O(1), но с о-очень большой константой (если реализовывать его c ветвлением на каждый бит). Кроме того, собственные аллокации менеджера памяти будут требовать много меньше страницы памяти, что тоже нежелательно.
В общем, текущая архитектура это tires - переросток: суть дерево с четырьмя уровнями ветвления, и с числом ветвления равным 2^12 дочерних элементов, на каждом уровне ветвления. Ветвления на каждом уровне - с использованием массива, и доступом к элементу по его порядковому номеру. (Каждый массив как раз помещается в страницу памяти.)
Разумеется, разные записи в таблице 4-го уровня указывают на разные таблицы 3-го уровня. (Иллюстрация неудачная.) Некоторые записи в каждой таблице - никуда не ведут (равны null), поэтому количество памяти требуемое менеджером памяти примерно пропорционально реальному использованию памяти. Поскольку, как правило, память выделяется в близко праположенных частях адресного пространства расходы менеджера, оказываются много меньше выделенной памяти. но, последнее утверждение - не гарантируется.