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

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

Пример

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

Область, край *р = createRegion();ListNode *голова = НОЛЬ;за (int я = 1; я <= 1000; я++) {    ListNode* newNode = allocateFromRegion(р, размер(ListNode));    newNode->следующий = голова;    голова = newNode;}// ...// (используйте здесь список)// ...destroyRegion(р);

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

Выполнение

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

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

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

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

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

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

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

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

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

Благодаря такой синтаксической структуре регионы вложенный, что означает, что если r2 создается после r1, он также должен быть освобожден до r1; в результате куча регионов. Более того, регионы должны быть освобождены в той же функции, в которой они созданы. Эти ограничения были ослаблены Aiken et al.[8]

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

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

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

  • Различные расширения к Язык программирования C:
    • Безопасный диалект C Циклон, который среди многих других функций добавляет поддержку явных регионов и оценивает влияние миграции существующих приложений C для их использования.[13][14][15]
    • Расширение C под названием RC[16] был реализован, который использует явно управляемые регионы, но также использует подсчет ссылок на регионах, чтобы гарантировать безопасность памяти, гарантируя, что ни одна область не будет освобождена преждевременно.[17][18] Регионы уменьшают накладные расходы на подсчет ссылок, поскольку внутренние ссылки на регионы не требуют обновления счетчиков при их изменении. RC включает явную систему статических типов для регионов, которая позволяет исключить некоторые обновления счетчика ссылок.[19]
    • Ограничение C, называемое Control-C, ограничивает программы использовать регионы (и только один регион за раз), как часть его дизайна, чтобы статически гарантировать безопасность памяти.[20]
  • Регионы были реализованы для подмножества Ява,[21] и стал важным компонентом управления памятью в Java в реальном времени, который объединяет их с формы собственности чтобы продемонстрировать инкапсуляцию объекта и исключить проверки во время выполнения при освобождении области.[22][23][24] Совсем недавно была предложена полуавтоматическая система для вывода областей во встроенных Java-приложениях реального времени, сочетающая статический анализ во время компиляции, политику выделения областей времени выполнения и подсказки программиста.[25][26] Регионы подходят для вычисления в реальном времени потому что их временные затраты статически предсказуемы, без сложностей, связанных с добавочной сборкой мусора.
  • Они были реализованы для логическое программирование языки Пролог[27][28] и Меркурий[29][30] путем расширения модели логического вывода Тофте и Талпина для поддержки поиска с возвратом и сокращений.
  • Управление хранилищем на основе региона используется во всем язык параллельного программирования ParaSail. Из-за отсутствия явных указателей в ParaSail,[31] нет необходимости в подсчете ссылок.

Недостатки

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

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

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

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

Рекомендации

  1. ^ а б Хэнсон, Дэвид Р. (1989). «Быстрое выделение и освобождение памяти в зависимости от времени жизни объекта». Программное обеспечение: практика и опыт. 20 (1): 5–12. Дои:10.1002 / spe.4380200104. S2CID  8960945. Архивировано из оригинал на 2012-10-20.
  2. ^ Росс, Дуглас (1967). «Пакет бесплатного хранения AED». Коммуникации ACM. 10 (8): 481–492. Дои:10.1145/363534.363546. S2CID  6572689.
  3. ^ Американский национальный институт стандартов, Inc. (1976). Американский национальный стандартный язык программирования PL / I.
  4. ^ 2010 Группа глобального развития PostgreSQL (1996). «Раздел 41.3: Управление памятью». Документация по PostgreSQL 8.2.15. Получено 22 февраля 2010.
  5. ^ Руджери, Кристина; Муртаг, Томас П. (1988). «Анализ времени жизни динамически размещаемых объектов». POPL '88: Материалы 15-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. Дои:10.1145/73560.73585. Получено 22 февраля 2010.
  6. ^ Тофте, Мадс; Жан-Пьер Тальпен (1993). Теория размещения стека в языках с полиморфными типами (Технический отчет). Департамент компьютерных наук Копенгагенского университета. 93/15. На Citeseer
  7. ^ Тофте, Мадс; Талпин, Жан-Пьер (1994). «Реализация типизированного λ-исчисления вызова по значению с использованием стека регионов». POPL '94: Материалы 21-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 188–201. Дои:10.1145/174675.177855. ISBN  0-89791-636-0. Получено 15 апреля 2014.
  8. ^ Айкен, Алекс; Мануэль Фендрих, Раф Левиен (1995). Лучшее управление статической памятью: улучшение регионально-ориентированного анализа языков высшего порядка (Технический отчет). Департамент EECS, Калифорнийский университет, Беркли. UCB / CSD-95-866. На Citeseer
  9. ^ Биркедал, Ларс; Тофте, Мадс; Вейлструп, Магнус (1996). «От вывода области к машинам фон Неймана через вывод представления области». POPL '96: Материалы 23-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 171–183. Дои:10.1145/237721.237771. ISBN  0-89791-769-3. Получено 22 февраля 2010.
  10. ^ Тофте, Мэдс; Биркедал, Ларс; Эльсман, Мартин; Халленберг, Нильс (2004). «Ретроспектива управления памятью на основе регионов». Символьные вычисления более высокого порядка. 17 (3): 245–265. Дои:10.1023 / B: LISP.0000029446.78563.a4. ISSN  1388-3690.
  11. ^ а б Халленберг, Нильс; Эльсман, Мартин; Тофте, Мэдс (2003). «Объединение вывода региона и сборки мусора». Уведомления SIGPLAN. 37 (5): 141–152. Дои:10.1145/543552.512547. ISSN  0362-1340.
  12. ^ Эльсман, Мартин (2003). «Безопасность сборки мусора для управления памятью на основе регионов». Уведомления SIGPLAN. 38 (3): 123–134. CiteSeerX  10.1.1.57.8914. Дои:10.1145/640136.604190. ISSN  0362-1340.
  13. ^ «Циклон: знакомство с регионами». Циклон Руководство пользователя. Получено 22 февраля 2010.
  14. ^ Гроссман, Дэн; Моррисетт, Грег; Джим, Тревор; Хикс, Майкл; Ван, Яньлин (2002). «Региональное управление памятью в циклоне». Уведомления SIGPLAN. 37 (5): 282–293. Дои:10.1145/543552.512563.
  15. ^ Хикс, Майкл; Моррисетт, Грег; Гроссман, Дэн (2004). «Опыт безопасного ручного управления памятью в циклоне». ISMM '04: Материалы 4-го международного симпозиума по управлению памятью. Нью-Йорк, Нью-Йорк, США: ACM. С. 73–84. Дои:10.1145/1029873.1029883. ISBN  1-58113-945-4. Получено 22 февраля 2010.
  16. ^ Гей, Дэвид (1999). "RC - безопасное региональное управление памятью для C". Домашняя страница Дэвида Гэя. Intel Labs Беркли. Архивировано из оригинал 26 февраля 2009 г.. Получено 22 февраля 2010.
  17. ^ Гей, Дэвид; Айкен, Алекс (1998). «Управление памятью с явными регионами». PLDI '98: Материалы конференции ACM SIGPLAN 1998 по разработке и реализации языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 313–323. Дои:10.1145/277650.277748. ISBN  0-89791-987-4. Получено 22 февраля 2010.
  18. ^ Гей, Дэвид Эдвард (2001). Управление памятью с явными регионами (PDF) (Докторская диссертация по информатике). Калифорнийский университет в Беркли. Получено 20 февраля 2010.
  19. ^ Гей, Дэвид; Айкен, Алекс (2001). «Языковая поддержка регионов». Уведомления SIGPLAN. 36 (5): 70–80. CiteSeerX  10.1.1.650.721. Дои:10.1145/381694.378815. ISSN  0362-1340.
  20. ^ Ковшик, Сумант; Дурджати, Динакар; Адве, Викрам (2002). «Обеспечение безопасности кода без проверок во время выполнения для систем управления в реальном времени». CASES '02: Материалы международной конференции 2002 г. по компиляторам, архитектуре и синтезу для встроенных систем. Нью-Йорк, Нью-Йорк, США: ACM. С. 288–297. Дои:10.1145/581630.581678. ISBN  1-58113-575-0. Получено 22 февраля 2010.
  21. ^ Кристиансен, Мортен В. (1998). Управление памятью на основе регионов в Java (Диплом магистра компьютерных наук). Департамент компьютерных наук (DIKU) Копенгагенского университета. Получено 20 февраля 2010.[постоянная мертвая ссылка ]
  22. ^ Биби, Уильям С .; Ринард, Мартин К. (2001). «Реализация памяти с ограниченным объемом памяти для Java в реальном времени». EMSOFT '01: Материалы Первого международного семинара по встроенному ПО. Лондон, Великобритания: Springer-Verlag. С. 289–305. ISBN  3-540-42673-6. Получено 22 февраля 2010.[постоянная мертвая ссылка ]
  23. ^ Сэлчану, Александру; Чандрасекхар Бояпати, Уильям Биби-младший, Мартин Ринард (2003). Система типов для безопасного управления памятью на основе регионов в Java в реальном времени (PDF) (Технический отчет). Лаборатория компьютерных наук Массачусетского технологического института. MIT-LCS-TR-869.CS1 maint: несколько имен: список авторов (связь)
  24. ^ Бояпати, Чандрасекар; Сальчиану, Александру; Биби младший, Уильям (2003). «Типы владения для безопасного управления памятью на основе регионов в Java в реальном времени». PLDI '03: Материалы конференции ACM SIGPLAN 2003 по разработке и реализации языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 324–337. Дои:10.1145/781131.781168. ISBN  1-58113-662-5. Получено 22 февраля 2010.
  25. ^ Накли, Чакер; Рипперт, Кристоф; Саланьяк, Гийом; Йовин, Серджио (2007). «Эффективное управление памятью на основе регионов для встраиваемых систем реального времени с ограниченными ресурсами» (PDF). Материалы «Практикума по реализации, компиляции, оптимизации объектно-ориентированных языков, программ и систем (ICOOOLPS'2006)». Получено 22 февраля 2010.
  26. ^ Саланьяк, Гийом; Рипперт, Кристоф (2007). «Полуавтоматическое управление памятью на основе областей для встроенных систем Java в реальном времени». RTCSA '07: Материалы 13-й международной конференции IEEE по встроенным вычислительным системам и приложениям реального времени. Вашингтон, округ Колумбия, США: Компьютерное общество IEEE. С. 73–80. Дои:10.1109 / RTCSA.2007.67. ISBN  978-0-7695-2975-2.
  27. ^ Махольм, Хеннинг (2000). Управление памятью на основе регионов в Prolog (PDF) (Магистр информатики). Копенгагенский университет, Дания. Архивировано из оригинал (PDF) 5 июня 2011 г.. Получено 20 февраля 2010.
  28. ^ Махольм, Хеннинг (2000). "Региональный менеджер памяти для пролога". ISMM '00: Материалы 2-го международного симпозиума по управлению памятью. Нью-Йорк, Нью-Йорк, США: ACM. С. 25–34. Дои:10.1145/362422.362434. ISBN  1-58113-263-8. Получено 22 февраля 2010.
  29. ^ Фан, Куан; Янссенс, Герда (2007). Анализ статической области для Меркурия. Конспект лекций по информатике: логическое программирование. Конспект лекций по информатике. 4670/2007. Springer Berlin / Heidelberg. С. 317–332. Дои:10.1007/978-3-540-74610-2. ISBN  978-3-540-74608-9. ISSN  1611-3349.
  30. ^ Фан, Куан; Сомоги, Золтан (2008). «Поддержка во время выполнения для управления памятью на основе регионов в Mercury». ISMM '08: Материалы 7-го международного симпозиума по управлению памятью. Нью-Йорк, Нью-Йорк, США: ACM. С. 61–70. Дои:10.1145/1375634.1375644. ISBN  978-1-60558-134-7. Получено 15 апреля 2014.
  31. ^ Тафт, Такер (2012). «Путь без указателя к объектно-ориентированному параллельному программированию». Блог ParaSail. Получено 14 сентября 2012.
  32. ^ Блэкберн, Стивен М.; МакКинли, Кэтрин С. (2008). «Immix: сборщик мусора в области маркировки с эффективностью использования пространства, быстрой сборкой и производительностью мутатора». PLDI '08: Материалы конференции ACM SIGPLAN 2008 года по разработке и реализации языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 22–32. Дои:10.1145/1375581.1375586. ISBN  978-1-59593-860-2. Получено 15 апреля 2014.