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

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

Распределение блоков было впервые введено в ядре Solaris 2.4 Джеффом Бонвиком . ^[1] В настоящее время он широко используется во многих Unix и Unix-подобных операционных системах, включая FreeBSD. ^[2] и Линукс , ^[3] как в распределителе SLAB, так и в его замене, SLUB . ^[4]

Основа

Слябовое распределение делает редкой очень дорогостоящую практику (по времени процессора) инициализации и уничтожения объектов данных ядра, которая может перевесить затраты на выделение памяти для них. ^[1] Когда ядро часто создает и удаляет объекты, накладные расходы на инициализацию могут привести к значительному падению производительности. Кэширование объектов приводит к менее частому вызову функций, которые инициализируют состояние объекта: когда объект, выделенный слябу, освобождается после использования, система выделения сляба обычно сохраняет его в кэше (а не выполняет работу по его уничтожению), готовую для повторного использования в следующий раз. необходим объект этого типа (что позволяет избежать работы по созданию и инициализации нового объекта).

При выделении блоков кэш для объекта данных определенного типа или размера имеет несколько предварительно выделенных «блоков» памяти; внутри каждой плиты имеются фрагменты памяти фиксированного размера, подходящие для объектов. ^[5] Распределитель слябов отслеживает эти фрагменты, поэтому при получении запроса на выделение памяти для объекта данных определенного типа обычно он может удовлетворить запрос свободным слотом (чанком) из существующего сляба. Когда распределителю предлагается освободить память объекта, он просто добавляет слот в список свободных (неиспользуемых) слотов содержащего блока. Следующий вызов для создания объекта того же типа (или выделения памяти того же размера) вернет этот слот памяти (или какой-либо другой свободный слот) и удалит его из списка свободных слотов. Этот процесс устраняет необходимость поиска подходящего пространства памяти и значительно снижает фрагментацию памяти. В этом контексте плита — это одна или несколько смежных страниц в памяти, содержащих предварительно выделенные фрагменты памяти.

Выполнение

Понимание алгоритма распределения плит требует определения и объяснения некоторых терминов:

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

Когда программа настраивает кэш, она распределяет ряд объектов по панелям, связанным с этим кэшем. Это количество зависит от размера связанных плит.

Плиты могут находиться в одном из следующих состояний:

пустой – все объекты на плите помечены как свободные.
частичный – плита состоит как из использованных, так и из свободных объектов
полный — все объекты на плите помечены как использованные.

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

Распределение происходит быстро, поскольку система заранее строит объекты и легко выделяет их из плиты.

Методики реализации

Бесплатные списки

Плита представляет собой одно выделение памяти для кэша на компьютере, размер которого обычно кратен размеру страницы . Плита будет разделена на несколько записей, которые затем будут запрошены кэшем, когда клиентский код запрашивает память для новых объектов. Тогда необходимо отслеживать, какие части плиты свободны для использования, а какие уже заняты. Обычно это делается с помощью «свободных списков»: списков свободных записей в плите, готовых для хранения новых объектов.

Список свободных мест может представлять собой отдельную структуру данных, например массив индексов, указывающих, какие записи блока свободны, или он может быть встроен в блок. Linux Распределитель SLUB хранит список свободных мест как связанный список указателей, каждый из которых хранится непосредственно в области свободной памяти плиты, которую они представляют. ^[6]

Размеры плит

Операционные системы могут использовать разные размеры блоков и внутренние макеты в зависимости от размера сохраняемых объектов. Причина того, что большие плиты имеют макет, отличный от маленьких, заключается в том, что это позволяет большим плитам лучше упаковываться в единицы размера страницы, что помогает при фрагментации. Например, объекты, размер которых составляет не менее 1/8 размера страницы для данного компьютера, могут получить выгоду от размера «большой плиты» с явными свободными списками, в то время как меньшие объекты могут использовать настройку «маленькой плиты», встраивая список свободных мест. отслеживание. В оригинальной презентации Бонвика о распределителе плит уже различались компоновки больших и малых плит. ^[1]

Системы, использующие распределение плит

AmigaOS (представлена в AmigaOS 4 )
DragonFly BSD (представлен в версии 1.0)
FreeBSD (представлена в версии 5.0)
ГНУ Мах ^[7]
Хайку (представлено в альфа-версии 2)
Horizon ( Nintendo Switch ) микроядро ^[8]
HP-UX (введен в версии 11i) ^[9]
Linux (представленный в ядре 2.2, теперь это одна из трех реализаций распределителя памяти вместе с SLOB и SLUB . Эти три распределителя обеспечивают своего рода интерфейс к зональному распределительному устройству для тех разделов ядра, которые требуют более гибкого распределения памяти, чем стандартный размер страницы 4 КБ).
NetBSD (представлен в версии 4.0)
Солярис (введен в версии 2.4)
Компилятор Perl 5 использует распределитель блоков для управления внутренней памятью. ^[10]^[11]
Memcached использует выделение блоков для управления памятью
иллюзии

См. также

Примечания

^ Jump up to: ^а ^б ^с Джефф Бонвик , Распределитель блоков: распределитель памяти ядра с кэшированием объектов (1994)
^ Руководство разработчика ядра FreeBSD.
^ М. Тим Джонс, Анатомия распределителя блоков Linux. Архивировано 2 октября 2013 г. на Wayback Machine.
^ Властимил Бабка, удалите распределитель SLAB.
^ Авраам Зильбершац и др .: Концепции операционной системы . Уайли: 2004. ISBN 0-471-69466-5
^ Ламетер, Кристоф. «Распределители плит в ядре Linux: SLAB, SLOB, SLUB» (PDF) . LinuxCon/Дюссельдорф 2014 (редакция от 3 октября 2014 г.) .
^ «Документация распределителя Gnu Mach» .
^ «Безопасность консоли — переключатель (34c3)» . media.ccc.de . Проверено 28 декабря 2017 г.
^ Крис Купер и Крис Мур, Внутренние устройства HP-UX 11i , Аппер-Сэддл-Ривер, Нью-Джерси: PTR Prentice Hall, 2004, ISBN 0-13-032861-8 , с. 334 .
^ «Perl5-Porters Weekly: 17 июня 2012 г.» . Проверено 18 ноября 2012 г.
^ Бонвик, Джефф. «Журналы и Vmem: расширение распределителя блоков на множество процессоров и произвольных ресурсов» . ЮСЕНИКС 2001 . Проверено 18 ноября 2012 г.

Внешние ссылки

Страница руководства FreeBSD uma(9)
Комментарий распределителя SLUB об управлении плитами в Linux с помощью двух разных распределителей: распределителя SLUB и распределителя SLAB.
Memory Compaction v7 (набор патчей для Linux от Мела Гормана, устраняющий проблемы фрагментации и сжатия SLAB, 2 апреля 2010 г.)
Обнаружение утечек памяти ядра Джонатан Корбет, Linux Weekly News, 2006; включает комментарии пользователей по сбору мусора
Производительность Linux: не становится ли Linux слишком медленным и раздутым? О SLAB и SLUB. Журнал свободного программного обеспечения 2010.

[bonwick-1] Jump up to: ^а ^б ^с Джефф Бонвик , Распределитель блоков: распределитель памяти ядра с кэшированием объектов (1994)

[bsdman-2] Руководство разработчика ядра FreeBSD.

[jones-3] М. Тим Джонс, Анатомия распределителя блоков Linux. Архивировано 2 октября 2013 г. на Wayback Machine.

[babka-4] Властимил Бабка, удалите распределитель SLAB.

[silberschatz-5] Авраам Зильбершац и др .: Концепции операционной системы . Уайли: 2004. ISBN 0-471-69466-5

[6] Ламетер, Кристоф. «Распределители плит в ядре Linux: SLAB, SLOB, SLUB» (PDF) . LinuxCon/Дюссельдорф 2014 (редакция от 3 октября 2014 г.) .

[7] «Документация распределителя Gnu Mach» .

[8] «Безопасность консоли — переключатель (34c3)» . media.ccc.de . Проверено 28 декабря 2017 г.

[9] Крис Купер и Крис Мур, Внутренние устройства HP-UX 11i , Аппер-Сэддл-Ривер, Нью-Джерси: PTR Prentice Hall, 2004, ISBN 0-13-032861-8 , с. 334 .

[p5p-weekly-10] «Perl5-Porters Weekly: 17 июня 2012 г.» . Проверено 18 ноября 2012 г.

[Bonwick2001-11] Бонвик, Джефф. «Журналы и Vmem: расширение распределителя блоков на множество процессоров и произвольных ресурсов» . ЮСЕНИКС 2001 . Проверено 18 ноября 2012 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]