[Computer System] 동적 메모리 할당기

 

이번에는 저번 글에 이어서 동적 메모리 할당기의 종류에 대해 알아보자. 일단 메모리 할당기는 크게 두 가지 분류로 나눌 수 있다. 

 

 

Implicit allocator

implicit allocator는 자바나 자바스크립트 등의 언어에서의 garbage collector 역할을 하는 동적 메모리 할당기이다. 이 할당기들은 Heap에서 특정 메모리 공간이 더 이상 참조되지 않을 때, 참조되지 않는다는 것을 detecting 하여 스스로 메모리를 반환시키는 할당기들이다.

 

 

Explicit allocator

오늘 중점적으로 알아볼 할당기이다. explicit allocator는 implicit allocator와는 달리 응용 프로그램이 특정 메모리 공간을 반환한다고 명시적으로 요청해야 한다. 즉 더 이상 사용하지 않는 공간을 스스로 반환하는 garbage collector는 달리 더 이상 공간을 사용하지 않는다고 시스템에 알려야 하는 것이다. 

가장 간단한 형태의 explicit allocator는 할당 요청이 들어왔을 때, 맨 앞 block부터 검사하면서 아직 할당되지 않았으며, 크기가 충분한 block을 찾으면 그 block의 주소를 return 해준다. 반환 요청이 들어왔을 때는 해당 주소의 block의 할당 정보를 바꿔주기만 하면 된다. 

 

Heap block with footer 

저번 글에서 언급했던 heap block은 explicit allocator를 구현하기에 정보가 부족하다. 할당 요청이 들어오면 블록들을 건너가며 사이즈가 맞는 블록을 찾아야한다. 이때 현재 블록에서 다음 블록으로 넘어가려면 현재 블록의 크기만 있어도 충분히 넘어갈 수 있다. 문제는 반환 요청이 들어올 때 발생한다. 블록이 반환되면 양 옆의 블록의 할당 여부를 검사하여 free block이 존재한다면 합쳐주어야 하는데, 다음 블록은 쉽게 넘어갈 수 있지만 이전 블록은 header의 위치를 찾을 수 없다. 이를 위해 block에 header 뿐만 아니라 header와 완전히 동일한 정보를 가지고 있는 footer를 block의 끝부분에 추가한다. 

이렇게 되면 현재 block pointer에서 8바이트만큼 뒤로 가면 항상 이전 block의 footer에 접근할 수 있다. 이렇게 footer에서 이전 블록의 크기와 할당 여부를 가져와 free block의 병합을 진행할 수 있게 된다. 

 

 

Coalesce

위에서 언급한 연결 과정에 대해 조금 더 자세히 알아보자. free block의 연결은 block의 반환 요청이 들어왔을 때, 또는 heap이 확장되어 새로운 free block이 추가된 경우 발생하며, 총 네 가지 경우로 분류할 수 있다. 

위의 그림은 첫번째 경우이다. 현재 반환된 block의 양 옆이 이미 할당된 block인 경우이다. 이때에는 더 이상 병합할 block이 없으므로 연결 과정을 종료한다. 

 

두 번째 경우는 반환된 block의 뒤의 block이 free block인 경우이다. 이때에는 반환된 block과 뒤의 block을 합쳐준다. 합쳐줄 때에는 반환된 block의 header와 뒤의 block의 footer 정보를 업데이트한다. 이때 size는 두 block의 size를 합한 것과 같다. block pointer는 반환된 block의 block pointer로 유지된다. 

 

세 번째 경우는 앞의 block이 free block인 경우이다. 이때에는 앞의 block의 header 정보와, 반환된 block의 footer 정보를 업데이트한다. 마찬가지로 size는 두 block의 size의 합과 같다. 이때 block pointer는 앞의 block의 block pointer로 이동한다.

 

마지막 경우는 양 옆의 block이 모두 free block인 경우이다. 이때는 앞의 block의 header와, 뒤의 block의 footer를 업데이트한다. 이때 size는 세 block의 size의 합과 같으며, block pointer는 앞의 block의 block pointer로 이동한다. 

 

Implicit Free Lists

먼저 가장 간단한 형태의 explicit allocator이다. 이름이 앞의 implicit allocator와 비슷하지만 다른 개념이다! 

앞에서 설명하지 않은 몇 가지가 그림에 포함되어 있는데, 살펴보고 넘어가자. 

• unused : 그림에서 맨 앞 부분을 의미한다. 이는 block pointer를 항상 8의 배수로 유지하기 위해 추가한 block이다.
• Prologue block : 반환된 block의 coalesce 과정 또는 탐색 과정에서 경계 조건을 제거하기 위해 추가하는 block이다. payload가 없기 때문에 크기는 8이고 항상 할당된 상태를 유지한다.
• Epliogue block : prologue block과 같이 경계 조건을 제거하기 위해 추가하는 block이다. 특히 할당할 block을 탐색할 때 경계 조건으로 사용한다. 이 block은 size가 0이고, 항상 할당된 상태를 유지한다. 

 

할당 과정

1. 현재 block의 header 또는 footer에서 size와 할당 여부를 받아와 할당할 수 있는지 확인한다.

2-1. 만약 할당할 수 없다면, size만큼 넘어가 다른 block에서 검사를 진행한다.

2-2. 할당할 수 있는 block을 찾으면, 해당 block의 header와 footer의 값에 1을 추가하여 할당 여부를 표시해 준다. 

3. 끝 block까지 할당할 수 있는 block을 찾지 못하면, heap을 확장한다. 

 

반환 과정

원래는 반환 과정이 좀 더 복잡하지만, coalesce 과정을 위에서 설명하였기 때문에 간단하게 쓴다. block을 반환할 때는 양 옆의 block의 할당 여부를 검사하여 위의 coalesce 과정을 진행해 주면 된다. 

 

앞으로 소개할 할당기에 비해 구현도 가장 간단하고 과정 또한 복잡하지 않다. 이 할당기는 아주 치명적인 단점이 있는데, block을 할당할 때 free block들만 검사하는 것이 아니라 이미 할당된 block들도 검사를 해야 하기 때문에 탐색에 많은 비용이 든다는 점이다. 이 점을 보완하기 위해 곧 소개할 explicit free list 방식이 있다. 

 

implicit free list 방식으로 test 해보았을 때의 score이다. test case는 카네기 멜런 대학교(CMU)의 Malloc Lab 과제의 case를 사용하였다. 점수를 보면 throughput이 낮게 나온것을 볼 수 있다. 

구현한 코드는 아래 링크에서 볼 수 있다.

 

https://github.com/Hin1209/malloc-lab/tree/implicit

GitHub - Hin1209/malloc-lab

 

 

Explicit Free Lists

이제 explicit free list 방식으로 기본적인 방식, segregated 방식, buddy system 방식으로 총 세가지 방식을 소개할 것이다. 이렇게 세 가지 방식은 위의 implicit free list 방식과는 달리 할당 요청이 들어왔을 때 모든 block을 검사하는 것이 아니라 free block들만 검사를 진행한다. 따라서 free block들을 이어주는 연결 리스트를 따로 관리한다. 

 

 

따라서 heap block에 추가적인 정보가 필요하다. 왼쪽은 할당이 되어있는 block이고, 오른쪽은 free block을 나타낸 것이다. free block을 보면 payload 공간에 predecessor와 successor 정보가 들어있는 것을 볼 수 있다. 여기에는 각각 free list 상에서 이전 block과 다음 block의 주소를 담겨있다. 할당이 된 상태에서는 더 이상 이 정보들은 필요가 없으므로 payload 내용으로 덮어쓴다. 

 

할당 과정 

1. 해당 block의 size를 검사한다. 이때 검사하는 block들은 모두 free list 내의 block이기 때문에 할당 여부를 검사할 필요가 없다.

2-1. 만약 size가 충분하지 않다면, free list 내의 다음 block으로 이동하여 1번부터 과정을 반복한다. 

2-2. size가 충분한 block을 찾았다면, 해당 block을 할당 처리하고, free list 내에서 지워준다. 이때 원래 successor와 predecessor를 서로 연결해주어야 한다. 

3. 만약 free list 끝까지 진행하는 동안 충분한 block을 찾지 못했다면, heap을 확장시킨다. 

 

반환 과정

block이 반환되면 반환된 block은 free list로 삽입되어야 한다. 이때 삽입 방식에 따라 차이가 존재한다. 나는 삽입되는 block은 항상 free list의 맨 앞에 추가하는 LIFO 방식으로 구현하였다. 다른 방식으로 address를 기준으로 정렬하여 삽입하는 방식이 있다. 

• LIFO Policy : 반환된 block을 free list 맨 앞에 추가하면 되기때문에 삽입이 빠름. 다만 address policy에 비해 메모리 이용도는 좋지 않을 수 있음
• Address Ordered Policy : 반환된 block을 block pointer 값을 기준으로 정렬하여 free list 내에 삽입함. 삽입될 위치를 탐색해야 하기 때문에 LIFO policy에 비해 시간이 오래 걸림. 메모리 이용도는 LIFO policy보다 좋을 수 있음.

 

LIFO Policy로 구현하였을 때 score이다. 위의 implicit free list와 비교하였을 때 throughput이 많이 좋아진 것을 볼 수 있다. 

구현한 코드는 아래 링크에서 확인할 수 있다. 

 

https://github.com/Hin1209/malloc-lab/tree/explicit/LIFO

GitHub - Hin1209/malloc-lab

 

Segregated Lists

segregated list 방식은 위의 기본적인 explicit free list 방식에서 딱 한 가지만 추가한 것이다. 따라서 구현이 explicit free list와 매우 유사하다!

segregated list 방식에서는 free block들을 block의 size를 기준으로 class를 나누어 관리한다. 즉 explicit free list에서 free list가 크기를 기준으로 여러 개가 된 것이다. 

구현할 때에는 위의 그림과 같이 2의 거듭제곱 형태로 class를 나누었다. free list의 class를 관리하는 방법으로는 여러가지가 있는데, 나는 각 class의 첫 free block 주소를 prologue block의 크기를 늘려 prologue block의 payload에 담았다. 

 

segregated list 방식은 위의 기본적인 explicit 방식에서 탐색을 조금 더 빠르게 하기 위해 class를 나누는 방식이다. 따라서 속도가 explicit free list 방식에 비해 빠르다. 할당과 반환은 위와 비슷하지만, 해당 block의 class를 찾는 과정이 추가되어야 한다. 

위의 방식과 점수가 비슷하지만, throughput이 40점이 만점인 것을 감안하면 explicit free list 방식도 throughput이 만점이기 때문에 속도의 차이가 점수에 영향을 미치지 않을 것이라 생각할 수 있다. 

구현한 코드는 아래 링크에서 확인할 수 있다.

 

https://github.com/Hin1209/malloc-lab/tree/segregated

GitHub - Hin1209/malloc-lab

 

 

Buddy System

마지막으로 buddy system 방식이다. 이 방식은 위의 segregated list 방식의 특수한 case이다. 위에서는 특정 class에 들어갈 수 있는 size가 여러개인 반면, buddy system에서는 한 class에는 한 가지 size의 block들만 들어갈 수 있다. 이때 모든 block의 크기는 반드시 $ 2^n $ 형태를 유지해야 한다. 

 

이러한 방식의 장점으로는 크기가 항상 $ 2^n $ 형태를 유지하기 때문에 외부 단편화가 잘 발생하지 않는다. 다만 내부 단편화가 어마어마하게 발생할 수 있다... 만약 크기가 $ 2^n + 1 $의 크기를 갖는 할당 요청이 들어오면, 이 요청을 만족시킬 수 있는 가장 작은 block의 size는 무려 $ 2^{n+1} $이다. 이렇게되면 대략 데이터의 크기에 육박하는 내부 단편화가 발생할 수 있다. 따라서 buddy system은 데이터의 크기가 $ 2^n $의 형태로 나타날 때 유리하다. 

 

buddy system은 place 과정과 coalesce 과정이 위의 방식들과 많이 다르다. 위의 방식들은 자신의 옆 block이 할당되었는지 여부를 따져보는데, buddy system에서는 해당 block의 buddy만을 검사해 합쳐준다. 

 

그렇다면 buddy를 찾아주는 과정을 함께 살펴보자. 

 

크기가 128인 heap이 있고, 처음에 여기 32 크기의 할당 요청이 들어왔다고 가정해보자. 먼저 지금은 free block이 크기가 128짜리 하나 있으므로 이 block을 할당해 줄 것이다. 

이때 block의 크기가 필요한 크기의 두배 이상이므로 반으로 잘라주는 작업을 진행한다.

 

반으로 잘라주고 나면 현재 block의 size는 64이고, bp에 size를 더하면 buddy의 bp를 구할 수 있다. 현재 크기가 너무 커서 반으로 잘라주는 작업을 진행 중이므로, buddy는 free list에 추가된다. 아직 block의 크기가 필요한 크기의 두 배 이상이므로 한 번 더 잘라주고 난 뒤 할당을 진행하면 결과는 다음과 같다. 

 

이제 할당을 몇번 더 진행하고, 반환도 몇 번 진행한 경우를 생각해 보자.

 

여기서 96번에 있는 block을 반환한다고 가정해 보자. 

이때 현재 bp와 block의 size를 이진수로 나타내면 그림과 같다. buddy system에서 핵심은 buddy의 bp는 현재 block의 bp와 딱 size에서 1의 값을 갖는 자리만 다르다는 점이다. 따라서 현재 bp의 size bit이 0 이므로, buddy의 주소는 현재 bp에서 size 자리의 bit만 1로 바꿔주면, 즉 현재 bp에서 size를 더하면 구할 수 있다. 

buddy가 free block이고, buddy의 크기가 현재 block의 크기와 같기 때문에 연결이 가능할 것이다. 

이번에는 size 자리의 bit가 1 이기 때문에, 현재 bp에서 size를 빼면 buddy의 주소가 나올 것이다. 마찬가지로 buddy의 크기와 현재 block의 크기가 같고 free block이기 때문에 연결이 가능할 것이다. 이번에는 buddy가 나보다 주소값이 작기 때문에, bp가 buddy의 bp로 이동한다.

 

이번에도 마찬가지로 size 자리의 bit가 1이기 때문에 buddy의 주소는 bp에서 size를 뺀 값이 된다. 하지만 이번에는 buddy의 크기도 다르고, 이미 할당된 block 이므로 더 이상 연결이 불가능하다. 이러한 상황이 발생하면 연결을 종료한다. 그림을 보면 알 수 있듯이 buddy system은 현재 block의 왼쪽에 32 크기의 free block이 있음에도 불구하고 연결을 진행하지 않는다. 이는 모든 block들의 크기가 $ 2^n $ 형태를 유지해야 한다는 점을 충족시키기 위해서이다. 당장 위의 그림에서 만약 왼쪽 block과 연결을 진행했다면 그 결과 합쳐진 block의 크기는 더이상 $ 2^n $을 유지하지 못할 것임을 알 수 있다. 

 

이렇게 block의 size 값과 주소값을 통해 buddy의 정보를 알 수 있다. 잘 생각을 해보면 위에서 진행했던 방식들과는 달리 buddy system에서는 block의 footer 정보를 사용하지 않는다는 것을 알 수 있다! 

 

buddy system을 test 해본 결과, 단편화가 너무 많이 발생하여 heap이 최대 크기 이상으로 확장 요청을 보내 모든 케이스를 통과하지 못했다... 

 

구현한 코드는 아래 링크를 통해 확인할 수 있다. 

 

https://github.com/Hin1209/malloc-lab/blob/buddy/mm.c

GitHub - Hin1209/malloc-lab