지역 기반 메모리 관리

Region-based memory management

컴퓨터 과학에서 영역 기반 메모리 관리는 할당된 각 개체가 영역에 할당되는 메모리 관리 유형입니다.영역(Zone, Arena, Area 또는 Memory Context라고도 함)은 한 번에 효율적으로 재할당 또는 할당 해제할 수 있는 할당된 개체의 집합입니다.스택 할당과 마찬가지로 영역은 오버헤드가 적은 메모리의 할당과 할당 해제를 용이하게 하지만 유연성이 높아 오브젝트의 수명이 할당된 스택프레임보다 길어집니다.일반적인 실장에서는 지역 내의 모든 오브젝트는 일반적으로 스택프레임의 할당 방법과 마찬가지로 연속된 단일 메모리주소 범위로 할당됩니다.

예

간단한 예로서 링크 리스트 데이터 구조를 할당하고 할당 해제하는 다음 C 코드를 생각해 보겠습니다.

지역 *r = create Region(지역 생성)(); 리스트 노드 *머리 = 특수한 순서; 위해서 (인트 i = 1; i <=> 1000; i++) {     리스트 노드* 새로운 노드 = allocate From Region(지역 할당 시작)(r, 크기(리스트 노드));     새로운 노드->다음 분. = 머리;     머리 = 새로운 노드; } // ... // (여기에 목록 사용) // ... 파괴 지역(r);

링크 리스트의 작성에는 많은 조작이 필요했지만 노드가 할당되어 있는 영역을 파괴함으로써 한 번의 조작으로 신속하게 할당을 해제할 수 있습니다.목록을 이동할 필요가 없습니다.

실행

간단한 명시적 영역은 구현이 간단합니다.다음 설명은 [1]Hanson을 기반으로 합니다.각 영역은 대용량 메모리 블록의 링크 목록으로 구현됩니다. 각 블록은 많은 할당을 처리할 수 있을 만큼 충분히 커야 합니다.현재 블록은 블록의 다음 빈 위치에 대한 포인터를 유지하며, 블록이 채워지면 새 블록이 할당되어 목록에 추가됩니다.영역의 할당이 해제되면 다음 자유 위치 포인터가 첫 번째 블록의 선두로 리셋되고 블록 목록을 다음 할당된 영역에 재사용할 수 있습니다.또는 영역이 할당 해제되면 블록 목록을 글로벌프리리스트에 추가할 수 있습니다.이 리스트는 나중에 다른 지역이 새로운 블록을 할당할 수 있습니다.이 간단한 스킴의 어느 경우든 영역에서 개별 객체의 할당을 해제할 수 없습니다.

이 스킴의 할당된 바이트당 총 비용은 매우 낮습니다.대부분의 할당은 다음 프리 포지션 포인터와의 비교와 업데이트만을 수반합니다.영역 할당 해제는 상시 작업이며 거의 수행되지 않습니다.일반적인 가비지 수집 시스템과 달리 데이터 유형에 태그를 지정할 필요가 없습니다.

이력 및 개념

지역의 기본 개념은 매우 오래되어 1967년 더글러스 T에서 처음 등장했습니다.Ross의 AED Free Storage Package는 메모리를 구역의 계층 구조로 분할했습니다.각 구역에는 독자적인 할당자가 있어 구역이 동시에 해방되어 구역이 [2]지역으로서 사용 가능하게 되었습니다.1976년 PL/I 표준은 AREA 데이터 [3]유형을 포함했습니다.1990년에 Hanson은 C의 명시적 영역(그가 영역이라고[clarification needed] 불렀음)이 가장 빨리 알려진 힙 할당 메커니즘보다 [1]더 뛰어난 할당된 바이트당 시간 성능을 달성할 수 있다는 것을 증명했습니다.명시적 영역은 풀이라고 불리는 Apache HTTP Server와 Postgre를 포함한 초기 C 기반 소프트웨어 프로젝트 설계에 중요한 역할을 했습니다.메모리 콘텍스트라고 불리는 SQL 데이터베이스 관리 시스템.[4]기존의 힙 할당과 마찬가지로 이러한 방식은 메모리 안전성을 제공하지 않습니다.프로그래머는 해당 영역이 당글링 포인터에 의해 할당 해제된 후 영역에 액세스하거나 영역 할당 해제를 잊어버려 메모리 누수가 발생할 수 있습니다.

지역 추론

1988년 연구자들은 컴파일러가 컴파일 시 특정 영역에 대한 개별 정적 할당 표현 할당뿐만 아니라 영역의 생성 및 할당 해제를 삽입하는 영역 추론 개념을 도입함으로써 안전한 메모리 할당을 위해 영역을 사용하는 방법을 조사하기 시작했다.컴파일러는 이를 행잉 포인터와 리크가 발생하지 않도록 보증할 수 있습니다.

Rugieri와 Murtagh의 [5]초기 작업에서는 각 기능의 시작 부분에 영역이 생성되고 마지막에 할당 해제됩니다.그런 다음 데이터 흐름 분석을 사용하여 각 정적 할당 식에 대한 라이프 타임을 결정하고 전체 라이프 타임을 포함하는 가장 어린 영역에 할당합니다.

1994년 Tofte와 Talpin의 주요 작업에서 이 작업은 유형 추론과 다형 영역 유형과 지역 [6][7]미적분의 이론적 개념에 기초한 다른 알고리즘을 사용하여 함수 프로그래밍 언어인 Standard ML에서 유형 다형성과 고차 함수를 지원하기 위해 일반화되었습니다.그들의 연구는 영역을 포함한 람다 미적분의 확장을 도입했고, 두 가지 구성을 추가했다.

e1 at : : e 식의1 결과를 계산하여 영역 ;에 저장한다.
letregion in in2 e end :영역을 생성하여 에 바인드하고 e를 평가하여2 지역 할당을 해제합니다.

이 구문 구조에 의해 영역은 중첩됩니다.즉, r 뒤에1 r이 작성되면2 r 전에 할당1 해제해야 합니다.그 결과 영역 스택이 생성됩니다.또한 영역은 생성된 기능과 동일한 기능으로 할당 해제되어야 합니다.이러한 제한은 에이켄 [8]등에 의해 완화되었다.

이 확장된 람다 미적분은 표준 ML 프로그램을 기계어로 컴파일하기 위한 메모리 세이프 중간 표현으로 사용되도록 의도되었지만, 대규모 프로그램에서 좋은 결과를 낼 수 있는 번역기를 구축하는 것은 재귀적인 문제를 포함한 새로운 분석을 통해 해결해야 하는 많은 실질적인 한계에 직면했습니다.ve 콜, 테일콜 및 단일 값만 포함된 지역 삭제.이 작업은 1995년에[9] 완료되었으며 가비지 수집 대신 지역 할당에 기반한 ML 버전인 ML 키트에 통합되었습니다.이를 통해 중간 크기의 테스트 프로그램에서 두 프로그램을 직접 비교할 수 있으며, 프로그램이 얼마나 "지역 친화적"인지에 따라 매우 다양한 결과("10배에서 4배까지")를 얻을 수 있었습니다. 그러나 컴파일 시간은 몇 [10]분 정도였습니다.ML Kit는 모듈 분리 컴파일을 위한 체계와 지역 추론과 가비지 [11][12]수집 추적을 결합한 하이브리드 기술이라는 두 가지 추가 기능으로 결국 대규모 애플리케이션으로 확장되었습니다.

새로운 언어 환경에 대한 일반화

ML Kit의 개발에 따라 지역도 다른 언어 환경으로 일반화되기 시작했습니다.

  • C 프로그래밍 언어에 대한 다양한 확장 기능:
    • 안전한 C 방언 Cyclon(다른 많은 기능 중)은 명시적 영역에 대한 지원을 추가하여 [13][14][15]기존 C 애플리케이션을 마이그레이션하여 사용할 때의 영향을 평가합니다.
    • 명시적으로 관리되는 영역을 사용하는 RC라고 불리는[16] C로의 확장이 구현되었지만 영역에서의 참조 카운트를 사용하여 영역이 [17][18]조기에 해방되지 않도록 함으로써 메모리 안전을 보증합니다.영역 내부 참조는 수정할 때 카운트를 업데이트할 필요가 없으므로 영역은 참조 카운트의 오버헤드를 줄입니다.RC에는 일부 참조 카운트 갱신을 [19]제거할 수 있는 영역용 명시적 정적 유형 시스템이 포함되어 있습니다.
    • Control-C라고 불리는 C의 제한은 메모리 안전을 [20]정적으로 확보하기 위해 프로그램의 설계의 일부로 지역(및 한 번에 하나의 지역만)을 사용하도록 제한합니다.
  • 영역은 [21]Java의 서브셋용으로 구현되어 실시간 Java에서 메모리 관리의 중요한 컴포넌트가 되었습니다.이러한 컴포넌트는 오브젝트 캡슐화를 나타내고 [22][23][24]영역 할당 해제 시 런타임 체크를 배제하기 위해 소유권 유형과 결합됩니다.최근에는 컴파일 타임 정적 분석, 런타임 영역 할당 정책 및 프로그래머 [25][26]힌트를 결합하여 임베디드 실시간 Java 애플리케이션에서 영역을 추론하는 반자동 시스템이 제안되었습니다.지역은 시간 오버헤드를 정적으로 예측할 수 있기 때문에 가비지 수집이 복잡하지 않기 때문에 실시간 컴퓨팅에 적합합니다.
  • Tofe 및 Talpin의 지역 추론 모델을 역추적 및 컷을 지원하도록 확장함으로써 논리 프로그래밍 언어[27][28] Prolog 및 Mercury에[29][30] 구현되었습니다.
  • 지역 기반 스토리지 관리는 병렬 프로그래밍 언어 ParaSail에서 사용됩니다.ParaSail에는 [31]명시적인 포인터가 없기 때문에 참조 카운트를 할 필요가 없습니다.

단점들

영역을 사용하는 시스템에서는 영역이 할당 해제되기 전에 매우 커져서 대량의 데드 데이터를 포함하는 문제가 발생할 수 있습니다.이러한 데이터를 일반적으로 "누출"이라고 부릅니다(결국 해방되더라도).누출을 제거하기 위해서는 일반적으로 수명이 짧은 새로운 지역을 도입하여 프로그램을 재구성해야 할 수 있습니다.이러한 유형의 문제를 디버깅하는 것은 특히 프로그래머가 문제를 진단하기 위해 기초적인 추론 알고리즘을 이해하거나 상세한 중간 표현을 검토해야 하는 영역 추론을 사용하는 시스템에서 어렵습니다.가비지 콜렉터를 추적하는 것은 프로그램을 변경하지 않고 이러한 유형의 데이터를 적시에 할당 해제하는 데 더 효과적입니다.이는 하이브리드 지역/GC 시스템의 [11]한 가지 이유였습니다.한편, 가비지 콜렉터의 트레이스에서는, 다시는 사용되지 않는 데이터에 대한 참조가 유지되고 있는 경우, 미묘한 누설이 발생할 가능성도 있습니다.

지역 기반 메모리 관리는 지역 수가 비교적 적고 각각에 많은 개체가 포함되어 있을 때 가장 적합합니다.소량 영역을 많이 포함하는 프로그램에서는 내부 플래그멘테이션이 발생하여 메모리 낭비가 발생하고 지역 관리의 시간 오버헤드가 발생합니다.다시 한 번, 지역 추론이 존재하는 경우 이 문제를 진단하기가 더 어려울 수 있다.

하이브리드 방식

위에서 설명한 바와 같이, RC는 영역과 기준 계수의 혼합을 사용하여 영역 내부 참조를 수정할 때 계수를 업데이트할 필요가 없기 때문에 기준 계수의 오버헤드를 제한한다.마찬가지로 일부 마크 영역 하이브리드 메서드는 가비지 컬렉션 트레이스를 영역과 결합합니다.이러한 메서드는 히프를 영역으로 분할하여 라이브개체가 포함된 영역이 마킹된 마크 스위프 패스를 실행한 후 마킹되지 않은 영역을 해방하는 기능을 합니다.이러한 기능을 [32]사용하려면 조각 모음을 지속적으로 수행해야 합니다.

레퍼런스

  1. ^ a b 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. S2CID 8960945. Archived from the original on 2012-10-20.
  2. ^ Ross, Douglas (1967). "The AED free storage package". Communications of the ACM. 10 (8): 481–492. doi:10.1145/363534.363546. S2CID 6572689.
  3. ^ American National Standards Institute, inc. (1976). American National Standard Programming Language PL/I.
  4. ^ 2010 PostgreSQL Global Development Group (1996). "Section 41.3: Memory Management". PostgreSQL 8.2.15 Documentation. Retrieved 22 February 2010.
  5. ^ 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. Retrieved 22 February 2010.
  6. ^ 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. 시트저에 대해서
  7. ^ 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. Retrieved 15 April 2014.
  8. ^ 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. 시트저에 대해서
  9. ^ 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. Retrieved 22 February 2010.
  10. ^ 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.
  11. ^ a b 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.
  12. ^ 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.
  13. ^ "Cyclone: Introduction to Regions". Cyclone User Manual. Retrieved 22 February 2010.
  14. ^ 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.
  15. ^ 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. Retrieved 22 February 2010.
  16. ^ Gay, David (1999). "RC - Safe, region-based memory-management for C". David Gay's homepage. Intel Labs Berkeley. Archived from the original on February 26, 2009. Retrieved 22 February 2010.
  17. ^ 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. Retrieved 22 February 2010.
  18. ^ Gay, David Edward (2001). Memory management with explicit regions (PDF) (PhD in Computer Science thesis). University of California at Berkeley. Retrieved 20 February 2010.
  19. ^ 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.
  20. ^ 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. Retrieved 22 February 2010.
  21. ^ Christiansen, Morten V. (1998). Region-based memory management in Java (Masters in Computer Science thesis). Department of Computer Science (DIKU), University of Copenhagen. Retrieved 20 February 2010.[영구 데드링크]
  22. ^ 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. Retrieved 22 February 2010.[영구 데드링크]
  23. ^ 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 techreport}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  24. ^ 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. Retrieved 22 February 2010.
  25. ^ 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)". Retrieved 22 February 2010.
  26. ^ 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.
  27. ^ Makholm, Henning (2000). Region-based memory management in Prolog (PDF) (Masters in Computer Science thesis). University of Copenhagen, Denmark. Archived from the original (PDF) on 5 June 2011. Retrieved 20 February 2010.
  28. ^ 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. Retrieved 22 February 2010.
  29. ^ Phan, Quan; Janssens, Gerda (2007). Static region analysis for Mercury. Lecture Notes in Computer Science: Logic Programming. Lecture Notes in Computer Science. Vol. 4670/2007. Springer Berlin / Heidelberg. pp. 317–332. doi:10.1007/978-3-540-74610-2. ISBN 978-3-540-74608-9. ISSN 1611-3349.
  30. ^ 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. Retrieved 15 April 2014.
  31. ^ Taft, Tucker (2012). "A Pointer-Free path to Object Oriented Parallel Programming". ParaSail blog. Retrieved 14 September 2012.
  32. ^ 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. Retrieved 15 April 2014.