Распределение памяти ядра

Ядро в процессе работы часто генерирует и уничтожает маленькие таблицы и буфера, память для каждого из которых выделяется динамически. В [VAHA96] перечислены следующие примеры.

• Преобразование имени пути может запросить буфер для копированияимени из пользовательского пространства.

• Подпрограмма allocb ( ) выделяет буфера произвольного размера.

• Ряд реализации UNIX выделяют "зомби"-структуры для хранения информации о состоянии выхода и использовании ресурсов завершенными процессами.

• В SVR4 и Solaris ядро динамически распределяет множество объектов (таких, как структуры процессов, блоки дескрипторов файлов и др.).

Размер большинства этих блоков гораздо меньше типичного размера страницы памяти и, соответственно, использование страничного механизма в данном случае крайне неэффективно. В SVR4 используется модификация системы двойников (описанной в разделе 7.2).

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

Беркли (Barkley) и Ли (Lee) из AT&T предложили модификацию, известную как "ленивая" система двойников [BARK89], которая принята в SVR4. Авторами замечено, что UNIX часто демонстрирует устойчивое состояние памяти ядра, т.е. количество требующихся блоков определенного размера мало меняется со временем. Таким образом, вполне возможна ситуация, когда освобождающийся блок размером 2ⁱ сливается со своим двойником в блок размером 2ⁱ⁺¹, который тут же вновь разделяется на два блока размером 2ⁱ в соответствии с запросом системы. Чтобы избежать излишних слияний и разделений блоков, слияние освобожденных блоков откладывается до того момента, когда оно оказывается действительно необходимым (и тогда производится максимально возможное количество слияний блоков).

В модифицированной таким образом системе двойников используются следующие параметры:

N_i — текущее количество блоков размером 2ⁱ;

A_i — текущее количество занятых блоков размером2ⁱ;

G_i — текущее количество глобально свободных блоков размером 2ⁱ (Это блоки, пригодные для слияния со своими двойниками. Когда двойник такого блока становится глобально свободным, эти два блока сливаются в глобально свободный блок размером 2ⁱ⁺¹. Все свободные блоки в системе двойников могут рассматриваться как глобально свободные);

L_i — текущее количество локально свободных блоков размером2ⁱ (Это блоки, не пригодные для слияния. Даже если двойник такогоблока становится свободным, эти два блока не сливаются, а остаются в ожидании последующих запросов на блоки данного размера.).

Выполняется следующее соотношение:

N_i= A_i+ G_i+ L_i

В целом данная система двойников пытается поддерживать пул локально свободных блоков и производит слияние, только когда количество локально свободных блоков превышает предопределенный порог (при наличии слишком большого количества локально свободных блоков возрастает вероятность недостатка блоков большего размера для удовлетворения требований системы). В основном при освобождении блока слияние не выполняется, что минимизирует накладные расходы. Никаких различий между локально и глобально свободными блоками при выделении блока в ответ на запрос системы не делается.

Для слияния используется критерий, согласно которому количество локально свободных блоков данного размера не должно превышать количество занятыхблоков этого размера (т.е. должно выполняться условие L_i < А_i). Это вполне разумный принцип для ограничения количества локально свободных блоков; эксперименты, описанные в [BARK89], подтверждают, что такая схема приводит к значительному снижению стоимости распределения памяти.

Для реализации описанной схемы ее авторы определили переменную задержки D_i = 4 – L_i = N_i - 2L_i –G_i . Алгоритм схемы приведен в листинге 8.1.

Листинг 8.1. Алгоритм "ленивой" системы двойников

Начальное значение D_i равно 0

После выполнения операций значение D_i изменяется следующим образом:

(I) Если следующая операция является запросом на выделение блока:

Если имеется свободный блок, выбрать его

Если выбранный блок локально свободен, D_i: = D_i+2 иначе D_i = D_i+2.

в противном случае получить два блока путем разделения большего блока на два меньших (рекурсивная операция).

Выбрать один из них, пометив второйкак локально свободный.

D_i остается неизменным (при этом значение D_i для других размеров блоков может измениться в связи с использованием рекурсивности).

(II). Если следующая операция — запрос на освобождение блока

При D_i 2

Пометить блок как локально свободный и освободить его локально

D_i = D_i- 2

При D_i =1

Пометить блок как глобально свободный и освободить его глобально; если это возможно - выполнить слияние блоков.

D_i := 0

При Di = 0

Пометить блок как глобально свободный и освободить его глобально; если это возможно - выполнить слияние блоков.

Выбрать один локально свободный блок размером 2ⁱ и освободить его глобально; если это возможно, выполнить слияние блоков.

D_i := 0