boost pool concept

Programing+ 2010.09.18 19:28

Original rink::http://boost.org/libs/pool/doc/concepts.html

Pool Concepts

"동적 메모리 할당은 1960 년 이후로 대부분의 컴퓨터 시스템에서 기본적인 부분이 되었다"

모두가 동적 메모리 할당을 사용한다. 만약 당신이 malloc 나 new 에 대해서 들어 보았다면, 당신은 동적 메모리 할당을 사용했던 것이다. 대부분의 프로그래머들은 힙을 "마술 가방" 쯤으로 취급하는 경향이 있다 : 우리는 그것에 메모리 할당을 요구하며 그것은 마법과 같이 우리를 위해 무엇인가를 생성해 준다. 그렇지만 때때로 우리는 힙이 마법이 아니기 때문에 문제에 빠지게 된다.

힙은 제한이 있다. 이용 가능한 거대한 양의 가상 메모리를 가지고 있는 (임베디드가 아닌) 큰 시스템에서도 제한은 있다. 모든 사람들은 물리적 제약에 대해 신경쓰지만, 약간은 더 사소한 "가상" 제약이 있으며, 이 제약은 당신의 프로그램 (혹은 전체 시스템이) 가상 메모리의 사용을 위해서 느려지게 될 때의 제약이다. 이 가상 제약은 물리적 제약보다는 당신의 프로그램에 더욱 더 문제가 된다. 특히 당신이 다중 작업 시스템을 실행하고 있다면 더욱 그러하다. 결국 큰 시스템을 실행할 때 당신의 프로그램이 가능한한 더 적은 리소스를 사용하도록 하고 가능한한 빨리 그것들을 해제하는 것이 좋다. 임베디드 시스템을 사용할 때 프로그래머들은 보통 낭비할 메모리가 별로 없다.

힙은 복잡하다. 그것은 어떤 크기의 어떤 유형의 메모리 요청이라도 만족해야 하며 빨라야 한다. 메모리 관리에 대한 일반적인 접근은 메모리를 부분으로 분할하고 그것들을 트리나 리스트 구조체를 사용해 크기로 정렬하는 것이다. locality 와 lifetime 평가와 같은 다른 요소들을 추가하면 힙은 매우 빠르게 복잡해 진다. 사실 너무 복잡하기 때문에 동적 메모리 할당을 어떤 방식으로 수행해야 하는 지에 대한 "완벽한" 해답은 존재하지 않는다. 아래의 다이어그램은 대부분의 일반적인 메모리 관리자가 작동하는 방식에 대해서 설명한다; 각 메모리 청크에 대해 그것은 내부적인 트리나 리스트 구조를 유지하기 위해서 그 메모리 부분을 사용한다. 청크가 프로그램에 대해 할당(malloc'ed out)될 때조차 메모리 관리자는 그것의 내부에 어떤 정보를 "저장"해야만 한다 - 일반적으로 그것의 크기이다. 그리고 나서 그 블록(block)이 해제되면(free'd) 메모리 관리자는 그것의 크기가 얼마인지 쉽게 말해줄 수 있다.

메모리 블록, 할당되지 않음
프로세스에 속하지 않는 메모리
메모리 할당자 알고리즘에 의해 내부적으로 사용되는 메모리 (일반적으로 8-12 바이트)
사용되지 않는 메모리
프로세스에 속하지 않는 메모리

 

메모리 블록, 할당됨(프로그램에 의해 사용됨)
프로세스에 속하지 않은 메모리
메모리 할당자 알고리즘에 의해 내부적으로 사용되는 메모리(일반적으로 4바이트)
프로그램에 의해 이용 가능한 메모리
프로세스에 속하지 않는 메모리

 

동적 메모리 할당의 복잡함 때문에 시간 혹은 공간의 곤점에서 그것은 종종 비효율적이다. 대부분의 메모리 할당 알고리즘은 각 메모리 블록과 함께 특정 형식의 정보를 저장하거나, 블록 크기나 내부 트리나 리스트 구조 내에서의 위치와 같은 특정 연관 정보를 저장하기도 한다. 그러한 "헤더 필드"를 위해서 한 개의 머신 워드를 프로그램에 의해 사용되고 있는 블록 안에 저장하는 것이 일반적이다. 그후의 명백한 문제는 작은 오브젝트들이 동적으로 할당될 때 일어난다. 예를 들어 int 가 동적으로 할당되면 자동으로 이 알고리즘은 헤더 필드를 위한 공간도 예약할 것이며, 우리는 결국 메모리의 50% 를 낭비하게 될 것이다. 물론 이것은 최악의 경우이다. 그러나 현대의 프로그램들은 힙에 작은 오브젝트들을 자주 사용한다; 그리고 그것은 이 문제를 더더욱 심각하게 만든다. Wilson et. al. 은 평균적인 경우 메모리 오버헤드는 10 ~ 20 % 정도라고 언급한다. 프로그램이 작은 오브젝트를 많이 사용할 수록 메모리 오버헤드가 늘어나게 된다. 프로그램이 가지는 메모리 오버헤드가 가상 제약과 더 관계있는 이유가 이것 때문이다.

시스템이 클수록 메모리 오버헤드는 (그것이 작동하기 위해서 사용하는 시간의 총량에 비해) 작은 문제이며, 결국 종종 무시된다. 그러나 시간에 민감한 알고리즘의 일부로서 작은 오브젝트들에 대한 할당과 해제가 많이 일어나는 상황이 있으며, 이러한 상황에서 시스템이 제공하는 메모리 할당자는 종종 너무 느려진다.

단순 분리 저장소는 이들 이슈를 모두 다룬다. 거의 대부분의 메모리 오버헤드가 그것을 사용해 해결되며, 모든 할당은 적은 양의 (아모타이즈, armotized) 상수 시간에 수행될 수 있다.

 

Simple Segregated Storage

단순 분리 저장소는 Boost Pool 라이브러리의 기본 착상이다. 단순 분리 저장소는 가장 간단하며, 아마도 가장 빠른 메모리 할당/해제 알고리즘이다. 그것은 메모리 블록을 고정 크기의 청크로 분할함으로써 시작된다. 그 블록이 어딨는지는 구현 시간까지 중요하지 않다. 풀은 단순 분리 저장소를 이러한 방식으로 사용하는 어떤 개체를 의미한다. 그림으로 설명해 보겠다 :

 

메모리 블록, 청크로 분할됨
프로세스에 속하지 않는 메모리
Chunk 0
Chunk 1
Chunk 2
Chunk 3
프로세스에 속하지 않는 메모리

 

주어진 블록 안의 각 청크는 항상 같은 크기이다. 이것은 단순 분리 저장소의 기본적인 제약이다 : 당신은 다른 크기의 청크를 요청할 수 없다. 예를 들어 당신은 (문자와 정수를 다른 크기라고 가정했을 때) 문자를 위한 정수형 풀을 요청하거나 정수를 위한 문자 풀을 요청할 수 없다.

단순 분리 저장소는 사용되지 않는 청크 내부에 free list 를 인터리빙함으로써 작동한다. 예를 들어 :

(역주 : 출처 : 네이버 사전

터리빙 《주기억 장치구성 기억 장치 모듈 내의 연속적인 기억 장치 소자들에 연속적으로 주소붙이지 않고, 일정수의 배수만큼 거리배정하는 방법》)

메모리 블록, 할당된 청크가 없음
프로세스에 속하지 않는 메모리
Chunk 0; points to Chunk 1
Chunk 1; points to Chunk 2
Chunk 2; points to Chunk 3
Chunk 3; end-of-list
프로세스에 속하지 않는 메모리

 

메모리 블록, 두 개의 할당된 청크를 가지고 있음
프로세스에 속하지 않는 메모리
Chunk 0; points to Chunk 2
Chunk 1 (in use by process)
Chunk 2; end-of-list
Chunk 3 (in use by process)
프로세스에 속하지 않는 메모리

 

free list 를 청크 내부에 인터리빙함으로써 각 단순 분리 저장소는 단지 단일 포인터에 대한 오버헤드만을 가지게 된다(리스트 안의 첫 번째 요소에 대한 포인터). 프로세스에 의해 사용중인 청크에 대한 메모리 오버헤드는 없다.

또한 단순 분리 저장소는 극적으로 빠르다. 가장 단순한 경우 메모리 할당은 free list 로부터 첫 번째 청크를 O(1)으로 거의 제거하고 있다. free list 가 비어있는 경우 다른 블록이 요구되고 분할되는데, 그것은 아모타이즈 O(1) 시간이 걸릴 것이다. 메모리 해제는 free list 의 앞으로 그 청크를 추가하는 것만큼 간단하며 O(1) 시간이 걸린다. 그러나 단순 분리 저장소의 더 복잡한 사용은 free list 를 정렬할 것을 요구하며, O(N) 의 해제를 하게 된다.

단순 분리 저장소는 시스템이 제공하는 할당자보다 더 빠르게 실행되며 더 적은 메모리 오버헤드를 요구하게 만들어 준다. 그러나 보편성(generality)을 잃게 된다. 풀을 잘 사용하는 경우는 (비연속적인) 작은 오브젝트들이 힙 상에서 할당되는 경우나 같은 크기의 오브젝트들이 반복적으로 할당 및 해제되는 경우이다.

참고 자료

  1. Doug Lea, A Memory Allocator. Available on the web at http://gee.cs.oswego.edu/dl/html/malloc.html
  2. Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, "Dynamic Storage Allocation: A Survey and Critical Review" in International Workshop on Memory Management, September 1995, pg. 28, 36. Available on the web at ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps

다른 구현들

풀 할당은 많은 프로그래밍 언어에서 찾아볼 수 있으며 매우 다양하다. 많은 구현들의 시작은 일반적인 프로그래밍 논문들에서 찾을 수 있다 : 일부가 아래에 나와 있다. 이것들 중 어느 것도 풀의 완벽한 구현은 아니라는데 주의하라; 이들 대부분은 사용자의 경험으로서의 풀에 대한 특정 관점을 남기고 있다. 그러나 각각의 경우 (어떤 관점은 이제 사용되지 않지만) 이들 예제는 이 문서에서 기술된 단순 분리 저장소의 같은 핵심 개념을 사용한다.

  • "The C++ Programming Language", 3rd ed., by Bjarne Stroustrup, Section 19.4.2. Missing aspects:
    1. Not portable
    2. Cannot handle allocations of arbitrary numbers of objects (this was left as an exercise)
    3. Not thread-safe
    4. Suffers from the static initialization problem
  • "MicroC/OS-II: The Real-Time Kernel", by Jean J. Labrosse, Chapter 7 and Appendix B.04. This is an example of the Simple Segregated Storage scheme at work in the internals of an actual OS. Missing aspects:
    1. Not portable (though this is OK, since it's part of its own OS)
    2. Cannot handle allocations of arbitrary numbers of blocks (which is also OK, since this feature is not needed)
    3. Requires non-intuitive user code to create and destroy the Pool
  • "Efficient C++: Performance Programming Techniques", by Dov Bulka and David Mayhew, Chapters 6 and 7. This is a good example of iteratively developing a Pool solution; however, their premise (that the system-supplied allocation mechanism is hopelessly inefficient) is flawed on every system I've tested on. Run their timings on your system before you accept their conclusions. Missing aspects:
    1. Requires non-intuitive user code to create and destroy the Pool
  • "Advanced C++: Programming Styles and Idioms", by James O. Coplien, Section 3.6. This has examples of both static and dynamic pooling. Missing aspects:
    1. Not thread-safe
    2. The static pooling example is not portable

Copyright © 2000, 2001 Stephen Cleary (scleary AT jerviswebb DOT com)

This file can be redistributed and/or modified under the terms found in copyright.html

This software and its documentation is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose. 

[출처] [boost pool]풀 개념|작성자 라이푸


YOUR COMMENT IS THE CRITICAL SUCCESS FACTOR FOR THE QUALITY OF BLOG POST