C/C++ 프로젝트에 사용할 메모리 관리자 직접 구현하기 (한글)

15 페이지 중 8 페이지 문서 옵션 샘플 코드  제안 및 의견 피드백 튜토리얼 평가 이 컨텐츠를 개선하기 위한 도움을 주십시오.

비트맵 메모리 관리자

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

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

비트맵 메모리 관리자

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

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

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

                    
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 )를 포함한다.

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

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

                    
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 을 참조한다.

                    
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 와 같다.

                    
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 와 같다.

                    
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로 설정해 더 이상 사용하지 않는다고 표시한다.

                    
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 를 사용해 무조건 가장 큰 값으로 메모리 블록을 할당한다. 문제는 해결하지만, 프로그램이 점유하는 메모리 양이 늘어나므로 비효율적이다.
• 다양한 객체 크기를 처리하는 범용 메모리 관리자를 구현한다.

위로

	15 페이지 중 8 페이지