Войти
В информатике, регион- Управление памятью на основе представляет собой тип управления памятью, в котором каждый выделенный объект назначается области области . Область, также называемая зоной, ареной, областью или контекстом памяти, представляет собой набор выделенных объектов, которые могут быть эффективно освобождены все сразу. Как и выделение стека, области облегчают выделение и освобождение памяти с низкими накладными расходами; но они более гибкие, позволяя объектам жить дольше, чем кадр стека, в котором они были размещены. В типичных реализациях все объекты в области выделяются в едином непрерывном диапазоне адресов памяти, аналогично тому, как обычно выделяются кадры стека.
В качестве простого примера рассмотрим следующий код C, который выделяет, а затем освобождает структуру данных связанного списка :
Регион * r = createRegion (); ListNode * head = NULL; for (int i = 1; i <= 1000; i++) { ListNode* newNode = allocateFromRegion(r, sizeof(ListNode)); newNode->next = head; head = newNode;} //... // (используйте здесь список) //... destroyRegion (r);Хотя для этого потребовалось много операций Чтобы создать связанный список, его можно быстро уничтожить за одну операцию, уничтожив область, в которой были выделены узлы. Нет необходимости перемещаться по списку.
Простое явное регионы просты в реализации; нижеследующее описание основано на Хансоне. Каждая область реализована как связанный список больших блоков памяти; каждый блок должен быть достаточно большим, чтобы обслуживать множество распределений. Текущий блок поддерживает указатель на следующую свободную позицию в блоке, и если блок заполнен, новый выделяется и добавляется в список. Когда область освобождается, указатель следующей свободной позиции сбрасывается на начало первого блока, и список блоков можно повторно использовать для создания следующей области. В качестве альтернативы, когда область освобождается, ее список блоков может быть e добавляется к глобальному списку фрилансеров, из которого другие регионы могут позже выделить новые блоки. В этой простой схеме невозможно освободить отдельные объекты в регионах.
Общая стоимость выделенного байта этой схемы очень мала; почти все выделения включают только сравнение и обновление указателя следующей свободной позиции. Освобождение региона - это операция с постоянным временем, которая выполняется редко. В отличие от типичных систем сборки мусора, нет необходимости маркировать данные их типом.
Основная концепция регионов очень старая, впервые появившись еще в 1967 году в пакете бесплатного хранения AED Дугласа Т. Росса, в котором память была разделена на иерархию зон. ; у каждой зоны был свой распределитель, и зона могла быть освобождена сразу, что делало зоны доступными для использования в качестве регионов. В 1976 году стандарт PL / I включал тип данных AREA. В 1990 году Хэнсон продемонстрировал, что явные области в C (которые он назвал аренами) могут обеспечить производительность по времени на выделенный байт, превосходящую даже самый быстрый из известных механизмов распределения кучи. Явные области сыграли важную роль в разработке ряда ранних программных проектов на основе C, включая HTTP-сервер Apache, который называет их пулами, и систему управления базами данных PostgreSQL, которая вызывает им контексты памяти. Подобно традиционному распределению в куче, эти схемы не обеспечивают безопасность памяти ; программист может получить доступ к области после ее освобождения с помощью висящего указателя или забыть освободить область, что вызовет утечку памяти.
В 1988 году исследователи начали исследовать, как использовать регионы для безопасного распределения памяти, введя концепцию вывода регионов, где создание и освобождение регионов, а также присвоение отдельных статических выражений распределения определенным регионам, вставляется компилятором во время компиляции. Компилятор может сделать это таким образом, чтобы гарантировать отсутствие зависших указателей и отсутствие утечек.
В ранней работе Руджиери и Муртага регион создается в начале каждой функции и освобождается в конце. Затем они используют анализ потока данных, чтобы определить время жизни для каждого выражения статического распределения и присвоить его самой молодой области, которая содержит все время жизни.
В 1994 году эта работа была обобщена в основополагающей работе Тофте и Талпина для поддержки полиморфизма типов и функций высшего порядка в Стандартном ML, язык функционального программирования, использующий другой алгоритм, основанный на выводе типа и теоретических концепциях полиморфизма и. Их работа представила расширение лямбда-исчисления, включая области, добавив две конструкции:
Из-за этой синтаксической структуры области вложены, что означает, что если r 2 создается после r 1, он также должен быть освобожден до r 1 ; в результате получается стопка регионов. Более того, регионы должны быть освобождены в той же функции, в которой они созданы. Эти ограничения были ослаблены Айкеном и др.
. Это расширенное лямбда-исчисление было предназначено для использования в качестве доказуемо безопасного для памяти промежуточного представления для компиляции стандартных программ машинного обучения в машинный код, но для создания транслятора Это дало бы хорошие результаты в больших программах, столкнувшись с рядом практических ограничений, которые необходимо было устранить с помощью новых анализов, включая работу с рекурсивными вызовами, хвостовыми рекурсивными вызовами и устранение областей, содержащих только одно значение. Эта работа была завершена в 1995 году и интегрирована в ML Kit, версию ML, основанную на распределении регионов вместо сборки мусора. Это позволило провести прямое сравнение между двумя тестовыми программами среднего размера, что дало сильно различающиеся результаты («в 10 раз быстрее и в четыре раза медленнее») в зависимости от того, насколько «дружественной к региону» программа была; время компиляции, однако, было порядка минут. В конечном итоге ML Kit был расширен до больших приложений с двумя дополнениями: схемой для раздельной компиляции модулей и гибридной техникой, сочетающей выведение области с трассировкой сборки мусора.
После разработки ML Kit области начали распространяться на другие языковые среды:
Системы, использующие регионы, могут испытывать проблемы, когда регионы становятся очень большими до того, как они будут освобождены, и содержат большую часть мертвых данные; их обычно называют «утечками» (даже если они в конечном итоге устраняются). Устранение утечек может включать реструктуризацию программы, как правило, путем введения новых регионов с более коротким сроком службы. Отладка этого типа проблем особенно трудна в системах, использующих логический вывод области, где программист должен понимать лежащий в основе алгоритм вывода или исследовать подробное промежуточное представление, чтобы диагностировать проблему. Сборщики мусора трассировки более эффективны при своевременном освобождении этого типа данных без изменения программы; это было одним из оправданий для гибридных систем региона / GC. С другой стороны, отслеживание сборщиков мусора также может показывать незначительные утечки, если сохраняются ссылки на данные, которые больше никогда не будут использоваться.
Управление памятью на основе регионов работает лучше всего, когда количество регионов относительно невелико, и каждая из них содержит много объектов; программы, содержащие много разреженных областей, будут демонстрировать внутреннюю фрагментацию, что приведет к потере памяти и дополнительным затратам времени на управление областями. Опять же, при наличии определения региона эту проблему может быть труднее диагностировать.
Как упоминалось выше, RC использует гибрид регионов и подсчет ссылок, ограничивая накладные расходы на подсчет ссылок, поскольку внутренние ссылки на регионы не требуют подсчета обновляться при изменении. Точно так же некоторые гибридные методы маркировки области объединяют сборку мусора трассировки с областями; они работают, разделяя кучу на регионы, выполняя проход по меткам, в котором помечаются все регионы, содержащие живые объекты, и затем освобождая все немаркированные области. Для сохранения эффективности требуется постоянная дефрагментация.
