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

Управление памятью на основе регионов — способ управления памятью, при котором каждый создаваемый в памяти объект приписывается к определённому «региону».

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

Преимущества

[править | править код]

По сравнению со стековой организацией выделения памяти, управление памяти на основе регионов позволяет более естественным путём реализовывать выделение памяти при параллельном программировании. Кроме того, регионы существенно облегчают работу с виртуализацией и различными техниками оптимизации производительности при работе с памятью, упрощая задачу по одновременному перемещению всех объектов, относящиеся к одному региону в память с более быстрым или более медленным доступом[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 году в пакете Дугласа Росса[англ.] 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]. Ими было предложено расширение лямбда-исчисления, включающее в него регионы, как особую сущность. Фактически, к лямбда-исчислению ими были добавлены следующие две конструкции:

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

Из-за такой синтаксической структуры регионы являются «вложенными», что означает, что если r2 создаётся после r1 , он также должен быть освобождён до r1. В результате получается «стек» регионов. Более того, регионы должны быть освобождены в той же функции, в которой они созданы. Ограничения были частично смягчены в работе 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[англ.].
  • Управление памятью на основе регионов используется в языке параллельного программирования ParaSail[англ.]. В силу отсутствия явных указателей в ParaSail[33] при реализации управления памятью в нём нет необходимости в дополнительном механизме подсчёте ссылок.

Недостатки

[править | править код]

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

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

Гибридные техники

[править | править код]

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

Примечания

[править | править код]
  1. ↑ в русских источниках этот термин почти не употребляется
  2. ↑ Это может быть необходимо, например, для того, чтобы поместить все объекты, относящиеся к конкретному экземпляру параллельно выполняемой процедуры в раздел памяти, близкий конкретному процессору многопроцессорной системы.
  3. ↑ 1 2 Hanson, David R. Fast allocation and deallocation of memory based on object lifetimes (англ.) // Software: Practice and Experience : journal. — 1989. — Vol. 20, no. 1. — P. 5—12. — doi:10.1002/spe.4380200104. Архивировано 20 октября 2012 года.
  4. ↑ Ross, Douglas. The AED free storage package (англ.) // Communications of the ACM. — 1967. — Vol. 10, no. 8. — P. 481—492. — doi:10.1145/363534.363546.
  5. ↑ American National Standards Institute, inc. American National Standard Programming Language PL/I (англ.). — 1976.
  6. ↑ 2010 PostgreSQL Global Development Group. Section 41.3: Memory Management. PostgreSQL 8.2.15 Documentation (1996). Дата обращения: 22 февраля 2010. Архивировано 12 февраля 2010 года.
  7. ↑ Ruggieri, Cristina; Murtagh, Thomas P. (1988). "Lifetime analysis of dynamically allocated objects". POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. doi:10.1145/73560.73585. Дата обращения: 22 февраля 2010.
  8. ↑ Tofte, Mads; Jean-Pierre Talpin (1993). A Theory of Stack Allocation in Polymorphically Typed Languages (Technical report). Department of Computer Science, Copenhagen University. 93/15. On Citeseer Архивировано 21 июня 2007 года.
  9. ↑ Tofte, Mads; Talpin, Jean-Pierre (1994). "Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions". POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 188—201. doi:10.1145/174675.177855. ISBN 0-89791-636-0. Архивировано 4 июля 2014. Дата обращения: 15 апреля 2014.
  10. ↑ Aiken, Alex; Manuel Fähndrich, Raph Levien (1995). Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages (Technical report). EECS Department, University of California, Berkeley. UCB/CSD-95-866. On Citeseer Архивировано 21 июня 2007 года.
  11. ↑ Birkedal, Lars; Tofte, Mads; Vejlstrup, Magnus (1996). "From region inference to von Neumann machines via region representation inference". POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 171—183. doi:10.1145/237721.237771. ISBN 0-89791-769-3. Дата обращения: 22 февраля 2010.
  12. ↑ Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels. A Retrospective on Region-Based Memory Management // Higher Order Symbolic Computing. — 2004. — Т. 17, № 3. — С. 245–265. — ISSN 1388-3690. — doi:10.1023/B:LISP.0000029446.78563.a4.
  13. ↑ 1 2 Hallenberg, Niels; Elsman, Martin; Tofte, Mads. Combining region inference and garbage collection // SIGPLAN Notices. — 2003. — Т. 37, № 5. — С. 141–152. — ISSN 0362-1340. — doi:10.1145/543552.512547.
  14. ↑ Elsman, Martin. Garbage collection safety for region-based memory management (англ.) // SIGPLAN Notices : journal. — 2003. — Vol. 38, no. 3. — P. 123–134. — ISSN 0362-1340. — doi:10.1145/640136.604190.
  15. ↑ Cyclone: Introduction to Regions. Cyclone User Manual. Дата обращения: 22 февраля 2010. Архивировано 21 августа 2010 года.
  16. ↑ Grossman, Dan; Morrisett, Greg; Jim, Trevor; Hicks, Michael; Wang, Yanling. Region-based memory management in cyclone // SIGPLAN Notices. — 2002. — Т. 37, № 5. — С. 282–293. — doi:10.1145/543552.512563.
  17. ↑ Hicks, Michael; Morrisett, Greg; Grossman, Dan (2004). "Experience with safe manual memory-management in cyclone". ISMM '04: Proceedings of the 4th international symposium on Memory management. New York, NY, USA: ACM. pp. 73—84. doi:10.1145/1029873.1029883. ISBN 1-58113-945-4. Дата обращения: 22 февраля 2010.
  18. ↑ Gay, David RC - Safe, region-based memory-management for C. David Gay's homepage. Intel Labs Berkeley (1999). Дата обращения: 22 февраля 2010. Архивировано из оригинала 26 февраля 2009 года.
  19. ↑ Gay, David; Aiken, Alex (1998). "Memory management with explicit regions". PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation. New York, NY, USA: ACM. pp. 313—323. doi:10.1145/277650.277748. ISBN 0-89791-987-4. Дата обращения: 22 февраля 2010.
  20. ↑ Gay, David Edward (2001). Memory management with explicit regions (PDF) (PhD in Computer Science thesis). University of California at Berkeley. Архивировано (PDF) 7 сентября 2019. Дата обращения: 20 февраля 2010.
  21. ↑ Gay, David[англ.]; Aiken, Alex[англ.]. Language support for regions // SIGPLAN Notices. — 2001. — Т. 36, № 5. — С. 70–80. — ISSN 0362-1340. — doi:10.1145/381694.378815.
  22. ↑ Kowshik, Sumant; Dhurjati, Dinakar; Adve, Vikram (2002). "Ensuring code safety without runtime checks for real-time control systems". CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems. New York, NY, USA: ACM. pp. 288—297. doi:10.1145/581630.581678. ISBN 1-58113-575-0. Дата обращения: 22 февраля 2010.
  23. ↑ Christiansen, Morten V. (1998). Region-based memory management in Java (Masters in Computer Science thesis). Department of Computer Science (DIKU), University of Copenhagen. Дата обращения: 20 февраля 2010. (недоступная ссылка)
  24. ↑ Beebee, William S.; Rinard, Martin C. (2001). "An Implementation of Scoped Memory for Real-Time Java". EMSOFT '01: Proceedings of the First International Workshop on Embedded Software. London, UK: Springer-Verlag. pp. 289—305. ISBN 3-540-42673-6. Дата обращения: 22 февраля 2010. (недоступная ссылка)
  25. ↑ Sălcianu, Alexandru; Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard (2003). A type system for safe region-based memory management in Real-Time Java (PDF) (Technical report). MIT Laboratory for Computer Science. MIT-LCS-TR-869. Архивировано (PDF) 28 сентября 2021. Дата обращения: 29 апреля 2020.{{cite tech report}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  26. ↑ Boyapati, Chandrasekhar; Salcianu, Alexandru; Beebee, Jr., William (2003). "Ownership types for safe region-based memory management in real-time Java". PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation. New York, NY, USA: ACM. pp. 324—337. doi:10.1145/781131.781168. ISBN 1-58113-662-5. Дата обращения: 22 февраля 2010.
  27. ↑ Nahkli, Chaker; Rippert, Christophe; Salagnac, Guillaume; Yovine, Sergio (2007). "Efficient region-based memory management for resource-limited real-time embedded systems" (PDF). Proceedings of "Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'2006)". Архивировано (PDF) 26 февраля 2012. Дата обращения: 22 февраля 2010.
  28. ↑ Salagnac, Guillaume; Rippert, Christophe (2007). "Semi-Automatic Region-Based Memory Management for Real-Time Java Embedded Systems". RTCSA '07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Washington, DC, USA: IEEE Computer Society. pp. 73—80. doi:10.1109/RTCSA.2007.67. ISBN 978-0-7695-2975-2.
  29. ↑ Makholm, Henning (2000). Region-based memory management in Prolog (PDF) (Masters in Computer Science thesis). University of Copenhagen, Denmark. Архивировано (PDF) 5 июня 2011. Дата обращения: 20 февраля 2010.
  30. ↑ Makholm, Henning (2000). "A region-based memory manager for prolog". ISMM '00: Proceedings of the 2nd international symposium on Memory management. New York, NY, USA: ACM. pp. 25—34. doi:10.1145/362422.362434. ISBN 1-58113-263-8. Дата обращения: 22 февраля 2010.
  31. ↑ Phan, Quan[англ.]; Janssens, Gerda[англ.]. Static region analysis for Mercury. — Springer Berlin / Heidelberg, 2007. — Т. 4670/2007. — С. 317–332. — (Lecture Notes in Computer Science). — ISBN 978-3-540-74608-9. — doi:10.1007/978-3-540-74610-2.
  32. ↑ Phan, Quan; Somogyi, Zoltan (2008). "Runtime support for region-based memory management in Mercury". ISMM '08: Proceedings of the 7th international symposium on Memory management. New York, NY, USA: ACM. pp. 61—70. doi:10.1145/1375634.1375644. ISBN 978-1-60558-134-7. Архивировано 1 июня 2018. Дата обращения: 15 апреля 2014.
  33. ↑ Taft, Tucker A Pointer-Free path to Object Oriented Parallel Programming. ParaSail blog (2012). Дата обращения: 14 сентября 2012. Архивировано 13 августа 2012 года.
  34. ↑ Blackburn, Stephen M.; McKinley, Kathryn S. (2008). "Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance". PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation. New York, NY, USA: ACM. pp. 22—32. doi:10.1145/1375581.1375586. ISBN 978-1-59593-860-2. Архивировано 19 ноября 2018. Дата обращения: 15 апреля 2014.