자체 메모리 관리자가 필요한 이유

메모리 할당과 해제를 직접 통제하면 코드 성능을 향상하기도 쉬워진다. 어째서일까? 먼저, C/C++ 언어에서 메모리를 관리하는 방식을 떠올려 보자. C에서는 malloc , free , calloc , realloc 과 같은 표준 라이브러리 함수를, C++에서는 new , new [ ] , delete , delete [ ] 와 같은 표준 라이브러리 함수로 메모리 관리 핵심을 구성한다. 이런 사실을 염두에 두고 다음 몇 가지 사항을 고려해 보자.

malloc 이나 new 와 같은 함수는 범용 메모리 할당자다. 즉 응용 프로그램이 단일 스레드라도, 응용 프로그램이 링크한 malloc 함수는 다중 스레드를 처리하는 기능까지 포함한다. 이 같은 부가 기능이 응용 프로그램 성능을 떨어뜨린다.

차례로 malloc 과 new 는 운영체제 커널에 요청하여 메모리를 할당받고, free 와 delete 는 운영체제 커널에 요청하여 메모리를 반환한다. 즉 메모리를 할당하거나 해제할 때마다 운영체제는 사용자 영역 코드와 커널 영역 코드 사이를 전환해야 한다는 뜻이다. 따라서 malloc 이나 new 를 반복적으로 호출하는 프로그램은 문맥 전환 횟수가 늘어나는 탓에 그만큼 성능이 떨어진다.

프로그램을 짜다 보면 메모리를 할당 받은 후 필요하지 않을 경우에도 실수로 내버려 두는 경우가 빈번한데, C/C++에서는 자동 가비지 컬렉션을 지원하지 않는다. 그러다 보면 프로그램이 점유하는 메모리 양이 점점 증가하고, 아주 큰 프로그램에서는 성능이 급격히 떨어진다. 메모리가 점점 귀해지면서 시간이 걸리는 하드 디스크를 참조하는 횟수가 늘어나기 때문이다.

설계 목표

우리가 설계할 메모리 관리자는 다음을 목표로 삼는다.

• 속력
• 안정성
• 사용자 편의성
• 이식성

속력

메모리 관리자는 컴파일러가 제공하는 할당자보다 속력이 빨라야 한다. 반복적으로 메모리를 할당하고 해제해도 프로그램 속력이 떨어지지 않아야 한다. 가능하다면, 프로그램에서 자주 사용하는 할당 패턴을 효율적으로 처리하도록 최적화해야 한다.

안정성

메모리 관리자는 프로그램이 종료하기 전에 모든 메모리를 시스템으로 반환해야 한다. 즉 메모리가 새지 않아야 한다. 또한 (너무 큰 메모리를 요청하는 경우처럼) 오류 상황을 무난하게 처리해야 한다.

사용자 편의성

프로그램을 크게 수정하지 않고도 메모리 관리자를 통합하기 쉬워야 한다.

이식성

다른 시스템으로 쉽게 이식이 가능해야 한다. 특정 플랫폼에서만 제공하는 메모리 관리 기능을 사용해서는 안 된다.

메모리 관리자 설계 전략

메모리 관리자를 설계할 때는 다음 전략을 고려한다.

• 사전에 큰 메모리 블록을 확보한다.
• 프로그램이 자주 요청하는 크기로 최적화한다.
• 프로그램이 해제하는 메모리를 재사용한다.

사전에 큰 메모리 블록을 확보한다.

가장 인기있는 메모리 관리 전략 중 하나다. 프로그램을 시작할 때나 실행하는 도중에 간간이 시스템으로부터 큰 메모리 블록을 할당 받는다. 그런 다음, 프로그램이 개별 자료 구조를 위한 메모리 할당을 요청하면 미리 확보해 둔 메모리 블록에서 떼어 준다. 시스템 호출 횟수가 줄어들므로 그만큼 성능이 높아진다.

프로그램이 자주 요청하는 메모리 크기로 최적화한다.

프로그램마다 자주 요청하는 메모리 크기가 있기 마련이다. 메모리 관리자가 이러한 요청을 효율적으로 처리하면 프로그램 성능이 높아진다.

프로그램이 해제하는 메모리를 재사용한다.

프로그램이 해제하는 메모리를 따로 보관했다가 다시 사용한다. 즉 프로그램이 메모리를 요청하면 먼저 보관함을 뒤진다. 보관함에서 적절한 메모리를 찾지 못하면 미리 확보해 둔 메모리 블록에서 떼어 준다. 기본적으로는 프로그램 속력을 향상하고 메모리 누수를 방지할 목적으로 메모리를 관리하지만, 이 전략은 해제된 메모리를 재사용함으로써 프로그램이 점유하는 메모리 양도 줄인다. 메모리 할당자를 직접 구현해서 얻는 또 다른 이익이라 하겠다!

C++ new/delete 연산에 걸리는 시간

간단한 예제로 시작하겠다. 프로그램에서 복소수를 표현하는 Complex 클래스를 사용한다고 가정하자. 또한 프로그램은 new 와 delete 연산을 사용해서 복소수를 할당하고 해제한다. 코드는 Listing 1 과 같다.

Listing 1. C++로 구현한 Complex 클래스

                    
class Complex 
  {
  public:
  Complex (double a, double b): r (a), c (b) {}
  private:
  double r; // Real Part
  double c; // Complex Part
  };
  
int main(int argc, char* argv[]) 
  {
  Complex* array[1000];
  for (int i = 0;i  <  5000; i++) {
    for (int j = 0; j  <  1000; j++) {
      array[j] = new Complex (i, j);
      }
    for (int j = 0; j  <  1000; j++) {
      delete array[j];
      }
    }
  return 0;
  }      
				

안쪽 루프 두 개는 메모리를 1000번 할당하고 1000번 해제한다. 바깥쪽 루프는 안쪽 루프 두 개를 5000번 반복한다. 즉 프로그램을 실행하면 사용자 코드와 커널 코드 사이에 문맥 전환이 1000만 번 일어난다. 솔라리스 10에서 gcc-3.4.6으로 프로그램을 컴파일하여 돌리면 평균 3.5초가 걸린다. 이 값이 컴파일러가 제공하는 전역 new / delete 연산을 사용하는 경우에 얻어지는 기준 성능 지표다. 컴파일러보다 속력을 높여주는 메모리 관리자를 직접 구현하려면 Complex 클래스에 new / delete 연산을 재정의해야 한다.

New/Delete 자세히 살펴보기

C++에서 메모리 관리 방식을 변경하려면 new 와 delete 연산을 중복 정의하면 된다. 클래스마다 메모리 정책을 달리 적용하려면 해당 클래스에서 new 와 delete 연산을 중복 정의한다. 프로그램 전체에 동일한 메모리 정책을 적용하려면 전역 new 와 delete 연산을 재정의한다. 연산을 중복 정의하는 방법은 두 가지다. Listing 2 를 참조한다.

Listing 2. new/delete 연산 중복 정의

                    
void* operator new(size_t size); 
void   operator delete(void* pointerToDelete); 
-OR-
void* operator new(size_t size, MemoryManager& memMgr); 
void   operator delete(void* pointerToDelete, MemoryManager& memMgr);

위에 정의된 new 연산자는 첫 번째 인수로 넘어온 size만큼 메모리를 가공하지 않고 할당한다. delete 연산은 인수로 넘어온 메모리를 해제한다. 여기서 각 연산은 메모리를 할당하거나 해제하는 작업만 수행한다. 생성자나 소멸자를 호출하지 않는다. 생성자는 new 연산이 메모리를 할당한 후에 호출되고, 소멸자는 delete 연산이 메모리를 해제하기 전에 호출된다.

아래에 정의된 메모리 지정(placement new) 연산자는 메모리를 할당해 주는 클래스인 MemoryManager 인수를 추가로 받는다. MemoryManager가 할당한 메모리에 최종적으로 생성자가 호출된다. 이 튜토리얼에서는 첫 번째 new / delete 를 사용한다. 두 번째 new/delete를 사용하면 프로그램 코드 전체에 MemoryManager& 인수를 추가해야 하므로 ‘사용자 편의성’이라는 설계 목표에 어긋난다.

실제로 메모리를 할당하고 해제하는 작업은 MemoryManager 클래스가 모두 수행한다. Listing 3 에서 보듯이, new / delete 연산은 단순히 해당하는 MemoryManager 함수를 호출한다. 여기서 전역 변수 선언은 다음과 같다. MemoryManager gMemoryManager; // Memory Manager, global variable .

Listing 3. new, new[], delete, delete[] 연산에서 MemoryManager 함수 호출

                    
MemoryManager gMemoryManager; // Memory Manager, global variable

void* operator new (size_t size) 
  {
  return gMemoryManager.allocate(size);
  }

void* operator new[ ] (size_t size)
  {
  return  gMemoryManager.allocate(size);
  }

void operator delete (void* pointerToDelete)
  {
  gMemoryManager.free(pointerToDelete);
  }

void operator delete[ ] (void* arrayToDelete)
  {
  gMemoryManager.free(arrayToDelete);
  }      
				

참고:

• new[ ] 연산자에 전달되는 size 인수는 (배열 요소 수 * 각 요소 크기) 값이다.
• 클래스에 밀접한 new , delete , new[ ] , delete[ ] 연산자에서는 this 포인터를 사용하지 못한다. 즉 위 연산은 모두 정적 메서드다. 설계 시 항상 염두에 두어야 할 사항이다.
• 메모리 관리자를 전역 변수로 선언하는 대신 싱글톤(Singleton)을 사용해도 좋다.

이제 메모리 관리자 클래스의 기본적인 인터페이스를 정할 차례다. Listing 4 를 참조한다.

Listing 4. 메모리 관리자 인터페이스

                    
class IMemoryManager 
  {
  public:
    virtual void* allocate(size_t) = 0;
    virtual void   free(void*) = 0;
  };

class MemoryManager : public IMemoryManager
  {
  public: 
    MemoryManager( );
    virtual ~MemoryManager( );
    virtual void* allocate(size_t);
    virtual void   free(void*);
  };  
				

성능 향상을 위해 allocate 와 free 함수는 인라인으로 선언할 계획이다.

첫 번째 메모리 관리자 -- Complex 클래스, 단일 스레드 환경

이제까지 설명한 원리를 염두에 두고 첫 번째 메모리 관리자를 구현해 보자. 설명을 쉽게 진행하기 위해 이 단계에서 구현하는 메모리 관리자는 단일 스레드 환경에서 Complex 객체만을 할당하고 해제한다. 구체적으로는, 메모리 관리자 내에 Complex 객체 풀(pool)을 확보한 후 요청이 들어오면 풀에서 객체를 할당한다. 필요한 객체 수가 풀에 있는 객체 수를 초과하면 풀 크기를 늘인다. 프로그램이 반환하는 객체는 풀에 다시 넣는다. 그림 1 은 Complex 객체 풀을 표현한 모습이다.

그림 1. Complex 객체 풀

풀에서 각 블록은 두 가지 목표를 수행한다.

• Complex 객체를 저장한다.
• 풀에서 자신을 다음 블록으로 연결한다.

Complex 클래스 내부에 포인터를 저장하는 방법은 바람직하지 못하다. 그랬다가는 프로그램이 점유하는 메모리 양이 전반적으로 증가한다. 대신, Complex 클래스 내 private 자료를 구조체로 묶은 후 Complex 포인터와 union을 생성한다. 즉 풀에 있을 때는 다음 블록을 가리키는 포인터가 되고, Complex 객체로 사용할 때는 실수와 복소수를 저장하는 독립적인 구조체가 된다. Listing 5 는 수정한 Complex 클래스다.

Listing 5. 추가적인 메모리 부하 없이 Complex*를 저장하는 변경된 자료 구조

                    
class Complex 
  {
  public:
    Complex (double a, double b): r (a), c (b) {}
    private:
    union { 
      struct { 
        double r; // Real Part
        double c; // Complex Part
        };
      Complex* next;
    };
  };
				

그러나 이런 전략은 ‘사용자 편의성’이라는 설계 목표를 위반한다. 메모리 관리자를 통합하려면 원래 Complex 클래스를 크게 뜯어 고쳐야 하기 때문이다. 그래서 FreeStore 라는 클래스를 새로 추가한다. 풀에 속할 때는 포인터, 그 외에는 Complex 개체가 되는 클래스다. Listing 6 은 FreeStore 클래스다.

Listing 6. FreeStore 객체 자료 구조

                    
struct FreeStore 
  {
  FreeStore* next;
  };      
				

그러면 풀은 FreeStore 객체로 이루어진 연결 리스트가 된다. 목록 내 각 요소는 다음 요소를 가리키며, 이 요소를 Complex 객체로 사용한다. MemoryManager 클래스는 자유 풀에서 첫 번째 요소를 가리키는 포인터만 저장한다. 요소가 부족할 때 풀을 확장하는 메서드(expandPoolSize)와 프로그램이 종료할 때 풀을 해제하는 메서드(cleanup)는 private 메서드로 구현한다. Listing 7 은 FreeStore 개념을 추가하여 Complex 클래스를 수정한 모습이다.

Listing 7. FreeStore 개념을 추가하여 Complex 클래스를 수정한 자료 구조

                    
#include <sys/types.h> 

class MemoryManager: public IMemoryManager 
  { 
  struct FreeStore
    {
     FreeStore *next;
    }; 
  void expandPoolSize ();
  void cleanUp ();
  FreeStore* freeStoreHead;
  public:
    MemoryManager () { 
      freeStoreHead = 0;
      expandPoolSize ();
      }
    virtual ~MemoryManager () { 
      cleanUp ();
      }
    virtual void* allocate(size_t);
    virtual void   free(void*);
  };

MemoryManager gMemoryManager;

class Complex 
  {
  public:
    Complex (double a, double b): r (a), c (b) {}
    inline void* operator new(size_t);
    inline void   operator delete(void*);
  private:
    double r; // Real Part
    double c; // Complex Part
  };   
				

다음은 메모리를 할당하는 의사코드다.

1. FreeStore 풀이 존재하지 않는다면 FreesStore 풀을 생성한 후 3단계로 이동한다.
2. FreeStore 풀에 요소가 바닥났다면 FreeStore 풀을 새로 생성한다.
3. FreeStore 풀에서 첫 번째 요소를 반환한 후 다음 요소를 자유 공간을 점유하는 첫 번째 요소로 기억한다.

다음은 메모리를 해제하는 의사코드다.

1. 해제할 포인터의 next 필드 값을 현재 FreeStore 풀에서 자유 공간을 점유하는 첫 번째 요소로 설정한다.
2. 해제할 포인터를 FreeStore 풀에서 자유 공간을 점유하는 첫 번째 요소로 저장한다.

Listing 8 은 Complex 클래스를 생성하고 해제하는 new 와 delete 연산을 코드로 보여준다. Listing 9 는 FreeStore 풀을 확장하고 삭제하는 expandPoolSize와 cleanup 함수를 보여준다. 그래도 아직 문제가 남아있다. 무엇일까?

Listing 8. Complex 클래스를 위한 메모리 할당과 해제 코드

                    
inline void* MemoryManager::allocate(size_t size)
  {
  if (0 == freeStoreHead)
    expandPoolSize ();

  FreeStore* head = freeStoreHead;
  freeStoreHead = head->next;
  return head;
  }

inline void MemoryManager::free(void* deleted)
  {
  FreeStore* head = static_cast <FreeStore*> (deleted);
  head->next = freeStoreHead;
  freeStoreHead = head;
  }

void* Complex::operator new (size_t size) 
  {
  return gMemoryManager.allocate(size);
  }

void Complex::operator delete (void* pointerToDelete)
  {
  gMemoryManager.free(pointerToDelete);
  }  
				

FreeStore 풀을 생성하는 방법은 다소 까다롭다. 편법처럼 보이지만 FreeStore* 포인터는 Complex 객체로도 사용한다는 사실을 명심해야 한다. 따라서 Listing 9 처럼 FreeStore* 요청이 들어오면 FreeStore* 크기와 Complex 크기 중 큰 값을 사용해서 할당해야 한다.

Listing 9. FreeStore 풀을 확장하고 삭제하는 코드

                    
#define POOLSIZE 32

void MemoryManager::expandPoolSize ()
  {
  size_t size = (sizeof(Complex) > sizeof(FreeStore*)) ?
    sizeof(Complex) : sizeof(FreeStore*);
  FreeStore* head = reinterpret_cast <FreeStore*> (new char[size]);
  freeStoreHead = head;

  for (int i = 0; i < POOLSIZE; i++) {
    head->next = reinterpret_cast <FreeStore*> (new char [size]);
    head = head->next;
    }

  head->next = 0;
  }

void MemoryManager::cleanUp()
  {
  FreeStore* nextPtr = freeStoreHead;
  for (; nextPtr; nextPtr = freeStoreHead) {
    freeStoreHead = freeStoreHead->next;
    delete [] nextPtr; // remember this was a char array
    }
  }  
				

흥미로운 참고 사항 한 가지 FreeStore 요소는 여전히 전역 new / delete 연산자로 생성한다. 그러나 여기서 malloc / free 조합을 사용해도 좋다. 양쪽 경우를 따져봐서 평균 성능은 별다른 차이가 없었다.

이상으로 Complex 클래스 메모리를 자체적으로 할당하고 해제하는 메모리 관리자를 구현했다. 앞서 기준 성능 지표가 3.5초였다는 사실을 기억하는가? 우리 메모리 관리자로 테스트 프로그램을 돌리면 0.67초가 걸린다! 테스트 프로그램용 클라이언트 코드를 변경할 필요도 없다! 상당한 차이가 나지 않은가? 주된 이유는 두 가지다.

• 사용자 코드와 커널 코드 사이를 전환하는 횟수가 줄었다. 해제되는 메모리를 풀에 넣었다가 재사용하기 때문이다.
• 메모리 관리자가 단일 스레드 할당자라서 테스트 프로그램이라는 목적에 적합하다. 다중 스레드 환경은 나중에 고려한다.

앞서 설계에 아직 문제가 있다고 말했다. 프로그램에서 new 로 Complex 객체를 할당한 후 해제하지 않으면 메모리 누수가 생긴다. 물론, 컴파일러가 제공하는 new / delete 전역 연산을 사용해도 마찬가지다. 그러나 우리가 메모리 관리자를 구현하는 이유는 단순히 성능 때문만이 아니다. 메모리 관리자는 설계부터 메모리 누수를 방지해야 한다. 현재 new / cleanUp 함수는 new 로 할당한 후 명시적으로 해제한 메모리만 운영체제로 반환한다. 이러한 문제를 해결하려면 프로그램 초기화 시 더 큰 메모리 블록을 요청한 후 저장하는 수밖에 없다. new 연산은 저장한 메모리 블록에서 필요한 만큼씩 할당하고, cleanUp 함수는 메모리 블록에서 생성한 개발 객체가 아니라 저장한 메모리 블록을 몽땅 해제해야 한다.

비트맵 메모리 관리자

비트맵 메모리 관리자는 앞서 구현한 고정 크기 메모리 관리 방식에서 한 걸음 더 나간다. 여기서는 운영체제로부터 비교적 큰 메모리 덩어리를 확보한 후 필요한 만큼씩 쪼개 사용한다. 프로그램을 종료할 때는 메모리 덩어리 전체를 단번에 해제하는 방법으로 메모리 누수를 막는다. 또 한 가지 장점이라면, 비트맵 메모리 관리자는 new[ ] 와 delete[ ] 도 지원이 가능하다.

비트맵 메모리 관리자는 운영체제로부터 커다란 메모리 덩어리를 할당받은 후 일정한 크기로 잘게 나눈다. 이 예제에서는 Complex 객체 크기로 세분한다. 그런 다음, 메모리 덩어리 내에 있는 블록 수에 따라 비트맵을 관리한다. 비트맵 비트 수는 블록 수와 동일하며, 각 비트는 각 블록의 할당/자유 상태를 표시한다. 프로그램이 새 Complex 객체를 요청하면 메모리 관리자는 비트맵을 살펴보고 자유 블록을 찾아 할당한다. 모든 자유 블록은 해당 비트가 1이다. 할당된 블록은 해당 비트가 0이다. new[ ] 와 delete[ ] 연산은 Complex 배열 할당/해제 시 설정/해제한 비트 수를 기억하는 자료 구조를 추가로 사용한다.

비트맵 메모리 관리자

메모리 관리자는 운영체제로부터 상당히 큰 메모리 덩어리를 요청한다. 이후로 프로그램이 요청하는 메모리는 이 덩어리에서 할당한다. 운영체제로부터 메모리 덩어리를 확보하지 못하면 메모리 관리자는 프로그램에 적당한 메시지를 반환하고 종료한다. 메모리 덩어리를 확보한 후에는 비트맵 비트를 모두 1로 설정한다.

자유 블록이 바닥나면 메모리 관리자는 더 큰 메모리 덩어리를 운영체제에 요청한다. 이 때 MemoryManager 자료 구조에서 사용하는 비트맵도 적절히 확장된다. 반면, 프로그램이 delete를 호출하면 해당 블록은 자유 블록이 된다. 따라서 프로그램이 연속적이지 않은 블록을 해제할 경우 메모리 단편화 현상이 일어난다.

Listing 10 은 MemoryManager 클래스 기본 구조다. MemoryPoolList는 운영체제에서 확보한 메모리 덩어리 시작 주소를 저장한다. 메모리 덩어리마다 상응하는 BitMapEntryList 가 있다. FreeMapEntry 는 (배열이 아닌) new 호출 시 다음 자유 블록을 신속하게 찾아내는 자료 구조다.

Listing 10. MemoryManager 클래스 정의

                    
class MemoryManager : public IMemoryManager 
  {
    std::vector<void*> MemoryPoolList;
    std::vector<BitMapEntry> BitMapEntryList;
    //the above two lists will maintain one-to-one correspondence and hence 
    //should be of same  size.
    std::set<BitMapEntry*> FreeMapEntries;
    std::map<void*, ArrayMemoryInfo> ArrayMemoryList;

  private:
    void* AllocateArrayMemory(size_t size);
    void* AllocateChunkAndInitBitMap();
    void SetBlockBit(void* object, bool flag);
    void SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag);
  public: 
    MemoryManager( ) {}
    ~MemoryManager( ) {}
    void* allocate(size_t);
    void   free(void*);
    std::vector<void*> GetMemoryPoolList(); 
  };
				

ArrayMemoryList 는 Complex 객체 배열로 할당된 메모리 정보를 저장한다. 기본적으로는 ArrayMemoryInfo 구조체 배열의 (엄밀하게는 배열 시작 주소의) 맵이다. Listing 11 에서 보듯이, ArrayMemoryInfo 구조체는 메모리 풀( MemPoolListIndex ), 비트맵에서 배열이 시작되는 위치( StartPosition ), 배열 크기( Size )를 포함한다.

Listing 11. ArrayMemoryInfo 구조체 정의

                    
typedef struct ArrayInfo
  {
  int   MemPoolListIndex;
  int   StartPosition;
  int   Size;
  }
ArrayMemoryInfo; 
				

비트맵은 BitMapEntry 객체로 손쉽게 구현한다. 쉽게 조작하기 위해서다. Listing 12 에서 보듯이, BitMapEntry 클래스는 몇 가지 메타 정보를 추가로 포함한다. 한 비트나 여러 비트를 조작하려면 SetBit 와 SetMultipleBits API를 사용한다. FirstFreeBlock() API는 비트맵에서 첫 번째 자유 블록을 찾아 반환한다.

Listing 12. BitMapEntry 클래스 정의

                    
typedef struct BitMapEntry
  {
  int      Index;
  int      BlocksAvailable;
  int      BitMap[BIT_MAP_SIZE];
  public:
    BitMapEntry():BlocksAvailable(BIT_MAP_SIZE)
      {
      memset(BitMap,0xff,BIT_MAP_SIZE / sizeof(char)); 
      // initially all blocks are free and bit value 1 in the map denotes 
      // available block
      }
    void SetBit(int position, bool flag);
    void SetMultipleBits(int position, bool flag, int count);
    void SetRangeOfInt(int* element, int msb, int lsb, bool flag);
    Complex* FirstFreeBlock(size_t size);
    Complex* ComplexObjectAddress(int pos);
    void* Head();
  }
BitMapEntry;      
				

메모리 관리자는 (비트맵으로 사용하는) 'n' 비트 배열을 모두 1로 초기화한다. 각 비트는 할당할 메모리 블록 하나를 뜻한다. 초기화 작업은 모두 BitMapEntry 생성자가 수행한다.

프로그램이 Complex 클래스용 (배열이 아닌) new 나 malloc 을 호출하면 메모리 관리자는 FreeMapEntries 자료 구조에서 자유 블록을 찾는다. 자유 블록이 존재하면 해당 자유 블록을 반환한다. 자유 블록이 없으면 새 메모리 덩어리를 운영체제에 요청한 후 새 BitMapEntry 를 설정한다. 그런 다음, 새 메모리 덩어리에서 자유 블록을 찾아 사용 불가능하다는 표시로 해당 블록 비트를 0으로 설정한 후 포인터를 프로그램으로 넘겨준다. 구체적인 코드는 Listing 13 을 참조한다.

Listing 13. MemoryManager::allocate 정의

                    
void* MemoryManager::allocate(size_t size)
  {
  if(size == sizeof(Complex))    // mon-array version
    {
    std::set<BitMapEntry*>::iterator freeMapI = FreeMapEntries.begin();
    if(freeMapI != FreeMapEntries.end())
      {
      BitMapEntry* mapEntry = *freeMapI;
      return mapEntry->FirstFreeBlock(size);
      }
    else
      {
      AllocateChunkAndInitBitMap();
      FreeMapEntries.insert(&(BitMapEntryList[BitMapEntryList.size() - 1]));
      return BitMapEntryList[BitMapEntryList.size() - 1].FirstFreeBlock(size);
      }
    }
  else  // array version
    {
    if(ArrayMemoryList.empty())
      {
      return AllocateArrayMemory(size);
      }
    else 
      {
      std::map<void*, ArrayMemoryInfo>::iterator infoI =ArrayMemoryList.begin();
      std::map<void*, ArrayMemoryInfo>::iterator infoEndI = 
        ArrayMemoryList.end();
      while(infoI != infoEndI)
        {
        ArrayMemoryInfo info = (*infoI).second;
        if(info.StartPosition != 0)  // search only in those mem blocks  
          continue;             // where allocation is done from first byte
        else 
          {
          BitMapEntry* entry = &BitMapEntryList[info.MemPoolListIndex];
          if(entry->BlocksAvailable < (size / sizeof(Complex))) 
            return AllocateArrayMemory(size);
          else 
            {
            info.StartPosition = BIT_MAP_SIZE - entry->BlocksAvailable;
            info.Size = size / sizeof(Complex);
            Complex* baseAddress = static_cast<Complex*>(
              MemoryPoolList[info.MemPoolListIndex]) + info.StartPosition;

            ArrayMemoryList[baseAddress] = info;
            SetMultipleBlockBits(&info, false);

            return baseAddress;
            } 
          }
        }
      }
    } 
  }   
				

블록 하나 단위로 비트를 설정하거나 해제하는 코드는 Listing 14 와 같다.

Listing 14. MemoryManager::SetBlockBit 정의

                    
void MemoryManager::SetBlockBit(void* object, bool flag)
  {
  int i = BitMapEntryList.size() - 1;
  for (; i >= 0 ; i--)
    {
    BitMapEntry* bitMap = &BitMapEntryList[i];
    if((bitMap->Head <= object )&amp;&amp; 
      (&(static_cast<Complex*>(bitMap->Head))[BIT_MAP_SIZE-1] >= object))
      {
      int position = static_cast<Complex*>(object) - 
      static_cast<Complex*>(bitMap->Head);
      bitMap->SetBit(position, flag);
      flag ? bitMap->BlocksAvailable++ : bitMap->BlocksAvailable--;
      }
    }
  }  
				

여러 블록 단위로 비트를 설정하거나 해제하는 코드는 Listing 15 와 같다.

Listing 15. MemoryManager::SetMultipleBlockBits 정의

                    
void MemoryManager::SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag)
  {
  BitMapEntry* mapEntry = &BitMapEntryList[info->MemPoolListIndex];
  mapEntry->SetMultipleBits(info->StartPosition, flag, info->Size);
  }

				

new[ ] 와 delete[ ] 를 처리하는 방식은 조금 다르다. 메모리 관리자는 배열이 아닌 버전을 담당하는 메모리 덩어리와 배열 버전을 담당하는 메모리 덩어리를 분리해 놓았다. 그러면 메모리를 할당할 때 양쪽 유형에서 자유 메모리를 찾는 속력이 높아진다. 프로그램이 new[ ] 를 호출하면 메모리 관리자는 ArrayMemoryList 를 참조해서 연속적인 자유 블록 배열을 찾는다. 찾으면 해당 블록 배열의 시작 주소를 반환하고 해당 비트를 0으로 설정한다. 찾지 못하면 운영체제에 새로운 메모리 덩어리를 요청한 후 여기서 필요한 메모리를 할당한다. new 에서 사용하는 메모리 덩어리와 new[ ] 에서 사용하는 메모리 덩어리는 모두 MemoryManager 내부에 있는 MemPoolList 에 저장한다.

프로그램이 Complex 객체에 대해 (배열이 아닌) delete 나 free 를 호출하면 메모리 관리자는 먼저 해제할 블록이 속하는 메모리 덩어리를 찾는다( Listing 16 참조). 그런 다음, BitMapEntry 를 참조해 해제할 블록에 해당하는 비트를 1로 설정해 더 이상 사용하지 않는다고 표시한다. 코드 복잡도는 O(1)이다. 프로그램이 delete [ ] 를 호출하는 경우는 ArrayMemoryList 배열에서 연관된 정보를 추출한 후 비트맵 시작 위치와 크기를 파악해서 여러 비트를 1로 설정해 더 이상 사용하지 않는다고 표시한다.

Listing 16. MemoryManager::free 정의

                    
void MemoryManager::free(void* object)
  {
  if(ArrayMemoryList.find(object) == ArrayMemoryList.end())
    SetBlockBit(object, true);         // simple block deletion 
  else
    {//memory block deletion
    ArrayMemoryInfo *info = &ArrayMemoryList[object];
    SetMultipleBlockBits(info, true);
    }
  }
				

완벽한 비트맵 메모리 관리자 코드는 다운로드 절을 참조한다. 코드는 동작하는 메모리 관리자 예제이며, 위에서 설명한 목록을 모두 포함한다.

위로

파생 클래스 문제

대개 파생 클래스 크기는 기반 클래스 크기와 다르다. 예를 들어, Complex 클래스에서 ComplexT 라는 클래스를 파생했다고 가정하자. ComplexT 클래스는 시간에 따라 변하는 Complex 값을 추적한다. 즉 ComplexT 클래스는 Complex 클래스에 시간을 나타내는 unsigned long 변수가 하나 더 있다. 두 클래스 크기가 다르므로 앞서 정의한 new / delete 연산으로 ComplexT 클래스를 할당/해제하지 못한다. ComplexT 클래스에 맞게 new / delete 연산을 다시 정의하면 모를까. 해결책은 세 가지가 있다.

• MemoryManager 가 Complex 메모리 풀과 ComplexT 메모리 풀을 두 개 관리한다. 다시 말하면, 할당/해제 함수와 포인터를 모두 쌍으로 정의한다. 문제는 해결하지만 확장성이 떨어진다.
• 풀 하나를 관리하되, 블록 크기는 파생 클래스 중 가장 큰 값으로 잡는다. 그런 다음, 할당 함수는 파생 조건에 상관없이 allocate 를 사용해 무조건 가장 큰 값으로 메모리 블록을 할당한다. 문제는 해결하지만, 프로그램이 점유하는 메모리 양이 늘어나므로 비효율적이다.
• 다양한 객체 크기를 처리하는 범용 메모리 관리자를 구현한다.

자유 리스트 기반 메모리 관리자

일반적인 프로그램에서는 자주 요청하는 메모리 블록 크기가 대개 몇 가지로 한정되어 있다. 이 절에서 구현할 메모리 관리자는 이러한 경험적 법칙을 활용한다. 메모리 관리자는 빈번히 사용하는 크기마다 자유 블록 주소 리스트를 관리하는데, 이를 기술 용어로 자유 리스트(free-list)라고 한다. 예를 들어 8, 16, 24, 32, 48, 64 바이트를 자주 요청하는 프로그램이 있다면, 메모리 관리자는 각 바이트 별로 자유 리스트 6개를 관리한다. 비트맵 메모리 관리자와 비슷하게, 메모리 관리자는 초반에 운영체제로부터 커다란 메모리 덩어리를 확보한다. 그런 다음, 메모리 관리자 내부에서 메모리 덩어리를 개별 리스트로 나누어 관리한다. 프로그램이 'm' 바이트를 요청하면, 메모리 관리자는 이 값을 'm'에 가장 가까운 블록 크기 'n'으로 변환한다. 그런 다음, 블록 크기가 'n'인 리스트에서 자유 블록을 찾아서 할당한 다음 프로그램에 돌려준다.

보호 바이트 간략 소개

'n' 바이트 블록은 객체만이 아니라 몇 가지 메타 정보도 저장한다. 각 블록은 끝 부분에 보호 바이트(guard byte)라는 추가 바이트를 포함한다. 보호 바이트는 힙 메모리에서 사용하는 개념이다. 일반적으로, memcpy 와 memset 함수는 원래 할당 받은 메모리 범위를 벗어나서 힙 메모리를 손상시킬 수 있다. 그래서 많은 컴파일러는 메모리 할당 시 블록 앞뒤에 특수 문자, 즉 보호 바이트를 추가한다. 그런 다음, 해당 블록을 참조할 때 앞뒤에 특수 문자가 있는지 확인한다. 블록 앞뒤에 특수 문자가 없으면 프로그램이 어느 순간에 값을 덮어썼다고 가정한다. 즉 힙 메모리가 더 이상 정상 상태가 아니며 손상되었다고 가정한다. 이는 프로그래머를 괴롭히는 까다로운 메모리 버그를 찾아내는 좋은 방법이다. 다음 예제에서는 네 바이트 중 두 바이트를 보호 바이트로 사용한다. 세 번째 바이트는 객체 크기를 저장하고, 마지막 바이트는 블록 상태(자유/할당)를 나타내는 플래그를 저장한다.

자유 리스트 메모리 관리자 구현

앞서 설명했듯이, 메모리 관리자는 블록 크기 별로 블록 포인터 리스트를 여러 개 관리한다. 또한 운영체제에서 확보한 메모리 덩어리를 memoryPool 로 관리한다. MemoryManager 소멸자는 풀에 든 메모리 덩어리 전체를 해제하여 메모리 누수를 막는다. Listing 17 은 메모리 관리자 자료 구조다.

Listing 17. 자유 리스트 메모리 관리자를 위한 MemoryManager 클래스 정의

                    
class MemoryManager : public IMemoryManager 
  {
  private:
    VoidPtrList     Byte8PtrList;
    VoidPtrList     Byte16PtrList;
    VoidPtrList     Byte24PtrList;
    VoidPtrList     Byte32PtrList;
    VoidPtrList     Byte40PtrList;
    std::vector<void*>    MemoryPoolList;

    . . . . . . . . . //helper routines may go in here

  public: 
    MemoryManager( ) {}
    ~MemoryManager( ) {}
    void* allocate(size_t);
    void   free(void*);
  };    
				

예제 프로그램은 크기가 각각 16, 28, 32바이트인 세 가지 클래스를 사용한다. 보호 바이트까지 고려하면 24, 32, 40바이트 블록이 필요하다. 즉 Byte24PtrList , Byte32PtrList , Byte40PtrList 가 가장 자주 쓰이므로 코드 역시 세 리스트를 위주로 구현한다. 그러나 설계가 유연하므로 다른 블록 크기를 추가하기도 쉽다.

각 클래스에서 new 와 delete 연산을 중복 정의한다. 각 allocate / free 연산은 메모리 관리자 함수를 호출하여 메모리를 할당하고 해제한다. 메모리를 할당하고 해제하는 함수는 아래서 상세히 설명한다. 초기 객체 수는 1024개로 잡는다. 또한 예제에서 사용할 클래스 크기는 상수로 미리 정의한다. Listing 18 을 참조한다.

Listing 18. 메모리 관리자가 사용할 상수 정의

                    
  const int JOB_SCHEDULER_SIZE = sizeof(JobScheduler);
  const int COMPLEX_SIZE = sizeof(Complex);
  const int COORDINATE_SIZE = sizeof(Coordinate);
  const int POOL_SIZE = 1024; //number of elements in a single pool
            //can be chosen based on application requirements 

  const int MAX_BLOCK_SIZE = 36; //depending on the application it may change 
                //In above case it came as 36
				

위 상수는 메모리 관리자가 allocate 와 free 함수에서 사용한다.

메모리 할당

allocate 함수는 블록 크기를 지정한 인수 size를 보고 어느 자유 리스트에서 블록을 할당할지 결정한다. 그런 다음, 해당 리스트에 남아있는 자유 블록이 있는지 찾는다. 자유 리스트는 블록 자체가 아니라 블록 포인터만 저장한다는 사실에 주의한다(블록 자체는 MemoryPoolList 에 속한다).

자유 리스트가 비어 있다면, 운영체제에서 추가로 메모리 덩어리를 요청한 후 InitialiseByte24List , InitialiseByte32List , InitialiseByte40List 함수 중 하나로 초기화한다.

자유 블록이 있으면, 해당 블록을 할당 상태로 표시하고 보호 바이트를 설정한 후 블록 주소를 반환한다. 구현은 Listing 19 를 참조한다.

Listing 19. MemoryManager::allocate 정의

                    
void* MemoryManager::allocate(size_t size)
  {
  void* base = 0;
  switch(size)
    {
    case JOB_SCHEDULER_SIZE :  
      {
      if(Byte32PtrList.empty())
        {
        base = new char [32 * POOL_SIZE];
        MemoryPoolList.push_back(base);
        InitialiseByte32List(base);
        }
      void* blockPtr =  Byte32PtrList.front();
      *((static_cast<char*>(blockPtr)) + 30) = 32; //size of block set
      *((static_cast<char*>(blockPtr)) + 31) = 0; //block is no longer free
      Byte32PtrList.pop_front();
      return blockPtr;
      }         
    case COORDINATE_SIZE :  
      {
      if(Byte40PtrList.empty())
        {
        base = new char [40 * POOL_SIZE];
        MemoryPoolList.push_back(base);
        InitialiseByte40List(base);
        }
      void* blockPtr =  Byte40PtrList.front();
      *((static_cast<char*>(blockPtr)) + 38) = 40; //size of block set
      *((static_cast<char*>(blockPtr)) + 39) = 0; //block is no longer free
      Byte40PtrList.pop_front();
      return blockPtr;
      }         
    case COMPLEX_SIZE : 
      {
      if(Byte24PtrList.empty())
        {
        base = new char [24 * POOL_SIZE];
        MemoryPoolList.push_back(base);
        InitialiseByte24List(base);
        }
      void* blockPtr =  Byte24PtrList.front();
      *((static_cast<char*>(blockPtr)) + 22) = 24; //size of block set
      *((static_cast<char*>(blockPtr)) + 23) = 0; //block is no longer free
      Byte24PtrList.pop_front();
      return blockPtr;
      }
    default : break;
    }
  return 0;
  }
				

메모리 해제

free 함수는 해제할 블록 주소를 받는다. 주어진 블록 주소로 블록 끝에 있는 보호 바이트를 찾은 후 블록 크기를 읽는다. 블록 크기는 마지막 바이트 바로 앞 바이트에 들어 있다. 크기를 얻은 후에는 객체를 자유 상태로 설정하고 (마지막 바이트를 1로 설정하고) 해당하는 자유 리스트를 찾는다. 객체는 삭제 단계 끝 부분에 자유 리스트로 들어가게 된다. 구현은 Listing 20 을 참조한다.

Listing 20. MemoryManager::free 정의

                    
void MemoryManager::free(void* object)
  {
  char* init = static_cast<char*>(object);

  while(1)
    {
    int count = 0;
    while(*init != static_cast<char>(0xde))  
          //this loop shall never iterate more than 
      {                 // MAX_BLOCK_SIZE times and hence is O(1)
      init++;
      if(count > MAX_BLOCK_SIZE)
        {
        printf ("runtime heap memory corruption near %d", object);
        exit(1);
        } 
      count++; 
      }
    if(*(++init) == static_cast<char>(0xad))  // we have hit the guard bytes
      break;  // from the outer while 
    }
  init++;
  int blockSize = static_cast<int>(*init);
  switch(blockSize)
    {
    case 24: Byte24PtrList.push_front(object); break;
    case 32: Byte32PtrList.push_front(object); break;
    case 40: Byte40PtrList.push_front(object); break;
    default: break;
    }
  init++;
  *init = 1; // set free/available byte   
  }   
				

자유 리스트 메모리 관리자 전체 코드는 다운로드 절에서 참조한다. 코드는 실제로 동작하는 자유 리스트 메모리 관리자 구현과 위에서 설명한 목록을 모두 포함한다.

장점과 단점

위에서 설계한 메모리 관리자에는 몇 가지 장점이 있다.

• 크기가 다양한 메모리 블록을 깔끔하게 처리한다.
• 설계가 유연하며, 프로그램 요구사항에 따라 자유 리스트 크기를 결정하도록 확장할 수 있다.
• 보호 바이트를 사용하여 메타 정보를 저장한다. 객체마다 저장되는 메타 정보는 여러 모로 유용한데, 특히 프로그램 실행 도중 힙 메모리 손상을 감지할 수 있다.

위 설계는 성능이 높아진다는 장점이 있는 반면 메모리를 많이 사용한다는 단점도 있다.

다중 스레드 메모리 관리자

지금까지는 병렬 환경을 고려하지 않고 메모리 관리자를 설계했다. 다중 스레드 환경에서는 여러 스레드가 동시에 메모리를 할당하고 해제할 위험이 존재한다. 그러므로 다중 스레드 환경에서는 메모리 관리자가 수행하는 메모리 할당/해제 연산이 원자적(atomic)이어야 한다. 다시 말하면, 두 스레드가 동시에 메모리 연산을 시도해도 메모리 관리자는 상호 배타성을 보장해야 한다는 뜻이다. 할당/해제를 원자적 연산으로 만드는 표준 방법 중 하나가 잠금(lock) 메커니즘이다. 메모리를 할당하거나 해제하려는 스레드는 먼저 하나뿐인 잠금을 소유해야 한다. 다른 스레드가 이미 잠금을 소유하고 있다면, 현재 스레드는 대기 상태(block)로 들어간다. Listing 21 은 잠금 방식을 사용하는 함수 서식을 보여준다.

Listing 21. pthread mutex 메서드

                    
#include <pthread.h>

int pthread_mutex_init(pthread_mutex_t *mutex, 
    const pthread_mutexattr_t *attr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);   
				

우리 목적에 맞추려면 잠금과 잠금 해제를 흉내내기 위해 GNU 컴파일러가 제공하는 잠금 메커니즘만으로 충분하다. pthread mutex는 표준 헤더인 pthread.h 에 정의되어 있다. allocation / free 코드는 pthread_mutex_lock 과 pthread_mutex_unlock 메서드 사이에 놓인다. 한 스레드가 메모리 풀을 참조하는 동안에 다른 스레드가 pthread 메서드를 호출하면 잠금이 해제될 때까지 기다리게 된다. Listing 22 는 코드를 수정한 모습이다.

Listing 22. allocation/free 메서드를 수정한 모습

                    
void* MemoryManager::allocate(size_t size) 
  {
  pthread_mutex_lock (&lock); 
  ... // usual memory allocation code
  pthread_mutex_unlock (&lock);
  }

void* MemoryManager::free(size_t size) 
  {
  pthread_mutex_lock (&lock); 
  ... // usual memory deallocation code
  pthread_mutex_unlock (&lock);
  }   				

이제 메모리 관리자 클래스에 pthread_mutex_lock 객체를 포함시킨다. 클래스 생성자를 적절히 변경해서 pthread_mutex_init 을 호출하여 잠금을 초기화한다. 마찬가지로, 메모리 관리자 소멸자는 pthread_mutex_destroy 를 호출하여 mutex 객체를 소멸한다. Listing 23 은 MemoryManager 클래스를 수정한 모습이다.

Listing 23. 다중 스레드 할당/할당 해제를 처리하는 MemoryManager 클래스

                    
class MemoryManager : public IMemoryManager 
  { 
  pthread_mutex_t lock;
  ... // usual MemoryManager code follows
  };

MemoryManager::MemoryManager () 
  {
  pthread_mutex_init (&lock, NULL);
  ... // usual constructor code 
  }

MemoryManager:: ~MemoryManager () 
  {
  ... // usual destructor code 
  pthread_mutex_destroy (&lock);
  }      
				

이제 다중 스레드 환경에서 메모리 관리자를 돌려 보자. 우리 테스트에서는 단일 스레드 환경보다 속력이 확실히 떨어졌다. 상황에 맞게 구현한 특수 메모리 관리자가 필요한 이유가 다시 한 번 드러난다.

요약

이 튜토리얼에서 다음 개념을 살펴보았다.

• 사용자 프로그램에서 메모리 관리자가 필요한 이유
• 메모리 관리자 설계 요구사항
• 할당하는 메모리 크기가 일정한 메모리 관리자 구현 방법
• 할당하는 메모리 크기가 다양한 메모리 관리자 구현 방법
• 다중 스레드 환경에서 메모리를 할당하고 해제하는 방법

좀더 자세한 내용이 궁금하다면 참고자료 절을 살펴본다.



출처 : http://www.ibm.com/developerworks/kr/library/tutorial/au-dw-au-memorymanager-i.html