Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Пример [ править ]

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

Регион  * r  =  createRegion (); ListNode  * head  =  NULL ; для  ( Int  я  =  1 ;  я  <=  1000 ;  я ++ )  {  ListNode *  newNode  =  allocateFromRegion ( г ,  SizeOf ( ListNode ));  newNode -> следующий  =  голова ;  head  =  newNode ; } // ... // (используйте здесь список)// ... destroyRegion ( r );

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

Реализация [ править ]

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

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

История и концепции [ править ]

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

Вывод региона [ править ]

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

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

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

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

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

Это расширенное лямбда-исчисление предназначалось для использования в качестве доказуемо безопасного для памяти промежуточного представления для компиляции программ стандартного машинного обучения в машинный код, но создание переводчика, который давал бы хорошие результаты в больших программах, столкнулось с рядом практических ограничений, которые необходимо было устранить с помощью анализ, включая обработку рекурсивных вызовов, хвостовых рекурсивных вызовов и удаление областей, содержащих только одно значение. Эта работа была завершена в 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] Регионы хорошо подходят для вычислений в реальном времени. потому что их временные затраты статически предсказуемы, без сложностей, связанных с добавочной сборкой мусора.
  • Они были реализованы для языков логического программирования Prolog [27] [28] и Mercury [29] [30] путем расширения модели логического вывода Тофте и Талпина для поддержки отслеживания с возвратом и сокращений.
  • Управление хранилищем на основе региона используется во всем языке параллельного программирования ParaSail . Из-за отсутствия явных указателей в ParaSail [31] нет необходимости в подсчете ссылок.

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

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

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

Гибридные методы [ править ]

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

Ссылки [ править ]

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