[Heap] chunk의 구조, free list, malloc(), free()

heap은 variable size memory로서, 프로그램이 실행되는 도중 동적으로 할당/해제되는 메모리 영역이다.

malloc()으로 allocate되고 free()로 deallocate된다.

 

chunk의 구조

header + chunk

 

header

8byte

 

 

chunk

 

chunk는 사용되고 있을 때와 free된 때의 모습이 아래처럼 다르다.

 

 

 

free chunk의 double-linked list

 

free chunk끼리는 double-linked list로 이어져 있다.

(그림 상에는 single-linked처럼 그려져있지만 아무튼 실제로는 double-linked이다.)

 

 

포인터 관계를 자세히 보면 아래와 같다.

 

 

malloc()

malloc(100)을 통해 chunk를 생성하면 아래와 같이 되며 108byte가 return된다. 

※ 그림 상 위쪽이 lower address, 아래쪽이 higher address이다.

메모리 할당 method

malloc()을 통해 들어온 request에 대해 어떻게 메모리를 할당해줄 것인가?

 

▶Basic 

만약 100byte만큼의 request가 들어왔다면...

 

1. Best fit

크기가 100byte 이상인 node 중 가장 작은 것 선택

- 단점: 효율이 좋지 않음 ㅡ free list의 모든 노드를 처음부터 끝까지 검색해야 하므로

 

2. Worst fit

크기가 100byte 이상인 node 중 가장 큰 것 선택

- 단점: 효율이 좋지 않음 ㅡ free list의 모든 노드를 처음부터 끝까지 검색해야 하므로

 

3. First fit

free list의 head에서부터 탐색하여, 크기가 100byte 이상이면 선택

- 전체 free list를 전부 검색할 필요가 없음

- 단점: 만약 뒤쪽에 좀더 적합한 노드가 있었다면, 공간 낭비가 발생할 수 있음    

 

4. Next fit

현재 탐색하고 있던 node부터 탐색하여, 크기가 100byte 이상이면 선택

- 전체 free list를 전부 검색할 필요가 없음

- 단점: 만약 뒤쪽에 좀더 적합한 노드가 있었다면, 공간 낭비가 발생할 수 있음   

 

basic method에서의 splitting은 아래와 같다.

만약 request가 1byte 였다면.. 

 

▶Buddy system

: free memory의 large buffer를 반복적으로 절반씩 split해서,

더이상 split하면 요구받은 size보다 작아지게 되면, 그전에 멈추고 allocate함

 

- 장점: 무조건 자신의 짝(buddy)이 있으므로 추후 merge하기가 용이  

- 단점: internal fragmentation

- 일반적인 user 어플리케이션에 사용

 

▶Slab allocator

: behavior가 예측 가능한 특정 어플리케이션들의 경우 (eg. kernel)

메모리 할당과 해제의 크기 패턴이 일정함

따라서 이러한 목적에 맞는 특수한 allocate 방식 채택함  

 

- segregated list의 진화된 방식임

 

 

free()

 

만약 free chunk끼리 인접해 있다면 이들은 하나의 free chunk로 merge된다.