할당기 공통 개념
-
Block
malloc lab의 시스템에서 cpu는 data를 Double Word(8byte) 단위로 읽어 들인다. 그리고 메모리의 위치는 Word 단위(4byte)로 움직인다. 그리고 한 메모리 영역을 Block이라고 지칭한다. Block내에는 여러 정보가 담겨있다. Block은 아래 이미지와 같이 구성된다.
Header 와 footer에는 해당 메모리 영역의 할당 여부(a)와 해당 블럭의 크기의 정보가 저장되어있다. 이를 통해 해당 블럭 양옆에 있는 블럭들의 할당 여부와 사이즈를 쉽게 파악 할 수 있다. 우리가 실제로 사용하는 부분은 Payload and padding 영역이다. payload는 데이터 값을 쓰는 부분이고 padding은 블럭을 더블워드 단위로 맞추기 위해 임의로 할당하는 영역이다.
-
Heap 영역 초기화
우선 mm_init 함수에서 Heap영역을 설정해 준다. 여기서 주목 할 것은 Prologue block과 Eplilogue Block이다. 이 두 블럭은 힙영역의 경계 역할을 하여 순회 구현을 단순하게 해 준다. 그리고 블럭은 항상 더블워드 사이즈 단위이여야 하므로 맨 왼쪽에 사용하지 않는 블럭을 할당한다.
-
Coalescing
Coalescing은 가용리스트 간의 연산이라고 생각하면 간단하다. Coalescing을 하는 이유는 아래 이미지를 보면 이해 할 수 있다.
크기 4와 크기2인 가용 블럭들을 합치면 크기 6이되어 크기 5만큼 할당 가능하다. 새로운 가용리스트가 생성 될때마다 Coalesce해야 메모리를 효율적으로 사용 가능하다. Coalesce는 4가지 경우가 있다.
case 2와 case4의 경우에는 가용리스트의 block ptr가 변경되므로 조정해주어야 한다.
묵시적 할당기(Implicit Allocator)
묵시적 할당기는 가장 기초적인 할당기이다. 명시적 할당기와 분리 가용 리스트 할당기는 묵시적 할당기를 약간 변형시킨 형태이다. 따라서 묵시적 할당기를 이해하면 쉽게 이해할 수 있다. 묵시적 할당기를 아주 간단하게 설명해보면 다음과 같다. 우선 메모리 할당 요청이 들어오면 힙영역에서 할당 가능한 블럭이 있는지 탐색한다. 만약 비어있는 영역의 크기가 요청받은 크기보다 크다면 요청받은 크기만큼 메모리 할당한다. 만약 할당 가능한 가용블럭이 없다면 힙 영역을 확장시킨 후 할당한다. 힙 영역 안에 있는 모든 블럭을 탐색하여 묵시적 할당기라 한다. 모든 블럭의 할당여부와 사이즈를 확인해야 하므로 속도가 느리다. 가용블럭을 탐색하는 방법은 3가지가 있다.
-
first fit
first fit은 힙 영역 시작지점부터 순차적으로 탐색한다. 매번 시작지점부터 탐색하므로 탐색 속도가 느리다.
-
next fit
next fit은 힙 영역 시작지점이 아닌 직전 탐색 지점 부터 탐색을 시작한다. 힙 영역 전체를 탐색하지 않아도 되는 경우가 발생하여 탐색 영역이 first fit 보다 적어 탐색 시간이 감소하는 경우가 생긴다.
-
best fit
best fit은 first fit과 같이 힙 영역 시작지점 부터 순차적으로 탐색한다. 두 방법간의 차이점은 가용블럭의 크기도 고려하는 것이다. 할당하려는 사이즈와 동일한 크기의 가용블럭을 찾아 할당한다. 따라서 best fit은 힙 영역 내에 있는 메모리를 효율적으로 사용 할 수 있다.
명시적 할당기(Explicit Allocator)
묵시적 할당기와 달리 명시적 할당기는 가용 리스트끼리만 연결하여 가용 리스트만 탐색하여 탐색 범위가 매우 줄어든다. mm_init 함수에서 가용 리스트들의 2개의 루트를 추가하여 순환 탐색을 용이하게 한다. 또한 LIFO(Last In First Out)방식으로 가용리스트를 추가 및 삭제한다.
위의 이미지는 mm_init 후의 heap 영역을 나타낸다. PRED 와 SUCC가 가용 리스트들의 루트 역할을 할것이다. PRED 와 SUCC는 변경하지 않는다.
위의 이미지는 New Block을 추가한 모습이다. 가용 블럭 안의 PRED 와 SUCC에는 가용리스트의 전(PRED),후(SUCC)의 주소값이 입력되어있다. 새로운 가용 블럭(New Block)이 생성되면 기존의 연결 관계를 수정하여 새로운 가용블럭을 연결 관계에 포함시켜 준다. 이때 새로운 가용블럭은 항상 PRED 루트 바로 다음(맨 처음)에 위치 시킨다. 이러한 규칙이 있으면 수정할 연결관계가 단순해 진다. 트리 구조라고 생각하면 이해가 쉽다.
기존 묵시적 할당기는 모든 블럭을 탐색해야 했지만 명시적 할당기는 가용 블럭만 탐색하므로 탐색속도가 매우 빠르다. 하지만 할당하고자 하는 사이즈와 가장 가까운 가용블럭을 탐색하지는 못한다. 이러한 한계점을 보완한 방법이 분리 가용 리스트 할당기이다.
분리 가용 리스트 할당기(Segregated List Allocator)
분리 가용 리스트 할당기는 명시적 할당기와 달리 크기가 비슷한 가용 블럭 끼리만 연결을 한다. 이러한 연결 리스트의 시작점을 모아둔 리스트(Segrtegated Free List)를 하나 생성하여 관리한다.
int list = 0;
// Select segregated list
while ((list < LISTLIMIT - 1) && (size > 1)) {
size >>= 1;
list++;
}
위의 코드에서 size는 가용블럭의 size이다. 비트마스킹을 이용하여 크기 별로 분류한다. 예를 들면 크기 10(1010)와 15(1111)의 list값은 3으로 동일하다. 2진수의 자리수만 고려하여 분류하기 때문에 크기의 범위 별로 가용블럭의 집단이 나뉘게 된다. 이를 간단한 그림으로 나타내면 아래와 같다.
명시적 할당기와 달리 코드가 매우 복잡하다. 이는 가용 블럭이 추가되고 삭제 되는 경우의 수가 더 많기 때문이다. 직접 손으로 그려보며 생각해보면 이해하기가 훨씬 수월할 것이다. 분리 가용 리스트 할당기는 next fit과 best fit의 장점을 모두 갖고 있다. 탐색은 Segregated Free list의 인덱스를 계산하여 해당 인덱스 부터 탐색을 시작한다. 또한 Segregated Free List 내부는 가용 블럭 크기 순으로 정렬 되기 때문에 할당 하려는 크기와 가장 근접한 크기의 가용 블럭이 탐색된다.
내부 단편화 및 외부 단편화
-
내부 단편화
내부 단편화란 가용 블럭의 크기보다 작은 크기를 할당하는 경우, 가용 블럭 내부에 사용할 수 없는 가용 메모리 영역이 생겨 메모리 효율을 저하시키는 것이다. 이는 best fit나 분리 가용 리스트를 통해 개선 할 수 있다.
-
외부 단편화
외부 단편화는 힙 영역 전체에 있는 가용 가능 크기는 크지만 작게 분할 되어있어 할당을 못하는 경우이다. 아래 이미지에 간단한 예시를 표현하였다.
위의 이미지에서 흰색 부분이 할당 할수 있는 영역이다. 흰색 부분은 총 9칸이지만 1,3,3,2로 단편화 되어있어 4칸만큼 할당하려 하면 힙 영역을 확장해야한다.
느낀점 및 더 보아야 할것
-
위의 방법들 만으로 최적화 하는 것은 한계가 있었다. 다른 사람들이 작성한 코드에서 어떻게 최적화한건지 적혀있지 않아서 알아 낼수 가 없었다. 이를 통해 코드 설명이 잘 되어있지 않다면 상대방을 얼마나 답답하게 할 수 있는지 깨달았다.
-
이러한 할당기 들이 실제로 어떻게 활용되고 있는지 궁금하다.
-
강의를 살펴보면 전주에 배웠던 RB트리를 활용할 수 있다고 한다. 자료구조가 이런곳에 쓰이나 싶었다.
-
C언어에 있는 형 변환과 포인터에 대해 추가적인 학습이 필요해 보인다.
-
[ ] Buddy System 학습
-
[ ] C언어 자료형 및 포인터 추가학습