Распространение вычислительной техники в различных сферах человеческой деятельности сопровождается развитием операционных систем. Разнообразие вычислительных устройств порождает множество типов ОС: мобильные, распределенные, реального времени, для суперкомпьютеров, для встроенных систем и другие. Стоит отметить, что это деление весьма условно — одна и та же ОС может быть отнесена к нескольким разным типам, между которыми отсутствуют четкие границы.
В общем случае современные ОС состоят из трех основных компонент: ядро, системные библиотеки, оболочка и прикладные программы. Ядро является центральной частью операционной системы, управляет ее ресурсами и процессами. Многие, на первые взгляд, совершенно различные операционные системы, такие как Android для смартфонов и Red Hat Enterprise Linux, используемый в основном на серверах, работают на одном общем ядре, пусть и с разными конфигурациями и наборами дополнительных патчей.
На данный момент операционные системы на базе ядра Linux используются повсеместно: домашние компьютеры, серверы, мобильные устройства, рабочие станции, суперкомпьютеры. В последнее десятилетие бурно развиваются дистрибутивы Linux для применения во встраиваемых системах. Новые версии ядра поддерживают широкий спектр архитектур — не только классические x86 и ARM, но и более экзотические, такие как RISC-V.
Вычислительные устройства могут в процессе работы могут сталкиваться с нехваткой оперативной памяти и простое увеличение ее объема не всегда возможно по техническим или экономическим причинам. Особенно это актуально для встраиваемых и мобильных систем, а также недорогих ноутбуков. Данную проблему можно решать и другим способом — сжатием неиспользуемых страниц памяти для экономии места в ОЗУ. В сжатом виде такие страницы занимают меньший объем и поэтому могут более компактно размещаться в некотором едином хранилище.
В зависимости от алгоритма сжатия и содержимого размер сжатой страницы может варьироваться в широких пределах, то есть в одних случаях он может почти не измениться по сравнению с размером исходной страницы, а в других — сократиться в несколько раз. С учетом того, что объекты со временем добавляются в хранилище и удаляются из него, возникает проблема фрагментации, которая способна свести на нет экономию памяти за счет сжатия. Другим крайне важным аспектом является производительность, так как при слишком низкой скорости операций со страницами из хранилища, может оказаться, что использование простой подкачки страниц будет эффективнее чем их сжатие. Для систем реального времени также стоит учитывать задержки, связанные со временем выполнения операций в худшем случае.
В данной работе будет представлен новый аллокатор, названный ztree. Главной целью при его разработке было достичь сочетания высокой плотности хранения и скорости работы, а также низких задержек.
Постановка задачи
Целью данной работы является разработка и реализация эффективного модуля ядра Linux для выделения памяти для сжатых страниц. Для достижения поставленной цели требуется решить несколько задач, которые приведены ниже.
Задачи:
> Изучить основы управления памятью в Linux
> Рассмотреть существующие решения и изучить их исходный код
> Предложить идеи для повышения эффективности аллокаторов
> Реализовать данные идеи и провести отладку кода
> Выбрать подходящие инструменты тестирования
> Провести с их помощью сравнительное тестирование реализованного модуля и существующих решений
Были изучены специализированные способы выделения памяти в ядре Linux, такие как распределитель страниц и заготовленные кэши. Использование этих методов позволяет оптимизировать процесс выделения памяти.
Основным недостатком существующих в ядре аллокаторов является медленный обход связного списка при добавлении или удалении объектов. Также zbud и z3fold оперируют отдельными страницами, что существенно ограничивает плотность хранения объектов. В случае zsmalloc дополнительными недостатками выступают зависимость от MMU и накладные расходы, связанные с модификацией таблицы страниц.
Благодаря использованию страничных блоков и красно-черных деревьев, представленный в данной работе аллокатор ztree предлагает плотность хранения данных, близкую к zsmalloc и высокую производительность.
Тесты показали, что стандартные аллокаторы могут иметь задержки при добавлении или удалении объектов, сопоставимые с задержками ввода-вывода в жестком диске. Все операции с объектами в ztree выполняются за O(log N), где N — общее число объектов в пуле. Это позволяет ограничить время выполнения операций в худшем случае по сравнению с существующими в ядре аллокаторами.
