힙 할당 메커니즘 (기초)

힙 할당 메커니즘

모든 힙 블럭에는 힙 정보를 포함하는 힙 메타데이터  8bytes를 포함한다.

따라서 8bytes를 요청하였을 경우 +8된 16bytes의 힙 청크가 있는 지 찾는다.

프론트엔드 할당자도 백엔드의 프리리스트도 블럭 크리별로 나뉘어져 각각이 링크드 리스트로 관리된다.

그런데, 힙 요청은 8bytes 단위로 요청하나 힙 블럭에는 항상 힙 메타데이터가 포함되므로 8bytes는 요청할 수 없다. 

==> 따라서 프리리스트의 [0]번째 인덱스는 사용되지 않거나 특수 목적으로 사용된다.

- 프론트엔드 할당자는 [0]인덱스를 사용하지 않음.

- 백엔드 할당자는 [0]인덱스에 [127]번째 블럭 크기보다 크면서 Virtual Alloc을 해야할 정도로는 크지 않는 힙들을 전부 담는다.

[할당 작업 순서]

1) 프론트 엔드 할당자(LAL, LFH)를 먼저 참조함.

이용 가능하다면 힙 관리자는 프리 블록 메모리를 호출자에게 반환함.

2) 백 엔드 할당자의 FreeList 참조.

프론트엔드에서 알맞은 메모리를 할당 받지 못하면 벡엔드로 할당 요청을 넘김.

백엔드 할당자에는 각각 특정 크기를 담당하는 128개의 프리 리스트가 존재.

정확하게 크기가 일치하는 것이 있다면 반환할 힙의 사용중임을 나타내는 Busy Flag를 갱신하고 FreeList에서 제거돼 호출자에게 반환.

일치하는 블럭이 없다면 요청 크기보다 큰 블록을 반으로 쪼개어 호출 크기를 만족시킬 수 있는지 확인.

이 중 하나는 Busy상태로 갱신 후 호출자게에 반환되며, 나머지는 쪼개진 크기의 FreeList에 추가된다.

프리리스트를 조사할 때 효율을 높이기 위해 힙 관리자는 프리 리스트를 비트맵으로 관리.

3) 백엔드의 프리리스트에서도 감당이 안된다면?

힙 관리자는 힙 세그먼트의 Reserved 영역에서 커밋해 커밋된 범위에서 새로운 블록을 생성하여 호출자에게 반환함.

4)  힙 세그먼트의 Reserved 공간으로 충족시킬 수 없다면?

기존 세그먼트의 2배 크기의 새로운 가상 메모리 할당을 요청

5) 메모리가 부족해 새 세그먼트를 수용할 수 없다면?

요청 크기를 반으로 줄여 다시 가상 메모리 할당 요청 (될 때까지 계속 반으로 줄여가며 요청)

6) 그래도 실패한다면?

호출자에게 오류를 반환.

ex)

16bytes 크기 요청 -> 프론트엔드 확인 -> 없을 경우 백엔드로 요청 -> (16+8(metadata))/8 = 3 ->  비트맵의 3번째 bit 확인!

if-1) 비트맵의 3번째 bit가 1이라면 FreeList[3] 에 있는 프리블럭을 반환.

if-0) bit가 0이라면 블록 분리 기법을 통해 더 큰 힙을 쪼개서 반환.