메모리 관리

구현 선택, 구현의 모순, 동적 할당

Jonathan Bartlett, 기술 디렉터, New Media Worx

요약: 리눅스 프로그래머들이 사용할 수 있는 메모리 관리 기술을 살펴본다. C 언어 중심으로 설명 하겠지만 다른 언어들에도 적용할 수 있다. 메모리 관리가 어떻게 수행되는지, 메모리를 수동으로 관리하는 방법, 카운팅(counting) 또는 풀링(pooling)을 반-수동으로 관리하는 방법, 가비지 컬렉션을 사용하여 메모리를 자동으로 관리하는 방법을 설명한다.

원문 게재일: 2004 년 11 월 16 일
난이도: 초급
페이지뷰: 4483 회

메모리가 관리되어야 하는 이유

메모리 관리는 컴퓨터 프로그래밍의 가장 근본적인 분야 중 하나이다. 스크립팅 언어의 경우 메모리가 관리되는 방법을 신경 쓸 필요는 없지만 그것이 메모리 관리가 덜 중요하다는 것을 의미하는 것은 아니다. 메모리 매니저의 능력과 한계를 아는 것이 효과적인 프로그래밍에 있어 중요하다. C와 C++ 같은 시스템 언어들 경우, 메모리 관리가 필요하다. 이 글에서는 수동, 반자동, 자동 메모리 관리 방법의 기초를 설명하겠다.

Apple II에서 어셈블리 언어 프로그래밍을 하던 시절, 메모리 관리는 큰 문제가 아니었다. 기본적으로 전체 시스템을 실행했다. 시스템이 어떤 메모리를 갖고 있는지는 문제가 아니었다. 얼마나 많은 메모리가 남아있는지 파악할 필요도 없었다. 모든 컴퓨터는 같은 양의 메모리를 갖고 있었기 때문이다. 따라서 메모리 요구사항에 거의 변화가 없다면 사용할 메모리 영역을 선택하여 사용했다

하지만 프로그램의 각 부분에 얼마나 많은 메모리가 필요한지 알지 못한다면 간단한 컴퓨터일지라도 문제가 있었다. 제한된 공간과 메모리 요구가 다양하다면 다음의 요구사항을 충족시킬 방법이 필요하다:

  • 데이터를 처리할 메모리의 양을 결정한다.
  • 사용할 수 있는 메모리에서 메모리 섹션을 확보한다.
  • 메모리 섹션을 사용 가능한 메모리 풀로 리턴하여 프로그램의 다른 부분 또는 다른 프로그램에서 사용할 수 있도록 한다.

이러한 요구사항을 해결하는 라이브러리를 할당자(allocators)라고 한다. 문제가 동적일수록 메모리 관리는 더욱 중요하고 메모리 할당자의 선택이 더욱 중요해진다. 메모리 관리에 사용할 수 있는 다른 방법을들 보도록 하자.


C-스타일의 메모리 할당자(allocator)

C 프로그래밍 언어는 위 세 가지 요구사항을 수행하기 위해서 두 개의 함수를 제공한다:

  • malloc: 주어진 바이트 수를 할당하고 여기에 포인터를 리턴한다. 사용할 수 있는 충분한 메모리가 없다면 null 포인터를 리턴한다.
  • free: malloc에 의해 할당된 메모리 조각에 대한 포인터를 취해, 프로그램이나 OS가 나중에 사용할 수 있도록 이를 리턴한다. (실제로, 몇몇 malloc 구현은 메모리를 OS가 아닌 프로그램으로 리턴할 수 있다.)

물리적 메모리와 가상 메모리

자신의 프로그램 안에서 메모리가 할당되는 방법을 이해하려면 OS로 부터 프로그램으로 메모리가 어떻게 할당되는 지를 이해해야 한다. 컴퓨터 상의 각 프로세스는 모든 물리적 메모리에 액세스 했다고 생각한다. 분명, 동시에 다중의 프로그램을 실행하기 때문에 각 프로세스는 모든 메모리를 가질 수 없다. 프로세스는 가상 메모리를 사용하고 있다.

예를 들어, 프로그램이 메모리 주소 629에 액세스한다고 해보자. 하지만 가상 메모리 시스템은 629 RAM 위치에 이를 반드시 저장할 필요는 없다. 사실 RAM에 존재할 필요도 없다. 물리적 RAM이 꽉 찼다면 디스크로 옮겨질 수도 있다. 주소가 메모리가 할당된 물리적 장소를 반드시 반영할 필요는 없기 때문에 이를 가상 메모리라고 한다. OS는 가상 주소 대 물리적 주소 테이블을 관리하여 컴퓨터 하드웨어가 주소 요청에 적절히 대응할 수 있도록 한다. 그리고, 주소가 RAM이 아닌 디스크상에 있다면 OS는 일시적으로 프로세스를 중지하고 메모리를 디스크에서 언로드(unload)하고 디스크에서 그 요청된 메모리에 로딩하고 프로세스를 재시작 한다. 이러한 방식으로 각 프로세스는 고유의 주소 영역을 갖고 실행하고 물리적으로 설치된 것 보다 많은 메모리에 액세스 할 수 있다.

32-bit x86 시스템상에서, 각 프로세스는 4 GB 메모리에 액세스 할 수 있다. 요즘, 대부분의 사람들은 자신들의 시스템에 4GB 메모리를 갖추고 있지 않다. swap을 포함하더라도 프로세스 당 4GB 이하이다. 따라서, 프로세스가 로딩되면 특정 주소로 초기 메모리 할당이 이루어지고 시스템 브레이크(system break)를 호출한다. 과거에 이것은 언매핑(unmapped) 메모리이다. 즉 RAM 또는 디스크에 상응하는 물리적 위치를 할당 받지 못한 메모리이다. 따라서 프로세스가 초기 할당부터 메모리가 부족하면 OS가 더 많은 메모리를 매핑하도록 요청해야 한다. (매핑은 수학용어로 일대일(one-to-one) 대응을 의미한다-메모리는 가상 주소가 상응하는 물리적 위치를 갖고 있을 경우 "매핑"되어 그곳에 저장된다.)

유닉스 기반 시스템은 추가 메모리로 매핑되는 두 개의 기본적인 시스템 호출을 갖고 있다:

  • brk: brk()는 매우 간단한 시스템 호출이다. 이 프로세스를 위한 매핑된 메모리의 끝에 있는 위치인 시스템 브레이크를 기억하는가? 프로세스에 메모리를 추가 또는 제거하기 위해 brk()는 그 위치를 단순히 앞뒤로 이동한다.
  • mmap: mmap() 또는 "memory map"은 brk() 비슷하지만 훨씬 유연하다. 우선, 프로세스의 끝 뿐만 아니라 어디에나 메모리를 매핑할 수 있다. 그리고 가상 주소를 물리적 RAM 또는 swap에 매핑할 수 있고 파일과 파일 위치로 매핑하여 읽고 쓰는 메모리 주소가 파일에서 데이터를 읽고 쓸 것이다. 하지만 여기서는 mmap의 기능에 초점을 맞춰 매핑된 RAM을 프로세스에 추가하는 것을 설명하겠다. munmap()mmap()와 반대되는 작동을 수행한다.

brk() 또는 mmap()은 가외의 가상 메모리를 프로세스에 추가하는데 사용될 수 있다. 우리 예제에서는 보다 간단하고 일반적인 brk()를 사용할 것이다.

할당자(allocator) 구현하기

C 프로그래밍을 많이 사용했다면 malloc()free()를 상당히 많이 사용했을 것이다. 하지만 이들이 OS에서 어떻게 구현되는지에 대해서는 많이 생각하지 못했을 것이다. 이 섹션에서는 mallocfree의 간단한 구현 코드를 소개하겠다.

이 예제를 실행하려면, 코드를 복사하여 malloc.c 파일에 붙인다.

대부분의 OS에서 메모리 할당은 두 개의 함수로 핸들된다:

  • void *malloc(long numbytes): 메모리의 numbytes를 할당하여 포인터를 파일 바이트로 리턴한다.
  • void free(void *firstbyte): 이전 malloc에 의해 리턴된 포인터가 있다면, 할당된 공간을 프로세스의 "유휴 공간(free space)"에 준다.

malloc_init은 메모리 할당자를 초기화 할 함수가 될 것이다. 세 가지 일을 수행한다: 초기화되는 할당자를 확인하고, 시스템 상에 유효 메모리 주소를 찾고, 관리되는 메모리의 앞에 포인터를 설정한다. 이 세 변수는 글로벌 변수이다:


Listing 1. 글로벌 변수
int has_initialized = 0;

void *managed_memory_start;

void *last_valid_address;

앞서 언급했듯이 매핑된 메모리의 끝-마지막 유효 주소-는 시스템 브레이크 또는 커런트 브레이크로 알려져 있다. 대부분의 유닉스 시스템 상에서 커런트 시스템 브레이크를 찾으려면 sbrk(0)함수를 사용한다. sbrk은 인자에 있는 바이트의 수 만큼 커런트 시스템 브레이크를 움직이고 새로운 시스템 브레이크를 리턴한다. 인자 0으로 이것을 호출하면 커런트 브레이크를 리턴한다. 다음은 malloc초기화 코드이다. 커런트 브레이크를 찾고 변수를 초기화한다:


Listing 2. 할당자 초기화 함수
/* Include the sbrk function */

#include <unistd.h>

void malloc_init()

{

	/* grab the last valid address from the OS */

	last_valid_address = sbrk(0);


	/* we don't have any memory to manage yet, so
	 *just set the beginning to be last_valid_address
	 */

	managed_memory_start = last_valid_address;

	/* Okay, we're initialized and ready to go */

 	has_initialized = 1;

}

이제 메모리를 올바르게 관리하기 위해 무엇을 할당하고 무엇을 할당 해제하는지를 트래킹할 수 있어야 한다. free가 호출된 후에 mark block 같은 사용되지 않은 것을 실행해야 한다. 그리고 malloc이 호출되면 사용되지 않은 block의 위치를 정할 수 있다. 따라서 malloc에 의해 리턴된 모든 메모리 조각의 시작에는 이 구조를 갖게 된다:


Listing 3. Memory Control Block 구조 정의
struct mem_control_block {

	int is_available;

	int size;

};

이제, malloc을 호출하는 프로그램에 문제를 일으킬 것이라고 생각할 수도 있다. 이들이 어떻게 구조를 알 수 있겠는가? 답은 '그것에 대해 알 필요가 없다' 이다; 이것을 리턴하기 전에 구조 뒤에 포인터를 움직임으로서 숨길 수 있다. 이는 리턴된 포인터가 어떤 목적으로도 사용되지 않은 메모리를 지적하도록 할 것이다. 이러한 방식으로, 호출 프로그램의 관점에서 볼 때, 그들이 얻는 모든 것은 유휴의 개방 메모리 이다. free()를 통해 포인터를 뒤로 전달하면 얼마간의 메모리 바이트를 저장하여 이 구조를 다시 찾는다.

이제 메모리 할당에 대해 논하기 전에 메모리를 비우는 것에 대해 이야기하려고 한다. 이것이 보다 간단하기 때문이다. 메모리를 비우기 위해 해야 할 일은 주어진 포인터를 취해서 sizeof(struct mem_control_block) 바이트를 백업하고 이를 사용 가능한 것으로 표시하는 것이다:


Listing 4. 할당 해제 함수
void free(void *firstbyte) {

	struct mem_control_block *mcb;

	/* Backup from the given pointer to find the
	 * mem_control_block
	 */

	mcb = firstbyte - sizeof(struct mem_control_block);

	/* Mark the block as being available */

	mcb->is_available = 1;

	/* That's It!  We're done. */

	return;
}

여러분도 보다시피 이 할당자에서 메모리 비우기는 매우 간단한 방식을 사용하여 일정한 시간에 수행된다. 메모리 할당은 약간 더 어렵다. 다음은 알고리즘의 아웃라인이다:


Listing 5. 주 할당자용 가상 코드
1. If our allocator has not been initialized, initialize it.

2. Add sizeof(struct mem_control_block) to the size requested.

3. Start at managed_memory_start.

4. Are we at last_valid address?

5. If we are:

   A. We didn't find any existing space that was large enough
      -- ask the operating system for more and return that.

6. Otherwise:

   A. Is the current space available (check is_available from
      the mem_control_block)?

   B. If it is:

      i)   Is it large enough (check "size" from the
           mem_control_block)?

      ii)  If so:

           a. Mark it as unavailable

           b. Move past mem_control_block and return the
              pointer

      iii) Otherwise:

           a. Move forward "size" bytes

           b. Go back go step 4

   C. Otherwise:

      i)   Move forward "size" bytes

      ii)  Go back to step 4

오픈 청크를 찾고 있는 링크 된 포인터를 사용하여 메모리를 검사하고 있다. 다음은 코드이다:


Listing 6. 주 할당자
void *malloc(long numbytes) {

	/* Holds where we are looking in memory */

	void *current_location;

	/* This is the same as current_location, but cast to a
	 * memory_control_block
	 */

	struct mem_control_block *current_location_mcb;

	/* This is the memory location we will return.  It will
	 * be set to 0 until we find something suitable
	 */

	void *memory_location;

	/* Initialize if we haven't already done so */

	if(! has_initialized) 	{

		malloc_init();

	}

	/* The memory we search for has to include the memory
	 * control block, but the users of malloc don't need
	 * to know this, so we'll just add it in for them.
	 */

	numbytes = numbytes + sizeof(struct mem_control_block);

	/* Set memory_location to 0 until we find a suitable
	 * location
	 */

	memory_location = 0;

	/* Begin searching at the start of managed memory */

	current_location = managed_memory_start;

	/* Keep going until we have searched all allocated space */

	while(current_location != last_valid_address)

	{

		/* current_location and current_location_mcb point
		 * to the same address.  However, current_location_mcb
		 * is of the correct type, so we can use it as a struct.
		 * current_location is a void pointer so we can use it
		 * to calculate addresses.
		 */

		current_location_mcb =

			(struct mem_control_block *)current_location;

		if(current_location_mcb->is_available)

		{

			if(current_location_mcb->size >= numbytes)

			{

				/* Woohoo!  We've found an open,
				 * appropriately-size location.
				 */

				/* It is no longer available */

				current_location_mcb->is_available = 0;

				/* We own it */

				memory_location = current_location;

				/* Leave the loop */

				break;

			}

		}

		/* If we made it here, it's because the Current memory
		 * block not suitable; move to the next one
		 */

		current_location = current_location +

			current_location_mcb->size;

	}

	/* If we still don't have a valid location, we'll
	 * have to ask the operating system for more memory
	 */

	if(! memory_location)

	{

		/* Move the program break numbytes further */

		sbrk(numbytes);

		/* The new memory will be where the last valid
		 * address left off
		 */

		memory_location = last_valid_address;

		/* We'll move the last valid address forward
		 * numbytes
		 */

		last_valid_address = last_valid_address + numbytes;

		/* We need to initialize the mem_control_block */

		current_location_mcb = memory_location;

		current_location_mcb->is_available = 0;

		current_location_mcb->size = numbytes;

	}

	/* Now, no matter what (well, except for error conditions),
	 * memory_location has the address of the memory, including
	 * the mem_control_block
	 */

	/* Move the pointer past the mem_control_block */

	memory_location = memory_location + sizeof(struct mem_control_block);

	/* Return the pointer */

	return memory_location;

 }

그리고 이것은 우리의 메모리 매니저이다. 이제 이를 구현하여 우리의 프로그램에서 실행시키도록 한다.

malloc 호환의 할당자를 구현하려면 (realloc()같은 몇몇 함수는 다루지 않았지만, malloc()free()도 주요 함수이다.) 다음 명령어를 실행한다:


Listing 7. 할당자 컴파일 하기
gcc -shared -fpic malloc.c -o malloc.so

이것은 malloc.so라는 파일을 만들어낸다. 이것이 우리 코드를 포함하고 있는 공유 라이브러리이다.

다음과 같이 유닉스 시스템에서 시스템 malloc() 대신 본인의 할당자를 사용할 수 있다:


Listing 8. 표준 malloc 대체
LD_PRELOAD=/path/to/malloc.so

export LD_PRELOAD

LD_PRELOAD 환경 변수는 동적 링커가 로딩할 실행 파일에 전에 주어진 공유 라이브러리의 심볼을 로딩하게 한다. 지정된 라이브러리에서 그 심볼에 우선순위를 준다. 따라서 이 세션에서 지금부터 우리가 시작하는 모든 애플리케이션은 시스템이 아닌 우리의 malloc()을 사용할 것이다. 몇몇 애플리케이션들 malloc()을 사용하지 않지만 이들은 예외인 경우이다. realloc() 같은 메모리 관리 함수를 사용하거나 malloc()의 내부 작동에 대한 어설픈 추측을 한다면 분명 충돌이 일어날 것이다. ash 쉘은 우리의 새로운 malloc()을 사용하면 작동이 잘 될 것이다.

malloc()이 사용되고 있다는 것을 확인하려면 함수의 엔트리 포인트에 있는 write()에 호출을 추가하여 이를 테스트해야 한다.

우리의 메모리 매니저는 보완되어야 할 것이 많이 있다. 다음과 같은 단점들이 있다:

  • 시스템 브레이크(글로벌 변수)에서 작동하기 때문에 다른 할당자 또는 mmap와 공존할 수 없다.
  • 메모리를 할당할 때, 최악의 시나리오는 모든 프로세스의 메모리를 거쳐야 한다는 것이다: 여기에는 디스크상에 위치한 많은 메모리가 포함되어 있다. 이는 OS가 데이터를 디스크에서 이동시켜야 한다는 것을 의미한다.
  • 메모리 부족 에러를 핸들링 할 방도가 없다.(malloc은 에러가 아닌 경우만 취급한다.)
  • realloc()같은 다른 많은 메모리 함수들을 구현하지 않는다.
  • sbrk() 요청한 것 보다 많은 메모리를 주기 때문에 힙의 끝에 메모리를 유출하게 된다.
  • is_available 플래그는 4-byte 단어를 사용한다. 1 bit 정보를 포함할 때에도 그렇다.
  • 할당자는 쓰레드 보안이 되지 않는다.
  • 할당자는 유휴 공간을 더 큰 블록으로 합체할 수 없다.
  • 할당자의 간단한 적합(fitting) 알고리즘이 잠재적인 메모리 단편화를 만든다.
  • 이외에도 많은 문제들이 남아있다.

기타 malloc 구현

malloc()의 여러 구현이 있고 저마다의 장단점이 있다. 할당자를 디자인할 때 다음 사항을 고려해야 한다:

  • 할당 속도
  • 할당 해제 속도
  • 쓰레디드 환경에서의 작동
  • 메모리가 파일링(filing)에 가까웠을 때의 작동
  • 캐시 지역성
  • 메모리 오버헤드 기록
  • 가상 메모리 환경에서의 작동
  • 크고 작은 객체들
  • 실시간 게런티

각 구현 마다 장단점이 있다. 우리의 단순한 할당자의 경우 할당이 매우 느리지만 할당 해제는 매우 빠르다. 가상 메모리 시스템을 사용한 빈약한 작동 때문이다. 큰 객체에 적합하다.

이외에도 다른 할당자들을 사용할 수 있다:

  • Doug Lea Malloc: Doug Lea Malloc은 Doug Lea의 원래 할당자, GNU libc 할당자 ptmalloc을 포함한 전체 할당자군이다. Doug Lea의 할당자는 기본적인 구조가 우리 버전과 매우 비슷하지만 인덱스를 결합하여 검색이 훨씬 빠르고 여러 사용되지 않는 청크들을 하나의 큰 청크로 결합하는 기능도 있다. 또한 캐싱을 활용하여 최근에 비워진 메모리를 빠르게 재사용할 수 있도록 한다. ptmalloc은 다중 쓰레드를 지원하도록 확장된 Doug Lea Malloc의 한 버전이다. (참고자료)
  • BSD Malloc: 4.2 BSD와 함께 배포되고 FreeBSD에 포함된 구현인 BSD Malloc은 사전 결정된 크기의 객체 풀(pool)로부터 객체를 할당하는 할당자이다. 객체 사이즈를 위한 사이즈 클래스를 갖고 있다. 따라서 일정 사이즈의 객체를 요구한다면 객체에 맞는 어떤 사이즈의 클래스든지 할당할 것이다. 빠른 구현이라는 장점이 있지만 메모리를 낭비할 수 있다. (참고자료)
  • Hoard: Hoard는 멀티쓰레디드 환경에서 빠르게 작동할 목적으로 작성되었다. 따라서 어떤 프로세스라도 메모리 할당을 기다리지 않도록 잠금(locking)을 최대한 활용하도록 설계되었다. 많은 할당과 할당 해제를 수행하는 멀티쓰레디드 프로세스의 속도를 크게 높일 수 있다. (참고자료)

이것들은 많은 할당자들에 대해 잘 알려진 것들이다. 여러분의 프로그램이 할당에 대해 특별한 필요가 있다면 그 프로그램이 메모리를 할당하는 방식에 맞는 커스텀 할당자를 작성하는 것이 더 낫다. 하지만 할당자 디자인이 익숙하지 않다면 커스텀 할당자는 더 많은 문제를 만들어 낼 수 있다. 이 문제에 관해서는 Donald Knuth의 저서 The Art of Computer Programming Volume 1: Fundamental Algorithms in section 2.5, "Dynamic Storage Allocation"을 참조하기 바란다. (참고자료)

C++에서, operator new()를 오버로드하여 클래스 기반 또는 템플릿 기반의 할당자를 구현할 수 있다. Andrei Alexandrescu의 Modern C++ Design의 4장("Small Object Allocation")에서는 작은 객체 할당자에 대해 설명하고 있다. (참고자료)

malloc()기반 메모리 관리의 단점

우리의 메모리 매니저 뿐만 아니라 malloc() 기반의 메모리 관리에도 단점은 있다. malloc()으로 메모리를 관리하는 것은 장기 실행하는 스토리지를 관리해야 하는 프로그램에게는 쥐약이다. 메모리 여유(floating)에 대한 레퍼런스가 많다면 언제 릴리즈 되어야 하는지 알기 힘들다. 수명주기가 현재 함수까지로 제한되어 있는 메모리는 관리가 쉽지만 그 이상의 수명주기를 가진 메모리는 훨씬 더 어렵다. 또한 많은 API들은 메모리 관리에 대한 책임이 호출 프로그램에 있는지 아니면 호출된 함수에 있는지에 대해 모호하다.

메모리를 관리할 때의 문제들 때문에 많은 프로그램들은 각자의 메모리 관리 규칙을 따르고 있다. C++의 예외 핸들링은 이 일을 더욱 복잡하게 한다. 가끔, 실제 연산 태스크를 수행 하는 것 보다 메모리 할당 및 클린업 관리에 더 많은 코드가 집중되어 있는 것 같다. 따라서 메모리 관리에 대한 다른 대안을 모색하고자 한다.


반자동 메모리 관리 전략

Reference counting

Reference counting은 반자동 메모리 관리 기술로서 어느 정도의 프로그래머 지원이 필요하다. 하지만 객체가 더 이상 사용되지 않는 다는 것 까지 알 필요는 없다. reference counting 방식은 여러분을 위한 것이다.

reference counting에서 공유된 모든 데이터 구조는 그 구조에 현재 활성화된 '레퍼런스'의 수를 포함하는 필드를 갖고 있다. 프로시저가 포인터에서 데이터 구조로 전달되면 레퍼런스 카운트(reference count)에 추가한다. 기본적으로 데이터 구조에 어떻게 위치들이 저장되는지를 명령하고 있는 것이다. 프로시저가 이것을 사용하는 것을 끝마치면 레퍼런스 카운트가 감소한다. 이와 동시에 카운트가 0으로 떨어졌는지를 확인한다. 그렇다면 메모리가 비워진 것이다.

이것의 장점은 주어진 데이터 구조가 따라야 하는 프로그램의 모든 경로를 따라갈 필요가 없다는 것이다. 이것에 대해 각 지역화된 레퍼런스는 카운트를 적절히 감소 또는 증가시킨다. 이로서 메모리를 사용중일 때 비워지게 되는 현상을 막는다. 하지만 레퍼런스 카운팅 방식의 데이터 구조를 사용할 때마다 reference counting 함수를 실행해야 한다. 또한, 빌트인 함수와 삼자 라이브러리는 reference counting 방식을 모르거나 사용할 수 없다. reference counting은 순환식 레퍼런스를 가진 구조에는 어려움을 겪는다.

reference counting을 구현하려면 두 개의 함수가 필요하다. 하나는 레퍼런스 카운트를 증가시키는 함수이고 하나는 레퍼런스 카운트를 감소시켜 0에 도달했을 때 메모리를 비우는 함수이다.

다음은 reference counting 예제이다:


Listing 9. 기본적인 reference counting 함수
/* Structure Definitions*/

/* Base structure that holds a refcount */

struct refcountedstruct

{

	int refcount;

}

/* All refcounted structures must mirror struct
 * refcountedstruct for their first variables
 */

/* Refcount maintenance functions */

/* Increase reference count */

void REF(void *data)

{

	struct refcountedstruct *rstruct;

	rstruct = (struct refcountedstruct *) data;

	rstruct->refcount++;

}

/* Decrease reference count */

void UNREF(void *data)

{

	struct refcountedstruct *rstruct;

	rstruct = (struct refcountedstruct *) data;

	rstruct->refcount--;

	/* Free the structure if there are no more users */

	if(rstruct->refcount == 0)

	{

		free(rstruct);

	}

}

무엇을 하고자 하느냐에 따라 REFUNREF 가 상황을 복잡하게 할 수 있다. 예를 들어 멀티쓰레디드 프로그램에 잠금을 추가하고자 한다면 refcountedstruct를 확장하여 메모리를 비우기 전에 호출 할 함수에 대한 포인터를 추가하고 싶을 것이다. (객체 지향 언어의 디스트럭터(destructor)와 같다-구조에 포인터가 포함되어 있을 때에만 필요하다.)

REFUNREF를 사용할 때, 포인터 할당에 있어 다음 규칙을 준수해야 한다:

  • UNREF 할당 전에 왼쪽 포인터가 가르키는 값
  • REF 할당 후에 왼쪽 포인터가 가르키는 값

refcounted 구조로 전달된 함수의 경우 다음 규칙을 따라야 한다:

  • REF 함수의 시작에 있는 모든 포인터
  • UNREF 함수의 끝에 있는 모든 포인터

다음은 reference counting을 사용하는 코드 예제이다:


Listing 10. reference counting 예제
/* EXAMPLES OF USAGE */


/* Data type to be refcounted */

struct mydata

{

	int refcount; /* same as refcountedstruct */

	int datafield1; /* Fields specific to this struct */

	int datafield2;

	/* other declarations would go here as appropriate */

};


/* Use the functions in code */

void dosomething(struct mydata *data)

{

	REF(data);

	/* Process data */

	/* when we are through */

	UNREF(data);

}


struct mydata *globalvar1;

/* Note that in this one, we don't decrease the
 * refcount since we are maintaining the reference
 * past the end of the function call through the
 * global variable
 */

void storesomething(struct mydata *data)

{

	REF(data); /* passed as a parameter */

	globalvar1 = data;

	REF(data); /* ref because of Assignment */

	UNREF(data); /* Function finished */

}

reference counting은 다소 간단하기 때문에 대부분의 프로그래머들은 라이브러리를 사용하기 보다는 이들 자체를 구현한다. 하지만 mallocfree 같은 저급의 할당자들을 의존하여 메모리를 할당 및 릴리스 하고 있다.

reference counting은 Perl 같은 고급 언어에서 많이 사용된다. 그러한 언어에서 레퍼런스 카운팅은 언어에 의해 자동으로 핸들 되어 확장 모듈을 작성하는 것 외에는 걱정할 것이 없다. 모든 것이 레퍼런스 카운팅 되어야 하기 때문에 속도는 느리지만 안전성이 높고 프로그래밍이 쉽다:

  • 간단한 구현
  • 사용이 쉬움
  • 레퍼런스가 데이터 구조의 일부이기 때문에 캐시 지역성이 우수함

하지만 단점도 있다:

  • 레퍼런스 카운팅 함수를 호출하는 것을 절대 잊어서는 안된다.
  • 순환 데이터 구조의 일부인 구조를 릴리스 하지 않는다.
  • 거의 모든 포인터 할당이 느리다.
  • 레퍼런스 카운팅 된 객체를 사용하는 동안 예외 핸들링 (try 또는 setjmp()/longjmp())을 사용할 때 추가 조치를 취해야 한다.
  • 레퍼런스를 핸들 할 여분의 메모리가 필요하다.
  • 레퍼런스 카운터는 구조 내에서 첫 번째 위치를 차지한다. 이는 대부분의 머신에서 가장 빠르게 액세스 할 수 있다.
  • 멀티쓰레디드 환경에서 수행할 때 느리고 어렵다.

C++는 reference counting 같은 상세한 포인터 핸들링을 핸들 할 수 있는 스마트 포인터(smart pointers)를 사용하여 프로그래머 오류를 줄일 수 있다. 하지만 스마트 포인터(C 라이브러리로의 링크)를 핸들 할 수 없는 레거시 코드를 사용해야 한다면 이를 사용하지 않는 것이 낫다. 따라서 이는 C++ 전용 프로젝트에만 유용하다. 스마트 포인터를 사용하려면 Alexandrescu의 Modern C++ Design의 "Smart Pointers"를 참조하기 바란다.

메모리 풀(pool)

메모리 풀은 메모리 관리를 반자동화 할 수 있는 또 하나의 방식이다. 메모리 풀은 특정 단계를 거쳐야 하는 프로그램을 위해 메모리 관리를 자동화한다. 예를 들어, 많은 네트워크 서버 프로세스들은 커넥션 당 할당된 메모리를 갖고 있다. 최대 수명은 현재 커넥션의 수명이다. 풀링 메모리를 사용하는 Apache는 고유의 메모리 풀을 갖고 있는 단계로 나뉘어진 연결을 갖고 있다. 이 단계의 끝에, 전체 메모리 풀은 한번에 비워진다.

풀링 메모리를 관리 할 때, 각 할당은 할당되어야 하는 곳부터 메모리의 풀을 지정해야 한다. 각 풀은 다른 수명을 갖고 있다. Apache에서 서버의 수명을 지속시키는 풀이 있다. 하나는 연결의 수명을 지속시키는 것이고 하나는 요청의 수명을 지속시키는 것이다. 따라서 연결 보다 오래 지속되는 데이터를 만들지 않는 일련의 함수를 갖고 있다면 커넥션 풀에서 이 모든 것을 할당하면서 연결 끝에는 자동으로 비워진다는 것을 알 수 있다. 게다가 어떤 구현은 메모리 풀이 비워지기 비로 직전에 호출되는 레지스터링 클린업 함수로 하여금 메모리가 비워지기 전에 수행되어야 하는 추가 태스크를 수행하도록 한다. (객체 지향의 디스트럭터와 비슷하다.)

자신이 프로그램에서 풀을 사용하려면 GNU libc의 obstack 구현 또는 Apache의 Apache Portable Runtime을 사용할 수 있다. GNU obstack는 GNU 기반 리눅스 배포판에 기본적으로 포함되기 때문에 유용하다. Apache Portable Runtime은 멀티플랫폼 서버 소프트웨어를 작성하는 모든 측면들을 핸들 할 수 있는 유틸리티가 많아서 좋다. (참고자료).

다음의 가상 코드는 obstack의 사용법을 보여준다:


Listing 11. obstack 코드 예제
#include <obstack.h>

#include <stdlib.h>

/* Example code listing for using obstacks */

/* Used for obstack macros (xmalloc is
   a malloc function that exits if memory
   is exhausted */

#define obstack_chunk_alloc xmalloc

#define obstack_chunk_free free

/* Pools */

/* Only permanent allocations should go in this pool */

struct obstack *global_pool;

/* This pool is for per-connection data */

struct obstack *connection_pool;

/* This pool is for per-request data */

struct obstack *request_pool;

void allocation_failed()

{

	exit(1);

}

int main()

{

	/* Initialize Pools */

	global_pool = (struct obstack *)

		xmalloc (sizeof (struct obstack));

	obstack_init(global_pool);

	connection_pool = (struct obstack *)

		xmalloc (sizeof (struct obstack));

	obstack_init(connection_pool);

	request_pool = (struct obstack *)

		xmalloc (sizeof (struct obstack));

	obstack_init(request_pool);

	/* Set the error handling function */

	obstack_alloc_failed_handler = &allocation_failed;

	/* Server main loop */

	while(1)

	{

		wait_for_connection();

		/* We are in a connection */

		while(more_requests_available())

		{

			/* Handle request */

			handle_request();

			/* Free all of the memory allocated

			 * in the request pool

			 */

			obstack_free(request_pool, NULL);

		}

		/* We're finished with the connection, time

		 * to free that pool

		 */

		obstack_free(connection_pool, NULL);

	}

}

int handle_request()

{

	/* Be sure that all object allocations are allocated
	 * from the request pool
	 */

	int bytes_i_need = 400;

	void *data1 = obstack_alloc(request_pool, bytes_i_need);

	/* Do stuff to process the request */

	/* return */

	return 0;

}

기본적으로 작동의 주요 단계가 끝나면 그 단계에 대한 obstack이 비워진다. 하지만 프로시저가 현재 단계 보다 더 길게 지속될 메모리를 할당하려면 커넥션 또는 글로벌 같은 장기 obstack을 사용할 수 있다. obstack_free()로 전달된 NULL은 obstack의 전체 내용을 비워야 한다는 것을 나타낸다. 다른 값들은 사용할 수 있지만 유용하지 않다.

다음은 메모리 풀링의 장점들이다:

  • 애플리케이션의 메모리를 관리하기가 수월하다.
  • 풀에서 한번에 되기 때문에 메모리 할당과 할당 해제가 훨씬 빠르다. 할당은 O(1) 시간에 수행될 수 있고 풀 릴리스는 끝난다. (실제로 O(n) 시간이지만 대부분의 경우 O(1)로 만드는 거대한 요소에 의해 나뉘어진다.)
  • 에러 핸들링 풀은 사전 할당되어 정규 메모리가 소진되면 프로그램이 복구할 수 있도록 한다.
  • 사용하기 쉬운 표준 구현들이 있다.

다음은 메모리 풀링의 단점들이다:

  • 메모리 풀은 단계 별로 작동하는 프로그램에만 유용하다.
  • 메모리 풀은 삼자 라이브러리로는 잘 작동하지 않는다.
  • 프로그램 구조가 바뀌면 풀이 변경되어야 하는데, 이로 인해 메모리 관리 시스템을 재디자인 해야 한다.
  • 할당하고 싶은 풀이 어떤 것인지를 기억해야 한다. 이것이 잘못되면 회복이 불가능하다.

가비지 컬렉션

가비지 컬렉션은 더 이상 사용하지 않는 데이터 객체들을 완전 자동으로 탐지 및 제거하는 것이다. 가비지 컬렉터는 사용 가능한 메모리가 특정 임계치로 떨어지면 자동으로 실행된다. 일반적으로 프로그램에서 사용할 수 있는 "기본" 설정-스택 데이터, 글로벌 변수, 레지스터-으로 시작한다. 그런 다음 서로 링크 된 데이터의 모든 조각들을 트레이스한다. 컬렉터가 찾는 모든 것은 좋은 데이터이다. 찾지 못하는 모든 것은 가비지(쓰레기)이고 파괴 및 재사용될 수 있다. 메모리를 효과적으로 관리하려면 많은 유형의 가비지 컬렉터들이 데이터 구조 내의 포인터 레이아웃을 알 필요가 있다. 그리고 올바로 작동하는 언어의 일부가 되어야 한다.

컬렉터 유형

  • 복사(Copying): 메모리 스토리지를 두 부분으로 나누고 데이터가 오직 한 쪽에만 있도록 한다. "기본" 요소들을 갖고 시작하면서 주기적으로 한 쪽에서 다른 쪽으로 데이터를 복사하기 시작한다. 새롭게 채워진 메모리 섹션은 활성이 되고 다른 쪽의 모든 것은 쓰레기로 간주된다. 또한 복사가 발생하면 모든 포인터들은 각 메모리 아이템의 새로운 위치를 가르키도록 업데이트 되어야 한다. 따라서 이 방식의 가비지 컬렉션을 사용하려면 컬렉터는 프로그래밍 언어로 통합되어야 한다.
  • 표시와 청소(Mark and sweep): 데이터의 각 조각은 태그로 표시된다. 가끔 모든 태그들은 0으로 설정되고 컬렉터는 "기본" 요소들로 시작하는 데이터부터 검사한다. 메모리를 만나면 태그를 1로 표시한다. 끝에 1로 태그가 붙지 않는 모든 것은 쓰레기로 간주되어 나중에 재사용된다.
  • 증가(Incremental): 증가 가비지 컬렉터는 모든 데이터 객체들을 전체적으로 실행할 필요가 없다. 모든 메모리를 실행하면 모으는 기간 동안 한꺼번에 멈춰야 하고 현재의 모든 데이터에 액세스하는 것과 관련한 캐시 문제 때문이다. 증가 컬렉터는 이러한 문제들을 방지한다.
  • Conservative: Conservative 가비지 컬렉터는 메모리를 관리하는 데이터 구조에 대해 알 필요가 없다. 단순히 모든 데이터 바이트를 보고 이들이 모두 포인터를 갖고 있다는 것으로 간주한다. 따라서 바이트의 시퀀스가 할당된 메모리 조각에 대한 포인터가 되면 이를 레퍼런스 된 것으로 표시한다. 이는 정수 필드가 할당된 메모리의 주소인 값을 포함한다면 레퍼런스 되지 않은 메모리가 모아질 때 문제가 될 수 있다. 하지만 이는 매우 드문 경우이고 적은 메모리만을 쓴다. Conservative 컬렉터는 모든 프로그래밍 언어로 통합될 수 있는 장점이 있다.

Hans Boehm's conservative 가비지 컬렉터는 가장 대중적인 가비지 컬렉터 중 하나이다. 무료이고 Conservative 유형이자 증가 유형이기 때문이다. --enable-redirect-malloc으로 이를 구현하여 (API 대신 malloc/free 사용하는)시스템 할당자 대용으로 사용할 수 있다. 사실 이렇게 하면 같은 LD_PRELOAD트릭을 트릭을 사용할 수 있다. 프로그램이 메모리를 유출한다는 의심이 들면 이 가비지 컬렉터를 사용하여 프로세스 사이즈를 줄일 수 있다. 메모리 유출이 심했을 때 Mozilla 초기에는 많은 사람들이 이 기술을 사용했다. 이 가비지 컬렉터는 Windows®와 UNIX 모두 사용할 수 있다.

다음은 가비지 컬렉션의 장점이다:

  • 메모리의 이중 유휴화(double-freeing)나 객체 수명을 걱정할 필요가 없다.
  • 어떤 컬렉터의 경우 일반 할당에 사용되는 같은 API를 사용할 수 있다.

다음은 가비지 컬렉션의 단점이다:

  • 대부분의 컬렉터를 사용할 때, 메모리가 비워져가고 있을 때 기회가 없다.
  • 많은 경우, 가비지 컬렉션은 다른 형태의 메모리 관리 보다 느리다.
  • 가비지 컬렉션 에러로 인한 버그는 디버그가 어렵다.
  • 사용되지 않는 포인터를 null로 설정하지 않는다면 메모리 유출이 있다.

결론

퍼포먼스, 용이성, 구현가능성, 쓰레딩 기능 등 비교할 것이 많다. 프로젝트 요구사항에 맞는 다양한 메모리 관리 패턴이 있다. 각 패턴마다 광범위한 구현을 갖추고 있고, 이들 각각 장단점이 있다. 프로그래밍 환경을 위해 디폴트 기술을 사용하는 것은 좋은 일이지만 사용할 수 있는 옵션을 아는 것 또한 중요한 일이다. 다음 표에서는 이 글에서 다루어진 메모리 관리 전략들을 비교했다.

표 1. 메모리 할당 전략 비교

전략 할당 속도 할당 해제 속도 캐시 지역성 용이성 보편성 실시간 사용 SMP 및 쓰레드 친화력
커스텀 할당자 구현에 의존 구현에 의존 구현에 의존 매우 어려움 없음 구현에 의존 구현에 의존
일반 할당자 적은 메모리 사용에 빠름 매우 빠름 거의 없음 쉬움 매우 보편적 No No
GNU malloc 중간 빠름 중간 쉬움 Very No 중간
Hoard 중간 중간 중간 쉬움 Very No Yes
Reference counting N/A N/A 우수함 중간 중간 Yes (malloc구현에 의존) 구현에 의존
Pooling 중간 매우 빠름 우수함 중간 중간 Yes (malloc 구현에 의존) 구현에 의존
가비지 컬렉션 중간 (slow when collection occurs) 중간 거의 없음 중간 중간 No 거의 없음
증가 가비지 컬렉션 중간 중간 중간 중간 중간 No 거의 없음
중도 증가 가비지 컬렉션 중간 중간 중간 쉬움 매우 보편적 No 거의 없음

참고자료

웹문서 기본 할당자 풀링 할당자 스마트 포인터 및 커스텀 할당자 가비지 컬렉터 가상 메모리 문서 malloc 문서 커스텀 할당자 문서 가비지 컬렉션 문서 웹 참고자료 developerWorks

필자소개

Jonathan Bartlett은 리눅스 어셈블리 언어 입문서인 Programming from the Ground Up의 저자이다. New Media Worx에서 개발 팀을 이끌고 있다.

 

출처 : http://www.ibm.com/developerworks/kr/library/l-memory/

+ Recent posts