아래 내용은 컴퓨터 시스템(computer systems: a programmer's perspective)의 '9.9장 - 동적 메모리 할당'의 내용을 재구성 하였습니다.
1. 동적 메모리 할당기
동적 메모리 할당기는 힙(heap)이라고 하는 프로세스의 가상 메모리 영역을 관리한다.
할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당되었거나 가용한 가상메모리의 연속적인 묶음이다.
할당기에는 명시적 할당기, 묵시적 할당기 두 개의 기본 유형이 있다.
명시적 할당기는 명시적으로 할당된 블록을 반환해 줄 것을 요구한다. C에서 malloc 함수를 호출해 블록을 할당하고, free 함수를 호출해 블록을 반환하는 것이 이에 해당한다.
묵시적 할당기는 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는 지를 할당기가 검출할 수 있을 것을 요구한다. 묵시적 할당기는 가비지 컬렉터라고 알려져 있으며, 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 부른다.
2. 묵시적 가용리스트
묵시적 가용 리스트를 이용한 명시적 할당기를 구현해보도록 하겠다.
이때 워드는 4바이트 객체, 더블워드는 8바이트 객체로 가정하고 더블워드 정렬(double-word alignment)을 조건으로 하겠다.
우리는 header, footer, 데이터 그리고 패딩으로 구성된 블록 형태를 사용할 것이다.
그리고 header와 footer에는 header와 footer를 포함한 블록의 총 크기와 할당 여부가 들어간다. header와 footer는 1워드(4byte)로 동일하다.
우리가 사용하는 블록의 형식은 아래와 같다.
더블워드 정렬을 조건으로 한다면 모든 블록의 크기는 8의 배수일 것이므로 가장 작은 블록의 크기는 8byte이 된다. 이때 블록의 크기를 2진수로 나타낸다면 하위 3비트는 항상 0이 된다. 즉 하위 3비트를 블록의 크기가 아닌 다른 것을 나타내는 데 사용할 수 있다. 이번에는 여기에 할당 여부를 저장하도록 한다.
즉 크기가 24바이트(0x18)인 할당된 블록의 header와 footer에는 아래와 같은 값이 들어간다.
0x00000018 | 0x1 = 0x00000019크기가 40바이트(0x28)인 가용 블록은 다음과 같은 header와 footer를 갖는다.
0x00000028 | 0x0 = 0x00000028블록에서 패딩은 사용하지 않는 영역으로 외부 단편화를 극복하기 위한 전략 또는 정렬 요구사항을 만족하기 위해 사용된다.
예를 들어 크기가 2byte인 데이터를 위한 메모리를 할당받고 싶다면 크기가 16byte인 블록을 할당해야 한다. 왜냐하면 데이터에 hearder와 footer를 더한다면 2 + 4 + 4 = 10byte가 되는데 더블워드 정렬조건을 만족하기 위해서는 블록의 크기는 8의 배수가 되어야 하기 때문이다. 이때 사용되는 것이 패딩으로 이 경우에는 6byte의 패딩이 데이터 뒤, footer 앞에 들어가게 된다.
위와 같은 블록 형식을 이용해 아래와 같이 힙을 연속된 할당 및 가용 블록의 배열로 구성할 수 있다.
이를 묵시적 리스트라고 한다. 가용 블록이 헤더 내 필드에 의해 묵시적으로 연결되기 때문이다.
3. 할당된 블록의 배치
만약 k바이트의 블록의 할당을 요청한다면 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다. 이때 검색을 수행하는 방법은 배치 정책에 의해서 결정되는데 정책에는 first fit, next fit, best fit이 주로 사용된다.
first fit은 가용리스트를 처음부터 검색해 크기가 맞는 첫 번째 가용 블록을 선택한다.
first fit의 장점은 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다는 것이다. 단점은 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우 검색 시간이 늘어난다는 것이다.
next fit은 firtst fit과 유사하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다.
next fit은 first fit에 비해 매우 빠른 속도를 갖는다. next fit이 first fit보다 최악의 메모리 이용도를 갖다고 한다.
best fit은 모든 가용 블록을 검색하며 크기가 맞는 가장 작은 블록을 선택한다.
best fit은 앞선 두 정책보다 더 좋은 메모리 이용도를 갖는다. 하지만 힙을 완전히 다 검색해야 하기에 묵시적 가용리스트 같은 단순한 가용리스트를 사용할 때는 적절하지 않을 수 있다.
4. 가용 블록 연결하기
할당기가 할당한 블록을 반환할 때, 새롭게 반환하는 블록에 인접한 다른 가용 블록들이 있을 수 있다. 이때 연결이라는 과정으로 인접 가용 블록들을 통합해야 한다.
블록을 반환될 때마다 인접 블록을 통합하는 즉시 연결을 사용할 수도 있지만 일정 시간 후에 가용 블록들을 연결하기 위해 기다리는 지연 연결을 사용할 수도 있다.
즉시 연결은 간단하고 상수 시간 내에 수행될 수 있지만, 일부 요청 패턴에 대해서는 블록이 연속적으로 연결되고 잠시 후에 분할되는 형태를 유발할 수 있다.
예를 들어 16byte의 블록이 반환되어 인접한 16byte의 블록과 연결되었을 때 16byte의 할당이 요청된다면 연결을 하지 않았다면 불필요한 분할의 과정이 필요하게 된다.
가용 블록을 연결하는 방법은 간단하다.
블록이 반환되었을 때 바로 앞의 존재하는 블록의 footer를 확인해 할당 여부를 확인하고, 바로 뒤에 존재하는 블록의 header를 확인해 할당 여부를 확인해 가용 블록이라면 연결을 수행하면 된다.
피드백 환영합니다.
-끝-
