Управление памятью по регионам - Region-based memory management

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

Пример

В качестве простого примера рассмотрим следующий код 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);

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

Реализация

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

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

История и концепции

Базовая концепция регионов очень старая, она впервые появилась еще в 1967 году в пакете бесплатного хранения AED Дугласа Т. Росса, в котором память была разделена на иерархию зон; у каждой зоны был свой распределитель, и зона могла быть освобождена сразу, что сделало зоны пригодными для использования в качестве регионов. В 1976 году стандарт PL / I включал тип данных AREA. В 1990 году Хэнсон продемонстрировал, что явные области в C (которые он назвал аренами) могут обеспечить производительность по времени на выделенный байт, превосходящую даже самый быстрый из известных механизмов распределения кучи. Явные области сыграли важную роль в разработке некоторых ранних программных проектов на основе C, включая Apache HTTP Server , который называет их пулами, и систему управления базами данных PostgreSQL , которая называет их контекстами памяти. Подобно традиционному распределению кучи, эти схемы не обеспечивают безопасность памяти ; программист может получить доступ к области после того, как она была освобождена через висящий указатель , или забыть освободить область, вызывая утечку памяти .

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

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

В ранних работах Руджери и Муртага регион создается в начале каждой функции и освобождается в конце. Затем они используют анализ потока данных, чтобы определить время жизни для каждого статического выражения распределения и назначить его самой молодой области, которая содержит все время жизни.

В 1994 году эта работа была обобщена в основополагающей работе Тофте и Талпина для поддержки полиморфизма типов и функций высшего порядка в Standard ML , языке функционального программирования , с использованием другого алгоритма, основанного на выводе типов и теоретических концепциях типов полиморфных областей и область исчисление . Их работа представила расширение лямбда-исчисления, включая регионы, добавив две конструкции:

e 1 at ρ: вычислить результат выражения e 1 и сохранить его в области ρ;
letregion ρ in e 2 end: создать область и привязать ее к ρ; оценить е 2 ; затем освободите область.

Из-за этой синтаксической структуры регионы являются вложенными , что означает, что если r 2 создается после r 1 , он также должен быть освобожден до r 1 ; в результате получается стопка регионов. Более того, регионы должны быть освобождены в той же функции, в которой они созданы. Эти ограничения были ослаблены Aiken et al.

Это расширенное лямбда-исчисление было предназначено для использования в качестве доказуемо безопасного для памяти промежуточного представления для компиляции программ стандартного машинного обучения в машинный код, но создание переводчика, который давал бы хорошие результаты в больших программах, столкнулось с рядом практических ограничений, которые необходимо было устранить с помощью новых анализ, включая обработку рекурсивных вызовов, хвостовых вызовов и удаление областей, содержащих только одно значение. Эта работа была завершена в 1995 году и интегрирована в ML Kit, версию ML, основанную на распределении регионов вместо сборки мусора. Это позволяло проводить прямое сравнение между двумя тестовыми программами среднего размера, давая сильно различающиеся результаты («в 10 раз быстрее и в четыре раза медленнее») в зависимости от того, насколько «дружественной к региону» программа была; время компиляции, однако, было порядка минут. В конечном итоге ML Kit был масштабирован для больших приложений с двумя дополнениями: схемой для раздельной компиляции модулей и гибридной техникой, сочетающей выведение области с трассировкой сборки мусора.

Обобщение на новые языковые среды

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

  • Различные расширения языка программирования C:
    • Безопасный диалект C Cyclone , который среди многих других функций добавляет поддержку явных регионов и оценивает влияние миграции существующих приложений C на их использование.
    • Было реализовано расширение для C, называемое RC, которое использует явно управляемые области, но также использует подсчет ссылок на регионы, чтобы гарантировать безопасность памяти, гарантируя, что ни одна область не будет освобождена преждевременно. Регионы уменьшают накладные расходы на подсчет ссылок, поскольку внутренние ссылки для регионов не требуют обновления счетчиков при их изменении. RC включает явную систему статических типов для регионов, которая позволяет исключить некоторые обновления счетчика ссылок.
    • Ограничение C, называемое Control-C, ограничивает программы использовать регионы (и только один регион за раз), как часть его дизайна, чтобы статически гарантировать безопасность памяти.
  • Области были реализованы для подмножества Java и стали критически важным компонентом управления памятью в Java реального времени , который объединяет их с типами владения, чтобы продемонстрировать инкапсуляцию объекта и устранить проверки во время выполнения при освобождении области. Совсем недавно была предложена полуавтоматическая система для вывода областей во встроенных приложениях Java реального времени, сочетающая статический анализ во время компиляции, политику выделения областей времени выполнения и подсказки программиста. Регионы хорошо подходят для вычислений в реальном времени, потому что их временные затраты статически предсказуемы, без сложностей, связанных с инкрементной сборкой мусора.
  • Они были реализованы для языков логического программирования Пролог и Меркурий путем расширения модели логического вывода Тофте и Талпина для поддержки отслеживания с возвратом и сокращений.
  • Управление хранилищем на основе региона используется во всем языке параллельного программирования ParaSail . Из-за отсутствия явных указателей в ParaSail нет необходимости в подсчете ссылок.

Недостатки

Системы, использующие регионы, могут испытывать проблемы, когда регионы становятся очень большими до того, как они будут освобождены, и содержат большую часть мертвых данных; их обычно называют «утечками» (даже если они в конечном итоге устраняются). Устранение утечек может включать реструктуризацию программы, как правило, путем введения новых регионов с более коротким сроком службы. Отладка этого типа проблемы особенно сложна в системах, использующих логический вывод области, где программист должен понимать лежащий в основе алгоритм вывода или исследовать подробное промежуточное представление, чтобы диагностировать проблему. Сборщики мусора трассировки более эффективны при своевременном освобождении этого типа данных без изменения программы; это было одним из оправданий для гибридных систем региона / GC. С другой стороны, отслеживание сборщиков мусора также может показывать незначительные утечки, если сохраняются ссылки на данные, которые больше никогда не будут использоваться.

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

Гибридные методы

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

использованная литература