Выделение и освобождение структур данных — это одна из наиболее частых операций, которые выполняются в любом ядре. Для того чтобы облегчить процедуру частого выделения и освобождения данных при программировании, вводятся списки свободных ресурсов (free list). Список свободных ресурсов содержит некоторый набор уже выделенных структур данных. Когда коду необходим новый экземпляр структуры данных, он может взять одну структуру из списка свободных ресурсов, вместо того чтобы выделять необходимый объем памяти и заполнять его данными соответствующей структуры. Позже, когда структура данных больше не нужна, она снова возвращается в список свободных ресурсов, вместо того чтобы освобождать память. В этом смысле список свободных ресурсов представляет собой кэш объектов, в котором хранятся объекты одного определенного, часто используемого типа.

Одна из наибольших проблем, связанных со списком свободных ресурсов в ядре, это то, что над ними нет никакого централизованного контроля. Когда ощущается недостаток свободной памяти, нет никакой возможности взаимодействовать между ядром и всеми списками свободных ресурсов, которые в такой ситуации должны уменьшить размер своего кэша, чтобы освободить память. В ядре нет никакой информации о случайно созданных списках свободных ресурсов. Для исправления положения и для универсальности кода ядро предоставляет уровень слябового распределения памяти (slab layer), который также называется просто слябовым распределителем памяти (slab allocator). Уровень слябового распределения памяти выполняет функции общего уровня кэширования структур данных.

Концепции слябового распределения памяти впервые были реализованы в операционной системе SunOS 5.4 фирмы Sun Microsystems [65] . Для уровня кэширования структур данных в операционной системе Linux используется такое же название и похожие особенности реализации.

Уровень слябового распределения памяти служит для достижения следующих целей.

• Часто используемые структуры данных, скорее всего, будут часто выделяться и освобождаться, поэтому их следует кэшировать.

• Частые операции выделения и освобождения памяти могут привести к фрагментации памяти (к невозможности найти большие участки физически однородной памяти). Для предотвращения этого, кэшированные списки свободных ресурсов организованы непрерывным образом в физической памяти. Так как структуры данных возвращаются снова в список свободных ресурсов, то в результате никакой фрагментации не возникает.

• Список свободных ресурсов обеспечивает улучшенную производительность при частых выделениях и освобождениях объектов, так как освобожденные объекты сразу же готовы для нового выделения.

• Если распределитель памяти может использовать дополнительную информацию, такую как размер объекта, размер страницы памяти и общий размер кэша, то появляется возможность принимать в критических ситуациях более интеллектуальные решения.

• Если кэш организован, как связанный с определенным процессором (т.е. для каждого процессора в системе используется свой уникальный отдельный кэш), то выделение и освобождение структур данных может выполняться без использования SMP-блокировок.

• Если распределитель памяти рассчитан на доступ к неоднородной памяти (Non-Uniform Memory Access NUMA), то появляется возможность выделения памяти с того же узла (node), на котором эта память запрашивается.

• Хранимые объекты могут быть "окрашены", чтобы предотвратить отображение разных объектов на одни и те же строки системного кэша.

Уровень слябового распределения памяти в ОС Linux был реализован с учетом указанных принципов.

Уровень слябового распределения памяти делит объекты на группы, которые называются кэшами (cache). Разные кэши используются для хранения объектов различных типов. Для каждого типа объектов существует свой уникальный кэш. Например, один кэш используется для дескрипторов процессов (список свободных структур

), а другой — для индексов файловых систем (). Интересно, что интерфейс построен на базе уровня слябового распределения памяти и использует семейство кэшей общего назначения.

Далее кэши делятся на слябы (буквально slab — однородная плитка, отсюда и название всей подсистемы). Слябы занимают одну или несколько физически смежных страниц памяти. Обычно сляб занимает только одну страницу памяти. Каждый кэш может содержать несколько слябов.

Каждый сляб содержит некоторое количество объектов, которые представляют собой кэшируемые структуры данных. Каждый сляб может быть в одном из трех состояний: полный (full), частично заполненный (partial) и пустой (empty). Полный сляб не содержит свободных объектов (все объекты сляба выделены для использования). Частично заполненный сляб содержит часть выделенных и часть свободных объектов. Когда некоторая часть ядра запрашивает новый объект, то этот запрос удовлетворяется из частично заполненного сляба, если такой существует. В противном случае запрос выполняется из пустого сляба. Если пустого сляба не существует, то он создается. Очевидно, что полный сляб никогда не может удовлетворить запрос, поскольку в нем нет свободных объектов. Такая политика уменьшает фрагментацию памяти.

В качестве примера рассмотрим структуры

, которые являются представлением в оперативной памяти индексов дисковых файлов (см. главу 12). Эти структуры часто создаются и удаляются, поэтому есть смысл управлять ими с помощью слябового распределителя памяти. Структуры выделяются из кэша (такое соглашение по присваиванию названий является стандартом). Этот кэш состоит из одного или более слябов, скорее всего слябов много, поскольку много объектов. Каждый сляб содержит максимально возможное количество объектов типа . Когда ядро выделяет новую структуру типа , возвращается указатель на уже выделенную, но не используемую структуру из частично заполненного сляба или, если такого нет, из пустого сляба. Когда ядру больше не нужен объект типа , то слябовый распределитель памяти помечает этот объект как свободный. На рис. 11.1 показана диаграмма взаимоотношений между кэшами, слябами и объектами.