[Heap Thoery] First Fit

First Fit

Heap 문제를 공략하기 위해서는 기본적인 할당 흐름을 이해할 수 있어야 한다.
그래서 이번 글에서는 블로그 활성화도 하고 복습도 할 겸 겸사겸사 끄적여보기로했다.

다음의 예제를 한번 살펴보자.

3줄 요약

1. a와 b에 각각 malloc^[1]을 요청한다.
2. a를 free^[2]한다.
3. a에 다시 malloc^[1]을 요청한다.

a에 300, b에 250 바이트가 동적 할당 되었다. 둘은 서로 다른 크기를 가지고 있는데
a를 free 해준 뒤 다시 재할당을 해주면 어떻게 될까?

[실행 결과] 서로 다른 크기로 할당했지만 결과는 이전과 동일한 주소를 가리키게 된다.
그렇다면 남은 50 바이트는 그대로 증발되느냐? 아니다. 남은 50바이트도 여전히 남아있다. 대신 a 청크가 두 개로 분리된다(300바이트 작을 경우). a1, a2 이런 식으로 말이다.

head
a1[250]
a2[50]
tail

↓ malloc(250) 재할당 후

head
a2 (a1값 반환됨)
tail

다음은 fastbin 예제이다. fastbin은 단일 연결 리스트^[3]라서 메모리 할당 및 해제 속도가 빠르며 LIFO 구조를 지니고 있다.
아래의 과정을 확인해보면 알 수 있다.

head - a - tail free⒜
head - b - a - tailfree⒝
head - c - b - a - tail free⒞
head - d - c - b - a - tail free⒟
head - c - b - a - tail malloc⒜
head - b - a - tail malloc⒝
head - a - tail malloc⒞
head - tail malloc⒟

[실행 결과]

Reference

---

1. 1.동적할당 ↩
2. 2.할당해제 ↩
3. 3.Singly Linked list ↩