Linux Kernel (Ядро линукса) (часть 1)

Управление областями памяти

В этом разделе речь пойдет об областях памяти, то есть о последовательностях ячеек, имеющих смежные физические адреса и произвольную длину.
Алгоритм buddy-система” принимает страничный кадр в качестве базовой области памяти. Такой подход хорош при обработке запросов на относительно большие порции памяти, но что же делать с запросами на маленькие области памяти из нескольких десятков или сотен байтов?

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

Классический подход (принятый в ранних версиях Linux) состоит в представлении областей памяти с геометрически распределенными размерами. Иными словами, размер области привязан к степени двойки, а не к размеру сохраняемых данных. В этом случае независимо от размера запрашиваемой памяти можно гарантировать, что внутренняя фрагментация будет всегда меньше 50%. Следуя такому подходу, ядро создает 13 геометрически распределенных списков свободных областей памяти, размеры которых лежат в диапазоне от 32 до 131 072. Buddy-система используется как для получения дополнительных страничных кадров, необходимых под новые области памяти, так и для освобождения страничных кадров, более не содержащих никаких областей. Для отслеживания свободных областей памяти в каждом страничном кадре применяется динамический список.

Slab-аллокатор

Выполнение алгоритма выделения области памяти на базе buddy-алгоритма не особенно эффективно. Более удачный алгоритм основан на схеме slab-
аллокатора, которая впервые была задействована в операционной системе
Solaris 2.4 фирмы Sun Microsystems. Алгоритм исходит из следующих предположений:
- Тип сохраняемых данных может влиять на способ выделения памяти; например, при выделении страничного кадра процессу, работающему в режиме пользователя, ядро вызывает функцию get zeroed page , заполняющую страницу нулями. Концепция slab-аллокатора развивает эту идею и рассматривает области памяти как объекты, состоящие из набора структур данных и пары функций или методов, называемых конструктором и деструктором. Первый инициализирует область памяти, в то время как второй деинициализирует ее.

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

- Функции ядра, как правило, многократно запрашивают области памяти одного и того же типа. Например, когда ядро создает новый процесс, оно выделяет области памяти под несколько таблиц фиксированного размера: дескриптор процесса, объект "открытый файл” и т. д.. После того, как процесс закончится, области памяти, содержавшие эти таблицы, можно будет использовать повторно. Поскольку процессы разрушаются и уничтожаются довольно часто, без slab-аллокатора ядро непроизводительно расходовало бы время на многократное выделение и освобождение страничных кадров, содержащих одни и же области памяти. Slab- аллокатор позволяет сохранить их в кэше и использовать повторно.
- Запросы на области памяти можно классифицировать по их частоте. Запросы на определенный объект памяти, про которые известно, что они возникают часто, можно очень эффективно обрабатывать, создав набор специализированных объектов, имеющих соответствующий размер, и избежав таким образом внутренней фрагментации. В то же время запросы на "редкие” объемы памяти можно обрабатывать по схеме, основанной на применении объектов с геометрически распределенными размерами (например, являющимися степенями двойки, как было принято в ранних версиях Linux), даже если этот подход приведет к внутренней фрагментации.
- Использование объектов, размеры которых не являются геометрически распределенными, имеет еще одно небольшое преимущество: начальные адреса структур данных в меньшей степени концентрируются вокруг физических адресов, являющихся степенями двойки. Это, в свою очередь, повышает эффективность аппаратного кэша процессора.
- Забота об эффективности аппаратного кэша выдвигает дополнительный аргумент в пользу минимизации вызовов аллокатора buddy-системы, на-
сколько это возможно. Каждый вызов функции buddy-системы "загрязняет" аппаратный кэш, тем самым увеличивая среднее время доступа к памяти. Влияние функции ядра на аппаратный кэш называется ее следом и определяется, как процент объема кэша, переписываемый функцией, когда заканчивается ее выполнение. Очевидно, что большие следы замедляют выполнение кода, идущего непосредственно после функции, потому что аппаратный кэш содержит бесполезную информацию.

Slab-аллокатор группирует объекты в кэши. Каждый кэш является хранилищем объектов одного типа. Например, когда открывается файл, область памяти, необходимая для хранения объекта "открытый файл", берется из кэша slab-аллокатора, называемого flip (от англ. "file pointer" — указатель на файл).
Область основной памяти, содержащая кэш, делится на участки. Каждый участок состоит из одного или нескольких смежных страничных кадров, которые содержат как выделенные, так и свободные объекты ядро периодически сканирует кэши и освобождает страничные кадры, соответствующие пустым участкам.