Управление памятью на основе регионов: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Строка 85: Строка 85:
{{cite conference |url=http://portal.acm.org/citation.cfm?id=581678 |title=Ensuring code safety without runtime checks for real-time control systems |last1=Kowshik |first1=Sumant |last2=Dhurjati |first2=Dinakar |last3=Adve |first3=Vikram |year=2002 |publisher=ACM |location=New York, NY, USA |accessdate=22 February 2010 |booktitle=CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems |pages=288–297 |isbn=1-58113-575-0 |doi=10.1145/581630.581678}}
{{cite conference |url=http://portal.acm.org/citation.cfm?id=581678 |title=Ensuring code safety without runtime checks for real-time control systems |last1=Kowshik |first1=Sumant |last2=Dhurjati |first2=Dinakar |last3=Adve |first3=Vikram |year=2002 |publisher=ACM |location=New York, NY, USA |accessdate=22 February 2010 |booktitle=CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems |pages=288–297 |isbn=1-58113-575-0 |doi=10.1145/581630.581678}}
</ref>.
</ref>.
* Регионы были реализованы для подмножества Java<ref>
⚫
* Регионы были реализованы для подмножества Java и стали критически важным компонентом управления памятью в языке [[RTSJ|Realtime Java]], который объединяет их с ''типами владения'' для контроля инкапсуляции объектов и устранения проверок во время выполнения для освобождения региона.
{{Cite thesis |degree=Masters in Computer Science |title=Region-based memory management in Java |url=ftp://ftp.diku.dk/diku/semantics/papers/D-395.ps.gz |last=Christiansen |first=Morten V. |year=1998 |publisher=Department of Computer Science (DIKU), University of Copenhagen |accessdate=20 February 2010 }}{{dead link|date=April 2018 |bot=InternetArchiveBot |fix-attempted=yes }}
⚫
</ref> и стали критически важным компонентом управления памятью в языке [[RTSJ|Realtime Java]], который объединяет их с ''типами владения'' для контроля инкапсуляции объектов и устранения проверок во время выполнения для освобождения региона<ref>{{cite conference |url=http://www.cag.lcs.mit.edu/~rinard/paper/emsoft01.ps |title=An Implementation of Scoped Memory for Real-Time Java |last1=Beebee |first1=William S. |last2=Rinard |first2=Martin C. |year=2001 |publisher=Springer-Verlag |location=London, UK |accessdate=22 February 2010 |booktitle=EMSOFT '01: Proceedings of the First International Workshop on Embedded Software |pages=289&ndash;305 |isbn=3-540-42673-6 }}{{Dead link|date=February 2020 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref>
{{cite techreport | title=A type system for safe region-based memory management in Real-Time Java | last1=Sălcianu |first1=Alexandru |author2=Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard |number=MIT-LCS-TR-869 | institution=MIT Laboratory for Computer Science |year=2003 |url=http://people.csail.mit.edu/rinard/techreport/MIT-LCS-TR-869.pdf}}
</ref><ref>
{{cite conference |url=http://portal.acm.org/citation.cfm?id=781168 |title=Ownership types for safe region-based memory management in real-time Java |last1=Boyapati |first1=Chandrasekhar |authorlink1=Chandrasekhar Boyapati|last2=Salcianu |first2=Alexandru |authorlink2=Alexandru Salcianu|last3=Beebee, Jr. |first3=William |authorlink3=William Beebee, Jr.|year=2003 |publisher=ACM |location=New York, NY, USA |accessdate=22 February 2010 |booktitle=PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation |pages=324&ndash;337 |isbn=1-58113-662-5|doi=10.1145/781131.781168}}
</ref>.


== Недостатки ==
== Недостатки ==

Версия от 02:00, 29 апреля 2020

В информатике управление памятью на основе региона - это тип управления памятью, при котором каждый создаваемый в памяти объект приписывается к определённому региону. Регион, также называемый зоной, ареной[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].

Недостатки

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

Примечания

  1. ↑ в русских источниках этот термин почти не употребляется
  2. ↑ Это может быть необходимо, например, для того, чтобы поместить все объекты, относящиеся к конкретному экземпляру параллельно выполняемой процедуры в раздел памяти близкий конкретному процессору многопроцессорной системы[англ.]*.
  3. ↑ 1 2 Hanson, David R. (1989). "Fast allocation and deallocation of memory based on object lifetimes". Software: Practice and Experience. 20 (1): 5—12. doi:10.1002/spe.4380200104. Архивировано 20 октября 2012.
  4. ↑ Ross, Douglas (1967). "The AED free storage package". Communications of the ACM. 10 (8): 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.
  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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
  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
  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. Дата обращения: 15 апреля 2014. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
  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
  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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
  12. ↑ Tofte, Mads; Birkedal, Lars; Elsman, Martin; Hallenberg, Niels (2004). "A Retrospective on Region-Based Memory Management". Higher Order Symbolic Computing. 17 (3): 245—265. doi:10.1023/B:LISP.0000029446.78563.a4. ISSN 1388-3690.
  13. ↑ Hallenberg, Niels; Elsman, Martin; Tofte, Mads (2003). "Combining region inference and garbage collection". SIGPLAN Notices. 37 (5): 141—152. doi:10.1145/543552.512547. ISSN 0362-1340.
  14. ↑ Elsman, Martin (2003). "Garbage collection safety for region-based memory management". SIGPLAN Notices. 38 (3): 123—134. CiteSeerX 10.1.1.57.8914. doi:10.1145/640136.604190. ISSN 0362-1340.
  15. ↑ Cyclone: Introduction to Regions. Cyclone User Manual. Дата обращения: 22 февраля 2010.
  16. ↑ Grossman, Dan; Morrisett, Greg; Jim, Trevor; Hicks, Michael; Wang, Yanling (2002). "Region-based memory management in cyclone". SIGPLAN Notices. 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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
  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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
  20. ↑ Gay, David Edward (2001). Memory management with explicit regions (PDF) (PhD in Computer Science thesis). University of California at Berkeley. Дата обращения: 20 февраля 2010.
  21. ↑ Gay, David; Aiken, Alex (2001). "Language support for regions". SIGPLAN Notices. 36 (5): 70—80. CiteSeerX 10.1.1.650.721. doi:10.1145/381694.378815. ISSN 0362-1340.
  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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
  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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка) (недоступная ссылка)
  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.{{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. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
Источник — https://ru.wikipedia.org/w/index.php?title=Управление_памятью_на_основе_регионов&oldid=106660203