[DevLog][CSAPP] 9장 9.9 malloc lab 동적할당기 구현

9.9 동적 메모리 할당

• 동적 메모리 할당을 하면 어떤 일이 일어나는가: 런타임 메모리 이미지에 있는 heap영역이 위로 상승하는 형태로 늘어난다. 이때 힙의 탑 부분을 가리키는 포인터를 brk라고 한다.
• 동적 메모리 할당기의 구분: 명시적 할당기가 있고 묵시적 할당기가 있다. 명시적 할당기는 코드 내에서 특정한 양의 메모리를 할당받고 해제할 때 사용한다. (c에서의 malloc, free와 c++의 new, delete가 이에 해당한다.) 묵시적 할당기는 프로그램이 종료될 때와 같이 블록들을 더이상 사용하지 않을 때 자동으로 할당 해제해 준다. 다른 말로는 garbage collector라고 한다

9.9.1. malloc과 free함수

01) malloc과 free

malloc은 C의 표준 라이브러리에서 지원하는 명시적 할당기다. 바이트 단위로 메모리를 요청받아 할당받은 다음, 그 시작 주소를 void* 로 리턴한다. 만약 메모리 할당에 실패한 경우에는 NULL이 리턴된다. 할당을 요청했는데 힙 공간이 부족한 경우, 시스템은 brk 포인터를 증가시켜 추가적으로 힙 공간을 넓힐 수 있다. 이를 sbrk가 한다.

void* malloc(4*sizeof(int)); // 4byte 정수형 * 4 = 16byte 요청

free는 역시 명시적인 방법으로 메모리를 반환하는 함수이다. 반환하고자 하는 주소값을 받아서 할당 상태에서 다시 가용 상태로 만든다. NULL을 반환하라고 명령할 경우, free는 아무것도 하지 않는다.

void free(void* ptr);

02) 블록의 단위

malloc은 32비트 모드에서 8바이트 단위로 블록을 리턴한다. (8바이트로 정렬한다.) 왜일까? primitive type의 최대 바이트수가 8이다. 즉, 하나의 블록 사이즈가 모든 타입을 담기 위한 충분조건이 되기 때문이다. (+나의 생각: 만약 4바이트 단위로 정렬한다면, 4byte의 외부 단편화가 다수 생기고, 결국 8바이트가 할당받지 못하는 경우들이 많아져 이용도가 낮아질 것 같다.)

9.9.2. 왜 동적 메모리 할당인가?

동적 메모리 할당은 언제 필요할까? 어떤 경우, 프로그램이 실행하기 전까지는 얼마만큼의 메모리가 필요할지 알 수 없다. 프로그램이 필요로 하는 메모리 양이 사용자의 input에 의해 결정되는 경우에서는 동적 메모리 할당이 필요하다.

9.9.3. 할당기 요구사항과 목표

1. 요청 순서에 관계없이 처리되어야 한다. malloc과 free가 연속된다 (할당-해제의 반복)는 보장이 없다.
2. 요정에 즉시 응답해야 한다. 즉, 일련의 요청을 다 받아놓고 작은 크기 요청순으로 처리하거나 할 수 없다.
3. 힙만 사용해야 한다. nonscalar, 즉 어떠한 메모리 관리를 위한 데이터 구조(여기서는 블록의 메타데이터)을 힙이 아닌 고정된 영역에 저장하면 할당받고자 하는 메모리의 양이 증가할수록 공간이 부족해진다. 그래서 동적으로 확장할 수 있는 힙 공간을 사용해야 한다.
4. 블록을 정렬 요건에 맞춰 정렬해야 한다. 어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 한다.
5. 할당된 블록을 수정할 수 없다. 가용 블록만 조작하고, 할당된 블록은 건드리지 않는다.

그렇다면 어떤 할당기가 좋은 할당기일까?

1. 요청에 빠르게 응답할수록 좋은 할당기이다.
2. 힙 총량 대비 할당받은 총량의 비율 (메모리 이용도)이 높을수록 좋은 할당기이다. (즉 여기저기 남는 부분이 없으면)

$U_k = {{max_{i \ge k}P_i}\over{H_k}}$

9.9.4. 단편화 Fragmentation

내부 단편화는 실제 필요한 양보다 더 많이 할당받은 경우를 말한다. 특히 블록을 8바이트 단위로 정렬하기 위해 필요하지 않은 공간도 할당해 주는 경우가 있는데 (ex. 32bit 모드에서 5바이트 요청하면 8바이트 준다.) 이 공간을 패딩 Padding이라고 한다. 내부 단편화는 외부 단편화보다 다루기가 쉬운데, 이전에 요청했던 정보를 가지고 단편화가 얼마만큼 일어났는지 계산할 수 있기 때문이다.

외부 단편화는 가용 블록의 총량이 할당받고자 하는 양보다 많거나 같음에도 불구하고 연속된 곳에 존재하지 않아 할당받을 수 없는 경우를 말한다. 예를 들어 내가 24바이트를 할당받고 싶은데 8바이트짜리 가용 블록 세 개가 연속되어 있지 않다면 할당받을 수 없다. 외부 단편화는 이전에 요청했던 정보만이 아니라 미래에 요청받을 양 역시 생각해야 하기 때문에 다루기 어려운 측면이 있다. 외부 단편화에 대처하기 위해 가용 블록의 크기를 증가시킬 수 있는데, 이는 가용 블록이 작을수록 더 큰 단위를 할당받을 때 '작은 블록이 비연속적으로 흩어져 있는 경우'가 많이 발생할 수 있기 때문이다. (물론 블록의 크기가 커질수록 내부 단편화의 확률도 같이 커진다. 균형을 잡는 것이 좋다.)

9.9.5. 구현 이슈

01) 가용 블록 구성 Free Block Organization

How do we keep track of free blocks? 할당기의 요구사항을 만족하고 기능적인 효율성을 높이기 위해서 우리는 블록마다 어떤 정보를 관리해야 할까?

02) 배치 Placement

How do we choose an appropriate free block in which to place a newly allocated block? 새로운 블록을 할당받을 때, 어디를 할당받는 것이 좋을까?

03) 분할 Splitting

After we place a newly allocated block in some free block, what do we do with the remainder of the free block? 블록을 특정 위치에 할당받았을 때, 남은 가용블록은 어떻게 처리할까? (ex. 16byte 가용블록 중 8byte 할당. 남은 블록은 잘라줘야겠죠.)

04) 연결 Coalescing

What do we do with a block that has just been freed? 블록을 할당 해제했을 때, 인접한 곳에 가용블록이 있다면 연결해 더 큰 가용블록을 만들어 줘야 하는데 (외부단편화 방지) 어떻게 할 수 있을까?

9.9.6. 묵시적 가용 리스트

블록은 헤더, 페이로드, 패딩으로 구성된다.

01) 헤더 Header

헤더에는 블록의 사이즈가 4byte 정수형으로 저장된다. 그런데 이때 블록의 사이즈 단위가 8바이트라는 것을 생각해보자. 이진 표현으로 바꾸면 블록의 하위 3비트는 항상 0이다. 그래서 이 비트는 가용/할당여부를 나타내는 1비트를 포함해 블록의 추가적인 메타데이터를 담을 수 있다.

02) 페이로드 Payload

실제로 할당받아 메모리가 저장될 부분이다. 할당 상태인 블록만이 이 공간을 가진다. 또 malloc함수가 반환하는 포인터는 페이로드의 시작 부분을 가리켜야 한다. (헤더를 가리키면.. 데이터가 덮어씌워지겠죠.)

03) 패딩 Padding

데이터 정렬을 위한 추가적인 공간으로, 줄 수도 있고 안 줄 수도 있다. 얼마만큼 주느냐도 구현의 이슈이다. 8byte 정렬 가용 블록 리스트에서는 8byte 미만 데이터의 크기를 k라 할 때, 8-k 만큼의 패딩 공간이 생길 것이다.

이러한 세 가지 요소가 묵시적 Implicit한 가용 리스트 구현방식에서의 기본적인 블록 포맷이다. 이 방식이 '묵시적'인 것은 각 블록들이 implicit하게 연결되기 때문이다. 그니까.. 별도의 포인터를 사용해 가용 블록을 연결하는 것이 아니라는 것이다. 이 리스트에서 가용 블록을 찾기 위해서는 오직 순차적인 검색만을 사용할 수 있다. (명시적 방법에서는 다음과 이전 블록을 가리키는 포인터가 포함된다.) 이 방법의 장점은 우선 단순하다는 점이다.

👀 그런데 그럼 어떻게 다음 블록을 알아? 나는 블록의 시작 주소를 알고 있고, 이 블록의 사이즈를 알고 있다. 따라서 시작 주소에 사이즈만큼 더하면 다음 주소의 블록이 나오겠죠.

9.9.7. 할당한 블록의 배치

가용 블록을 찾는 세 가지 방법

나는 k공간을 할당받고 싶다.

01) First Fit: 블록 리스트를 순차적으로 검색하다가 사이즈가 k이상인 블록을 만나면 할당받는다.

• 장점: 리스트 앞부분부터 할당받기 때문에 초반에 빨리 할당받을 수 있다.
• 단점: 앞쪽에 작은 가용 블록이 배치될 가능성이 높다. 갈수록 검색 시간이 늘어난다!

02) Next Fit: 마지막으로 할당받은 위치를 저장해두었다가, 그 위치부터 순차적으로 검색한다.

• 왜 이런 방법? '이전 검색에서 가용 블록을 발견했다면 다음 검색에서는 리스트의 나머지 부분에서 원하는 블록을 찾을 가능성이 높다' 는 Donald Knuth 의 아이디어. First Fit의 단점 부분을 개선한 방법으로 보여진다.
• 장점: First Fit에 비해 빠를 수 있다. (단점에 해당하는 경우에)
• 단점: 세 가지 방법 중 최악의 메모리 이용도를 갖는다. - 연구에 의해 검증되었다.

03) Best Fit: 블록 리스트 전체를 탐색해서 k공간을 할당할 수 있으면서도 가장 작은 가용블록을 검색한다.

• 장점: 가장 최적화된 방법이다. 메모리 이용도가 좋다.
• 단점: 언제나 힙을 다 검색해야 한다.

9.9.8. 가용 블록의 분할

왜 분할하는가? 할당을 받았는데, 남은 공간이 8byte이상이라면 분할해야 다음 번 할당에서 사용할 수 있기 때문에 분할한다. 만약 분할하지 않는다면, 블록 전체를 다 할당받게 되어 다음 번 할당에서 sbrk를 호출해야 할 것이다.

9.9.9. 추가적인 힙 메모리 획득하기

만약 할당기가 요청한 블록은 찾을 수 없다면 인접해 있는 가용 블록을 연결해 더 큰 가용 블록을 만들어 본다. 그래도 안 되면 sbrk를 호출해 힙 영역을 늘린다.

9.9.10. 가용 블록 연결하기

어떤 경우에 연결하면 될까? 블록을 방금 할당 해제했는데, 옆에 가용 블록이 인접해 있다면 서로 연결하여 더 큰 가용 블록을 만들어 외부 단편화의 위험을 낮출 수 있다. 하나의 구현 이슈로서, 언제 연결을 수행할 것인가 의 문제가 있다. 블록을 할당 해제한 후 바로 연결해도 된다. 그러나 다음 할당에서 방금 연결한 블록을 다시 분할하는 경우가 생길 수 있다. 이는 결국 미래에 어떤 할당 요청이 올 지 모르기 때문에 발생한다. 따라서 한 가지 방법은, 가용 블록이 없을 때까지 연결을 지연시키는 것이다. 즉, 연결 작업이 필요할 때까지 이를 미룬다. 그래서 가용 블록이 없으면, 리스트를 검색하여 블록들을 연결해주고, 그래도 없는 경우 sbrk를 호출한다.

9.9.11. 경계 태그로 연결하기

경계 태그란? 할당을 해제한 경우에는 인접한 가용 블록들끼리 연결해서 더 큰 가용 블록을 만들어야 한다. 만약 인접한 가용 블록이 다음에 오는 블록이라면, 헤더를 이용해 그 주소를 찾을 수 있다. 그런데 이전 블록이 가용 블록이라면 어떻게 될까? 블록을 순차적으로 다 검색해야 한다. (나로서는 이전 블록의 사이즈와 시작 위치를 알 수 없으므로)

Knuth는 각 블록마다 헤더를 복사한 푸터 'footer'를 블록의 끝에 붙임으로서 이전 블록으로 상수 시간 내에 접근할 수 있도록 하는 방법을 제안했다. 만약 각 블록의 끝에 푸터가 있다면, 현재 블록의 헤더 시작지점에서 1워드(헤더/푸터의 크기)만큼 감소시킨 주소를 확인하여 이전 블록의 사이즈를 알 수 있다. 그 후 이전 블록의 사이즈만큼 뒤로 이동한다.

이를 '경계 태그 Boundary Tag' 라고 한다. 경계 태그를 사용하면 가용 블록들의 연결이 모두 상수 시간 $O(1)$ 안에 이루어질 수 있다. 단점으로는 헤더와 푸터를 모두 유지해야 한다는 것이다. 경우에 따라서는 헤더와 푸터가 블록의 절반을 차지하게 될 수도 있는데, 특히 작은 크기의 블록을 많이 사용하게 될 경우 불리하다.

👀 결국 앞의 블록이 가용 상태인 경우에만 푸터가 필요한 것? 그래서 할당된 블록은 푸터를 위한 공간을 할애하지 않아도 된다. 블록이 가용 상태로 바뀔 때만 푸터를 달아준다.