✖


Jump to content

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

(Перенаправлено из вывода по региону )

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

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

Пример

[ редактировать ]

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

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

Выполнение

[ редактировать ]

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

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

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

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

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

[ редактировать ]

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

  • Различные расширения языка программирования C:
    • Безопасный диалект C Cyclone , который среди многих других функций добавляет поддержку явных регионов и оценивает влияние миграции существующих приложений C на их использование. [13] [14] [15]
    • Расширение C под названием RC. [16] был реализован, который использует явно управляемые регионы, но также использует подсчет ссылок на регионы, чтобы гарантировать безопасность памяти, гарантируя, что ни один регион не будет освобожден преждевременно. [17] [18] Регионы уменьшают накладные расходы на подсчет ссылок, поскольку ссылки, внутренние по отношению к регионам, не требуют обновления счетчиков при их изменении. RC включает в себя явную систему статических типов для регионов, которая позволяет исключить некоторые обновления счетчика ссылок. [19]
    • Ограничение C, называемое Control-C, ограничивает программы использованием регионов (и только одного региона за раз) как часть своей конструкции для статического обеспечения безопасности памяти. [20]
  • Регионы были реализованы для подмножества Java , [21] и стал важнейшим компонентом управления памятью в Java реального времени , который объединяет их с типами владения для демонстрации инкапсуляции объектов и устранения проверок во время выполнения при освобождении области. [22] [23] [24] Совсем недавно была предложена полуавтоматическая система для определения регионов во встроенных Java-приложениях реального времени, сочетающая статический анализ во время компиляции, политику выделения регионов во время выполнения и подсказки программисту. [25] [26] Регионы хорошо подходят для вычислений в реальном времени, поскольку их временные затраты статически предсказуемы, без сложности инкрементальной сборки мусора.
  • В Java 21 добавлен Java API для выделения и выпуска арен.

[27] . Заявленная цель — улучшить безопасную интеграцию с собственными библиотеками, чтобы предотвратить утечки памяти JVM и снизить риск повреждения памяти JVM собственным кодом. [28]

Недостатки

[ редактировать ]

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

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

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

[ редактировать ]

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

Ссылки

[ редактировать ]
  1. ^ Перейти обратно: а б Хэнсон, Дэвид Р. (1989). «Быстрое выделение и освобождение памяти в зависимости от времени жизни объекта» . Программное обеспечение: практика и опыт . 20 (1): 5–12. дои : 10.1002/спе.4380200104 . S2CID   8960945 . Архивировано из оригинала 20 октября 2012 г.
  2. ^ Росс, Дуглас (1967). «Пакет бесплатного хранения AED» . Коммуникации АКМ . 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 г. {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )
  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). «Управление памятью на основе регионов в Cyclone». Уведомления 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 в Беркли. Архивировано из оригинала 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) (технический отчет). Лаборатория компьютерных наук Массачусетского технологического института. МИТ-LCS-TR-869. {{cite tech report}}: 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. ^ «Сегменты памяти и арены» . Оракул.
  28. ^ Чимадамор, Маурицио. «JEP 454: API внешних функций и памяти» . OpenJDK.
  29. ^ Махольм, Хеннинг (2000). Управление памятью на основе регионов в Prolog (PDF) (магистерская диссертация в области компьютерных наук). Университет Копенгагена, Дания. Архивировано из оригинала (PDF) 5 июня 2011 года . Проверено 20 февраля 2010 г.
  30. ^ Махольм, Хеннинг (2000). «Региональный менеджер памяти для пролога» . ISMM '00: Материалы 2-го международного симпозиума по управлению памятью . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 25–34. дои : 10.1145/362422.362434 . ISBN  1-58113-263-8 . Проверено 22 февраля 2010 г.
  31. ^ Фан, Куан ; Янссенс, Герда (2007). Логическое программирование . Конспекты лекций по информатике. Том. 4670/2007. Шпрингер Берлин/Гейдельберг. стр. 317–332. дои : 10.1007/978-3-540-74610-2 . ISBN  978-3-540-74608-9 . ISSN   1611-3349 .
  32. ^ Фан, Куан ; Сомоджи, Золтан (2008). «Поддержка выполнения управления памятью на основе региона в Mercury» . ISMM '08: Материалы 7-го международного симпозиума по управлению памятью . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 61–70. дои : 10.1145/1375634.1375644 . ISBN  978-1-60558-134-7 . Проверено 15 апреля 2014 г.
  33. ^ Тафт, Такер (2012). «Путь без указателей к объектно-ориентированному параллельному программированию» . Блог ParaSail . Проверено 14 сентября 2012 г.
  34. ^ Блэкберн, Стивен М .; МакКинли, Кэтрин С. (2008). «Immix: сборщик мусора с маркировкой области с экономией пространства, быстрой сборкой и производительностью мутатора» . PLDI '08: Материалы конференции ACM SIGPLAN 2008 года по проектированию и реализации языков программирования . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 22–32. дои : 10.1145/1375581.1375586 . ISBN  978-1-59593-860-2 . Проверено 15 апреля 2014 г.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Region-based_memory_management&oldid=1233388083#Region_inference"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 12b2f808ee8bef49c222898fe63bc6ed__1720459680
URL1:https://arc.ask3.ru/arc/aa/12/ed/12b2f808ee8bef49c222898fe63bc6ed.html
Заголовок, (Title) документа по адресу, URL1:
Region-based memory management - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)