Управление памятью на основе регионов

По сравнению со стековой организацией выделения памяти, управление памяти на основе регионов позволяет более естественным путём реализовывать выделение памяти при параллельном программировании. Кроме того, регионы существенно облегчают работу с виртуализацией и различными техниками оптимизации производительности при работе с памятью, упрощая задачу по одновременному перемещению всех объектов, относящиеся к одному региону в память с более быстрым или более медленным доступом^[2].

В качестве простого примера приведём следующий код на языке C, который выделяет, а затем освобождает такую структуру данных, как связанный список:

Region *r = createRegion();ListNode *head = NULL;for (int i = 1; i <= 1000; i++) {    ListNode* newNode = allocateFromRegion(r, sizeof(ListNode));    newNode->next = head;    head = newNode;}// ...// (use list here)// ...destroyRegion(r);

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

Простые явно заданные регионы легки в реализации; следующее описание основано на статье Дэвида Хэнсона (англ.)^[3]. Каждый регион реализуется как связанный список больших блоков памяти; каждый из блоков должен быть достаточно большим, чтобы внутри него можно было выделить память для многих объектов. В структуре данных региона присутствует указатель на следующую свободную позицию внутри блока, и, если блок заполнен до конца, система управления памятью выделяет новый блок и добавляет его в список. Когда регион освобождается, указатель следующей свободной позиции сбрасывается в начало первого блока, и весь уже ранее созданный список блоков может быть повторно использован для нового размещения объектов внутри региона. В альтернативном варианте реализации, когда регион освобождается, список выделенных для него блоков может быть возвращён в глобальный список свободных блоков, из которого другие регионы могут позже выделить новые блоки. В рамках подобной простой схемы, однако, невозможно индивидуально освобождать память от конкретных объектов внутри блока.

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

Сама концепция регионов весьма стара. Впервые она была реализована в 1967 году в пакете Дугласа Росса^[en] AED free storage, в котором память была разделена на иерархию зон. Для каждой из зон дисциплина управления памятью могла быть настроена индивидуально. Каждая из зон могла быть освобождена одной общей операцией. Таким образом, в этом программном пакете Росс впервые реализовал концепцию управления памяти на основе регионов практически^[4]. В 1976 в стандарт языка PL/I был включён тип данных AREA, предназначенный для группового управления структурами данных^[5]. В 1990 году Хансон продемонстрировал, что явно определяемые области в языке C (которые он назвал аренами) при управлении памятью могут обеспечить производительность, измеряемую как время, затрачиваемое на один выделенный байт, превосходящую даже самый быстрый из известных механизмов распределения кучи^[3]. Явно выделяемые регионы сыграли важную роль в разработке ряда ранних программных проектов на основе C, включая Apache HTTP Server, в котором их называют пулами, и СУБД PostgreSQL, в которой их называют контекстами памяти^[6]. Подобно традиционному распределению через кучу, эти схемы не обеспечивают безопасность доступа к памяти; программист может получить доступ к области памяти после её освобождения через висячую ссылку или забыть об освобождении области, что приводит к утечке памяти.

Вывод регионов

В 1988 году учёные начали исследовать, как использовать регионы для безопасного выделения памяти, введя концепцию вывода регионов. В рамках этой техники директивы на выделение и освобождение регионов, а также отдельных размещаемых в памяти объектов, статически привязываемых к конкретному региону, компилятор вставляет в код на этапе компиляции. Компилятор умеет сделать это таким образом, что можно гарантировать отсутствие висячих указателей и утечек памяти. В ранней работе Ruggieri и Murtagh исследовали вариант этой техники, при котором регион создаётся при выполнении каждой функции и освобождается после окончания её работы^[7]. При этом они использовали анализ потоков данных, чтобы определить время жизни для каждого статически распределённого в память объекта, и, затем, назначить этот объект для распределения в самый младший по времени создания регион, который содержит объекты с таким временем жизни. В 1994 эта работа была обобщена в оригинальной работе Tofte и Talpin, которые расширили технику, предложенную Ruggieri и Murtagh, для поддержки полиморфизма типов и функций высшего порядка в функциональном языке программирования Standard ML. В работе Tofte и Talpin был использован другой алгоритм, основанный на выводе типов и теоретических концепциях типов регионов и исчисления регионов^[8][9]. Ими было предложено расширение лямбда-исчисления, включающее в него регионы, как особую сущность. Фактически, к лямбда-исчислению ими были добавлены следующие две конструкции:

e₁ at ρ: вычислить результат выражения e₁ и сохранить его в регионе ρ;

letregion ρ in e2 end: создать регион и связать его с ρ; вычислить e₂, затем освободить регион.

Из-за такой синтаксической структуры регионы являются «вложенными», что означает, что если r₂ создаётся после r₁ , он также должен быть освобождён до r₁. В результате получается «стек» регионов. Более того, регионы должны быть освобождены в той же функции, в которой они созданы. Ограничения были частично смягчены в работе Aiken и др.^[10]

Это расширенное лямбда-исчисление предназначалось для того, чтобы служить доказуемо безопасным с точки зрения работы с памятью промежуточным представлением для компиляции программ Standard ML в машинный код. Однако создание транслятора, который мог бы давать хорошие результаты для больших программ, столкнулось с рядом практических ограничений. Они должны были решаться с помощью нового анализа, в том числе работы с рекурсивными вызовами, вызовами с хвостовой рекурсией и устранением из генерируемого промежуточного представления регионов, содержащих только одно значение. Эта работа была завершена в 1995 году^[11]. Её результаты были использованы ML Kit, версии ML, работа с памятью в которой была основана на регионах, вместо сборки мусора. Появление ML Kit позволило провести прямое сравнение между двумя вариантами компиляции тестовых программ среднего размера, что дало сильно различающиеся результаты («в 10 раз быстрее и в четыре раза медленнее») в зависимости от того, насколько «дружественной к регионам» была конкретная тестовая программа^[12]. ML Kit был в конечном итоге масштабирован для больших приложений. В нём были реализованы два дополнения: раздельная компиляция модулей и гибридная техника, сочетающая вывод границ региона с обычной сборкой мусора.^[13][14]

Реализация концепции в других языках программирования

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

• В различных расширениях языка программирования C:
  • В безопасном диалекте языка C Cyclone, в который, помимо многих других функций, была добавлена поддержка явно заданных регионов. Этот язык был во многом ориентирован на миграцию существующих приложений на C и их доработку для использования регионов^[15][16][17].
  • В расширении C, названном RC, также были реализованы явно задаваемые регионы^[18]. Но в этом языке был использован подсчёт ссылок по регионам, чтобы дополнительно гарантировать безопасность памяти, контролируя, что ни один регион не будет освобождён преждевременно^[19][20]. Регионы уменьшают накладные расходы на подсчёт ссылок, поскольку внутренние ссылки на регионы не требуют обновления счётчиков при их изменении. RC включает в себя явную статическую систему типов для регионов, которая позволяет исключить некоторые обновления счётчика ссылок^[21].
  • Подмножество C, называемое Control-C, требует от программ использовать регионы (и только одного региона в каждый конкретный момент времени выполнения). Эти ограничения рассматриваются авторами языка как часть его конструкции, предназначенной для статического обеспечения безопасности памяти^[22].
• Регионы были реализованы для подмножества Java^[23] и стали критически важным компонентом управления памятью в языке Realtime Java, который объединяет их с типами владения для контроля инкапсуляции объектов и устранения проверок во время выполнения для освобождения региона^[24][25][26]. Совсем недавно была предложена полуавтоматическая система для определения регионов во встроенных Java-приложениях реального времени, сочетающая статический анализ во время компиляции, управляемые политики выделения регионов во время выполнения и хинты (подсказки) программиста компилятору^[27][28].Регионы хорошо подходят для вычислений в реальном времени, потому что временные затраты на их поддержку являются статически предсказуемыми, и намного более простыми, чем в традиционных сборщиках мусора.
• Регионы были реализованы для языков логического программирования Prolog^[29][30] и Mercury^[31][32]; в этих реализациях модель вывода регионов Tofte и Talpin была расширена для бэктрекинга и прологовских операторов cut^[en].
• Управление памятью на основе регионов используется в языке параллельного программирования ParaSail^[en]. В силу отсутствия явных указателей в ParaSail^[33] при реализации управления памятью в нём нет необходимости в дополнительном механизме подсчёте ссылок.

Системы, использующие регионы, могут испытывать проблемы, когда регионы становятся очень большими, прежде чем они будут освобождены, и поэтому содержат большую долю мёртвых данных. Такие регионы принято называть «утечками памяти» (хотя они, в конечном итоге, всё же освобождаются). Устранение этих утечек может требовать реструктуризации программы. Она обычно производится путём добавления новых регионов с более коротким сроком службы. Отладка такого типа проблем особенно трудна в системах, использующих вывод регионов, при котором программист должен понять алгоритм логического вывода, лежащий на более низком уровне системы или подробно разбирать промежуточное представление, чтобы диагностировать проблему. Отладка программ при использовании традиционных сборщиков мусора намного проще, а своевременного освобождения памяти, попадающей в утечки, можно добиться без реструктуризации программы, просто за счёт устранения логических ошибок в её построении. Эти соображения повлекли за собой появление гибридных систем, сочетающих управление памятью на основе регионов и обычную сборку мусора^[13]. С другой стороны, при отладке программ со сборкой мусора также могут наблюдаться утечки, если сохраняются ссылки на данные, которые никогда не будут использоваться снова и это обстоятельство программисту приходится отслеживать значительно внимательнее, чем в системе с управлением памятью на основе регионов.

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

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