3 Уровни области подкачки

Страницы с собственными данными первоначально являются страницами, копируемыми при записи или заполняемыми нулями. Когда выполняется изменение, и, соответственно, копирование, начальное хранилище объекта (обычно файл) не может больше использоваться для хранения копии страницы, когда VM-системе нужно использовать ее повторно для других целей. В этот момент на помощь приходит область подкачки. Область подкачки выделяется для организации хранилища памяти, которая иначе не может быть доступна. FreeBSD создает структуру управления подкачкой для объекта VM, только когда это действительно нужно. Однако структура управления подкачкой исторически имела некоторые проблемы.

Во FreeBSD 3.X в структуре управления областью подкачки предварительно выделяется массив, который представляет целый объект, требующий хранения в области подкачки--даже если только несколько страниц этого объекта хранятся в области подкачки. Это создает проблему фрагментации памяти ядра в случае, когда в память отображаются большие объекты или когда ветвятся процессы, занимающие большой объем памяти при работе (RSS). Также для отслеживания памяти подкачки в памяти ядра поддерживается ``список дыр'', и он также несколько фрагментирован. Так как ``список дыр'' является последовательным списком, то производительность при распределении и высвобождении памяти в области подкачки неоптимально и ее сложность зависит от количества страниц как O(n). Также в процессе высвобождения памяти в области подкачки требуется выделение памяти в ядре, и это приводит к проблемам блокировки при недостатке памяти. Проблема еще более обостряется из-за дыр, создаваемых по чередующемуся алгоритму. Кроме того, список распределения блоков в области подкачки легко оказывается фрагментированной, что приводит к распределению непоследовательных областей. Память ядра также должна распределяться по ходу работы для дополнительных структур по управлению областью подкачки при выгрузке страниц памяти в эту область. Очевидно, что мест для усовершенствований предостаточно.

Во FreeBSD 4.X подсистема управления областью подкачки была полностью переписана мною. При этом структуры управления областью подкачки распределяются при помощи хэш-таблицы, а не через линейный массив, что дает им фиксированный размер при распределении и работу с гораздо меньшими структурами. Вместо того, чтобы использовать однонаправленный связный список для отслеживания выделения пространства в области подкачки, теперь используется побитовая карта блоков области подкачки, выполненная в основном в виде древовидной структуры с информацией о свободном пространстве, находящейся в узлах структур. Это приводит к тому, что выделение и высвобождение памяти в области подкачки становится операцией сложности O(1). Все дерево также распределяется заранее для того, чтобы избежать распределения памяти ядра во время операций с областью подкачки при критически малом объеме свободной памяти. В конце концов, система обращается к области подкачки при нехватке памяти, так что мы должны избежать распределения памяти ядра в такие моменты для избежания потенциальных блокировок. Наконец, для уменьшения фрагментации дерево может распределять большой последовательный кусок за раз, пропуская меньшие фрагментированные области. Я не сделал последний шаг к заведению ``указателя на распределение'', который будет передвигаться по участку области подкачки при выделении памяти для обеспечения в будущем распределения последовательных участков, или по крайней мере местоположения ссылки, но я убежден, что это может быть сделано.